TURINGMACHINE

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 - 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:

since 1st January 2000, last changed 13th April 2018