Turing Machine Code Golf

Question

Ok guys, today's goal is to build a Turing machine simulator. For those that don't know what it is, see the Wikipedia article. The state table we are using today is found at the end of the Formal Definition that's part of that page.

The code will take a sequence of "0" and "1" string characters, an integer representing the character that the machine starts with, and an integer representing the state of the program (in no particular order), and output the final result of the operations on the string, as well as the final position. Examples:

Example 1:

1010 state A(0)
   ^ (3)
1011 state B(1)
  ^ (2)
1011 state B(1)
 ^ (1)
1111 state A(0)
  ^ (2)
1111 state C(0)
   ^ (3)
1111 HALT
  ^ (2)

Example 2:

110100 state B(1)
   ^ (3)
110100 state B(1)
  ^ (2)
111100 state A(0)
   ^ (3)
111100 state C(2)
    ^ (4)
111110 state B(1)
     ^ (5)
1111110 state A(0)
      ^ (6, tape has been extended to right)
1111111 state B(1)
     ^ (5)
1111111 state B(1)
    ^ (4)
1111111 state B(1)
   ^ (3)
1111111 state B(1)
  ^ (2)
1111111 state B(1)
 ^ (1)
1111111 state B(1)
^ (0)
01111111 state B(1)
^ (0, tape has been extended to left)
11111111 state A(0)
 ^ (1)
11111111 state C(2)
  ^ (2)
11111111 HALT
 ^ (1)

Misc:

• Your code must properly handle attempts to write into "blank spaces" on the tape, by extending the string as necessary.
• Since the state machine specified does not specify any sort of "blank tape" action, treat all blank values as 0.
• You must count only the method that handles evaluation of a string with initial state, how you output that data is up to you.
• Moving right on the tape is incrementing up (string position 0 is all the way at the left), state 0 is A, state 1 is B, and state 2 is C.

(hopefully) final edit: I offer my most sincere apologies as to the confusion and trouble I've caused with this question: I misread the supplied state table I listed, and got it backwards. I hope you'll forgive me for wasting your time; it was entirely unintentional!

Chrysolite

Why is it voted to close? i waited a suitable time, it's a valid question (see meta.stackexchange.com/questions/20912/so-weekly-code-golf ), and it's not underspecced or anything... – Chrysolite

There are precedents for code golf being acceptable. – Unsustainable

Must be a toughie... Or maybe i asked it at a bad time! :) – Chrysolite

Unbelievable. No one posted an answer... :/ Fine i'll slice off some rep ,maybe that will get people interested. – Chrysolite

I cannot reproduce the results from your examples, even when I compute them by hand. Can you explain the chart maybe? I'm reading it as state A=0 and C=3, and move the tape right equates to decrementing the iterator over the string, and the second parameter is the index of the string to start at. Is that all correct? – Shu

Edited my answer with more info. – Chrysolite

what does "blow up" mean? Is it when we try to move beyond the left most position on the tape? – Matti

No, it's when the machine will not halt because it just keeps expanding the tape and writing 1s into the value. Since there's no easy way to look for this, you don't technically have to check for this. But if you implement Busy Beaver(3) checking in your machine then you get bonus points :) en.wikipedia.org/wiki/Busy_beaver – Chrysolite

Can you provide an example where the tape is extended to the left but does not "blow up"? – Matti

RE: "moving right on the tape is incrementing up". Are you referring to what the R and L in the table mean? Because "moving right on the tape" is the opposite of "move the tape right," which is what the table is referring to. – Shu

I cannot get either "blow up" example to blow up, even when hand calculated. I cannot figure out what I am doing wrong. All of the other examples match with my code. – Watershed

"implement Busy Beaver checking" sounds kind of hard.... – Upbow

@gnibbler: Imagine a regular number line, with 0 at the very left of the string and positive numbers going right. When you move the "turing machine" right one symbol, it is equivalent to moving it left one symbol. And when you move the turing machine right noe symbol, the "instruction pointer", or the spot where the "turing machine"s "head" is should go up by one. – Chrysolite

