Turing Machine JAPH

turing.pl

#!/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;{

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. ;)

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

$ ./turing.pl prog0.tur 1101111
1110000
$ ./turing.pl prog0.tur 1111
10000
$ ./turing.pl prog0.tur 100000
100001
$ ./turing.pl prog0.tur 104
Died at ./turing.pl line 3, <> line 9.