Section 9.4 Turing Machines
781
18. What number-theoretic function of one variable is computed by the following Turing machine?
(0, 1, 1, 1, R)
(1, b, b, 9, R)
(1, 1, 1, 2, R)
(2, b, b, 3, L)
(3, 1, b, 9, L)
(2, 1, 1, 4, R)
(4, b, b, 5, L)
(5, 1, b, 3, L)
(4, 1, 1, 6, L)
(6, 1, 1, 6, L)
(6, b, 1, 7, L)
(7, b, 1, 8, L)
(8, b, 1, 9, L)
19. Find a Turing machine to compute the function
f (n) = b
1 if n = 0
2 if n ∙ 0
20. Find a Turing machine to compute the function
f (n) = b
n
if n is even
n + 1 if n is odd
21. Find a Turing machine to compute the function
f (n) = 2n
22. Find a Turing machine to compute the function
f (n) = b
n∙3
if 3 divides n
undefined otherwise
23. Find a Turing machine to compute the function
f (n 1 , n 2 ) = n 1 + n 2
24. Find a Turing machine to compute the function
f (n 1 , n 2 ) = b
n 1 if n 1 is even
n 2 if n 1 is odd
25. Find a Turing machine to compute the function
f (n 1 , n 2 ) = b
n 1 − n 2 if n 1 ≥ n 2
0
otherwise