This article includes the base for building of
simple tools to learning and studying famous Turing
machines. The program AlanMath (the abbreviation of Alan
Mathison Turing) interprets descriptions of Turing
machines as the following example: a Turing machine
accepting the set of all strings
COPIES("a", N) || COPIES("b", N), for N >= 0,
can be described:
Begin End # 1
Begin # # End R
Begin a A 2 R
2 B B 2 R
2 a a 2 R
2 b B 3 L
3 B B 3 L
3 A A 5 R
3 a a 4 L
4 a a 4 L
4 A A Begin R
5 B B 5 R
5 # # End R
|
Figure 1.
The first line in the description contains:
Start Halt Blank Head [note]
|
| Start |
|
- a word, the name of the start state |
| Halt |
|
- a word, the name of the halt state |
| Blank |
|
- a character used to denote a
blank
(but no really blank) |
| Head |
|
- a number, the initial position of the head
on the
tape |
A transition table follows as the series of
5-tuples, one on each line. The transition is like
this:
State Symbol NewSymbol NewState Move
[note]
|
| State |
|
- a word, the current state |
| Symbol |
|
- a character, the current symbol
a character on
the tape below the head |
| NewSymbol |
|
- a character, the new symbol
a character written
on the tape |
| NewState |
|
- a word, the new state |
| Move |
|
- the direction
of move the head:
"R" to the right, "L" to the left |
This description corresponds to the book of Zohar
Manna Mathematical theory of Computation, McGraw-Hill,
NY, 1974. The program AlanMath can be necessary adapt for an
another textbook.
When the ASCII file FIGURE1.TXT includes the description
from the figure 1, then the program AlanMath on the figure
2 with the value of the argument
FIGURE1.TXT shows the course of the computation and
writes "Accepted" for the input string "aaabbb"; writes
"Rejected" for the input string "aaabb".
/* AlanMath */
TM = ARG(1)
parse value LINEIN(TM) with Start Halt Blank Head .
T. = ""
/* 5-tuples are State Symbol NewSymbol NewState Move */
do while LINES(TM) > 0
parse value LINEIN(TM) with State Symbol T.State.Symbol
end
Tape. = Blank; Shot = ""
say "Enter input string"; parse pull Input .
do J = 1 to LENGTH(Input)
Tape.J = SUBSTR(Input, J, 1);
Shot = Shot || Tape.J
end
say COPIES(" ", Head - 1) ||"_"; say Shot "in" Start
State = Start; Symbol = Tape.Head
do until State = Halt | T.State.Symbol = ""
parse var T.State.Symbol Tape.Head State Move .
Shot = OVERLAY(Tape.Head, Shot, Head, 1)
if Move = "L" then Head = Head - 1; else Head = Head + 1
if Head = 0 then leave
Symbol = Tape.Head
say COPIES(" ", Head - 1) || "_"; say Shot "in" State
end
if State = Halt then say "Accepted"; else say "Rejected"
|
Figure 2
The following example shows the course of the computation for
the input string "ab" in the environment of Personal REXX for Windows(tm) Version 3.50, Quercus Systems:
