Turing machine simulator (LaTeX)
From LiteratePrograms
- Other implementations: C | C++ | C++ | Haskell | Java | LaTeX | OCaml | Ruby | Scheme | Sed | Unlambda
This is an implementation of a turing machine in LaTeX. Since LaTeX is foremost a typesetting software, this program produces text to be typeset. More exactly, it generates a textual description of what happens when running a three-state busy beaver.
This program was successfully tested with LaTeX2e on Linux.
Contents |
Definition of the turing machine
A turing machine consists of several parts:
- A tape which is infinite on one or both sides, and at each position contains one of a finite set of symbols.
- A read/write head which can move along the tape one position at a time, read the symbol at the current position, and replace that symbol with another symbol.
- A state machine, which controls the read-write head according to a table defining the actual program.
The state machine's table contains for each combination of current state and current symbol at the head's position
- what symbol to write at that position (replacing the current symbol)
- in which direction (left or right) to move the head afterwards
- the next state of the state machine
There's a special "halt" state, which causes the turing machine to stop operation. Usually that halt state is not counted, i.e. an n-state turing machine has actually n+1 states: n "working" states and the halt state.
Definition of the busy beaver
A busy beaver is turing machine with the following properties:
- It has exactly two symbols. One of them may be called "blank" or "zero", the other symbol may be called "one".
- It runs on a tape which is infinite on both sides.
- If started on an empty tape (i.e. one which is filled with the "blank" symbol), it stops after a finite number of steps. After that, the tape contains as many ones as possible.
The document
As LaTeX is a typesetting program, the input files always describe documents. It will turn out that our document is quite short (about two pages), so the article document class is appropriate. A 12 point font is chosen for better readability. The document structure looks like the following:
<<turing.tex>>= \documentclass[12pt]{article} definitions \begin{document} document text \end{document}
Our document gets a nice title.
<<document text>>= \title{The Tale of the Busy Beaver} \maketitle
After that, we run the turing machine. The turing machine itself generates the describing text.
<<document text>>= \RunTuringMachine
The turing machine implementation
The turing machine consists of the head, the tape, the state machine and the state table.
<<definitions>>= head definitions tape definitions state machine definitions state table definitions
Note that since those macros are called from within printed text, additional spaces and line breaks may be significant for the resulting text output. Since the LiteratePrograms wiki software may induce such extra spaces and line breaks, sometimes macros are not split into individual chunks even if doing so would be a presentational advantage.
The head
The only relevant information about the head is its current position. That position can conveniently be stored in a tex counter. The initial position of the head is 0.
<<head definitions>>= \newcounter{headpos} \setcounter{headpos}{0}
Head movements just add or subtract 1 from the head's position. Also, those actions add some text to the document stating that movement.
<<head definitions>>= \newcommand{\Moveleft}{\addtocounter{headpos}{-1}% moved one position to the \textbf{left}} \newcommand{\Moveright}{\addtocounter{headpos}{1}% moved one position to the \textbf{right}}
The tape
The tape basically is a mapping from position to symbol. This is done by defining an unique macro for each visited position, containing the corresponding symbol. The name of the macro is derived by appending the head's current position in decimal notation to the prefix TapeAt.
To compute a macro name at runtime, there exist the TeX primitives \csname and \endcsname. The expansion of whatever is between those primitives makes up the new symbol's name. A side effect of this is that the new symbol's name can consist of any character sequence, even if those characters could otherwise not be part of a macro name. In our case, the digits and (for negative positions) the minus sign are such characters. Using the macro \arabic to get at the decimal representation of the tape position, the complete macro name is written
\csname TapeAt\arabic{headpos}\endcsname
Another side effect of \csname … \endcsname is that if the macro has not yet been defined, it gets defined to be equivalent to \relax. Now automatic definition is fine, but the value of newly defined macros should be zero, not \relax. Thus if the macro was undefined before, it has to be re-defined to the correct value. This means that the macro name will be needed several times; since it's quite complicated to write, it makes sense to alias it with an easier accessible name, \TapeAtHead. Such an alias is done through \let. However, the obvious solution
\let\TapeAtHead=\csname TapeAt\arabic{headpos}\endcsname
is wrong: This would alias \TapeAtHead with \csname, and then try to expand TapeAt\arabic{headpos}\endcsname. The solution is \expandafter, which expands its second argument before the first:
\expandafter\let\expandafter\TapeAtHead\expandafter=%
\csname TapeAt\arabic{headpos}\endcsname
The % comments out the line break; the effect is that the second line is directly appended to the first one.
Now that we have the type position in a convenient alias, we need to define it to zero if it wasn't already defined. Testing if it was defined is done with \ifx: If it was not defined before, it's now \relax. In that case, it's re-defined as zero. Since we don't want to redefine \TapeAtHead, but the macro it references, \expandafter is used again:
\ifx\TapeAtHead\relax\expandafter\def\TapeAtHead{zero}\fi
The whole thing is packed into a macro which delivers the symbol. The obvious solution would be for the macro to expand to the symbol's name. This works great for output, but it will turn out that we'll also need the symbol value to calculate another macro's name, and \def may not be used in between \csname and \endcsname. Therefore another approach is used: The macro takes another macro name as argument, and defines that macro to the symbol value.
\def#1{\TapeAtHead}
Putting all this together gives the following macro definition for reading the tape:
<<tape definitions>>= \newcommand{\ReadTape}[1]{% \expandafter\let\expandafter\TapeAtHead\expandafter=% \csname TapeAt\arabic{headpos}\endcsname% \ifx\TapeAtHead\relax\expandafter\def\TapeAtHead{zero}\fi \def#1{\TapeAtHead} }
To write to the tape, the macro name is computed, and the resulting macro is defined to the new symbol. However, unlike reading, which is a "silent" operation, writing is self-descriptive: Besides changing the tape, it also adds some text to the document stating that it wrote that symbol.
<<tape definitions>>= \newcommand{\Write}[1]{% \expandafter\def\csname TapeAt\arabic{headpos}\endcsname{#1}% wrote a \textbf{#1} at this position, }
The state machine
The state machine executes the entry of the state table corresponding to the current state and tape sybol.
The tape symbol is read at the beginning into the macro \Symbol, by expanding the macro \ReadTape
\ReadTape{\Symbol}
At the end of the macro, the corresponding state table entry is executed by constructing a macro name from the state name and tape symbol. This is again done with \csname … \endcsname:
\csname#1\Symbol\endcsname
The argument #1 contains the current state's name.
In addition, it contains most of the output text. The text first tells which state the machine just changed to, or initially is. Since the first invocation of the state machine therefore needs a different initial text, that text is stored in a separate macro which is redefined by the state machine after output.
<<state machine definitions>>= \newcommand{\StateInitialText}{Initially the busy beaver was in state }
After that, a new sentence begins in a new paragraph. The new sentence starts with noting the current step number, which is incremented before output. For this step number, we need a counter.
<<state machine definitions>>= \newcounter{step} \setcounter{step}{0}
The text continues by stating again the current state (while technically being redundant, it makes a better read), the current position and symbol. The description of the action is then mostly generated by the expanded state table macro (or rather the actions expanded from there). This state table macro also recursively invokes the next state.
So the complete state macro reads as follows:
<<state machine definitions>>= \newcommand{\State}[1]{\ReadTape{\Symbol}% \StateInitialText \textbf{#1}.% \renewcommand{\StateInitialText}{and switched to state } \addtocounter{step}{1}% At the beginning of step \textbf{\arabic{step}}, the busy beaver was in state \textbf{#1}, sitting at position \textbf{\arabic{headpos}} of the tape. The tape at this position contained a \textbf{\Symbol}. The beaver \csname#1\Symbol\endcsname}
Finally we have to define how to start the turing machine. The busy beaver starts in state A, thus we simply invoke that state.
<<state machine definitions>>= \newcommand{\RunTuringMachine}{\State{A}}
The state table
The state table just consists of a list of macros named as concatenation of state name and symbol name (this of course has as precondition that no two state name/symbol name combinations give the same macro name).
For the "working states", we just invoke the appropriate actions (write new symbol, move, invoke new state) in the correct order. The corresponding macros are self-describing, so we don't need any immediate text here.
<<state table definitions>>= \newcommand{\Azero}{\Write{one}\Moveright\State{B}} \newcommand{\Aone}{\Write{one}\Moveleft\State{C}} \newcommand{\Bzero}{\Write{one}\Moveleft\State{A}} \newcommand{\Bone}{\Write{one}\Moveright\State{B}} \newcommand{\Czero}{\Write{one}\Moveleft\State{B}} \newcommand{\Cone}{\Write{one}\Moveleft\State{Halt}}
The Halt state is special because no further activity is done. Therefore just a text is output which states exactly this. Since \State is not called again, this indeed terminates the recursion and therefore halts the program.
As the text of the halt state is independent of the current tape symbol, to avoid redundancy both \Haltzero and \Haltone invoke the macro \Halt which contains the actual text.
<<state table definitions>>= \newcommand{\Haltzero}{\Halt} \newcommand{\Haltone}{\Halt} \newcommand{\Halt}{stopped any activity.}
Output sample
The output of this program looks like the following (but typeset e.g. as PostScript or PDF; only the beginning of the text is shown):
Initially the busy beaver was in state A.
At the beginning of step 1, the busy beaver was in state A, sitting at position 0 of the tape. The tape at this position contained a zero. The beaver wrote a one at this position, moved one position to the right and switched to state B.
At the beginning of step 2, the busy beaver was in state B, sitting at position 1 of the tape. The tape at this position contained a zero. The beaver wrote a one at this position, moved one position to the left and switched to state A.
At the beginning of step 3, the busy beaver was in state A, sitting at position 0 of the tape. The tape at this position contained a one. The beaver wrote a one at this position, moved one position to the left and switched to state C.
| Download code |