Ok, sorry guys my examples are wrong. I have selected 2 of my examples and have completely processed them by hand to show you all intermediate states. Please comment if you are still confused.) – Chrysolite

Can the initial sequence of 0 and 1 be empty? – Uhl

An empty tape is equivalent to a single 0, so yes. Though some scripts may not support taking an empty tape as the start so an empty tape is disallowed (in the interests of not disrupting competition). – Chrysolite

Oh - wait... we don't have to count the I/O routines in the char count? Just the eval function itself? – Bartell

is it legal not to bother at all with state table ? If you want a beaver and only test for input and output internal implementation should be irrelevant (if we are really simulating a turing machine, with head, states, etc.) Golf should not make assumptions about inner working of program. – Extensile

@kriss: Sure, that's fine. Just take the simulation specific stuff as only if you actually go that way. I would be quite interested in a program that attempts to directly transform input to output! – Chrysolite

@DigitalRoss. My Python version is just a port of the lua code, so it matches the worked example here – Matti

@Aaron: no, i feel it provides a better feel for the actual answers since some languages need a lot of "scaffolding" to get a working program and i prefer not to count that. – Chrysolite

What is the correct output for 1000000 3 1? – Matti

In that case there is no correct output, your program should eventually crash. However if you implement Busy Beaver checking for BB(4) (i think that's right), you can catch it and report that the program will run forever. – Chrysolite

Well for 1000000 3 1 your lua outputs 1011100 3, My golfscript outputs "1011100"3, My Python outputs ([1, 0, 1, 1, 1, 0, 0], 3) and Aaron's C outputs 10111 3 missing the zeros on the end. Are the zeros significant to the answer or not? – Matti

Oh wait i get it yeah that sounds right. The zeros on the end are significant because while i am allowing treating blanks as 0s for the purposes of making an implementable machine, i would like those zeros saved. – Chrysolite

@Chrysolite no problem about the confusion, I still had fun programming it – Shu

Answer 1

Perl function 101 char

sub f{($_,$S,$p)=@_;for(%h=map{$i++,$_}split//;7^$S;$p-=$S<=>3){$S=7&236053>>3*($S%4*2+!!$h{$p}++)}};

f(@ARGV);
@allpos = sort keys %h;
for (@allpos){
    print $h{$_}?1:0;
}
print " H ".($p-$allpos[0])."\n";

This one was fun to find. Two tricks. It use a hash for the tape, and know what ? A hash is auto-extensible, so no need any more to care about tape boundaries. The other trick is for combining both read and write of the cell accessed. Just had to change internal conventions 0 and space means 0 and any other value means 1. These two tricks implies some trivial decoding of output, but I believe it's ok. I also not counted the final semi-colon in my function as gnibbler didn't counted his in his golfscript.

If someone is interested I can also post my other tries. They are a bit longer but uses fun tricks. One is regex based for instance and works directly with tape as string another one is a kind of bit-fu.

Perl function 112 char

sub f{($_,$S,$p)=@_;for(split//;7^$S;@_=($p=0,@_)if($p-=$S<=>3)<0){$S=7&236053>>3*($S%4*2+$_[$p]);$_[$p]=1}@_};

@res = f@ARGV;
print @res," H $p\n";

I counted the function only and it takes a string, a state num and a position in that order as specified. The function returns new tape state as an array.

Another variant 106 char

sub f{($_,$S,$p)=@_;for(split//;7^$S;$p-=$S<=>3){$S=7&236053>>($S%4*6+$_[$p]*3);$_[$p++]=1;@_=(0,@_)}@_};`

@res = f(@ARGV);
print @res," H $p\n";

It is not clear if this one is cheating or not. It gives correct results and automatically extends tape (no fixed limit), but to avoid testing if it is necessary or not to extend tape it does so every step and adjust index.

Another variant 98 char

This one is also on the merge but in a different way. It just use globals to pass parameters inside the function. Hence you set your variables outside the function instead of inside. Thus removing 14 characters from the function body.

sub f{for(split//;7^$S;@_=($p=0,@_)if($p-=$S<=>3)<0){$S=7&236053>>3*($S%4*2+$_[$p]);$_[$p]=1}@_};

($_,$S,$p) = @ARGV;
@res = f();
print @res," H $p\n";

Extensile

But if I pass a list instead of a string I can take 14 bytes off the Python, in that case perl is 9 bytes behind ;) – Matti

ok, so let's really golf, don't pass anything use globals. Parameter passing cost 25 chars here. Going back to a one liner could even be shorter. – Extensile

@gnibbler: ok i got back to same API as python. – Extensile

The argument input order isn't really specified, so go ahead and rearrange them if you want :) – Chrysolite

Hmm. I didn't catch that with the C program but that is definitely NOT allowed! As it would not be a true turing machine without an infinite (or auto-extending tape). – Chrysolite

Only a couple of days left to fix the error! if you don't, then i'll have to award the bounty to gnibbler... – Chrysolite

Congratulations! you are officially the winner of my code golf :) – Chrysolite

Answer 2

Python - 133 Characters

Have to beat perl for a while at least :)

def f(t,i,s):
 t=map(int,t) 
 while s<3:t=[0]*-i+t+[0][:i>=len(t)];i*=i>0;c,t[i]=s*4+t[i]*2,1;i+=1-(2&2178>>c);s=3&3401>>c
 return t,i

Python - 172 Characters

def f(t,i,s):
 t=map(int,t)
 while s<3:
  t=[0]*-i+t+[0]*(i-len(t)+1);i=max(0,i);c,t[i]=t[i],1;i,s=[[(i-1,1),(i+1,2)],[(i+1,0),(i-1,s)],[(i+1,1),(i-1,3)]][s][c]
 return t,i

testcases

assert f("1010",3,0) == ([1, 1, 1, 1], 2)
assert f("110100",3,1) == ([1, 1, 1, 1, 1, 1, 1, 1], 1)

Villalobos

Ok, i fixed up the examples. Sorry for the trouble! – Chrysolite

Answer 3

C - 282 44 98 chars (including all inner-loop var and table declarations)

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

char*S="  A2C1C2  C3A2A0";
f(char*p,char c){char*e;while(c){e=S+*p*8+c*2;*p=1;p+=*e++-66;c=*e-48;}}

char T[1000];
main()
{
  char *p;
        char c;
        char *e;

    int initial;
    scanf("%s %d %c",&T[500],&initial,&c);
    c = c - '0' + 1;

    for(p=&T[500]; *p; p++)
        *p -= '0';

    p = &T[500+initial];

    f(p, c);

    char *left = T;
    while((left < T+500)&&(!*left))
        left++;

    char *right = T+sizeof(T)-1;
    while((right > T+500)&&(!*right))
        right--;

    initial = p - left;

    for(p=left; p<=right; p++)
        *p+='0';

    printf("%.*s %d\n\n",right-left+1,left,initial);
}

Bartell

You can drop 4 chars by using #include <string> and #include <stdio> – Genesa

@Genesa - I know that technically you're supposed to be able to do that - but it doesn't work for me on either GCC 3.4.4 or 4.3.2 (the two gccs I have available to me) – Bartell

You should be able to drop those two lines and compile with gcc -w – Matti

Ok, i fixed up the examples. Sorry for the trouble! – Chrysolite

To be fair I think you need to include the declaration & definition of the variables you use in your character count. As it is there is no way I could call f() from another main and reproduce your results. – Shu

There is also some issue. The tape is statically allocated to 1000 cells and 500 zeroes are preallocated at the beginning. Also the tape is not passed in to the function, it's a global. If such assumptions are OK my perl function goes down to 80 chars instead of 122. – Extensile

Thanks for catching that kriss, this is NOT allowed unfortunately (see my comment on kriss's answer for why). – Chrysolite

Only a couple of days left to fix the error! if you don't, then i'll have to award it to gnibbler... – Chrysolite

This is far longer than 98 chars anyway. Where whitespace characters are required to keep the syntax or semantic of the program, they should be counted too. I count about 400 chars. – Eubank

@drhirsch - This golf isn't counting main program - just the turing function itself. – Bartell

@Chrysolite - give it to him. I suspect that once I try to figure out all the evolving rules the perl will be shorter anyway... – Bartell

Answer 4

C# - 157 characters

void T(List<int>t,ref int p,int s){while(s!=3){if(p<0)t.Insert(0,p=0);if(p==t.Count)t.Add(0);var c=t[p]==1;t[p]=1;p+=s==0==c?1:-1;s=s==1==c?1:c?s==0?2:3:0;}}

The method takes a List<int> as tape, so it can be expanded as long as memory allows it.

Assertion:

List<int> tape;
int pos;

tape = "1010".Select(c => c - '0').ToList();
pos = 3;
T(tape, ref pos, 0);
Debug.Assert(String.Concat(tape.Select(n => n.ToString()).ToArray()) == "1111" && pos == 2);

tape = "110100".Select(c => c - '0').ToList();
pos = 3;
T(tape, ref pos, 1);
Debug.Assert(String.Concat(tape.Select(n => n.ToString()).ToArray()) == "11111111" && pos == 1);

If we cheat and allocate a large enough array from start, 107 characters:

void X(int[]t,ref int p,int s){while(s!=3){var c=t[p]==1;t[p]=1;p+=s==0==c?1:-1;s=s==1==c?1:c?s==0?2:3:0;}}

Starwort

you could trim 4 chars off the function if you were to remove the ref attribute on the int property p – Chrysolite

@RCIX: Then the method would not output the final position. – Starwort

Answer 5

Golfscript - 102 Characters

{:s;{\:$;:^0<{0.:^$+:$}{^$}if.,@>!'0'*+.^=1&s.++:c;.^<1+\^)>+:$[^(^).^(^)^(]c=:^3"120113"c=3&:s-}do}:f

;
["1010" 3 0 f]p
["110100" 3 1 f]p
["1000000" 3 1 f]p

106 Characters

{:s;\:$;:i{0<{0.:i$+:$}{i$}if.,@>!'0'*+.i=1&s.++:c;.i<1+\i)>+:$;[i(i).i(i)i(]c=:i 3"120113"c=3&:s-}do$\}:f

113 Characters
Whole program reading from stdin

' '/(:$;(~:i;~~:s;{0i>{0.:i$+:$}{i$}if.,@>!'0'*+.i=1&s.++:c;.i<1+\i)>+:$;[i(i).i(i)i(]c=:i;3"120113"c=3&:s-}do$`i

examples

$ echo -n 1010 3 0 |../golfscript.rb turing.gs 
"1111"2
$ echo -n 110100 3 1 |../golfscript.rb turing.gs 
"11111111"1

Villalobos

Can't get any version working :-( stops with syntax error. Is it dependent on a specific version of ruby ? (tried with 1.8) – Extensile

Answer 6

Perl 142 char (not counting reading args on command line and final print. Well, most of code is the beaver program, the engine itself is only 46 char.

I changed input format to put the state at it's position in the string. I don't feel guilty at all as otherwise most of code was going to be border management when head was out of string. Even in this version string border management cost 17 chars... The trick is just to remember you can express turing machines as Markov chains... what I did with regexes.

perl -e '$b=shift;%p=qw(A0|A$ 1B ^A1|0A1 C01 1A1 C11 0B0|^B0 A01 1B0|1B$ A11 B1 1B 0C0|^C0 B01 1C0|1C$ B11 C1 1H);while($b!~/H/){$b=~s/$_/$p{$_}/for keys%p}print"$b\n"' 00A1011

111H1111

Note: as a matter of fact this is not really golfed yet but just a naive first attempt. I may come back with something real short.

Extensile

That has a syntax error in it; it looks like SO formatted the $_ in the regex. You could also drop 3 characters by changing the @ARGV[0] to just be shift. You also don't seem to be using off the second argument. – Hangeron

If i'm correct, can't you format your code so that it takes the state table as an argument? Then it would blow away everyone elses answer. – Chrysolite

Sure I can, but that would definitely be cheating as all other programs hard-code the beaver state table. You could also pass in a state table in other programs (something like a bidimentional array) mapping char and state to newstate, newchar and move and they would also became quite small. – Extensile

Answer 7

Perl, 97 (96 indeed, because final ";" is optional for sub block)

sub f{($_,$a,pos)=@_;s/\G./$&+2*$a+2/e;1while s!(.?)(2|5)|(3|4|6)(.?)!$2?4+$1.1:8+$4+$3+5*/3/!e}
f@ARGV;
#output
s/7/1/;print;print " H ",(-1+length$`);

The idea : $_ variable contains 0s and 1s except under the head. Under the head, 0 in A state gives 2, 1 in A state gives 3, 0 in B state gives 4, 1 in B state gives 5, 0 in C state gives 6, 1 in C state gives 7.

so following the first example "1010" (pos 3, state A) gives "1051" then "1411", "1131", "1117" (1111, state C, pos 3) and stop (plus move tape to right)

Fist

There is always some better way to do it :-) – Extensile

Answer 8

To clarify, this program simulates the Busy Beaver Turing Machine exactly as described in the wikipedia article, not the OP (the OP has R and L switched)

Python 255 char

def f(k,i,s):
 t=map(int,k)
 while s<3:
    if i==len(t):t+=[0]
    if i<0:t=[0]+t;i=0
    x=t[i],s
    if x==(0,0):t[i]=1;i-=1;s=1
    if x==(0,1):t[i]=1;i+=1;s=0
    if x==(0,2):t[i]=1;i+=1;s=1
    if x==(1,0):i+=1;s=2
    if x==(1,1):i-=1;s=1
    if x==(1,2):i-=1;s=3
 return t,i

Shu

you can put you ifs on one line like this if i<0:t=[0]+t;i=0 and then use single space for the first indent and tabs for the double indents – Matti

Ok, i fixed up the examples. Sorry for the trouble! – Chrysolite

Again, i offer my apologies. I've corrected my examples and realized my error. – Chrysolite

Answer 9

Lua, 232

Now using table lookup.

j={{-1,1},{1,-1},{1,-1}}u={{1,2},{-1,0},{-1,1}}t,i,s=...i=i+1
s=s+1 z="0"o="1"while s<4 do if i<1 then t=z..t i=1
elseif i>#t then t=t..z end c=t:sub(i,i):byte()-47
t=t:sub(0,i-1)..o..t:sub(i+1)i=i+j[s][c]s=s+u[s][c]end print(t,i-1)

This is just RCIX's answer re-golfed, 332 characters.

t,i,s=...i=i+1 s=s+0 r=string.rep b=string.sub z="0"o="1"while s<3 do if i<1 then
t=z..t i=1 elseif i>#t then t=t..z end c=b(t,i,i)t=b(t,0,i-1)..o..b(t,i+1,#t)if
s<1 then i=i+(c==o and 1 or -1)s=c==z and 1 or 2 elseif s<2 then i=i+(c==o and
-1 or 1)s=c==z and 0 or s else i=i+(c==o and -1 or 1)s=c==z and 1 or 3 end end
print(t,i-1)

• uses ... operator to assign input params
• uses and and or instead of if statements when shorter
• replaced some elseif with just else by assuming valid input/states
• removed spaces after parens, ellipse operator, and end quotes

Ashford

Wow. I didn't even know you could use the ... operator to get args from a command line! – Chrysolite

Answer 10

F# - 275 characters

Okay, so definitely not the shortest but learning. If anyone can assist on getting the String.mapi to use a function rather then the fun match with I would appreciate it, I keep getting 'The pattern discriminator x is not defined'. Anyone know of a site that details the rules of using the function keyword in a lambda?

let rec t s i p=
    match s with
    |3->(p,i)
    |_->let g=[[(1,1);(-1,2)];[(-1,0);(1,1)];[(-1,1);(1,3)]]
        let p=match i with|_ when i<0 ->"0"+p|_ when i=p.Length->p+"0"|_->p
        let i=max 0 i
        let m,n=g.Item(s).Item((int p.[i])-48)
        String.mapi(fun x c->match x with|_ when x=i->'1'|_->c) p |> t n (i+m)

Usage

t 1 2 "101011" |> printfn "%A"

Here is an expanded version for readability:

let rec tur state index tape =
    printfn "Index %d: State %d: Tape %s:" index state tape
    match state with
    |3 -> (tape, index)
    |_ -> let prog = [[(1,1);(-1,2)];[(-1,0);(1,1)];[(-1,1);(1,3)]]
          let tape = match index with |_ when index<0 ->"0"+tape |_ when index=tape.Length->tape+"0" |_->tape
          let index = max 0 index
          let move,newstate = prog.Item(state).Item((int tape.[index])-48)
          String.mapi (fun i c -> match i with |_ when i=index->'1' |_->c) tape
          |> tur newstate (index+move)

I'm also trying to think of a better way to handle the manipulation of the string, something other then the String.mapi. Comments and suggestions (constructive please) welcome and encouraged.

Knowledgeable

Hint: rewrite 'String.mapi (fun i c -> match i with |_ when i=index->'1' |_->c) tape' as 'String.mapi (fun i c -> match c with |_ when i=index->'1' |c->c) tape'. Now you can curry the second argument c instead of the first argument i as follows: 'String.mapi(fun i->function|_ when i=index->'1'|c->c)tape'. Using a simple if..then..else will make it even shorter. – Bloc

Answer 11

Lua:

Semi-golfed version:

a=arg
t=a[1]
i=a[2]+1
s=a[3]+0
r=string.rep
b=string.sub;z="0";o="1";while true do if i<1 then
        t=z..t
        i=1
    elseif i>#t then
        t=t..z
    end
    c=b(t,i,i)
    if i>0 then
        t=b(t,0,i-1)..o..b(t,i+1,#t)
    else
        t="1"..b(t,i+1,#t)
    end
    if s==0 then
        if c==z then
            i=i-1
            s=1
        elseif c==o then
            i=i+1
            s=2
        end
    elseif s==1 then
        if c==z then
            i=i+1
            s=0
        elseif c==o then
            i=i-1
        end
    elseif s==2 then
        if c==z then
            i=i+1
            s=1
        elseif c==o then
            i=i-1
            break
        end
    end
end
print(t,i-1)

Compacted version weighing in at 441 characters:

a=arg t=a[1] i=a[2]+1 s=a[3]+0 r=string.rep b=string.sub;z="0";o="1";while true do if i<1 then t=z..t i=1 elseif i>#t then t=t..z end c=b(t,i,i) if i>0 then t=b(t,0,i-1)..o..b(t,i+1,#t) else t="1"..b(t,i+1,#t) end if s==0 then if c==z then i=i-1 s=1 elseif c==o then i=i+1 s=2 end elseif s==1 then if c==z then i=i+1 s=0 elseif c==o then i=i-1 end elseif s==2 then if c==z then i=i+1 s=1 elseif c==o then i=i-1 break end end end print(t,i-1)

Pass the arguments in form of tape, instruction pointer, state, like the following:

turing.lua 1010 3 0

Chrysolite

you are adding one to i instead of subtracting when halting – Matti

Answer 12

Ruby, 129

(when indent removed)

def pr t,z,s      # DEBUG
  p [t,s]     # DEBUG
  p [' '*z + '^'] # DEBUG
end       # DEBUG


def q t,z,s
  s*=2
  (t=t.ljust z+1
    (t=' '+t;z=0)if z<0
    a=t[z]&1
    t[z]=?1
    b=s>0?1-a: a
    s="240226"[s|a]&7
    z+=b*2-1)while s!=6
  [t,z]
end

p q "1010",3,0
p q "110100",3,1

Fico