Turing

Turing Machines Introduction Turing machines were described in 1936 by Alan Turing. It is a theoretical model that can be adapted to simulate the logic of any computer algorithm. Thus it can be considered an ideal model of a general purpose computer. But even the Turing machine cannot solve problems which are beyond the theoretical limits of computation. Turing machines can be used to prove the decidability (whether they can or cannot be done) of any problem that may or may not be related to programming. e.g. Ambiguity of a grammar. They can also be used the find whether a problem is tractable (can be solved in polynomial time) or not. Thus turing machines can be used to differentiate between intractable and undecidable problems. The class of languages accepted by Turing machines is the class of Type 0 (recursively enumerable) languages.

Definition: A Turing machine consists of a, • a finite control, • a tape • a head that can be used for reading or writing on that tape The finite control can be in any of the finite set of states. The tape is divided into cells and each cell can hold a single symbol from a finite set. The tape head is always placed over any of the tape cells and is said to scan that cell. Initially it is placed over the left cell holding the input. The tape head can read/write symbols and move around on the tape (left/right). It is similar to a finite automata but has unlimited and unrestricted memory. Thus they can manipulate infinite tapes.

Figure A

Basic working Figure A shows a Turing machine. Initially the tape will have only the input string chosen from the input alphabet and the rest of the tape is blank. Blank is a tape symbol and not a symbol from the input alphabet. The tape can also contain tape symbols other than blank or input symbols. The tape head reads the current symbol and depending upon the state of the finite control a move is carried out. When the machine need to store any information, it is written on tape and later read when needed. Once started, the computing continues and there are three possible outcomes possible accept, reject or loop. Looping

simply means that the machine won’t halt. The output is obtained when the machine enters the designated accepting and rejecting states or else it will go on forever without halting. One major problem faced in turing machine is that we cannot distinguish between looping and merely taking long time to execute. For this, turing machines are made so that they halt on all inputs. Such turing machines are called deciders because they always make a decision to accept or reject.

Defining move The move taken by the turing machine at any time is a function of the present state of finite control and the symbol scanned from the tape. When a move occurs the following may take place: • • •

Change State (sometimes retain the current state) Write a symbol on cell scanned (sometimes retain the current symbol) Move the tape head left or right (if the tape head is not required to move by the turing machine logic, it can be stationary. But a move will be formally accepted if the head moves. So a move is defined when the head moves, then previous moves are combined with the present move into a single move)

Formal Definition: A Turing machine (TM) can be formally notated similar to a finite automata or PDA. A TM can be described by a 7-tuple: M = (Q, ∑, Γ, δ, q0, B, F) where, Q: ∑: Γ : δ :

The finite set of states of the finite control The finite set of input symbols. The complete set of tape symbols. ∑ is subset of Γ. The transition function. δ(q, X) = (p, Y, D) • q is a current state which is a member of Q. • X is a tape symbol which is a member of Γ . • p is the next state which is a member of Q. • Y is a symbol in Γ replacing the previous state symbol. • D is direction in which the head moves and can be L or R (left/right) q0 : The start state of finite control which is a member on Q. B : The blank symbol which is in Γ but not in ∑. F : The set of final (accepting) states which is a subset of Q.

Conventions for Representation     

Lower case letters at the beginning of alphabet are used to represent input symbols. eg: a,b,c Lower case letters from the end of alphabet are used to represent the strings of input symbols. eg: w,x Capital letters from the end of alphabet are used for tape symbols. eg: X1, X2, B (blank) Greek alphabets are used to represent tape strings.eg: α,β Letters p, q and nearby are used for states.

Difference between finite automata and Turing machine The following list summarizes the differences between finite automata and Turing machines.

1. A Turing machine can both write on the tape and read from it. 2. The read-write head can move both to the left and to the right. 3. The tape is infinite. 4. The special states for rejecting and accepting take effect immediately.

