
	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:

    { <state>, <symbol>, <action>, <new-state> }

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{ <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{ <stat> }		    

Sets the initial state of the machine. It must be of the form q<number>.


      \Program{ <quadruple1>
		<quadruple2>
		... }

Describes the program. <quadruple> must have the form {<stat>, <symbol>,
<action>, <newstat>}. <action> 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{ <title> }

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 $
