Turing Machine Simulator

Question

Write a Turing machine simulator.

For simplicity we can assume statuses as integer, symbols as char, blank symbol equals whitespace

5-tuple in the form of current state, input symbol, next state, output symbol, direction (left or right) the order is not mandatory but specify if you swap it

The machine must stop when an unknown state is reached, no other halt condition allowed.

The tape is infinite in both directions and you can always read an empty character.

Input: the initial tape, an initial state and a program. you are free to read the data from anywhere in the format you like

Output: the tape after the execution of the program

Required: an example program that run on top of your simulator

This is a code-colf so the shortest code win.

I'll post an implementation and some example programs in the next few hours.

Answer 1

GolfScript, 92 characters

~:m;n\+{:^.n?)>1<]m{2<1$=},.{~2>~^n/~1>[@\+]n*1$%n/~\1$1<+[\1>.!{;" "}*]n*\%@}{;;^0}if}do n-

The Turing machine in GolfScript became much longer than intended. Still playing around with different representations of the tape.

First line of the input is the original state, second line the initial tape, followed by an array of transitions (with order current state, input symbol, next state, direction, output symbol).

Example (also available online)

> 0
> '101'
> [[0 '0' 0 1 '0']
>  [0 '1' 0 1 '1']
>  [0 ' ' 1 -1 ' ']
>  [1 '0' 2 1 '1']
>  [1 '1' 3 -1 '0']
>  [3 '0' 2 1 '1']
>  [3 ' ' 2 1 '1']
>  [3 '1' 3 -1 '0']] 

110 

Answer 2

Python, 101 189 152 142

a=dict(zip(range(len(b)),b))
r=eval(p)
i=s=0
while 1:
 c=a.get(i,' ')
 s,m,a[i]=r[s,c]
 if 0==m:exit([x[1]for x in sorted(a.items())])
 i=i+m

b and p are the inputs, b is the initial tape, p encodes the rules as (string representation of) a dict from (in-state, in-tape) tuple to (out-state, head move, out-tape) tuple. If move is 0 the program finishes, 1 is move to the right and -1 is move to the left.

b="aaba"

p="""{(0, 'a'): (1, 1, 'a'),
      (0, 'b'): (0, 1, 'b'),
      (1, 'a'): (1, 1, 'a'),
      (1, 'b'): (0, 1, 'b'),
      (1, ' '): (1, 0, 'Y'),
      (0, ' '): (0, 0, 'N')}"""

This sample program tests if the last letter of the string (before empty tape) is 'a', if so it writes 'Y' at the end of the string (first empty space).

Edit 1:

Changed the tape to be represented as a dict, as it seemed the shortest way to write an extensible data structure. The second to last line is mostly transforming it back into readable form for output.

Edit 2:

Thanks to Strigoides for a great deal of improvements.

Edit 3:

I had unnecessarily made it so 0 as output would leave the place as it is. I removed this as we can always write the output the same as the input.

Answer 3

APL (110)

