TOC Chapter 9

Chapter 9. Turing Machines

We have seen earlier that FSA have finite amount of memory and hence cannot do certain things. For example, no FSA can accept {aⁿbⁿ|n ≥ 1}. Though, it is possible to have FSA for adding two arbitrarily long binary numbers, we cannot have an FSA which can multiply two arbitrarily long binary numbers. Hence the question arises. What happens when we leave this restriction of finite memory? What problems can be solved by mechanical process with unlimited memory? By mechanical process, it is meant a procedure so completely specified that a machine can carry it out. Are there processes that can be precisely described yet still cannot be realized by a machine (computer)?

Programming – the job of specifying the procedure that a computer is to carry out – amounts to determining in advance, everything that a computer will do. In this sense, a computer’s program can serve as a precise description of the process the machine can carry out, and in this same sense it is meaningful to say that anything that can be done by a computer can be precisely described.

9.1. Turing Machine as an Acceptor

The TM can be considered as an accepting device accepting sets of strings. Later, we shall see that TM accept the family of languages generated by type 0 grammars. The set accepted by a TM is called a recursively enumerable set.

When we consider the TM as an accepting device, we usually consider a one-way infinite tape. In the next chapter, we shall see that by having a two-way infinite tape, the power does not change. The TM consists of a one-way infinite read/write tape and a finite control (Figure 9.1).'

9.2. Turing Machine as a Computing Device

In the last section, we have viewed TM as an acceptor. In this section, we consider the TM as a computing device. It computes functions which are known as partial-recursive functions. In this section, we consider the tape of the TM as infinite in both directions. We can make this assumption without loss of generality as in the next chapter, we shall prove the equivalence of one-way and two-way infinite tapes. The machine is started with some non-blank portion on the tape, with the rest of the tape containing blanks only. This is taken as the input. After making some moves, when the machine halts, the non-blank portion of the tape is taken as the output. For some inputs, the machine may get into a loop in which case the output is not defined. Hence, the function computed will be a partial function. While considering the TM as a computing device we do not bother about the final states. Initial tape head position has to be specified.

Example 9.4. (Unary to binary converter)

The input is a string of a’s which is taken as the unary representation of an integer; aⁱ represents integer i. The output is of the form b_iXⁱ where b_i is a binary string which is the binary representation of integer i. The mapping for the TM which does this is given below. The tape symbols are {, a, X, 0, 1}. The machine has two states q₀ and q₁. q₀ is the initial state and a right moving state. q₁ is a left moving state.

δ(q0, a)	=	(q1, X, L)
δ(q1, X)	=	(q1, X, L)
δ(q1, )	=	(q0, 1, R)
δ(q1, 0)	=	(q1, 1, R)
δ(q1, 1)	=	(q1, 0, L)
δ(q0, X)	=	(q0, X, R)
δ(q0, )	=	(q2, , halt)

The machine works like a binary counter. When it has converted j ‘a’s into X’s, it prints binary number j to the left of the position where it started. Let us consider the working of the machine on aaaaa. It should output 101X X X X X.

The machine starts in state q₀ on the leftmost a.

9.3. Techniques for Turing Machine Construction

Designing a TM to solve a problem is an interesting task. It is somewhat similar to programming. Given a problem, different TMs can be constructed to solve it. But, we would like to have a TM which does it in a simple and efficient manner. Like we learn some techniques of programming to deal with alternatives, loops etc, it is helpful to understand some techniques in TM construction, which will help in designing simple and efficient TM. It should be noted that we are using the word ‘efficient’ in an intuitive manner here, though later in Chapter 12, we shall deal with it formally. Next, we consider some techniques.

1. Considering the state as a tuple

In Example 9.2.2, we considered a TM which makes a copy of a given string over Σ = {a, b}. After reading a ‘a,’ the machine remembers it by going to q_a and after reading a ‘b,’ it goes to q_b. In general, we can represent the state as [q, x] where x ∊ Σ denoting that it has read a ‘x.’

Problems and Solutions

