views:

1883

answers:

12

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!

+1  A: 

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
RCIX
you are adding one to `i` instead of subtracting when halting
gnibbler
Thanks, missed that!
RCIX
+9  A: 

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);
}
Aaron
You can drop 4 chars by using #include <string> and #include <stdio>
plinth
@plinth - 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)
Aaron
You should be able to drop those two lines and compile with **gcc -w**
gnibbler
Ok, i fixed up the examples. Sorry for the trouble!
RCIX
Graphics Noob
@Graphics Noob, I guess that's a fair point.
Aaron
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.
kriss
Thanks for catching that kriss, this is NOT allowed unfortunately (see my comment on kriss's answer for why).
RCIX
Only a couple of days left to fix the error! if you don't, then i'll have to award it to gnibbler...
RCIX
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.
drhirsch
@drhirsch - This golf isn't counting main program - just the turing function itself.
Aaron
@RCIX - give it to him. I suspect that once I try to figure out all the evolving rules the perl will be shorter anyway...
Aaron
+2  A: 

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
Graphics Noob
`t=map(int,k)` should do it
gnibbler
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
gnibbler
Thanks for the tips gnibbler, I'll update
Graphics Noob
Ok, i fixed up the examples. Sorry for the trouble!
RCIX
Again, i offer my apologies. I've corrected my examples and realized my error.
RCIX
+10  A: 

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)
gnibbler
Ok, i fixed up the examples. Sorry for the trouble!
RCIX
now perl is at 122 ;-)
kriss
+3  A: 

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.

kriss
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.
s1n
thanks. Corrected
kriss
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.
RCIX
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.
kriss
+3  A: 

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
gnibbler
gonna have to work harder to beat C :)
RCIX
Can't get any version working :-( stops with syntax error. Is it dependent on a specific version of ruby ? (tried with 1.8)
kriss
@kriss I'm using 1.8.7
gnibbler
+1  A: 

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.

David
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.
cfern
+6  A: 

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";
kriss
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 ;)
gnibbler
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.
kriss
@gnibbler: ok i got back to same API as python.
kriss
The argument input order isn't really specified, so go ahead and rearrange them if you want :)
RCIX
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).
RCIX
Only a couple of days left to fix the error! if you don't, then i'll have to award the bounty to gnibbler...
RCIX
Cool! you're winning right now by one character :)
RCIX
Congratulations! you are officially the winner of my code golf :)
RCIX
+1  A: 

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
gwell
Wow. I didn't even know you could use the `...` operator to get args from a command line!
RCIX
+2  A: 

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;}}
Guffa
you could trim 4 chars off the function if you were to remove the `ref` attribute on the int property `p`
RCIX
@RCIX: Then the method would not output the final position.
Guffa
A: 

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
DigitalRoss
+2  A: 

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)

brx
There is always some better way to do it :-)
kriss