780
Modeling Arithmetic, Computation, and Languages
4. Find a Turing machine that recognizes the set of all strings of 0s and 1s containing at least one 1.
5. Find a Turing machine that recognizes 0*10*1.
6. Find a Turing machine to accept the set of nonempty strings of well-balanced parentheses. (Note that
(( )(( ))) is well balanced and (( )(( )) is not.)
7. Find a Turing machine that recognizes 50
2n
1
n
2
2n
0 n ≥ 06.
8. Find a Turing machine that recognizes 5w * w
R
0 w [ 50, 16* and w
R
is the reverse of the string w}.
9. Find a Turing machine that recognizes 5w 1 * w 2 0 w 1 , w 2 [ 50, 16* and w 1 ≠ w 2 6.
10. Find a Turing machine that recognizes the set of palindromes on {0, 1}*, that is, the set of all strings in
{0, 1}* that read the same forward and backward, such as 101.
11. Find a bit-inverter Turing machine that replaces every 0 in a string of 0s and 1s with a 1 and every 1 with a 0.
12. Find a Turing machine that changes a unary string to a string of the same length with alternating 1s and 0s.
13. Find a nonhalting Turing machine that begins with a single 1 on its tape and successively generates strings
of the form 0
n
10
n
, n ≥ 1, that is, such strings appear every so often on the tape.
14. Find a Turing machine that, given an initial tape containing a (possibly empty) string of 1s, adds a single
0 to the left end of the string if the number of 1s is even and adds two 0s to the left end of the string if the
number of 1s is odd.
15. Find a Turing machine that converts a string of 0s and 1s representing a nonzero binary number into a
string of that number of 1s. As an example, the machine should, when started on a tape containing
b
...
1 0 0 b ...
halt on a tape containing
b
...
1 1 1 1 b ...
16. Find a Turing machine that, given an initial tape containing a nonempty string of 1s, marks the right end
of the string with a * and puts a copy of the string to the right of the * . As an example, the machine should,
when started on a tape containing
b
...
1 1 1 b ...
halt on a tape containing
b
...
1 1 1
1 1 1
*
b ...
17. What number-theoretic function of three variables is computed by the following Turing machine?
(0, 1, b, 0, R)
(0, * , b, 1, R)
(1, 1, 1, 2, R)
(2, * , * , 3, R)
(3, 1, 1, 2, L)
(2, 1, 1, 4, R)
(4, 1, 1, 4, R)
(4, * , 1, 5, R)
(5, 1, b, 5, R)
(5, b, b, 6, R)
Modeling Arithmetic, Computation, and Languages
4. Find a Turing machine that recognizes the set of all strings of 0s and 1s containing at least one 1.
5. Find a Turing machine that recognizes 0*10*1.
6. Find a Turing machine to accept the set of nonempty strings of well-balanced parentheses. (Note that
(( )(( ))) is well balanced and (( )(( )) is not.)
7. Find a Turing machine that recognizes 50
2n
1
n
2
2n
0 n ≥ 06.
8. Find a Turing machine that recognizes 5w * w
R
0 w [ 50, 16* and w
R
is the reverse of the string w}.
9. Find a Turing machine that recognizes 5w 1 * w 2 0 w 1 , w 2 [ 50, 16* and w 1 ≠ w 2 6.
10. Find a Turing machine that recognizes the set of palindromes on {0, 1}*, that is, the set of all strings in
{0, 1}* that read the same forward and backward, such as 101.
11. Find a bit-inverter Turing machine that replaces every 0 in a string of 0s and 1s with a 1 and every 1 with a 0.
12. Find a Turing machine that changes a unary string to a string of the same length with alternating 1s and 0s.
13. Find a nonhalting Turing machine that begins with a single 1 on its tape and successively generates strings
of the form 0
n
10
n
, n ≥ 1, that is, such strings appear every so often on the tape.
14. Find a Turing machine that, given an initial tape containing a (possibly empty) string of 1s, adds a single
0 to the left end of the string if the number of 1s is even and adds two 0s to the left end of the string if the
number of 1s is odd.
15. Find a Turing machine that converts a string of 0s and 1s representing a nonzero binary number into a
string of that number of 1s. As an example, the machine should, when started on a tape containing
b
...
1 0 0 b ...
halt on a tape containing
b
...
1 1 1 1 b ...
16. Find a Turing machine that, given an initial tape containing a nonempty string of 1s, marks the right end
of the string with a * and puts a copy of the string to the right of the * . As an example, the machine should,
when started on a tape containing
b
...
1 1 1 b ...
halt on a tape containing
b
...
1 1 1
1 1 1
*
b ...
17. What number-theoretic function of three variables is computed by the following Turing machine?
(0, 1, b, 0, R)
(0, * , b, 1, R)
(1, 1, 1, 2, R)
(2, * , * , 3, R)
(3, 1, 1, 2, L)
(2, 1, 1, 4, R)
(4, 1, 1, 4, R)
(4, * , 1, 5, R)
(5, 1, b, 5, R)
(5, b, b, 6, R)