Will Ridgers

tiny c turing machine

· codegolf c

Here is a small Non-deterministic Turing machine written in C.

#include <stdio.h>
#define w while
#define b break
int i,j;char s='S',d[]="S0a0>S1a0>a0a0>a1a0>a-H--";struct t{t*l;t*r;char v;};
int main(int c, char**v){t*h=0;w(v[1][j]){t*n=new t;n->v=v[1][j];n->l=h;n->r=0;if(h)h->r=n;
h=n;++j;}w(1){if(!h->l)b;h=h->l;}w(1){if(s=='H')b;i=0;w(d[i]){if(s==d[i]&&h->v==d[i+1]){
s=d[i+2];h->v=d[i+3];t*m=new t;m->v='-';if(d[i+4]=='<'){if(!h->l){m->l=0;m->r=h;h->l=m;}
h=h->l;}if(d[i+4]=='>'){if(!h->r){m->l=h;m->r=0;h->r=m;}h=h->r;}b;}i+=5;}}printf("%c:",s);
w(1){if(!h->l)b;h=h->l;}w(h){putchar(h->v);h=h->r;};return 0;}

Expanded and readable it looks like this.

#include <stdio.h>

int i,j;

char state = 'S';
char delta[] = "S0a0>S1a0>a0a0>a1a0>a-H--";

// node for linked list
struct cell
{
    cell *left;
    cell *right;
    char value;
};

int main(int argc, char **argv)
{
    // create the head
    cell* head = 0;

    // write input to tape
    while (argv[1][j]) {
        // make a new cell for each input character
        cell* newCell = new cell;
        newCell->value = argv[1][j];

        // add it to the right of head
        newCell->left = head;
        newCell->right = 0;

        // if head is a node, add newCell to the left
        if (head) {
          head->right = newCell;
        }

        // move head to the newCell
        head = newCell;

        ++j;
    }

    // move head to leftmost character
    while (1) {
        // stop if the next cell is empty
        if (!head->left) {
          break;
        }

        head = head->left;
    }

    while (1) {
        // exit if we reach the halting state
        if ( state == 'H') {
          break;
        }

        i = 0;

        // check the delta function
        while (delta[i]) {
            // does current state and head value match?
            if (state == delta[i] && head->value == delta[i+1]) {
                // switch to new state
                state = delta[i+2];
                // write new value
                head->value = delta[i+3];

                // create a new cell (might need this, might not)
                cell* blankCell = new cell;
                blankCell->value = '-';

                // are we moving to the left?
                if (delta[i+4] == '<') {
                    // add blankCell if there is no cell here
                    if (!head->left) {
                        blankCell->left = 0;
                        blankCell->right = head;
                        head->left = blankCell;
                    }

                    // set head to left cell
                    head = head->left;
                }

                // are we moving to the right?
                if (delta[i+4] == '>') {
                    // add blankCell if there is no cell here
                    if (!head->right) {
                        blankCell->left = head;
                        blankCell->right = 0;
                        head->right = blankCell;
                    }

                    // set head to right cell
                    head = head->right;
                }

                break;
            }
            i+=5;
        }
    }

    // print the state
    printf("%c:",state);

    // move head to far left
    while (1) {
        if ( !head->left )
        break;

        head = head->left;
    }

    // move from left to right, printing cell value as we go.
    while (head) {
        putchar( head->value );
        head = head->right;
    };

    // note, we should delete the tape here but we're trying to be small so... ;)
    return 0;
}

The delta function is encoded in a char array. The TM checks every fifth index i for a matching state and i+1 for a matching character on the tape. When it finds a match it changes to state i+2, writes i+3 and moves i+4. This way I can encode the delta function in as little space as possible. I used a fair amount of while loops and it worked out cheaper to add a `#define. Same for break.