File:MonusTuringMachine ExampleRuns.gif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int bool;
typedef int symT;            /* tape symbol */
typedef int stateT;          /* state */
typedef int posT;            /* tape cell address */
typedef int stepT;           /* computation step count */

#define true                    ((bool)1)
#define false                   ((bool)0)
#define dLeft                   ((posT)-1)      /* move left */
#define dRight                  ((posT)1)       /* move right */
#define dNone                   ((posT)0)       /* don't move */
#define posNil                  ((posT)-999)    /* illegal pos */
#define stateNil                ((stateT)-999)  /* illegal state */



/* ***************************************************************** */
/* ***** machine definition *************************************@@* */
/* ***************************************************************** */



/*
 * Change this section in order to simulate a different Turing machine.
 *
 * The transition table trans[][] needs to be indexed by numbers in a
 * range [0...symMax) and [0...stateMax), we use the types symT and
 * stateT for this.
 * 
 * On the other hand, to keep the machine definition readable, we use
 * Ascii characters for state names, symbols, and direction names, all
 * mapped to type char.
 * 
 * The tables symName[] and stateName[] hold the correspondance between
 * both representations; routines encodeState(), decodeState(),
 * encodeSym(), decodeSym() implement mappings in both directions.
 * 
 * The entries in trans[][] must be ordered in accordance with symName[]
 * and stateName[].
*/



#include "turingMachineMonus.c"



/* ***************************************************************** */
/* ***** machine access routines ********************************@@* */
/* ***************************************************************** */



static inline char getTape(
    posT pos)
{
    if (0 <= pos && pos < tapeMax)
        return tape[pos];
    fprintf(stderr,"Error: can't read tape position %d\n",pos);
    abort();
}



static inline void setTape(
    posT pos,
    char c)
{
    if (0 <= pos && pos < tapeMax) {
        tape[pos] = c;
    } else {
        fprintf(stderr,"Error: can't write tape position %d\n",pos);
        abort();
    }
}



static inline stateT decodeState(
    char c)
{
    stateT s;

    for (s=0; s<stateMax; ++s)
        if (stateName[s] == c)
            return s;
    fprintf(stderr,"Error: can't decode state '%c'\n",c);
    abort();
}



static inline char encodeState(
    stateT state)
{
    if (0 <= state && state < stateMax)
        return stateName[state];
    fprintf(stderr,"Error: can't encode state %d\n",state);
    abort();
}



static inline symT decodeSym(
    char c)
{
    symT s;

    for (s=0; s<symMax; ++s)
        if (symName[s] == c)
            return s;
    fprintf(stderr,"Error: can't decode symbol '%c'\n",c);
    abort();
}



static inline char encodeSym(
    symT sym)
{
    if (0 <= sym && sym < symMax)
        return symName[sym];
    fprintf(stderr,"Error: can't encode symbol %d\n",sym);
    abort();
}



static inline posT decodeDir(
    char c)
{
    if (c == 'L')
        return dLeft;
    else if (c == 'R')
        return dRight;
    else if (c == 'N')
        return dNone;
    fprintf(stderr,"Error: can't decode direction '%c'\n",c);
    abort();
}



static inline bool decodeTrans(
    const char *tr,
    stateT *state,
    symT *sym,
    posT *dir)
{
    if (tr == NULL)
        return false;
    *state = decodeState(tr[0]);
    *sym   = decodeSym(tr[1]);
    *dir   = decodeDir(tr[2]);
    return true;
}



/* ***************************************************************** */
/* ***** printing ***********************************************@@* */
/* ***************************************************************** */



static inline void setColor(
    const char *c)
{
    printf("%c[%sm",0x1b,c);
}



/* color codes for VT100 terminal emulator */
#define coOff           "0"     /* no color */
#define coStep          "33"    /* cumputation step number */
#define coNoHead        "32"    /* auxiliary dots in head/state line */
#define coTapeOld       "34"            /* unchanged tape symbol */
#define coTapeChgd      "36;1"          /* altered tape symbol */
//#define coStateOld    "31"            /* unchanged state */
//#define coStateChgd   "35"            /* changed state */
#define coStateOld      "40;31"         /* unchanged state */
#define coStateChgd     "47;35;1"       /* changed state */


