L= {ww: w ∈{a,b} + }.
9. Construct a Turing machine to compute the function
f (w)= w R ,
where w ∈ {0,1} + .
10. Design a Turing machine that finds the middle of a string of even length.
Specifically, if w = a 1 a 2 …a n a n+1 …a 2n , with a i ∈ Σ, the Turing machine
should produce
, where c ∈ Γ – Σ
11. Design Turing machines to compute the following functions for x and y
positive integers represented in unary.
12. Design a Turing machine with Γ = {0,1, } that, when started on any cell
containing a blank or a 1, will halt if and only if its tape has a 0 somewhere
on it.
13. Write out a complete solution for Example 9.8.
14. Give the sequence of instantaneous descriptions that the Turing machine in
Example 9.10 goes through when presented with the input 111. What
happens when this machine is started with 110 on its tape?
15. Give convincing arguments that the Turing machine in Example 9.10 does
in fact carry out the indicated computation.
16. Complete all the details in Example 9.11.
9. Construct a Turing machine to compute the function
f (w)= w R ,
where w ∈ {0,1} + .
10. Design a Turing machine that finds the middle of a string of even length.
Specifically, if w = a 1 a 2 …a n a n+1 …a 2n , with a i ∈ Σ, the Turing machine
should produce
, where c ∈ Γ – Σ
11. Design Turing machines to compute the following functions for x and y
positive integers represented in unary.
12. Design a Turing machine with Γ = {0,1, } that, when started on any cell
containing a blank or a 1, will halt if and only if its tape has a 0 somewhere
on it.
13. Write out a complete solution for Example 9.8.
14. Give the sequence of instantaneous descriptions that the Turing machine in
Example 9.10 goes through when presented with the input 111. What
happens when this machine is started with 110 on its tape?
15. Give convincing arguments that the Turing machine in Example 9.10 does
in fact carry out the indicated computation.
16. Complete all the details in Example 9.11.