Lab

The basic rules for writing a Turing machine program are as follows:

Each command you make to the Turing machine must have two command pairs each of which has two elements: First it must have a state number. Second, it must have a tape space description. For example, 1,1, says in state one on top of a one. 2,1, says in state two on top of a one.

Each line contains two instruction pairs, the first is the antecedent of a conditional, the second is the consequent. In other words, each line says If____ is true, then____. For example, the line 1,1 1,1,> says if you are in state one on top of a one, then go to state one on top of a one and move one to the right. Try writing this in the Programming box and click on the Install Program button.  Note: There is currently a bug in the applet so that to enter new programs you must first select a program from the pull-down bar next to the Load New Program button, click on the Install Program button.  Now you can enter your program and hit the install button.

Enter some 1s in the Initial Characters on Tape window and click the start button. The 1s will appear on the tape as the machine starts.  These 1s were your input.  The machine should have moved right for each square it came to that had a 1 and stopped at the end of the string.  What is written in the tape when the machine stops is the output.  Commands that keep the machine in the same state are called recursive commands. The machine will do them over and over again until the conditions (in this case being over a 1) change.

Now, move the Initial Tape Position to the right until the number next to it says 10.  Try putting the left arrow in the command so it looks like: 1,1 1,1,< Click Install Program, enter some 1s in the Initial Characters on Tape window and click the start button. The machine should now move one space to the left and stop on the blank square.

Now, write 1,1 2,1,> in the programming box and click Install Program, enter some 1s in the Initial Characters on Tape window and click the start button. Looking at the message box, what did the machine do? This command says, if you are in state one on top of a one go to state 2 on top of a one and go right once. Commands that include a state change, like 1,1 2,1,>, tell the machine to execute the command only once.

Play around with the commands for a while until you feel comfortable with how they work.

1.) Here is a successor function calculator:

1,1, 1,1,>

1,_ 2,1,<

2,1, 2,1,<

It works for the following "alphabet" for natural numbers:

_ = 0

1 = 1

11 = 2

111 = 3

1111 = 4

11111 = 5

and so on

Paste the program in the Program Box, Click Install Program, write several strokes in the Initial Characters on Tape window, and then click Start. Try a few other strings. Does the program work?

2.) Using the same alphabet (as above) can you write an adder for the positive integers {1,2,3,4,...}? The inputs should have the structure of first addend (number to be added), then a space, then the second addend (number to be added). The inputs and outputs should look as follows:

Input  (What you write in the Initial Characters on Tape window)	Translation	Output (What is written on the tape when the machine stops)
11  11	2 + 2	1111
111  111	3 + 3	111111
11  111	2 + 3	11111
1  1111	1 + 4	11111

Your machine should start at the beginning of the input string and stop at the beginning of the output string.

Paste your adder (what you have in the program box) below or write it in:

Hint: Don't approach the problem as adding per say. Approach the problem as getting from the input to a string without a blank in it.

3.) Test your answer on the above inputs.  Does it work?

4.) Does you adder work for zero (a blank)  plus some number? How about some number plus zero?




5.) If your adder can't handle zeros, can you fix it? Paste the new adder in.