A Turing Machine (Or Deterministic Turing Machine, DTM) Is a 6-Tuple M = (Q, , , , Q0

Models of Computation

Turing Machines

A Turing machine (or deterministic Turing machine, DTM) is a 6-tuple M = (Q, , , , q0, F), where

1)Q is a finite alphabet (the set of states),

2) is a finite alphabet (the set of input symbols),

3) is a finite alphabet (the set of allowable tape symbols) which contains a special symbol B, the blank symbol,

4): QQ{L,N,R} is a partial function (the transition function),

5)q0 is a specified element of Q (the initial state), and

6)F is a subset of Q (the set of accepting states).

……BBBBB x a y BBBBB……

Read-Write Head

Finite Control

If : Q2Q{L,N,R}, then M is said to be nondeterministic (NTM). As in finite automata and pushdown automata, DTM is a special case of NTM in which |(p,a)|1 for each pQ and a, and we write (p,a)=(q,b,d) instead of (p,a)={(q,b,d)}. In what follows we shall consider NTMs in general.

An ID (instantaneous description) of M is an element of *Q*. An ID xpy means that M is currently in state pQ, and xy* is the current contents on the tape up to the rightmost nonblank symbol or the symbol to the left of the head, whichever is rightmost (Note that the blank B may occur in xy).

The initial ID for input x* is q0x. An accepting ID is an ID of the form xfy for some fＦ and xy*.

Moves in M (a binary relation ├M , or simply ├ ,on IDs)

For p,qQ, a,b,c, x,y*, we write

i)xcpay ├ xqcby if (p,a) contains (p,b,L),

ii) xpay ├ xqby if (p,a) contains (p,b,N), and

iii) xpay ├ xbqy if (p,a) contains (p,b,R).

├* is the reflexive transitive closure of ├.

A sequence of ID’s 1, 2, …, n is called a computation (on x) by M if i├i+1 for each i (and 1=q0x).

The language accepted by M (M is regarded as an acceptor)

L(M) = {x* | q0x ├* yfz, fF, yz*}

M can be regarded as a transducer also:

M(x)={yz* | q0x ├* yfz, fF}

M(L)=xLM(x)

Examples and Exercises

1. A DTM M=(Q,,,,q0,Z0,F) accepting D1

M uses a segment of its tape as a pushdown stack (Cf. the PDA M in Example 1 on p.2, Handout #008). Indeed, at any moment M’s tape contents are of the form BZ0Bky for some k, where  represents the current contents of the stack with the rightmost symbol of  being the top, and y is the remaining (i.e., not yet scanned) portion of the input:

Q={q0,q1,r,f,goleft[,goleft],goleft$,push,goright,goleft}, ={[,]}, ={B,Z0,$}, and F={f}.

(q0,B)=(f,B,N) … If input is , M accepts it immediately.

(q0,])=(r,B,N) … If the leftmost symbol of input is ], M rejects the input, i.e., M enters state r, and halts (no more move is defined for state r).

