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
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces