TOC Chapter 10

Chapter 10. Variations of Turing Machines

In Chapter 9, we defined the computability model called “Turing Machine” (TM). This model is one of the most beautiful, simple, and an useful abstract model. We had elaborate discussion of this model through various examples. One can think of variations of the basic model in many ways. For example, one can work with two tapes, instead of a single tape. These models are got by adding extra components and power to the control and hence, appear to be more powerful than the basic model, but they are not. We could also consider some restricted version of the basic model. In this chapter we are considering such variants and discuss their computing capabilities. We note that the power is not increased by adding extra components and not decreased by considering the restricted versions.

10.1. Generalized Versions

In this section, we consider the following generalized versions of the basic model and show that they are equivalent to the basic model as far as accepting power is concerned. The variants are:

1. Turing machines with two-way infinite tapes
2. Multitape TM
3. Multihead TM
4. Non-deterministic TMs
5. Turing machines with 2-dimensional tapes

   
   

   10.2. Restricted Turing Machines

   In this section we can discuss some more variations of TMs, which are in the form of restrictions. For example, we have an offline TM that has a restriction on the input tape. One can view the development of TM from finite state automata in a hierarchical way. When viewed as language recognizers FSA, PDA models could not recognize some languages, whereas a TM can do so. One can view the tape of the basic TM as input tape, output tape, and processing space. For example, a PDA is equivalent to a NTM with input tape, resembling the input tape of the PDA, the storage tape resembling the stack of the PDA. Now the processing of NTM can simulate the processing of the PDA. Hence, any computing can be simulated by a TM. But there are some standard ways a TM can be restricted leading to multi-stack TMs, counter machines, etc, without losing out on accepting power.

   Definition 10.3 A deterministic TM with read only input and two storage tape is called a deterministic two stack Turing machine (DTSTM). When the head of the DTSTM tries to move left on the tapes, a blank symbol will be printed.

   
   

   10.3. Turing Machines as Enumerators

   The languages accepted by the TM are recursively enumerable sets. One can think of a TM as generating a language. An enumerator is a TM variant which generates a recursively enumerable language. One can think of such a TM to have its output on a printer (an output tape). That is, the output strings are printed by the output device printer. Thus, every string that is processed freshly, is added to the list, thereby printing it also.

   The enumerator machine has an input tape, which is blank initially, an output device which may be a printer. If such a machine does not halt, it may perform printing of a list of strings infinitely. Let M be an enumerator machine and G(M) be the list of strings appearing on output tape. We have the following theorem for M.

   10.4. Equivalence Between Turing Machines and Type 0 Languages

   In this section, we prove the equivalence between Type-0 grammars and TM. That is, any recursively enumerable set can be generated by a type 0 grammar and it can also be recognized by a TM.

   Theorem 10.12 If L is the language generated by an unrestricted grammar G = (N, T, P, S), then L is recognized by a TM. Proof For G, we construct a TM M with two tapes such that on one tape we put the input w and the other tape is used to derive w using P. Each time a rule from P is applied, compare the two tapes for acceptance or rejection of w. Initially put w on one tape. Then, M initially places S on the second tape. Nondeterministically select a rule S → α from P, replace S by α on the second tape. Now compare the tapes, if they agree accept w. Otherwise, from the present string α, choose a location ‘i’ nondeterministically such that β is a subword occurring in α from position i. Choose a rule β → γ again nondeterministically. Apply to α, by inserting γ at the position of β. Now, let the present tape content be α1. If α1 = w, then accept w, otherwise continue the procedure.

   
   

   10.5. Linear-Bounded Automata

   A linear-bounded automata (LBA) is a NTM with a bounded, finite-input tape. That is, input is placed between two special symbols ¢ and $.

   ¢	a1	a2	...	an	$

   
   

   10.6. Gödel Numbering

   In the construction of counter automata, we have used the concept of Gödel numbering. Let us consider this topic more formally.

   Perhaps the most famous and most important of the several deep theorems about mathematical logic proved by Kurt Gödel (1931) was his incompleteness theorem: for any sound logical axiomatic system that is sufficiently rich to contain the theory of numbers, there must be number-theoretic statements that can neither be proved nor disproved in the system. Gödel’s theorem is one of the most significant discoveries made in the twentieth century, since it places a limit on the efficacy of mathematical reasoning itself. During proving his result, Gödel used a numbering scheme which is called Gödel numbering.

   Problems and Solutions

   1.	For the following two-way infinite TM, construct an equivalent one-way TM.
   Solution.
   2.	Construct a TM M with a 2-dimensional tape. M starts with initial ID: ... X X X ... X X X ... i.e., a row of n X’s surrounded by blanks. It has to halt with the final ID. ... X ... X X   ...   X X ... X ... i.e., above and below the row of n X’s, a row of (n−2) X’s is printed, centrally adjusted.
   Solution.	K = {q0, ..., q11} Γ = {X, Y, } δ is given by: δ(q0, X) = (q1, Y, R) δ(ql, X) = (q2, Y, U) δ(q2, ) = (q3, X, D) δ(q3, Y) = (q4, Y, D) δ(q4, ) = (q5, X, U) δ(q5, Y) = (q1, Y, R) δ(q1, ) = (q6, , L) δ(q6, Y) = (q7, Y, U) δ(q7, X) = (q8, , D) δ(q8, Y) = (q9, Y, D) δ(q9, X) = (q10, , U) δ(q10, Y) = (q10, X, L) δ(q10, ) = (q11, , halt)

   
   

   Exercises

   1.	Consider the following TM with two-way infinite tape. M = ({q0, q1, q2, q3}, {0, 1}, {0, 1}, δ, q0, {q3}) where δ is given by: δ(q0, 0) = (q1, 1, R) δ(q1, 1) = (q2, 0, L) δ(q2, 0) = (q0, 1, R) δ(q1, 0) = (q3, 0, R) Construct an equivalent one-way infinite tape TM.
   2.	It is desired to design a TM that copies patterns of 1’s and 2’s in accordance with the following format: First, design the machine as a 2-track machine. Assume that the given pattern is initially written in the top track and that the bottom track is initially blank. Let the machine use the bottom track to mark each symbol in the given pattern with an X as it is copied. Give the state diagram of the machine. Now, convert the 2-track machine of (a) into an equivalent one-track machine by assigning single symbols to ordered pairs of upper and lower-track symbols. Choose this assignment so that the resulting machine meets the format specified at the beginning of the problem. How many tape symbols does the 1-track machine use? What are their roles?
   3.	It is desired to design a 2-tape TM that behaves as follows. The machine’s first tape is initially inscribed with a pattern of the form and the second tape is left blank. The machine is to determine which of the given blocks of 1’s is the longest and is to halt with a copy of that block on its second tape. The original pattern is to be left unchanged on the first tape. The machine is to halt scanning the 0 to the right of the given pattern on its first tape and the 0 to the left of the block formed on the second tape. Design an appropriate machine, using the symbol alphabet {0, 1} for each tape. Describe your machine graphically, using the same conventions used for ordinary TM, except that: (1) the symbols scanned and written on the machine’s first and second tapes are to be represented by symbol pairs of the form , as in the case of two-track machines; and (2) each state is to be labeled with a pair of direction symbols of the form to indicate the directions that the machine is to move on its first and second tapes when it enters that state. Each of D1 and D2 may be either L, R, or –, where the symbol − indicates that the machine does not shift the tape head in question.
   4.	Let M be any TM that operates on a doubly infinite tape. Show that there exists another doubly infinite machine that duplicates each of M’s computations in at most half as many steps as M, as long as ’s initial and final tape patterns are properly encoded. Describe a typical step in ’s computation. Hint: Let the squares of M’s tape be represented on three tracks of ’s tape according to the following scheme.                             M’s tape:   −5 −4 −3 −2 −1 0 1 2 3 4 5                                   −11 −9 −7 −5 −3 −1 1 3 5 7 9   ’s tape:   −10 −8 −6 −4 −2 0 2 4 6 8 10       −9 −7 −5 −3 −1 1 3 5 7 9 11
   5.	Construct a TM with two-dimensional tape which gives the following output for the given input. Output is an array of X’s surrounded by blanks.
   6.	Give type 0 grammar for the TM, given in Exercise 1. given in Exercise 7, Chapter 9.