(q0,[)=(goleft,[,L), (goleft,B)=(goright,Z0,R), (goright,[)=(goright,[,R), (goright,])=(goright,],R), (goright,B)=(goleft,$,L), (goleft,[)=(goleft,[,L), (goleft,])=(goleft,],L), (goleft,Z0)=(q1,Z0,R) … If the leftmost symbol of the input is [, M creats the stack bottom symbol, Z0, on the immediate left of the leftmost input symbol, and at the same time creates the endmarker $ on the immediate right of the rightmost input symbol. After that, M begins checking the input when it enters q1 with its read-write head on the leftmost symbol of the input.

(q1,[)=(goleft[,B,L), (goleft[,B)=(goleft[,B,L), (goleft[,[)=(push,[,R), (goleft[,Z0)=(push,Z0,R), (push,B)=(q1,[,R), (q1,B)=(q1,B,R) … If the leftmost symbol of the remaining input is [, M pushes it in the stack.

(q1,])=(goleft],B,L), (goleft],B)=(goleft],B,L), (goleft],[)=(q1,B,R), (goleft],Z0)=(r,B,N) … If the leftmost symbol of the remaining input is ], M pops up the top symbol of the stack if any. If the stack is empty, M rejects the input (Too many ]’s).

(q1,$)=(goleft$,B,L), (goleft$,B)=(goleft$,B,L), (goleft$,Z0)=(f,B,N), (goleft$,[)=(r,B,N) … When M reaches the end of input, M checks if the stack is empty. If it is, M accepts the input; otherwise M rejects (Too many [‘s).

q0[1[2]3[4[5]6]7]8├goleftB[1[2]3[4[5]6]7]8├Z0goright[1[2]3[4[5]6]7]8

├Z0[1goright[2]3[4[5]6]7]8├Z0[1[2goright]3[4[5]6]7]8├* Z0[1[2]3[4[5]6]7]8gorightB

├Z0[1[2]3[4[5]6]7goleft]8$├*Z0goleft[1[2]3[4[5]6]7]8$├goleftZ0[1[2]3[4[5]6]7]8$

├Z0q1[1[2]3[4[5]6]7]8$├*goleft[Z0B[2]3[4[5]6]7]8$├Z0pushB[2]3[4[5]6]7]8$

├Z0[q1[2]3[4[5]6]7]8$├ Z0goleft[[B]3[4[5]6]7]8$├ Z0[pushB]3[4[5]6]7]8$

├ Z0[[q1]3[4[5]6]7]8$├ Z0[goleft][B[4[5]6]7]8$├ Z0[Bq1B[4[5]6]7]8$├ Z0[BBq1[4[5]6]7]8$

├ Z0[Bgoleft[BB[5]6]7]8$├* Z0goleft[[BBB[5]6]7]8$├* Z0[pushBBB[5]6]7]8$

├*Z0[[q1BB[5]6]7]8$├* Z0[BBBBBBq1]8$ ├Z0[BBBBBgoleft]BB$

├* Z0goleft][BBBBBBB$ ├Z0Bq1BBBBBBB$ ├*Z0BBBBBBBBq1$

├ Z0BBBBBBBgoleft$BB (=Z0BBBBBBBgoleft$)├* goleft$Z0BBBBBBBBB

(=goleft$Z0)├fBBBBBBBBB (=f)

2. A DTM M for {anbn | n0}

At each step of M’s computations, the contents of M’s tape will be of the form #kaik#kbjk when the input is aibj. Initially k=0.

(q0,a)=(qa,#,R), (qa,a)=(qa,a,R), (qa,#)=(qa,#,R) … M rewrites the leftmost a on the tape with #, and moves its head to the right to seek the leftmost b on the tape.

(qa,b)=(qb,#,L), (qb,#)=(qb,#,L), (qb,a)=(qb,a,L) … If the desired b is found, M rewrites it with #, and moves its head to the left as far as either # or a is encountered.

(qa,B)=(r,B,N) … If no b is found eventually, M rejects the input, say x, because #a(x)>#b(x) in this case.

(qb,B)=(q0,B,R) … This means that M has just reached the leftmost nonblank square on the tape.

(q0,#)=(qno-a,#,R), (qno-a,#)=(qno-a,#,R), (qno-a,B)=(f,B,N), (qno-a,b)=(r,B,N) … In case there is no a, M begins to check whether there is no b left, either. If so, M enters f to accept the input; otherwise M enters r to reject the input, because #a(x)<#b(x) in this case.

(q0,B)=(f,B,N) … In case input is , M accepts it immediately.

M=({f,r,q0,qa,qb,qno-a}, {a,b}, {a,b,#,B}, , q0, {f}).

3. An NTM for XX={xx | x in {a,b}*}

In what follows, c and d represent arbitrary symbol from {a, b}.

(q0,c)={(q0,c,R), (qc,#,L)} … As far as M guesses that its head is still left of the midpoint of input xx, M chooses transition (q0,c,R)(q0,c), whereas M chooses transition (qc,c,R)(q0,c) just when it guesses that it has just reached the center of xx.

(qc,d)={(qc,d,L)} … After having marked the tape symbol, c, which M guessed to be the center of input, M moves its head to the left till it reaches the left end of the input, memorizing the symbol c as its state.

(qc,B)={(checkc,B,R)}, (qc,#)={(checkc,#,R)}, (checkc,c)={(q1,#,R)}, (checkc,e)={(r,e,N)} if ec … At each intermediate step of the computation, M’s tape contents are of the form B#ku#kvB or of the form B#ku#k#vB where two #ks represent that those two parts (of input) have already been chcked to be equal (Initially k=0). M checks whether or not the leftmost symbol of u is c. If so, M continues the computation; otherwise M rejects the input.

(q1,#)={(qno-u,#,R)}, (q1,c)={(q1,d,R)}, (q1,#)={(q2,#,R)}, (q2,#)={(q2,#,R)}, (q2,c)={(q’c,#,L)}, (q’c,#)={(q’c,#,L)}, (q’c,d)={(qc,d,L)}, (qc,d)={(qc,d,L)} … For the second and later cycles of checking equality of the leftmost symbols of u and v, M has to memorize whether or not it has already passed the two segments of the form #k.

(qno-u,#)={(qno-u,#,R)}, (qno-u,B)={(f,B,N)}, (qno-u,c)={(r,B,N)} … In case u=, M checks if v=, too. If so, M accepts the input; otherwise M rejects.

(q0,B)={(f,B,N)} … M accepts  immediately.

M=({q0,q1,q2,qno-u,qa,qb,q’a,q’b,r,f}, {a,b}, {a,b,#,B}, , q0, F).

Ex. 1) Modify M so as to accept XRX={xRx | x in {a,b}*}.

2) Modify M so that it is deterministic and accepts XcX={xcx | x in {a,b}*}.

Exercises

Give DTMs or NTMs for the following languages. Explain your idea on the TMs in English. If possible, give detailed definitions of their transition functions.

a) {anbncn | n 0} b) {am | m=n2}

c) {x in {a,b}* |#a(x)=#b(x)} d) {ap | p is prime}

Prove that for any {D,N}TMs M and N there exists a {D,N}TM that accepts L(M)L(N). Thus the class of recursively enumerable sets is closed under intersection.

Multi-tape TMs

If M=(Q, , , , q0, F) is a k-tape NTM, then  is a partial function from Qk to the subsets of Qk{L,N,R}k.

…… BBBBB xk ak yk BBBBB……

………

……BBBBB x2 c a2 y2 BBBBB……

……BBBBB x1 a1 y1 BBBBB……

q ID (p, x1a1y1, x2ca2y2, xkakyk)

If (q, b1,b2, …bk,N,L,…,R)(p, a1,a2,…ak), then M may move to

…… BBBBB xk bk yk BBBBB……

………

……BBBBB x2 c b2 y2 BBBBB……

……BBBBB x1 b1 y1 BBBBB……

p ID (p, x1b1y1, x2cb2y2, xkbkyk)
TMs = Type 0 Grammars

Recursively enumerable set

L is said to be recursively enumerable if L=L(M) for some NTM M.

Recursive set

A halting TM is a TM which halts on any input. L is said to be recursive if L=L(M) for some halting TM M.

THEOREM ℒ(k-tape DTM)=ℒ(1-tape TM), ℒ(k-tape NTM)=ℒ(1-tape NTM).

Proof.

ak M’ regards those k squares on k tapes

… as one symbol

a2 ([a1,s1], [a2,s2], …, [ak,sk]),

where si = + if the i-th tape head stays

a1 at the square; si =  otherwise.

When M makes a one-step move, M’ scans the whole nonblank section on each tape to rewrite the corresponding square. For example, if

ak a’k

… ([a1,+], [a’2,], …, [ak,+])

a’2 a2

([a’1,], [a2,+], …, [a’k,])

a1 a’1

and (q, b1,b2, …bk,R,…,L,N)(p, a1,a2,…ak), then

bk a’k

… ([b1,+], [a’2,], …, [bk,])

a’2 b2

([a’1,], [b2,], …, [a’k,])

b1 a’1

THEOREM ℒ(DTM)=ℒ(NTM).

THEOREM ℒ(halting TM)ℒ(TM). This inclusion is proper.

THEOREM ℒ(TM)=ℒ(type 0 grammar)=ℒ0.

Proof. ℒ(NTM)ℒ(type 0 grammar): Given any DTM M, construct a type 0 grammar G such that L(G)=L(M).

G has nonterminals of the forms [q,A,a] or [A,a], where qQ, A and a. [q,A,a] menas that orresponding M’s current state is q and that M is currently scanning A, whereas [q,A,a] and [A,a] are to memorize input symbol a.

Before starting to simulate M’s computation, G guesses not only input a0a1…an* but also some amount of space to be used in the computation, which is represented by nonterminal [,]:

{S[,]S | S[,] | [q0,a,a]S1, S1[a,a]S1 |  : a}P.

By those productions, G generates

[,]i[q0,a0,a0][a1,a1]…[an,an][,]j for some i,j0,

which corresponds to M’s initial ID q0a0a1…an.

Assume that at some moment G has [q,a,A] as its current intermediate string in the derivation, to which M’s ID 'qa' corresponds, where ' and ' are those strings which are obtained from  and  by extracting the first component A from each symbol [A,a] in them.

If (q,A) contains (p,B,N), then [q,a,A][p,a,B] is in P.

If (q,A) contains (p,B,R), then [q,a,A][c,C] [a,B][p,c,C] is in P, where (c,C) (){(,)}.

If (q,A) contains (p,B,L), then [c,C][q,a,A][p,c,C][a,B] is in P, where (c,C)  (){(,)}.

Finally, if M enters an accepting state, then G begins to extract input a0a1…an from nonterminals of the form [a,A]:

If fF, then {[f,a,A]a, [b,B]aba, a[b,B]ab, [,] : a,b, A,B}  P.

ℒ(NTM) ℒ(type 0 grammar): Given any type 0 grammar G, construct an NTM M such that L(M)=L(G).

#009