View Single Post
Feb7-11, 04:14 PM
P: 5
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!
Phys.Org News Partner Science news on
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts