TURING
MACHINE

 

 

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:

The course of the computation


To be continued... main page czech

since 1st January 2000, last changed 13th April 2018
Copyright 2000-2018 Vladimir Zabrodsky.
 
mail