10. How will you recognize a language in a TM?
11. How are Turing machines used as Transducers?
12. Explain what do you mean by an N-Track Turing machine?
13. Explain the following terms
(a) Semi-infinite tape
(b) Offline Turing machine
(c) Multitape Turing machine
(d) Nondeterministic “Multidimensional Turing Machine”
14. What do you mean by “Multidimensional Turing Machine”?
15. What do you mean by a binary TM?
16. State the Church-Turing Thesis.
17. State the weak form and strong form of Turing’s Thesis.
18. What do you mean by Recursively enumerable languages?
19. How will you enumerate strings in language?
20. What are non-recursively enumerable languages?
21. What do you mean by Undecidability?
22. What do you mean by the Halting problem?
23. What is an Universal Turing machine?
24. State the implications of Halting problem.
25. What do you mean by Post’s Correspondence problem?
EXERCISES
1. Design a Turing machine which recognizes the language consisting of
all strings of 0s whose length is a power of 2. i.e., it decides the language
L
n
n
=
≥
{ |
}.
0
0
2
2. Design a Turing machine which recognizes the language
L w w w
=
∈
{ # |
{ , } }.
*
01
3. Design a Turing machine which recognizes the language
L a b c i j k
i j k
i j k
=
× =
≥
{
|
, ,
}
and
1 .
4. Design a deterministic Turing machine (DTM) to accept the language
L a b c i
i i i
=
≥
{
|
}
0 .
5. Define a DTMs to accept the following languages. Specify the 5-tuple in
each. (Use multi-tape machine if necessary).
(a) { |
{ , } }
*
xx x ∈ 01
(b) { |
{ , }
}
*
x x
x x
R
∈
=
01 and
6. Design DTMs to compute the following functions. (Input number can
be in unary, i.e., n is encoded as 1
n ).
(a) Successor function: f N
N
: → where f n n
( ) = +1.
Turing Machines
205