(b) f N N
N
: × → such that


f a b
a b
( , )
/
=
(c) f N
N
: → such that


f n
n
( )
log
=
2
.
7. Define Nondeterministic Turing machines to accept the following
languages.
(a) { |
{ , } }
*
xx x ∈ 01
(b) { |
{ , }
}
*
x x
x x
R
∈
=
01 and
8. Define a multiheaded Turing machine, a model in which each tape can
have k tape heads. Prove that a Deterministic Turing Machine (DTM)
with one work tape can simulate a two-headed Turing machine.
9. Design a Turing machine which computes the function
f n n
n n
( , ) min( , )
1
2
1
2
=
for all non-negative integers n 1 and n 2 .
10. Design a Turing machine which computes the function f n
( ) = 3 if n ≥ 5
and f n
( ) = 0 if n =0, 1, 2, 3 or 4.
11. Construct a Turing machine which computes the function f (n) = n mod
5.
12. Design a Turing machine which recognizes the set {
|
}
0 1 2
0
n n n n ≥ .
13. Design a TM that recognizes the set of all bit strings that contain an even
number of 1
s
.
14. Construct a TM that recognizes the set of all bit strings which end with a
0.
15. Design a Turing machine with tape symbols 0, 1 and B that given a bit
string as input, replaces all but the leftmost 1 on the tape with 0s and
does not change any of the other symbols on the tape.
16. Design a TM with tape symbols 0, 1 and B that replaces the first 0 with a
1 and does not change any of the other symbols on the tape.
17. Design a TM that recognizes the set
{
|
}.
0 1
0
2n n n ≥
18. Show that the recursiveness problem of Type-0 grammars is unsolvable.
19. Show that the problem of determining whether or not a TM over {0,1}
will print ever the symbol 1, with a given tape configuration is
unsolvable.
20. Show that there exists a TM for which the halting problem is
unsolvable.
SHORT QUESTIONS AND ANSWERS
1. What is a Turing machine?
A finite-state machine with storage is called a Turing machine.
2. What is the analogy between a Turing machine and a Push Down
206
Theory of Automata, Formal Languages and Computation