Instantaneous Descriptions Instantaneous Descriptions (ID) like those used for PDAs can also be used to represent the current state of a turing machine. Each ID has to represents the current state of finite control and current position of head. These information can be represented together by placing the symbol representing current state to the left of the next symbol to be scanned in the tape string as shown in example. We can then call this the tapeplus-state string or ID. Since the tape of the turing machine is infinitely long, it is impossible to represent the whole tape in an ID. A representation of the whole tape in an ID will result in an infinite prefix and suffix for a state. We thus show only the portion of tape between the leftmost and rightmost non-blank. Thus a typical ID will be, X1 X2 . . . Xi-1 q Xi Xi+1 … Xn in which, 1. q is the current state of the machine 2. The head is going to scan the ith symbol from left. 3. X1 X2 … Xn is the portion between the leftmost and rightmost non-blank.

Representing moves Using Instantaneous Description A single move or group of moves can be represented as a transition from on ID to another. As usual for the machine M = (Q, ∑, Γ, δ, q0, B, F) symbol

or

are used to represent a single move and

(reflexive, transitive closure ) to represent more than one move. Consider the move from state q to state p after reading symbol Xi and the head then moves to left: δ(q, X) = (p, Y,L) It can be represented as, X1 X2 . . . Xi-1 q Xi Xi+1 … Xn

X1 X2 . . . Xi-2 p Xi-1 Y Xi+1 … Xn

Initially the tape head was positioned over Xi and now it is positioned over Xi-1 There are two exceptions to this. 1. If i=1, then the head moves to left and it will be over a blank. q X1 X2 … Xn

p B Y X2 … Xn

2. If i=n and Y=B, then the symbol B is written over Xn and Xn disappears into the infinite sequence and does not appear in the next ID. X1 X2 … Xn-1 q Xn

X1 X2 … Xn-2 p Xn-1

or

Now consider the move from state q to state p after reading symbol Xi and the head then moves to right: δ(q, X) = (p, Y,R) It can be represented as, X1 X2 . . . Xi-1 q Xi Xi+1 … Xn

X1 X2 . . . Xi-1 Y p Xi+1 … Xn

Initially the tape head was positioned over Xi and now it is positioned over Xi+1 There are two exceptions to this. 1. If i=n, then the head moves to right and it will be over a blank. X1 X2 … q Xn

p B Y X2 … Xn-1Y p B

2. If i=1 and Y=B, then the symbol B is written over X1 and X1 disappears into the infinite sequence and does not appear in the next ID. q X1 X2 … Xn

p X2 … Xn

Designing Turing machine Construct a turing machine that accept the language {0n1n | n ≥ 1} First we can start by listing down some valid and invalid input strings. The valid inputs are 01, 00001111 etc. and invalid inputs are ε, 001, 0010 etc. The basic logic is to change 0 to X and 1 to Y in an alternating fashion until all 0s and 1s are matched. The numbers of states depends upon the problem and are introduced as required. In the present problem, we require a total of 5 states q0 through q4 where q0 is the start state and q4 is the accepting state. The input alphabet is {0,1} and the tape symbols are {0,1,X,Y,B}. Thus the turing machine can be represented as M = ({q0, q1, q2, q3, q4}, {0, 1}, {0, 1, X, Y, B}, δ, q0, B, q4) And δ is given in the table below: State

Symbol 0

1

X

Y

B

q0

(q1, X, R)

-

-

(q3,Y, R)

-

q1

(q1, 0, R)

(q2, Y, L)

-

(q1, Y, R)

-

q2

(q2, 0, L)

-

(q0, X, R)

(q2, Y, L)

-

q3

-

-

-

(q3, Y, R)

(q4, B, R)

q4

-

-

-

-

-

