- #1

wheezyg

- 5

- 0

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!

"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!

Last edited by a moderator: