[FWP] Turing machine simulator

[Mark Rogaski <wendigo@pobox.com>]

In a fit of insomnia, I worked up a simulation of a simple one head, one
R/W tape, deterministic Turing machine.  The rules for it are as such:

1. The first argument is the name of a file containing a comma delimited
   list of finite-state control instructions representing

      curr_state,read_symbol,new_state,write_symbol,head_direction

   The second argument is a character string representing the initial
   contents of the tape.

2. The states are encoded as integers >= 0 or '!!' for the halt state.

3. The symbols may be any printable ASCII character.  An empty square is
   encoded as '##' and a comma is encoded as 'CM'.

4. Head direction is either 'L' or 'R'.

5. If the TM encounters a transition for which no finite-state control
   instruction exists, the simulator dies.

6. The TM starts with the tape head at the leftmost position.

7. Attempting a solution to the halting problem is not recommended. ;)



Here is my version of the simulator:

#!/usr/local/bin/perl -nl
@a=map{s/##//;s/CM/,/;$_}split(",",$_);$s->[$a[0]]{$a[1]}=[@a[2..4]];}continue{
eof&&last;}$q=$i=0;@t=split(//,shift);while("!!"ne$q){($q,$t[$i],$_)=@{$s->[$q]
{$t[$i]}||die};$i+=(/R/?1:-1);if($i<0){$i++;unshift(@t,"");}}print@t;{


And, an example program to increment a binary string:

0,1,0,1,R
0,0,0,0,R
0,##,1,##,L
1,1,1,0,L
1,0,2,1,L
1,##,2,1,L
2,1,2,1,L
2,0,2,0,L
2,##,!!,##,R


And the results:


wendigo@deathstar:~/turing> ./turing.pl prog0.tur 1101111
1110000
wendigo@deathstar:~/turing> ./turing.pl prog0.tur 1111
10000
wendigo@deathstar:~/turing> ./turing.pl prog0.tur 100000
100001
wendigo@deathstar:~/turing> ./turing.pl prog0.tur 104
Died at ./turing.pl line 3, <> line 9.


Whaddya think?

Mark

-- 
Mark Rogaski                  | "I've said this before but I'll say it again:
wendigo@pobox.com             |     Smashing Pumpkins IS REO Speedwagon."
http://www.pobox.com/~wendigo |                      -- Steve Albini
__END__                       |

PGP signature