1.	Consider the following TM M′ with transitions as follows: δ(q0, 1) = (q1, 0, R) δ(q1, 1) = (q1, 1, R) δ(q1, 0) = (q2, 1, R) δ(q2, 0) = (q3, 0, L) δ(q3, 0) = (q0, 0, R) δ(q3, 1) = (q3, 1, L) q0 is the initial state and 0 is taken as blank symbol. Trace the sequence of moves when the machine is started on What happens when it is started on: 1. 2. 3. 4.
Solution.	a. q0 1 1 1 1 0 0 0 1 1 0 q1 1 1 1 0 0 0 1 1 0 1 q1 1 1 0 0 0 1 1 0 1 1 q1 1 0 0 0 1 1 0 1 1 1 q1 0 0 0 1 1 0 1 1 1 1 q2 0 0 1 1 0 1 1 1 q3 1 0 0 1 1 0 1 1 q3 1 1 0 0 1 1 0 1 q3 1 1 1 0 0 1 1 0 q3 1 1 1 1 0 0 1 1 q3 0 1 1 1 1 0 0 1 1 0 q0 1 1 1 1 0 0 1 1 0 0 q1 1 1 1 0 0 1 1 0 0 1 q1 1 1 0 0 1 1 0 0 1 1 q1 1 0 0 1 1 0 0 1 1 1 q1 0 0 1 1 0 0 1 1 1 1 q2 0 1 1 0 0 1 1 1 q3 1 0 1 1 0 0 1 1 q3 1 1 0 1 1 0 0 1 q3 1 1 1 0 1 1 0 0 q3 1 1 1 1 0 1 1 0 q3 0 1 1 1 1 0 1 1 0 0 q0 1 1 1 1 0 1 1 0 0 0 q1 1 1 1 0 1 1 0 0 0 1 q1 1 1 0 1 1 0 0 0 1 1 q1 1 0 1 1 0 0 0 1 1 1 q1 0 1 1 0 0 0 1 1 1 1 q2 1 1 No move for (q2, 1); machine halts with output The first block of 1’s is shifted step by step to the right till it becomes adjacent to the second block of 1’s. b. 1. It will halt when the ID is as below: First block of 1’s will be shifted to the right till it is adjacent to the second block; but third block of 1’s is not affected. 2. When there is only one block of 1’s it gets shifted one cell to the right and the process repeats. It never stops as there is no second block of 1’s. 3. Since the machine starts with the third 1 in the first block, the portion of the first block from this point is shifted to the right till it becomes adjacent to the second block. 4. There is only one block of 1’s. The portion of the block from the initial position is shifted one cell to the right and this process starts repeating and never stops as there is no second block 1’s. The portion of the block of 1’s to the left of the initial tape head position is unaffected.
2.	Construct a TM with three characters 0, 1, and # which locates a ‘1’ under the following conditions. There is only one # on the tape and somewhere to the right of it is a ‘1.’ The rest of the tape is blank. The head starts at or to the left of the #. When the TM halts, the tape is unchanged and head stops at the ‘1.’ Zero is taken as the blank symbol.
Solution.	The transition table is as follows. Here q3 is the (halt or) final state: 0 1 # q0 (q0, 0, R) (q0, 1, R) (q1, #, R) q1 (q1, 0, R) (q2, 1, R) – q2 (q3, 0, L) – – q3 – – –
3.	Construct a TM over an alphabet {0, 1, #}, where 0 indicates blank, which takes a non-null string of 1’s and #’s and transfers the rightmost symbol to the left-hand end. Thus, ...000#1#1#1000... becomes ...0001#1#1#000.... The head is initially at the leftmost non-blank symbol.
Solution.	The machine mainly has to move to the right-hand end, read the character, to identify the rightmost 1 or #. Then, move it to the leftmost end and halt. The transitions are: 0 1 # q0 (q1, 0, L) (q0, 1, R) (q0, #, R) q1 (q4, 0, R) (q2, 0, L) (q3, 0, L) q2 (q4, 1, L) (q2, 1, L) (q2, #, L) q3 (q4, #, L) (q3, 1, L) (q3, #, L) q4 (q5, 0, R) – –
4.	Design a TM with one track, one head, and three characters 0, 1, # to compute the following functions. Input and output are to be in binary form as follows. Zero is represented as # # and 7 is represented as # 1 1 1 #. That is the binary string represented by ‘n’ is enclosed between two #’s on left and right of it. is the blank symbol. f(n)= n + 1 g(n) = 2n. Input is #n# Output is #n + 1# in (a) and #2n# in (b)
Solution.	The function to be computed is f(n) = n + 1. Input is Output is The transition table is given below: 0 1 # q0 – – (q1, #, L) – q1 (q4, 1, L) (q2, 0, L) (q3, 1, L) – q2 (q4, 1, L) (q2, 0, L) (q3, 1, L) – q3 – – – (q4, #, L) q4 – – – – The function to be computed is g(n) = 2n. Input is Output is 0 1 # q0 (q0, 0, R) (q0, 1, R) (q1, 0, R) – q1 – – – (q2, #, L) q2 – – – –

Exercises

1.	Draw a state diagram for a TM accepting each of the following languages: {x ∊ {0, 1}*|#1(x) = 2#0(x) + 1}. The language of all non-palindromes over {a, b}.
2.	Consider the TM whose state transition is given below: δ(q0, 1) = (q1, 0, R) δ(q1, 0) = (q2, 1, R) δ(q2, 1) = (q3, 0, L) δ(q3, 0) = (q0, 1, R) δ(q0, 0) = (q0, 0, R) δ(q1, 1) = (q1, 1, R) δ(q2, 0) = (q2, 0, R) δ(q3, 1) = (q3, 1, L) Here, q0 is the start state and q2 is a final state. For each of the initial tape configurations, determine the final tape pattern that the machine will produce and indicate the final head position. ...01110111110... ...01110110... Here ‘B’ means the head is presently reading that symbol ‘B.’ What effect will the machine have on an arbitrary initial pattern of the form ... 01m01n0 ..., where m and n are positive integers. Explain briefly how the machine works. What is the final position of the reading head? Show how to modify the given transitions so that the machine will always halt at its starting position.
3.	Consider the TM described by the following state diagram. Determine the behavior of the machine for each of the following initial configurations: ...000000000000... ...00000100101100... ...01100010000000... Describe as clearly and concisely as you can the initial tape configurations for which the machine will eventually halt.
4.	Design a TM for the following job. When started anywhere on a tape that is blank except for a single 1, the machine eventually halts with that 1 under its reading head. The remainder of the tape is to be blank when the machine halts.
5.	Design a TM that behaves as follows: When presented with a tape containing an arbitrary string of 1’s and 2’s (preceded and followed by blanks) and made to scan the first symbol in the string, the machine is to reverse the string. Thus, if presented with the tape pattern, ...00121121200... the machine should eventually produce the tape pattern, ...00212112100... and halt as indicated. The final pattern is to occupy the same region of the tape as the initial pattern. A solution using between six and nine states is reasonable.
6.	Construct a TM to carry out the following operations: A left shift of its input by one cell. A cyclic left shift of its input by one cell. Let c be in Σ (the input alphabet). If the input word x = x1cx2 where x1 is in (Σ – {c})*, then produce cx2 as output. A duplication of its input. i.e., if the input is w, the output should be ww. Let 1 be in Σ. If the input is x 1i for some i ≥ 0, then the output should be x shifted left i cells. So, input x is unchanged on output while x 1 is given by the solution to (a) above. Let 1 be in Σ and the input be x 1i for some i ≥ 0. Then output xi.
7.	Consider the following TM transitions: Here, q0 is the initial state, and q2 is the final state. δ(q0, a) = (q1, b, R) δ(q0, b) = (q3, , R) δ(q0, ) = (q2, , L) δ(q1, a) = (q1, b, R) δ(q1, b) = (q1, a, R) δ(q1, ) = (q2, , L) δ(q3, a) = (q4, , R) δ(q3, b) = (q3, b, R) δ(q4, a) = (q1, b, R) Give four words accepted by the TM together with their configuration sequences. Give four words that are not accepted by the TM and in each case explain why not.
8.	Design a TM that when started on any tape pattern of the form: ...01n01x00...(n > 0, x ≥ 0) eventually halts with the pattern ...01n01x + n00... on its tape. The new pattern is to start in the same square as the given pattern.
9.	Using the TM of problem (8) as a submachine, design a new TM that behaves as follows. When started on any pattern of the form: ...01m01n00... (m, n > 0) the machine is eventually to halt with the pattern ...01mn0... on its tape. The location of this final pattern may be chosen to make the design of the machine as simple as possible.
10.	For each of the following languages, construct a TM that recognizes the language: {xyx|x and y are in {a, b}*and|x| > 1} {aibicjdj|i ≠ j} {aba2b2a3b3 ... anbn|n ≥ 0}
11.	Consider the TM with input alphabets {a, b}, start state q0 with the following transitions: δ(q0, ) = (q1, , R) δ(q1, a) = (q1, a, R) δ(q1, b) = (q1, b, R) δ(q1, ) = (q2, , L) δ(q2, a) = (q3, , R) δ(q2, b) = (q5, , R) δ(q2, ) = (q2, , N) δ(q3, ) = (q4, a, R) δ(q4, a) = (q4, a, R) δ(q4, b) = (q4, b, R) δ(q4, ) = (q7, a, L) δ(q5, ) = (q6, b, R) δ(q6, a) = (q6, a, R) δ(q6, b) = (q6, b, R) δ(q6, ) = (q7, b, L) δ(q7, a) = (q7, a, L) δ(q7, b) = (q7, b, L) δ(q7, ) = (q2, , L) What is the final configuration if the input is ab? What is the final configuration if the input is baa? Describe what the TM does for an arbitrary input string in {a, b}*.
12.	Construct a TM to accept the language {aibj|i < j}.
13.	Construct a TM to accept the language {w ∊ {a, b}*|w contains the same number of a′s and b′s}
14.	Construct a TM to accept the language {w ∊ {a, b}*|w = wR}.
15.	Construct a TM to compute the following functions. Let the input x be represented in unary notation: f (x) = x + 2 f (x) = 2x f (x) = x mod 2.
16.	Give informal arguments which explain why TMs are more powerful than PDAs.