/* variant 1: print tape in one line, and state + head below it */
static inline void print1(
    stepT i,            /* current computation step */
    stateT prvState,    /* previous state */
    stateT curState,    /* current state */
    posT curPos,        /* current head position */
    posT chgdPos)       /* position where a symbol was altered (if any) */
{
    posT p;

    /* print tape */
    if (curState != prvState || chgdPos != posNil) {
        printf("\t");
        for (p=0; p<tapeMax; ++p) {
            setColor(p!=chgdPos ? coTapeOld : coTapeChgd);
            printf("%c",tape[p]);
            setColor(coOff);
            printf(" ");
        }
        printf("\n");
    }
    /* print step */
    setColor(coStep);
    printf("%4d",i);
    setColor(coOff);
    printf("\t");
    /* print head / state */
    for (p=0; p<tapeMax; ++p) {
        if (p == curPos) {
            setColor(curState==prvState ? coStateOld : coStateChgd);
            char const c = encodeState(curState);
            printf("%c",c);
        } else {
            setColor(coNoHead);
            printf(".");
        }
        setColor(coOff);
        printf(" ");
    }
    printf("\n");
}



/* variant 2: print tape and state + head in a single line */
static inline void print2(
    stepT i,
    stateT prvState,
    stateT curState,
    posT curPos,
    posT chgdPos)
{
    posT p;

    /* print step */
    setColor(coStep);
    printf("%4d",i);
    setColor(coOff);
    printf(" ");
    /* print tape / head / state */
    for (p=0; p<tapeMax; ++p) {
        if (p == curPos) {
            /* print head / state */
            setColor(curState==prvState ? coStateOld : coStateChgd);
            char const c = encodeState(curState);
            printf("%c",c);
            setColor(coOff);
        } else {
            printf(" ");
        }
        /* print tape */
        setColor(p!=chgdPos ? coTapeOld : coTapeChgd);
        printf("%c",tape[p]);
        setColor(coOff);
        printf(" ");
    }
    printf("\n");
}



/* ***************************************************************** */
/* ***** running ************************************************@@* */
/* ***************************************************************** */



/* perform a single machine step, */
/* fail if no transition is defined */
static inline bool step(
    stateT *curState,
    posT *curPos,
    posT *chgdPos)
{
    stateT newState;
    symT newSym;
    posT dir;

    char const curChar = getTape(*curPos);
    symT const curSym  = decodeSym(curChar);
    const char *next   = trans[curSym][*curState];
    if (! decodeTrans(next,&newState,&newSym,&dir))
        return false;
    if (newSym != curSym) {
        char const newChar = encodeSym(newSym);
        *chgdPos = *curPos;
        setTape(*curPos,newChar);
    } else {
        *chgdPos = posNil;
    }
    *curPos += dir;
    *curState = newState;
    return true;
}



/* run as long as possible */
static inline void run(void)
{
    stateT curState;
    stateT prvState;
    posT curPos;
    posT chgdPos;
    stepT i;

    curState = decodeState(startStateName);
    prvState = stateNil;
    curPos = startPos;
    chgdPos = posNil;
    for (i=0; ; ++i) {
        print2(i,prvState,curState,curPos,chgdPos);
        prvState = curState;
        if (! step(&curState,&curPos,&chgdPos))
            break;
    }
}



/* ***************************************************************** */
/* ***** main ***************************************************@@* */
/* ***************************************************************** */



int main(
    int argc,
    const char * const argv[argc])
{
    int i;

    for (i=1; i<argc; ++i) {
        if (strcmp(argv[i],"-tape") == 0) {
            posT const lg = strlen(argv[i+1]);
            if (lg != tapeMax) {
                fprintf(stderr,"Error: tape has %d symbols, not %d\n",
                                                                lg,tapeMax);
                abort();
            }
            strncpy(tape,argv[i+1],tapeMax);
            i += 1;
        } else {
            fprintf(stderr,"Error: illegal %dth argument '%s'\n",i,argv[i]);
            abort();
        }
    }
    run();
    printf("\n");
    return 0;
}

/* tape description */

#define tapeMax                 ((posT)16)

static char tape[tapeMax] = { 
/*       0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  */
        '_','_','_','I','I','I','I','I','#','I','I','I','_','_','_','_',
};

static posT startPos = 3;



/* finite control description */

#define symMax                  ((symT)3)       /* alphabet size */
#define stateMax                ((stateT)7)     /* state count */



static const char symName[symMax] = { 
/*       0    1    2    */
        'I', '#', '_',
};



static const char stateName[stateMax] = { 
/*       0    1    2    3    4    5    6        */
        'a', 'b', 'c', 'd', 'e', 'f', 'g',
};



/* string format: <nextStep><output symbol><head move>, */
/* use NULL if no transition is defined */
static const char * const trans[symMax][stateMax] = { 
/*          a      b      c      d      e      f      g */
/*I*/   { "b_R", "bIR", "d#L", "dIL", "eIL", "f_R",  NULL, },
/*#*/   { "f_R", "c#R", "c#R", "d#L", "e_L", "f_R",  NULL, },
/*_*/   {  NULL,  NULL, "e_L", "a_R", "gIR", "g_R",  NULL, },
};

static char startStateName = 'a';