A Turing machine to accept {0n1n | n ≥ 1} Analysing the transitions The transitions are numbered T1, T2,..., T10 for explanatory purpose. The transitions can be exercised using input strings like 0011 (valid), 0010 (Invalid) T1: δ (q0, 0) At first the machine is in state q0 and the head scans the first 0 from left. We have a 0 so rewrite it with X, change the state to q1 and move to right starting the search for a 1. T2: δ (q1, 0) Now the head may encounter a 0 but we rewrite it, and move to right and continue search for 1. T3: δ (q1, Y) The head may encounter a Y but we rewrite it, and move to right and continue search for 1. T4: δ (q1, 1) The head encounters a 1 so replace it with Y, change the state to q2 and start moving to left in search for the leftmost 0 (comes after the rightmost X). T5: δ (q2, Y) The head may encounter a Y but we rewrite it, and move to left and continue search for the leftmost 0 (comes after the rightmost X). T6: δ (q2, 0) Now the head may encounter a 0 but we rewrite it (because it may not be the leftmost 0), and move to left and continue search for the rightmost X. T7: δ (q2, X) We encounter rightmost X, so rewrite it, and move to right and change the state to q0. Now the machine is at q0, the machine may follow the path from T1 if it encounters a 0. Otherwise continue down. T8: δ (q0, Y) Instead if the machine encounters a Y, change to state q3 and move right searching for a blank B. T9: δ (q3, Y) When q3 encounter a Y, just rewrite it and move right in search for B. T10: δ (q3, B) When q3 encounters B then machine change to state q4 and the string is accepted. If M encounters any other transitions other than the above ones, then the input string is in the wrong form and M dies without accepting the string. At any time, the string on the tape can be represented using the regular expression 0*X*1*Y*. The entire sequence of moves for the input 0011 can be represented as q00011

Xq1011

X0q111

Xq20Y1

q2X0Y1

Xq00Y1

XXq1Y1

XXYq11

XXq2YY

Xq2XYY

XXq0YY

XXYq3Y

XXYYq3B

XXYYBq4B

For invalid input 0010 the moves are q00010

Xq1010

X0q110

Xq20Y0

q2X0Y0

XXq1Y0

XXYq10

Xq00Y0 XXY0q1B

