Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
add comment

8 Answers 8

up vote 2 down vote accepted

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 
share|improve this answer
    
you beat my sed implementation by one char, time to see if I can do better –  Geoff Reedy Oct 30 '12 at 18:30
add comment

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 anbn 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
share|improve this answer
add comment

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.

share|improve this answer
    
I don't think this is a valid solution because in your implementation the tape is limited. This way you need to know in advance the memory consumption of your program. And there are problems moving left. Hint: a tape can be made from two modified stack in wich you can always pop a blank symbol. –  Marco Martinelli Oct 23 '12 at 19:00
    
Ah, true. Sorry, didn't think this too far. –  shiona Oct 23 '12 at 19:08
    
Uhm.. afaik the tape is infinite in both direction and you can always read an empty character. I will specify that in the answer. –  Marco Martinelli Oct 23 '12 at 19:10
    
You were correct (we had had more strict rules in our exercises). I fixed at least some of the flaws. –  shiona Oct 23 '12 at 19:52
    
You can remove the space in the first line, r=0;s=0 can become r=s=0 (and the semicolon at the end of that line is unnecessary), you can remove the function w, as it is unused, the brackets can be removed in (s,m,t)=r[s,c], the try/except block can be shortened using dict.get; c=a.get(i,' '), since m is either 0 or 1, you can use if m-1:, and you can shorten your map() call by converting it to a list comprehension. –  Strigoides Oct 24 '12 at 2:27
show 2 more comments

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')
share|improve this answer
    
How can i try it? I'm using linux and tried with aplus but it doesn't work (undefined token :( ). Which interpreter / compiler should I try? –  Marco Martinelli Oct 25 '12 at 9:32
    
I'm using Dyalog APL. I'm not aware of using any Dyalog-specific functions but A+ is not completely the same thing. There's a free version of Dyalog but it's only for Windows. (It might run under Wine but it does use its own input method so you can type APL.) If you get Dyalog running, just enter/paste the APL code (on one line), then the Turing machine program (on a second line), then the initial tape (on the third line). –  marinus Oct 25 '12 at 15:32
    
ok, I will try that, thank you –  Marco Martinelli Oct 25 '12 at 15:45
add comment

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.

share|improve this answer
    
Another problem is there's no provision for discovering what part of the tape is interesting. That's gonna cost quite a bit to do a currentdict{search-for-min-and-max}forall juggle-params-for-for. :( –  luser droog Oct 27 '12 at 9:50
    
Tried my own, but was way beyond your conciseness. But I suggested some improvements to your code. –  Thomas W. Nov 7 '12 at 8:07
    
BTW, what about the initial tape? I removed the commented out line from the un-golfed code because it didn't seem to do the job. ("0 not" returns -1, therefore no iteration of the loop) –  Thomas W. Nov 7 '12 at 8:10
    
Excellent improvements! ... About the initial tape code, I think I mistyped it from my notebook. S.B. 0 1 0 not{(%stdin)(r)file read not{exit}if def}for. I'm not sure why I thought I could get away with omitting that from the golfed version. :P –  luser droog Nov 7 '12 at 8:35
    
Oh, wait, -1! Then 0 not should be 16#7fffffff. Sorry. Aha! that's why it was commented! It came straight out of the notebook, didn't get tested, and I trimmed all comments without looking when I golfed it up. Don't tell the Python guy! :P –  luser droog Nov 7 '12 at 9:28
add comment

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 anbn, 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

share|improve this answer
add comment

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.

share|improve this answer
    
There are problems with your implementation. Try this program that swap a and b 0 'a' 0 'b' R; 0 'b' 0 'a' R with input aaa the output is bab instead of bbb. And there are problems moving left. –  Marco Martinelli Oct 24 '12 at 8:20
    
Thanks for the attention! Update fixes both, I think (hope). –  luser droog Oct 24 '12 at 9:11
    
uhm.. still getting bab –  Marco Martinelli Oct 24 '12 at 9:15
    
yeah, but this time it's correct! 'aaa' corresponds to positions [0,-1,1] on the tape. But the output that should show this clearly needs work. –  luser droog Oct 24 '12 at 9:29
add comment

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
share|improve this answer
1  
While similar, BrainFuck is not the same as a Turing Machine. For one, determining if the contents of a cell are equal to the contents of another cell is not an atomic operation. Also, the question requires a TM program which runs on top of the simulator. –  luser droog Oct 30 '12 at 4:58
    
It does resemble a turing machine in many ways, but the language itself is not a turing machine. In order to handle any turing machine from the 5-tuple form mentioned in the question, a rather nontrivial Brainfuck program needs to be written. –  CMP Jan 4 '13 at 17:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.