I while ago I had a little contest with a friend to write a C/C++ Deterministic Turing Machine (DTM) in as little bytes of code as possible. We drew up a simple specification and set to work! Here’s mine (uncompressed):
#include <stdio.h> #define w while int i,j,k,h=1024; char s='S',t[2049],d[]="S0a0>S1a0>a0a0>a1a0>a-H--"; int main(int c, char**v) { w(i<h*2){t[i]='-';++i;}t[i]='\n'; w(v[1][j]){t[j+h]=v[1][j];++j;}; w(1){ if(s=='H')break;i=0; w(d[i]){ if (s==d[i]&&t[h]==d[i+1]){ s=d[i+2];t[h]=d[i+3]; h-=d[i+4]=='<'; h+=d[i+4]=='>'; break; } i+=5; } } printf("%c:",s); w(k<2049){if(t[k]!='-')putchar(t[k]);++k;}; return 0; } |
The delta function is encoded in a char array. The DTM 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. One neat trick I used was adding/subtracting the result of a boolean operation to change the h value.
h-=d[i+4]=='<'; |
This will subtract 1 if the head should move left, otherwise it will subtract 0 (do nothing). This removed the need for an if statement and got the code down by a couple of bytes.
Overall I am pretty happy. A limitation would be that the tape has a finite number of cells, but we agreed to this in our specification. I plan to write a Non-deterministic Turing Machine (NTM) next time I have a slow-day. This time I will use a linked list so the tape length is limited only by the size of the systems RAM.