(It's not even that short...)

0(''⍞){×⍴X←0~⍨⍺∘{x y S T s m t←⍺,⍵⋄S T≡x,⊃⊃⌽y:s,⊂(⊃y){m:(¯1↓⍺)(⍵,⍨¯1↑⍺)⋄(⍺,⊃⍵)(1↓⍵)}t,1↓⊃⌽y⋄0}¨⍵:⍵∇⍨⊃X⋄,/⊃⌽⍺}⎕

It reads two lines from the keyboard: the first is the program and the second is the initial tape.

The format is

(in-state in-tape out-state movement out-tape) 

and they should all be on the same line. 'Movement' is 0 to move right and 1 to move left.

Example program (line breaks inserted for clarity, they should be all on one line.)

(0 ' ' 1 0 '1')
(0 '1' 0 0 '1')
(1 '1' 1 0 '1')
(1 ' ' 2 1 ' ')
(2 '1' 3 1 ' ')

The program adds two unary numbers together, for example:

in:  1111 111
out: 1111111

Example 2 (adapted from the binary increment program from Marco Martinelli's entry):

(0 '0' 0 0 '0')
(0 '1' 0 0 '1')
(0 ' ' 1 1 ' ')
(1 '0' 2 0 '1')
(1 '1' 3 1 '0')
(3 '0' 2 0 '1')
(3 ' ' 2 0 '1')
(3 '1' 3 1 '0')

Answer 4

GNU sed with -r - 133 117 111 93 chars

Yes, sed is turing complete. GNU sed and -r (extended regexps) is only to save a few characters, it is only a small change to work with POSIX sed.

:s
s/^(.*@)(.*)>(.)(.*#\1\3([^@]*@)(..))/\5\2\6>\4/
T
s/(..)l>|r>/>\1/
s/>@/@> /
s/>#/> #/
bs

Input format is

[initial state]@[non-empty tape with > marking head position]#[state]@[input symbol][next state]@[output symbol][direction l or r]#...

The delimiters @, # and head character > cannot be used as a symbol on the tape. State labels cannot contain @ > or #.

It will run all of the programs in the input, one per line

Examples:

Marco's aⁿbⁿ program

Input

0@>aaabbb#0@a1@ r#0@ 4@ r#1@a1@ar#1@b1@br#1@ 2@ l#2@b3@ l#2@a5@al#3@b3@bl#3@a3@al#3@ 0@ r#4@ 5@Tr

Output

5@    T>  #0@a1@ r#0@ 4@ r#1@a1@ar#1@b1@br#1@ 2@ l#2@b3@ l#2@a5@al#3@b3@bl#3@a3@al#3@ 0@ r#4@ 5@Tr

Marco's Hello! program

Input

0@> #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r

Output

6@Hello!> #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r

Answer 5

Postscript (205) (156) (150) (135)

<<
>>begin
/${stopped}def([){add dup{load}${exit}if}def
0 A{1 index{load}${pop( )}if
get{exec}${exit}if}loop
3{-1[pop}loop{1[print}loop

This is probably cheating, but the transition table contains code to perform the transitions. And since the tape is represented by a mapping from integers to integers, I've represented states as a mapping from names to dictionaries so the tape and the program coexist in the same anonymous dictionary.

Extra savings by making all state names executable, so they auto-load.

Ungolfed with embedded "Hello" program. An extra 52 chars buys a loop to read the tape from stdin. Run with gsnd -q tm.ps.

%!
<<
    /A<<( ){dup(H)def 1 add B}>>
    /B<<( ){dup(e)def 1 add C}>>
    /C<<( ){dup(l)def 1 add D}>>
    /D<<( ){dup(l)def 1 add E}>>
    /E<<( ){dup(o)def 1 add F}>>
>>begin %ds: int-keys=tape name-keys=prog
0 A %pos state
{ %loop
    1 index{load}stopped{pop( )}if  %pos state tape(pos)
    get    {exec}stopped{exit  }if  %new-pos new-state
} loop
% Loop from tape position 0 to left until left tape end is found
0{                                  %pos
  -1 add                            %new-pos
  dup{load}stopped{exit}if          %new-pos tape(new-pos)
  pop                               %new-pos tape(new-pos)
}loop
% Move to the right and print all chars until right end is hit
{                                   %pos
  1 add                             %new-pos
  dup{load}stopped{exit}if          %new-pos tape(new-pos)
  print                             %new-pos tape(new-pos)
}loop

So the table-format is

/in-state<<in-tape{dup out-tape def movement add out-state}
           in-tape2{dup out-tape2 def movement2 add out-state2}>>

where in-state is a name, in-tape and out-tape are chars (ie. integers, or expressions which yield integers), movement is -1 for left or 1 for right, and out-state is an executable name. Multiple in-tape transition for the same state may be listed in full-form, or abbreviated as above.

Answer 6

Groovy 234 228 154 153 149 139 124

n=[:];i=0;t={it.each{n[i++]=it};i=0};e={p,s->a=p[s,n[i]?:' '];if(a){n[i]=a[1];i+=a[2];e(p,a[0])}else n.sort()*.value.join()}

Formatted for readability

n=[:];
i=0;
t={it.each{n[i++]=it};i=0};
e={p,s->
    a=p[s,n[i]?:' '];
    if(a){
        n[i]=a[1];
        i+=a[2];
        e(p,a[0])
    }else n.sort()*.value.join()
}

t is the function that set the tape e is the function that evaluate the program

Example 1 - Print "Hello!" on the tape :)

t('')
e([[0,' ']:[1,'H',1],
   [1,' ']:[2,'e',1],
   [2,' ']:[3,'l',1],
   [3,' ']:[4,'l',1],
   [4,' ']:[5,'o',1],
   [5,' ']:[6,'!',1]],0)

Example 2 - Leave a T on the tape if the initial string is in the form of aⁿbⁿ, stop otherwise.

t('aaabbb')
e([[0,'a']:[1,' ',1],
   [0,' ']:[4,' ',1],
   [1,'a']:[1,'a',1],
   [1,'b']:[1,'b',1],
   [1,' ']:[2,' ',-1],
   [2,'b']:[3,' ',-1],
   [2,'a']:[5,'a',-1],
   [3,'b']:[3,'b',-1],
   [3,'a']:[3,'a',-1],
   [3,' ']:[0,' ',1],
   [4,' ']:[5,'T',1]],0)

Example 3 - Increment of a binary number

t('101')
e([[0,'0']:[0,'0',1],
   [0,'1']:[0,'1',1],
   [0,' ']:[1,' ',-1],
   [1,'0']:[2,'1',1],
   [1,'1']:[3,'0',-1],
   [3,'0']:[2,'1',1],
   [3,' ']:[2,'1',1],
   [3,'1']:[3,'0',-1]],0)

in the examples 1 means move to the right and -1 means move to the left

Answer 7

C (not golfed yet)

I suppose I can't win with this, still it was fun getting it to work. This is even more true now that it really does work. :)

Except it's only infinite in one direction. I suppose it needs a negative tape, too. Sigh....

Negative wasn't so bad. We interleave the two sides as evens and odds. Complication is now it needs to display the tape in sequential order, as the file itself is now jumbled. This is a legitimate alteration to make, I think. Turing himself simplified this way.

#include<stdio.h>
int main(int c, char**v){
    int min=0,max=0;
    int pos=0,qi;sscanf(v[1],"%d",&qi);
    FILE*tab=fopen(v[2],"r");
    FILE*tape=fopen(v[3],"r+");
    setbuf(tape,NULL);
    do {
        min = pos<min? pos: min;
        max = pos>max? pos: max;
        fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET);
        int c = fgetc(tape), qt=qi-1,qr;
        fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET);
        char x = c==EOF?' ':c, xt=x-1,xr,d[2];
        if (x == '\n') x = ' ';
printf("%d '%c' %d (%d)\n", qi, x, pos, (int)ftell(tape));
        while((qt!=qi)||(xt!=x)){
            fscanf(tab, "%d '%c' %d '%c' %1[LRN]", &qt, &xt, &qr, &xr, d);
            if (feof(tab)){
                goto HALT;
            }
printf("%d '%c' %d '%c' %s\n", qt, xt, qr, xr, d);
        }
        qi=qr;
        rewind(tab);
        fputc(xr,tape);
        pos+=*d=='L'?-1:*d=='R'?1:0;
    } while(1);
HALT:
printf("[%d .. %d]:\n", min, max);
    for (pos = min; pos <= max; pos++){
        fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET);
        //printf("%d ",pos);
        putchar(fgetc(tape));
        //puts("");
    }
    return qi;
}

And here's the test-run:

522(1)04:33 AM:~ 0> cat bab.tm
0 'a' 0 'b' R
0 'b' 0 'a' R
523(1)04:33 AM:~ 0> echo aaaaa > blank; make tm ; tm 0 bab.tm blank; echo; cat blank
make: `tm' is up to date.
0 'a' 0 (0)
0 'a' 0 'b' R
0 'a' 1 (2)
0 'a' 0 'b' R
0 'a' 2 (4)
0 'a' 0 'b' R
0 ' ' 3 (6)
0 'a' 0 'b' R
0 'b' 0 'a' R
[0 .. 3]:
bbbÿ
babab

The program outputs the tape in sequential order, but the file represents the negative and positive sides interleaved.

Answer 8

Brainfuck: 0 characters

Urban Müller created brainfuck in 1993 with the intention of designing a language which could be implemented with the smallest possible compiler [...]. Several brainfuck compilers have been made smaller than 200 bytes. [...]

The language consists of eight commands, listed below. A brainfuck program is a sequence of these commands, possibly interspersed with other characters (which are ignored). The commands are executed sequentially, except as noted below; an instruction pointer begins at the first command, and each command it points to is executed, after which it normally moves forward to the next command. The program terminates when the instruction pointer moves past the last command.

The brainfuck language uses a simple machine model consisting of the program and instruction pointer, as well as an array of at least 30,000 byte cells initialized to zero; a movable data pointer (initialized to point to the leftmost byte of the array); and two streams of bytes for input and output (most often connected to a keyboard and a monitor respectively, and using the ASCII character encoding).

Wikipedia article about brainfuck

Input format that I like:

• +: Increase current value on the band
• -: Decrease current value on the band
• >: Go one up on the band
• <: Go one down on the band
• [: if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command*.
• ]: if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command*.
• .: Print current value on the band interpreted as ascii
• ,: Read a value and write it the the current cell on the band