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. Now, click on the start button. The machine should have moved right for each square it came to that had a 1 and stopped at the end of the string. Try putting the left arrow in the command so it looks like: 1,1, 1,1,< Click "Install program" and then click "start". The machine should now move one space to the left and stop on the blank square. 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, write 1,1, 2,1,> in the programming box and click "Install Program" and "Start". 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 box, and then click "Start". Try a few other strings. Does the program work?

2.) Using the same alphabet can you write an adder for the positive integers? The inputs should have the structure of first addend space second addend. The inputs and outputs should look as follows:

Input	Output

1 1	11

1 11	111

11 1	111

Paste your adder in below

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.) Does you adder work for zero plus some number? How about some number plus zero?

4.) Can you fix your adder to handle zero if it can't? Paste the new adder in.