• Support PF! Buy your school textbooks, materials and every day products Here!

X+y Turing machine

  • Thread starter wheezyg
  • Start date
  • #1
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!
 
Last edited by a moderator:

Answers and Replies

  • #2
33,513
5,195
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.
 
  • #3
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
"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?
 
  • #4
5
0
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.
 
Last edited:
  • #5
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Are you sure the turing machine wasn't supposed to be:
Code:
q1 1 B q1
q1 B R q2
q2 B 1 q3
q2 1 R q2
 

Related Threads on X+y Turing machine

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
9
Views
2K
Replies
0
Views
861
  • Last Post
Replies
0
Views
812
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
690
  • Last Post
Replies
5
Views
1K
Top