Re: Perl Quiz of the Week #24 (Turing Machine simulation)

Zed Lopez <[email protected]> writes:

> If helloworld.tm contains:
>
>         s0 _ s1 h R
>         s1 _ s2 e R
>         s2 _ s3 l R
>         s3 _ s4 1 R
>         s4 _ s5 o R
>         s5 _ s6 _ R
>         s6 _ s7 w R
>         s7 _ s8 o R
>         s8 _ s9 r R
>         s9 _ s10 l R
>         s10 _ s11 d R
>
> then
>
>         tm.pl helloworld.tm
>
> should output:
>
>         hello_world

Not quite. ;-)

  $ ./tm.pl helloworld.tm 
  hel1o_world

I'm quite pleased with this quiz and spent some time looking around
for more Turing Machine programs to test my solution with.  Here's one
I found (and translated from a different format):

# Sample palindrome detector from:
#   http://userpages.wittenberg.edu/bshelburne/Turing.htm

# The following Turing Machine program detects palindromes made up of
# strings of 0's and 1's. Starting in state A it reads (and erases)
# either a 1 or a 0 changing its state to B or C to "record" that a 1
# or 0 was read. It then moves right to locate the right end of the
# string where it backs up (moves left) and tries to match a
# corresponding 1 or 0. If successful, it move left to the beginning
# of the string and repeats.

# Palindrome Detector for strings of 0's and 1's
# A is Start State; Z is Accept State

A 1 B _ R # detect 1 - store as state B
A 0 C _ R # detect 0 - store as state C
A _ Z _ R # empty string - done! (even number) 
B 0 B 0 R # go right
B 1 B 1 R
B _ D _ L # end of string detected - go back
C 0 C 0 R # go right
C 1 C 1 R
C _ E _ L # end of string detected - go back
D 1 F _ L # found 1, cancel it, & go back
D _ Z _ L #   or found blank - done! (odd number)
E 0 F _ L # found 0, cancel it & go back
E _ Z _ L #   or found blank - done! (odd number)
F 0 F 0 L # go back
F 1 F 1 L
F _ A _ R # beginning of string detected


Enjoy,
Jon