A TURING MACHINE IN TeX ======================= QUICK START ----------- If you want to run the machine RIGHT NOW, do the the following. For a more detailed explanation go to the next section. You should have the files turing.tex example.tex example2.tex example3.tex Now, run TeX on any of the files example?.tex, for instance: $ tex example and you will get the output example.dvi. View it with the tool you use for preview dvi files, for example: $ xdvi example NOT SO QUICK START ------------------ Donald Knuth's TeX is not only the greatest package for typesetting, but it is also a real programming language. I have written a small example to show this. Surely, the code is too long, but I tried to make it clear. A Turing machine consists of an infinite tape with a cursor in which you can make four kinds of operations: o move cursor right o move cursor left o write a symbol at the cursor's position o read a symbol from the position pointed by the cursor When the machine begins to work it is in some state, and the operations can alter this state. Usually they are noted by q0, q1, q2 and so on. A program for this machine is a set of quadruples with the form: { , , , } The machine looks for a quadruple whose two first elements coincides with the actual state and with the symbol at the cursor's position. If it is found, then the machine performs the action indicated, toggles to the new state and repeats this step. If it is not found, then the machine stops. This machine is an abstraction of a real computer, but they are equivalents in some sense. The theory can be found in many books, for example: A.G. Hamilton. Logic for mathematicians. Cambridge University Press Let's follow a run of the machine step by step. Suppose the tape is a sequence of 0's and 1's as follows: 0000111000 ^ The symbol "^" represents the position of the cursor. Let's suppose that the machine begins in state q0, and the program is: { q0, 1, R, q1 } { q1, 1, R, q0 } { q1, 0, R, q2 } { q2, 0, 1, q3 } where R is the action "move right" and 1 in the fourth quadruple is the action "write 1 at cursor's position". The machine performs the following operations (the actual state is marked besides the cursor and the corresponding quadruple is written on the right). 0000111000 { q0, 1, R, q1 } ^q0 0000111000 { q1, 1, R, q0 } ^q1 0000111000 { q0, 1, R, q1 } ^q0 0000111000 { q1, 0, R, q2 } ^q1 0000111000 { q2, 0, 1, q3 } ^q2 0000111010 stops ^q2 This program recognizes if the sequence of 1's which follows the cursor is even or odd. If it is odd, the machine prints 1 at the end as in the example before. If it is even, the machine just stop at the end of the sequence (try to make a step-by-step execution in this case). This example is a bit silly, but you can make more complex programs with little effort. The TeX implementation follows very closely this notation. The complete code for this example is at the end of this file. First of all, the code of the machine must be loaded with \input turing.tex For specifying the tape just write \Tape{0000>111000} The symbol ">" marks the cursor's position. Note that the tape length is finite (of course, what did you expect? ;-) ). But, it is potentially infinite in the sense that it is stretchable without limit. When an operation moves beyond the limits of the tape, it stretches with 0's. To specify the initial state write \Stat{q0} And to specify the program write \Program{{q0,1,R,q1} {q1,1,R,q0} {q1,0,R,q2} {q2,0,1,q3}} And to run the program write \run Finally, run TeX on the file where you put these things. If everything goes okay, you will have the TeX output "turing.dvi". Look at this and you will see the execution step-by-step. And this is all! The interesting part of this is the code, which shows how TeX can do some things such as recursion or parameter passing between functions. Please, look at it, modify it, write your own code. You can use a lot of programming techniques to make your documents look wonderful. I hope this small example help you with that. I have added two more examples, a little more sophisticated, extracted from the book of Hamilton. An example of copy and another of multiplication. SUMMARY OF COMMANDS ------------------- These are the commands recognized by the machine: \Tape{ } Defines the tape. It is a sequence of any kind of symbols (except R or L which are reserved for actions) with any length. The cursor's initial position is indicated by ">" before the symbol that it points to. \Stat{ } Sets the initial state of the machine. It must be of the form q. \Program{ ... } Describes the program. must have the form {, , , }. can be R: moves right, L: moves left or any symbol (except R or L), in which case the machine prints that symbol. \run Executes the machine. \Tit{ } Sets the title for printing. \prprogtrue \prprogfalse This flag indicates whether the program's quadruples must be printed. \stepbysteptrue \stepbystepfalse This flag indicates whether the execution must be printed step by step or just the final state of the tape. CODE OF THE EXAMPLE ------------------- --- cut here --- \input turing.tex \Tape{0000>111000} \Stat{q0} \Program{{q0,1,R,q1} {q1,1,R,q0} {q1,0,R,q2} {q2,0,1,q3}} \run \bye --- cut here --- Feel free to contact me. Walter Moreira. 01/04/2000. walterm@cmat.edu.uy $Id: README,v 1.5 2000/04/23 00:37:23 walterm Exp $