Steve Hawley writes: The program I sent is a fully programmable Turing Machine, hence the name Alan.ps. In spite of the bad reputation that PostScript has for speed (being an interpreted language), the programs running on this interpreter running under the PostScript interpreter in a LaserWriter NT run at engine speed: the bottleneck is paper throughput, not laying glyphs on the page. The variable /it is the input tape (see, I told you it was mnemonic) which is simply a string which each character is a cell on the tape and each cell contains a member of the symbol set. /tm is the input machine. It is a dictionary that consists of state key/value pairs. Each state is a dictionary that contains one key for every valid member of the symbol set that it understands. The value of a state is a procedure that executes that state. The supplied demonstatration program performs addition. The input tape is in the form: The output is a string of 3's whose cardinality is the sum of those of the 1's and 2's. This is typically the first assignment to CS theory students after introducing a Turing Machine. Here is the unobfuscated version of the demo machine: /inputtape (x1112222) def /machine 10 ddbegin % ddbegin: dict dup begin % seek for the first 1 on the tape. /findfirst1 3 ddbegin % Read a 1? write an x, goto endseek /1 { (x) writecell r /endseek setstate } def % Read an x? Step to the right /x { r } def % Read a 3? We're done. /3 { (done.) why halt } def end def % seek to end of tape /endseek 5 ddbegin % Read a 1? Step to the right /1 { r } def % Read a 2? Write a 3, step right. (converts all 2's to 3's) /2 { (3) writecell r } def % Read a 3? Step right /3 { r } def % Read a space? (first empty cell) Write a 3, change state. ( ) cvn { (3) writecell /startseek0 setstate } def end def /startseek0 2 ddbegin % Read an x (mark)? Back to start. /x { /findfirst1 setstate } def % Read a 1? Step left /1 { l } def % Read a 3? Step left /3 { l } def end def end def % define the start state. /startstate /findfirst1 def The output is for each state a snapshot of the tap surrounding the tape head. You can, of course, program you own Turing Machines. Anyone who is taking a CS theory course might find this a handy tool. I provide you with the following procedures (in obfuscated form): l - step the head to the left r - step the head to the right wc - write the first char of the string on the top of the stack to the current cell (ie, (3) writecell). ss - set the state to a new state for the next execution. w - record a string as an "error" message. (reason) w ht - halt execution and post the reason. All error checking is done for you so that a step off the end of the tape or an unknown symbol error will be caught. The only real failing of this program is that a Turing Machine is supposed to have an infinite tape. Here we have 5000 cells. If you step past this limit, you will get an internal error. The limit on PostScript strings is 32K, so you can up the ante by changing the appropriate constants in the code. Which is all you need to run a Turing Machine. I'm proud of the core of the machine simulator itself, which is the paragon of simplicity (in unobfuscated form): /runmachine { % copy the input tape to the working machine tape inputtape machinetape copy length /tapelen exch def % boot the machine (!!) startstate setstate % show the initial tape showtape { { onechar dup (overflowed machine tape) why machinetape headpos get % get next cell as an int 0 exch put cvn % put in onechar and make into a name (unknown state) why machine currstate get % get the current state (unknown symbol) why exch get exec % get and run the proc from the state showtape % show the tape halted { stop } if % halt flag set? } loop } stopped pop % we get here on an error (or completion). showwhy % tell us why. showpage % spit out the final page. } bind def