A function index is “Turing computable” if there exists a Turing machine
that can perform the above task.
Ì Exam ple 4.1.1: Design a Turing machine that accepts the set of all even
palindromes over {0,1}.
Solu tion
There are various steps involved in processing even length palindromes. The
TM scans the first symbol of input tape (0 or 1), erases it and changes state (q 1 ,
or q 2 ). TM scans the remaining part without changing the tape symbol until it
encounters b. The read/write head moves to the left. If the rightmost symbol
tallies with the leftmost symbol (which can be erased but remembered), the
rightmost symbol is erased. Otherwise TM halts. The read/write head moves to
the left until b is encountered. The above steps are repeated after changing the
states suitably. The transition table is as shown below.
Pres ent
State
Input Sym bol
0
1
b
→ q 0
bRq 1
bRq 2
bRq 7
q 1
0Rq 1
1Rq 1
bLq 3
q 2
0Rq 1
1Rq 2
bLq 4
q 3
bLq 5
q 4
bLq 6
q 5
0Lq 5
1Lq 5
bRq 0
q 6
0Lq 6
1Lq 6
bRq 0
q 7
Ì Exam ple 4.1.2: Given Σ = { , }
01 , design a Turing machine that accepts
the language denoted by the regular expression 00
* .
Solu tion
Let us start at the left end of the input, we read each symbol and check that it is
a 0. If it is, then we continue by moving right. If a blank is reached without
seeing anything else other than 0, we terminate and accept the string.
If the input contains a 1 anywhere, the string is not in L(00
* ), and so we
halt in a nonfinal state. In order to keep track of computation, two internal
states Q q q
= { , }
0
1 and the final state F
q
= { }
1 are enough.
190
Theory of Automata, Formal Languages and Computation