Transition Diagrams for Turing machines A turing machine can be represented using a state transition diagram like a PDA. The nodes will represent the different states. An arc from state q0 to q1 will be labeled as 0/X → which represents the transition function (q0, 0) = (q1, X, R), the arrow represents the direction (right) the head moves. Another arc from q2 to q2 (self loop) will be labeled Y/Y← which represents the transition function (q2,Y)= (q2, Y, L, the arrow represents the direction (left) the head moves. The start state is represented by word “Start” and an arrow entering that state. Accepting states are represented using double circles.

0/0 → Y/Y → 0/0 ← Y/Y ← Start

q0

0/X →

Y/Y →

q3

B/B →

q1

1/Y ←

q2

X/X →

q4

Y/Y →

Transition diagram for a TM that accepts strings of the form 0n1n 

Language of a Turing Machine

A turing machine is said to accept a language if the machine reaches an accepting state when any string from that language is placed on tape and processed. Formally if M = (Q, ∑, Γ, δ, q0, B, F) is a turing machine, then L(M) which is a set of strings w is the language accepted by M if, q0w

αpβ

i.e. on providing the string w at the start state q0, it should finally reach some final state p were α, β are any tape strings. The set of languages accepted by a turing machine are called Recursively Enumerable (RE) (Type 0) languages. The RE languages are recognized by the turing machines i.e. they are Turing-recognizable. The languages decided by turing machines are called Turing-decidable (recursive) languages i.e. the machine can halt on the input to reveal the input string is accepted or rejected.

Turing machine and halting The most important question is “When does a turing machine halt?”. A turing machine always halts if it enters an accepting state. In this state, a further move is undefined. But we cannot guarantee that the machine halts if it does not enter an accepting state. And this is called the halting problem and it leads to an uncertainty in the operation of a turing machine. Turing machines that halt on all inputs regardless of acceptance can be a good model for an algorithm. If an algorithm to a problem exists, then the problem is decidable and the corresponding turing machine halts on all inputs.

Variants of Turing Machine Turing machines have several variants which have the same language recognizing power as the basic turing machine. They include versions with multi tapes and non determinism and are called variants of the turing machine model. The property of turing machine by which the variants have the same language recognizing power is called robustness. And turing machine is more robust than PDA and finite automata. A possible variant for the basic turing machine is the one which allows the head to remain stationary during a move. This feature does not add any power to the original turing machine because an ordinary turing machine can be used to simulate the same by replacing the stationary head transition by two transitions. One transition moves the head to the right and the second back to left. Thus there exists equivalence between the turing machine variants. To show that two models are equivalent we just need to simulate one by the other. 1. Multitape Turing machine The multitape turing machine has a single finite control and a finite number of tapes. Each tape has its own head for reading or writing. Each tape is divided into cells and hold symbols from the tape alphabet. As in the single-tape TM, the set of tape symbols includes a blank, and has a subset called the input symbols, of which the blank is not a member. Multitape Turing machines, like one-tape TM's, accept by entering an accepting state. Initially: 1. The input, a finite sequence of input symbols, is placed on the first tape. 2. All other cells of all the tapes hold the blank.

3. The finite control is in the initial state. 4. The head of the first tape is at the left end of the input. 5. All other tape heads are at some arbitrary cell. The transition function is changed to allow for reading, writing, and moving the heads on some or all of the tapes simultaneously. Formally, the transition function can be represented as, δ: Q x Γk → Q x Γk x {L, R, S}k The machine with k tapes and at state Q, on reading the k input symbols will reach a new state in Q, write on each tape, move the heads left, right or remain stationary. The expression below denotes a possible transition. δ (qi, a1, . . . , ak) == (qj, b1 , . . . , b k , L, R, . . . , S) The machine changes from state qi to state qj and symbols a1, . , ak of the different tapes changes to b1, ..., b k and moves left, right or remain stationary. Thus in one move, the turing machine does the following: 1. The finite control enters a new state, which could be the same as the previous state. 2. On each tape, a new tape symbol is written on the cell scanned. Any of these symbols may be the same as the symbol previously there. 3. Each of the tape heads makes a move, which can be left, right, or stationary. The heads move independently, so different heads may move in different directions, and some may not move at all. Multitape Turing machines appear to be more powerful than ordinary Turing machines, but we can show that they are equivalent in power. As we know that two machines are equivalent if they recognize the same language. Equivalence of Single tape and Multitape Turing Machine The language accepted by single tape turing machine is recursively enumerable language. And surely all multitape turing machines will accept recursively enumerable languages because a single tape turing machine is a multi tape turing machine. The equivalence is established if we can prove that single tape turing machine can accept all languages accepted by a multitape turing machine. And that is similar to proving there are no languages not recursively enumerable yet are accepted by multitape turing machine. Theorem: Every language accepted by a multitape turing machine is recursively enumerable. Proof: This proof is done by showing that a single tape turing machine can be used to simulate any multitape turing machine and hence language accepted by multitape turing machine is recursively enumerable. For this consider the representation of a multitape turing machine using a single tape turing machine (Figure B).

Figure B: Simulation of a multitape turing machine using single tape with multiple tracks Consider a multitape turing machine M with k tapes then we can construct a single tape turing machine N having 2k tracks on its tape to simulate M. Half of these tracks hold the tapes of M and the other half hold a single marker character (X) which indicates the position of each head of M. Assume k=2, then track 2 and track 4 hold the contents of the two tapes of M. Track 1 holds the position of head of first tape and track 3 holds the position of head of second tape. To simulate a move of M, the head of machine N must visit the k head markers. The machine N must keep track of the number of head markers scanned and this value must be kept in N’s finite control. When N visits each head marker, it stores the scanned symbol in the finite control. Thus after visiting the k tracks corresponding to the k tapes, machine N will know the current state of M (symbols scanned by each head of M). Thus N will know the move M will make. N will now revisit all the head markers and change the corresponding symbol in the track representing the corresponding tapes of M. Then it may move the head markers to the left or right as required by the move. And finally, N changes its state as recorded in the finite control. At this point, N have simulated a move of M. We make the accepting states of N all the states that are the accepting state of M. If M accepts then N also accept and N does not accept otherwise. Thus N can simulate M completely. Running time The running time or time complexity is an important concept for a turing machine. The running time of a turing machine M with an input string w is the number of steps that M makes before halting. If M does not halt on input w then the running time is infinite. The time complexity of a turing machine T(n) is a function which is maximum of all running times of M over a string w of length n. Assuming the turing machines halt on all inputs, the constructed single tape turing machine has greater running time than the corresponding multitape turing machine. But still both the running times are polynomial and comparable. In fact the single tape turing machine will take time that is not more than the square of time taken by the multitape turing machine. Theorem: The time taken by the single tape TM N to simulate n moves of the k-tape TM M is O(n2). Proof:

After n moves of M, the tape head markers cannot have separated by more than 2n cells. Thus, if N starts at the left most marker, it has to move no more than 2n cells right, to find all the head markers. It can then make an excursion leftward, changing the contents of the simulated tapes of M, and moving head markers left or right as needed. Doing so requires no more than 2n moves left, plus at most 2k moves to reverse direction and write a marker X in the cell to the right (in the case that a tape head of M moves right). Thus, the number of moves by N needed to simulate one of the first n moves is no more than 4n + 2k. Since k is a constant, independent of the number of moves simulated, this number of moves is O(n). To simulate n moves requires no more than n times this amount, or O(n2). 1. Nondeterministic Turing Machines Non deterministic turing machines are those which differ from the deterministic ones from the fact that on taking an input symbol, the machine can change to several possible states. The transition function δ will be such that for each state q and tape symbol X, δ (q,X) is a set of triples, {(q1, Y1, D1), (q2, Y2, D2), … , (qk, Yk, Dk)}

where k is a finite integer.

The NTM at each step, can chose, any of the triples to be the next move. A NTM M is defined such that M accepts an input w if there exists a sequence of moves from the initial ID with w as input to an ID with an accepting state. The existence of other choices that do not lead to an accepting state is not relevant. Non determinism as such does not increase the power of a turing machine i.e. NTMs accept accept no languages not accepted by a deterministic TM. The proof involves showing that for any non deterministic turing machine MN there exist an equivalent deterministic truing machine MD. For this MD is used to simulate the accepting states of MN by going through the various possible paths in MN and for this purpose a queue is used. Theorem: If MN is a nondeterministic Turing machine, then there is a deterministic Turing machine MD such that L (MN) = L (MD). Proof: The basic idea is to find an accepting state by trying out all possible paths in the nondeterministic machine MN using the deterministic machine MD. If MD finds an accepting state, it terminates or the simulation continues. We can view the possible paths in MN for an input string w as a tree. Each branch of the tree represents one of the branches of non determinism. Each node of the tree is an instantaneous descriptions (IDs) of MN. The root of the tree is the starting ID. The turing machine TD searches the tree for an accepting ID. There are two searching strategies depth first search and breadth first search. The depth-first search strategy goes all the way down one branch before backing up to explore other branches. If MD were to explore the tree in this manner, MD could go forever down one infinite branch and miss an accepting configuration on some other branch. Hence we design MD to explore the tree by using breadth first search instead. This strategy explores all branches to the same depth before going on to explore any branch to the next depth. This method guarantees that MD will visit every node in the tree until it encounters an accepting configuration. For simulation of MN, MD will be designed as a multitape turing machine (Figure C). The first tape of MD holds the sequence of IDs of MN with the starting ID at the left of the tape. The IDs are separated using * symbol and a marker character x is used to mark the ID that is to be scanned i.e all the IDs to the left of x are explored and will be ignored. The second tape called the scratch tape is used for temporarily holding ID before they are written onto first tape.

Figure C: Simulation of an NTM by DTM When an ID is encountered by the finite control it does the following: 1. MD examines the state and scanned symbol of the current ID. If the state in the current ID is accepting, then MD accepts and simulates MN no further. 2. However, if the state is not accepting, and the state-symbol combination has k moves, then MD uses its second tape (holds ID temporarily) to copy the ID and then make k copies of that ID at the end of the sequence of IDs on the first tape. 3. MD modifies each of those k IDs to replace them with the IDs after the different possible k choices for MN. 4. MD returns to the marked, current ID, erases the mark, and moves the mark to the next ID to the right. The cycle then repeats with step (1). The above procedure is breadth first search itself. If MN requires n moves to reach the accepting state, then MD should eventually reach that accepting state. Suppose m is the maximum number of choices or paths possible from a particular state in MN. Then from an initial ID, MN can reach at most m IDs after one move, m2 IDs after two moves and so on. Thus after n moves, MN can reach 1+m+m2+…+mn IDs. This number is atmost nmn IDs. Due to the breadth first search, accepting states are found by M D in the first nmn IDs that it considers. The only consideration is that MD finds the accepting ID in some finite time. Thus if MN accepts, so does MD. Thus we conclude that L (MN) = L (MD). Note: The constructed deterministic TM will take exponentially more time than nondeterministic TM.

1. Offline Turing Machines An Offline Turing machine is a multi tape Turing machine whose input tape is read only. Usually end markers like ^ or $ are provided at the beginning and end of the input. The Turing machine is not allowed to move its head off this region between ^ and $. The offline Turing machine is a special case of multi tape Turing machine and is in no way powerful than any other model of Turing machine. An offline TM can be used to simulate any Turing machine M by using one more tape than M. The first thing the offline Turing machine does is copy its own input to the extra tape, and it simulates M as if the extra tape were M’s input. The need for offline Turing machine becomes apparent when we consider the amount of storage space to be less than the input length.

Universal Turing Machines are discussed in Chapter # together with the Universal Language. Refer page ###.

Solved Problems: 1. Design Turing machines for the following languages: (a) The set of strings with an equal number of 0's and 1’s (b) {anbncn | n ≥ 1} (c) {wwR | w is any string of 0’s and 1’s} Solution: (a) The set of strings with an equal number of 0's and 1’s M = ({q0, q1, q2, q3, q4 , qf}, {0, 1}, {0,1, X, Y,B}, δ, q0, B, {qf }) where δ is as follows: Symbol State

0

1

B

X

Y

q0

(q2,X,R)

(q1,X,R)

(qf,B,R)

-

(q0,Y,R)

q1

(q3,Y,L)

(q1,1,R)

-

-

(q1,Y,R)

q2

(q2,0,R)

(q3,Y,L)

-

-

(q2,Y,R)

q3

(q3,0,L)

(q3,1,L)

-

(q0,X,R)

(q3,Y,L)

qf

-

-

-

-

In explanation, the TM makes repeated excursions back and forth along the tape. The symbols X and Y are used to replace 0's and 1's that have been cancelled one against another. The difference is that an X guarantees that there are no unmatched 0's and 1's to its left (so the head never moves left of an X), while a Y may have 0's or 1's to its left. Initially in state q0, the TM picks up a 0 or 1, remembering it in its state (q1 = found a 1; q2 = found a 0), and cancels what it found with an X. As an exception, if the TM sees the blank in state q0, then all 0's and 1's have matched, so the input is accepted by going to state qf. In state q1, the TM moves right, looking for a 0. If it finds it, the 0 is replaced by Y, and the TM enters state q3 to move left an look for an X. Similarly, state q2 looks for a 1 to match against a 0. In state q3, the TM moves left until it finds the rightmost X. At that point, it enters state q0 again; moving right over Y's until it finds a 0, 1, or blank, and the cycle begins again.

Solution: (b) {anbncn | n ≥ 1} M = ({q0, qa, qb, qc, qY , qZ, qf}, {a, b, c}, {a, b, c, X, Y, Z}, δ, q0, B, {qf }) where δ is as follows: State

Symbol a

b

c

X

Y

Z

B

q0

(qa,X,R)

-

-

-

(qY , Y,R)

-

-

qa

(qa, a, R)

(qb, Y,R)

-

-

(qa, Y,R)

-

-

qb

-

(qb, b,R)

(qc, Z, L)

-

-

(qb, Z,R)

-

qc

(qc, a, L)

(qc, b, L)

-

(q0,X,R)

(qc, Y, L)

(qc, Z, L)

-

qY

-

-

-

-

(qY , Y,R)

(qZ, Z,R)

-

qZ

-

-

-

-

-

(qZ, Z,R)

(qf ,B,R)

qf

-

-

-

-

-

-

-

The above TM is the 3-character version of the same machine given in the as example. Solution: (c) {wwR | w is any string of 0’s and 1’s} M = ({qinit, q0, q1, q0R, q1R, qback, qf}, {0, 1}, {0, 1, B}, δ, qinit, B, {qf}) where δ is as follows: State

Symbol 0

1

B

qinit

(q0,B,R)

(q1,B,R)

(qf ,B,R)

q0

(q0, 0,R)

(q0, 1,R)

(q0R,B, L)

q1

(q1, 0,R)

(q1, 1,R)

(q1R,B, L)

q0R

(qback,B, L)

-

-

q1R

-

(qback,B, L)

-

qback

(qback, 0, L)

(qback, 1, L)

(qinit,B,R)

qf

-

-

-

2. Design a Turing machine that takes as input a number N and adds 1 to it in binary. To be precise, the tape initially contains a $ followed by N in binary. The tape head is initially scanning the $ in state q0. Your TM should halt with N +1, in binary, on its tape, scanning the leftmost symbol of N + 1, in state qf. You may destroy the $ in creating N + 1, if necessary. For instance, q0$10011

$qf10100, and

q0$11111 qf100000. (a) Give the transitions of your Turing machine, and explain the purpose of each state. (a) Show the sequence of ID’s of your TM when given input $111. Solution: (a) Give the transitions of your Turing machine, and explain the purpose of each state.

M = ({q0, qR, q1, qL, qB, qf}, {0, 1}, {$, 0, 1, B}, δ, q0, B, {qf}) State

Symbol Explanation Initial $ reader

$

0

1

B

q0

(qR, $,R)

-

-

-

qR

-

(qR, 0,R)

(qR, 1,R)

(q1,B, L)

q1

(qB, 1, L)

(qL, 1, L)

(q1, 0, L)

-

Seeking end of string Carry bit = 1

qL

(qf , $,R)

(qL, 0, L)

(qL, 1, L)

-

Carry bit = 0

qB

-

-

(qf ,B,R)

-

Formatting

qf

-

-

-

-

Accepting state

(b) Show the sequence of ID’s of your TM when given input $111. q0$111

$qR111

$1qR11

$11qR1

$111qR

$11q11

$1q110

$q1100

q1$000

qBB1000

qf1000

2. A common operation in Turing-machine programs involves “shifting over.” Ideally, we would like to create an extra cell at the current head position, in which we could store some character. However, we cannot edit the tape in this way. Rather, we need to move the contents of each of the cells to the right of the current head position one cell right, and then find our way back to the current head position. Show how to perform this operation. Hint: Leave a special symbol to mark the position to which the head must return.

Solution: Assuming ∑ = {0, 1}, shift converts an ID of the form wq1v to ID wq6Bv. shift is defined as follows: State

Symbol 0

1

B

q1

(q2,B,R)

(q3,B,R)

(q5,B, L)

q2

(q2, 0,R)

(q3, 0,R)

(q4, 0, L)

q3

(q2, 1,R)

(q3, 1,R)

(q4, 1, L)

q4

(q4, 0, L)

(q4, 1, L)

(q5,B, L)

q5

(q6, 0,R)

(q6, 1,R)

(q6,B,R)

q6

-

-

-

Note: There is no extra character; B is used to keep track of the location of cell.