Troubleshooting X+y Turing Machine Example

[wheezyg]

I am working out of Cutlands computability book and I am having trouble understanding the following example:

"The function x+y is Turing-computable." Then the example lists the following specifications:
q_1 1 B q_1
q_1 B R q_2
q_2 1 B q_3
q_2 B R q_2


I wanted to verify this worked for, say, x=2 and y=1. I should end up with three. I started by writing out the tape the machine should begin with (blank marked by B):
...| 1 | 1 | B | 1 | B | ...

The first problem I am having is not understanding where I should start and what state it the start should be. When I start with the following square (marked with * to the right of the number in the square) at state q_1, I get the following:

Start ...| 1* | 1 | B | 1 | B | ...
End ...| B | B | B | 1 | B | ...

Which cannot be correct since I am attempting to add 2&1 not subtract 1 from 2. Can someone please point out what I am doing wrong?

Thank you!

 

[Mark44]

No help for your question, but for future reference, the word is Turing, after Alan Turing, a British mathematician who was on the team during WW II that decrypted the messages encoded by the German Enigma machine.

 

[Hurkyl]

"The function x+y is Turing-computable." Then the example lists the following specifications:
q_1 1 B q_1
q_1 B R q_2
q_2 1 B q_3
q_2 B R q_2

What does a row of this table actually mean?

 

[wheezyg]

They are just the quadruples that give the specification for the machine.

These can be of the form q_i s_j s_k q_l where the action is specified for the Turing machine in state q_i containing the symbol s_j. If s_k is another symbol, we replace s_j with s_k, if s_k = L (or R) we move one square to the left (or right). The final q_l tells us that we now change the state of q_i to q_l.

So q_2 1 B q_3 (row three) tells me to change the value of 1 in the square of state q_2 to B (blank) then change its state to q_3.

I am stuck on the example since I don't know if I am starting in the correct square in e correct state.

 

[Hurkyl]

Are you sure the turing machine wasn't supposed to be:

q1 1 B q1
q1 B R q2
q2 B 1 q3
q2 1 R q2