This READ ME file accompanies xTuringMachine, a program for constructing and running Turing machines. (August 1995.) David J. Eck Department of Mathematics and Computer Science Hobart and William Smith Colleges Geneva, NY 14456 email: eck@hws.edu WWW: http://hws3.hws.edu:9000/eck/index.html This file contains the following information: -- copyright information -- short advertisement for "The Most Complex Machine" -- information and instructions for xTuringMachine -- descriptions of sample Turing machines ---------------------------------------------------------------------- Copyright information: --------------------- xSortLab can be freely distributed for private, non-commercial use. (I stipulate, however, that this material should not be adopted for use in a course unless the book _The Most Complex Machine_ is also adopted.) This material can be included on inexpensive CD-ROM shareware collections. It can be made available for downloading from FTP sites and on-line services, provided that no charge is made beyond such basic charges as connect time and membership fee. About "The Most Complex Machine": -------------------------------- I wrote xTuringMachine, and several others, for use with my introductory computer science textbook: _The Most Complex Machine: A Survey of Computers and Computing_ (AK Peters Ltd, Wellesley, MA, ISBN number 1-56881-054-7), just published as of August 1995. You should find an order form for this book in the folder containing the program (just in case you are interested). You can find information about the book and other programs on the World Wide Web at this URL: http://math.hws.edu/TMCM.html or by anonymous FTP or gopher to: math.hws.edu in the directory /pub/TMCM. About xTuringMachine: -------------------- I will not try to explain the concept of Turing machines in any detail, but the basic idea is simple enough: A machine wanders along an infinite tape that is divided into squares. Each square is either blank or contains a single symbol. The Turing machine can read, write, and erase symbols. In xTuringMachine, the possible symbols are i, o, x, y, z, and $. The symbol "#" is often used to represent a blank space. The Turing machine has a "state" which is simply a number. In xTuringMachine, the state is a number between 0 and 19. A Turing machine can also be in a special state called the "halt state", which is indicated in xTuring Machine by "h". The Turing machine has a "program", which is just a set of rules. Each rule takes the form: "If you are in such-and-such a state and if you read such-and-such a symbol, then write such-and-such a symbol, move one square in such-and-such a direction, and change to such-and-such a state." Thus each rule is determined by 5 pieces of information: Current state, current symbol, symbol to write, direction to move, and new state. When you run xTuringMachine, you will see a table with 5 columns. Each row of this table represents one of the rules of the Turing machine. You "program" the machine by constructing this table. To "run" a Turing machine, it is started in state number 0 on a tape containing some "input data". It then "computes" by following its rules until it enters the halt state. At that point, it stops running, and the contents of the tape represent the "output" of the computation. Although Turing machines are very simple, they can perform any computation that can be performed by any computer (given enough time--and more states than you are allowed to use in xTuringMachine). This is hard to believe at first, but some of the sample machines perform reasonable non-trivial computations. I suggest that you begin by running some of the sample machines that I've included in the folder named "Sample Machines". In the window that you will see when the program starts up, the machine and its tape are shown at the top. The machine displays its current state, which starts out as 0. The machine's rule table is shown at the bottom left of the window. Between the rule table and the tape are some buttons. You can control the machine with the RUN and STEP buttons. The STEP button makes the machine execute a single step of its program. (When the machine enters its halt state, the STEP button changes to a RESET button. Pressing the RESET button will reset the state of the machine to zero so that it can begin a new computatin.) When you press the RUN button, the machine will run automatically until it enters its halt state. (It is, of course, possible that it will just run forever.) While the machine is running, the RUN button becomes a STOP button. The functions of the RUN and STEP buttons are duplicated by the RUN, STOP and STEP commands in the CONTROL menu. The speed at which a machine runs is controlled by the SPEED menu. At the "Fastest" speed, most of the machine disappears so that it can run as quickly as possible. The easiest way to set the contents of the machine's tape is with the TYPE IN TAPE command in the CONTROL menu. It should be evident what to do when you enter the command. The CLEAR button or the CLEAR TAPE command will erase everthing on the tape. You can use the mouse to change the tape contents or the state of the machine. Use the mouse to point to one of the squares or to the "display screen" of the machine. The cursor will change to a pencil. Then, when you press the mouse, you will get a pop-up menu from which you can select the new value that you want. (You can only change the state of the machine while it is not running.) You can also use the pencil cursor to edit the rules in rule table. Only the values in the three rightmost columns can be changed. If you move the mouse to the area above the tape, but not directly over the machine's display screen, it will become a hand. You can use this hand cursor to drag the machine ALONG WITH ITS TAPE. If you just want to move the machine, without dragging the tape along, hold down the option key while you point at the machine. Then, when you drag the machine, it will move along the tape. The hardest thing to explain about xTuringMachine is how to construct rules tables. You are not allowed to simply type in new rules. Instead, you have to use the MAKE button to create a new rule, and then edit the rule to produce the effect you want. The MAKE button is just above the rule table, on the left. (Sometimes, the name of the MAKE button changes to GOTO.) Next to the MAKE button, you'll see a state number and a symbol. You can edit the state number and the symbol with the pencil cursor. Clicking on the MAKE button, or pressing return, will add a rule to the table. The first two entries in that rule--the Current state and the Current symbol--will be the values that were next to the Make button. The other three entries in the rule will be default values: the symbol to Write will be the same as the Current symbol; the direction to move will be R (for "right"); and the New state will be the same as the Current state. The new rule will be "hilited" by drawing a red box around it. If the rule already exists in table, the MAKE button will be a GOTO button instead. Pressing the GOTO button will simply hilite the rule. (As you use the STEP button, you'll notice that after you press it, the next rule to be applied will be hilited, if it exists in the table. If it does not exist, then the state/symbol next to the MAKE button will be hilited instead.) It is possible to use the keyboard to construct and edit the rule table. The up and down arrow keys can be used to move the hiliting box form one rule to another. The tab key will move the hiliting between the rule table and the state/symbol next to the MAKE button. You can change the hilited values by typing new values on the keyboad. To change the symbol, type i, o, x, y, z, $, #, or space bar. To change the state number, type a number or type h for the halt state. To change the direction of motion, type r or l for right or left. You can also move the hiliting box by clicking the mouse (except when the cursor is a pencil). You can use the mouse to drag a rule up or down in the table. (As you move the mouse, you will see a moving box that is sometimes dotted and sometimes dark. It is dark when the mouse it at a legal position for the rule; if you release the mouse when the box is dotted, nothing will happen.) The CONTROL menu has a DELETE RULE command for deleting the hilited rule. The EDIT menu is non-functional. Any menu commands I have not mentioned should be self-evident. Sample Machines: --------------- The following sample Turing Machines are included in the folder named "Sample Machines": 1. "Add 1" -- If the tape contains a sequence of o's and i's, representing a binary number, and if the Turing Machine is started on the right end of that sequence, it will add one to the binary number and then halt on the same square where it started. If you run the machine again, it will add one again, and so forth. This is a very simple machine, but it shows how a very simple computation, meaningless in itself, can be interpreted as having an interesting and useful meaning. If you change the halt state in the fourth line of the rule table to a zero, the machine will go into a loop in which it "counts" by adding one over and over, forever. It is especially interesting to watch this counting machine run at the highest possible speed (Speed number 1, "Fastest", in the "Speed" menu.) 2. "Kill x's" -- If the tape contains a sequence of x's, y's, z's, i's, and o's and if the machine is started anywhere on this sequence, it will remove all the x's from the sequence. To do this, it first moves to the right end of the sequence and switches to state 1. In state 1, it moves left, searching for x's. When it finds one, it erases it and moves all the letters to the right one space over to fill up the space left by erasing the x. 3. "Copy x's, y's, and z's" -- If the tape contains a sequence of x's, y's and z's, and if the machine is started at the left end of the sequence, it will make a copy of the sequence to the right of the original copy, and it will halt on the left end of the copy. States 1 - 4 copy an x, states 5 - 8 copy a y, and states 9 - 12 copy a z. State 0 detects the next character to be copied and switches to the appropriate state (1, 5, or 9) depending on what character it finds. If state 0 detects a blank, the copying is done and the machine moves to the right and halts. (If you change the halt state in the first rule of the table to a zero, the machine will run forever, making copy after copy of the original sequence.) 4. "Sort x's, y's and z's" -- If the tape contains a sequence of x's, y's and z's, and if the machine is started at the left end of the sequence, it will sort the sequence so that all the x's come before all the y's which come before all the z's, and it will halt at the right end of the sorted sequence. (What sorting means here is just that a final sequence is computed that contains the same number of x's as the original, the same number of y's, and the same number of z's, in the correct order.) The machine moves from left to right through the string. If it finds an x, it skips over it. If it finds a y, it tries to "swap" it with an x further to the right in the sequence. (To do this, it replaces the y with a $ and searches to the right for an x; if it finds an x, it replaces it with a y, goes back to the $, and replaces it with an x; if it doesn't find an x, it goes back to the $ and replaces it with a y.) If the machine finds a z, it swaps it with the x or the y that is closest to the right end of the string. (One complication: if it picks up a y to swap with the z and if it finds an x on the way back to the $, it drops the y and picks up the x instead, because it would not make sense to move a y to the left of an x.) At the end of all this, all the x's have been moved to the left and all the z's have been moved to the right. 5. "Binary addition" -- If the tape contains two binary numbers, separated by a single space, and if the Turing machine is started on the rightmost digit of the number on the right, then it will compute the binary sum of the two numbers and will halt on the rightmost digit of the answer. (Remember that binary nubmers are written with i's and o's in xTuringMachine, not with 0's and 1's.) For example, if the tape contains iioi ioi, representing 13 and 5 in binary, then the machine will halt with iooio on its tape, representing 18 in binary. The machine does addition the same way a person would, adding the numbers "column by column," from right to left. (You would only see "columns" if you wrote the numbers on a paper, one above the other.) The machine keeps track of what column it is currently working on by writing x's and y's instead of o's and i's in the columns it has already processed. 6. "Binary Multiplication" -- If the tape contains two binary numbers, separated by a single space, and if the Turing machine is started on the rightmost digit of the number on the right, then it will compute the binary PRODUCT of the two numbers and will halt on the rightmost digit of the answer. The machine repeatedly subtracts 1 from the number on the right and adds the number on the left to itself until the number on the right becomes zero. (The first time it adds the number on the left to itself, it effective just copies it.) When it is done, the original numbers are erased and the result is the product of the two input numbers. 7. "3N+1 sequence" -- This machine must be started on a tape that contains a sequence of x's, with a $ on the square to the left of that sequence. The Turing machine must be started on the square containing the $. The computation performed by this machine is as follows: (1) If the number of x's is even, it will erase half the x's, effectively dividing the number of x's by two; if the number of x's is odd, it will multiply the number of x's by three and add one more x. (2) It will then move to the left of the $ and add 1 to a binary number there. (The first time, it simply writes a 1, the second time, it changes this to 10, the third time to 11, etc.) (3) Then it checks whether there is just one x to the right of the $. If so, the machine halts. Otherwise, it returns to (1) and repeats the process. If this machine is started with N x's, it will compute the "3N+1 sequence" starting with N and will count the number of steps in that sequence. It halts with the number of steps written in binary to the left of the $. The 3N+1 sequence for N is computed just as indicated above: If N is even, it is replaced by N divided by 2; if N is odd, it is replaced by 3 times N plus 1. The process stops when--and if--N becomes equal to 1. For example, the 3N+1 sequence starting with N=3 is: 3 10 5 16 8 4 2 1. This sequence is interesting to mathematicians since no one knows whether or not it is the case that the sequence will terminate for EVERY possible value of N (even though it does terminate for every value that has ever been tested).