Chapter 9: Variations of the Turing Machine – Introduction to Automata Theory, Formal Languages and Computation

9

Variations of the Turing Machine

Introduction

Till now, we have discussed about the Turing machine with a single head and a single tape. It has been clear from the given examples that the Turing machine is a powerful computational machine. But, for some cases, it may seem that the Turing machine takes a lot of time for computation, and it is complex. To understand the computational power of the Turing machine and to reduce the time complexity, researchers have proposed different models of the Turing machine. These models have given us freedom to use a suitable machine wherever applicable to solve a variety of problems by the Turing machine. It can be proved that, computationally, all these Turing machines are equally powerful. That is, what one type of Turing machine can compute, any other type can also compute. However, the efficiency of computation, that is, how fast they can compute, may vary.

9.1  Variations of the Turing Machine

The different types of Turing machine are

  • Multi-tape Turing machine
  • Multi-head Turing machine
  • Two-way infinite tape
  • K-dimensional Turing machine
  • Non-deterministic Turing machine
  • Enumerator

9.1.1  Multi-tape Turing Machine

The name suggests that this type of Turing machine has multiple tapes instead of one. Each of the tapes is connected to the finite control by a read–write head. It means for m tapes there are m read–write heads. The transitional function of the multi-tape Turing machine depends on the present state and the input symbol scanned by each of the read–write head from the respective input tape. Depending on the present state and the input symbols scanned by each of the head, the Turing machine can

  • Change its state.
  • Write a new symbol on the respective cell of the respective tape from where the inputs were scanned.
  • Move the head to one left or one right.

A multi-tape Turing machine having k tapes (k ≥ 1) is symbolically represented as

 

TM = (Q, Σ, Γ, δ, q0, B, F)

 

where Q: Finite set of states

      Σ: Finite set of input alphabets

      Γ: Finite set of allowable tape symbols

      q0: Initial state

      B: A symbol of Γ called blank

      F: Final states

      δ: Transitional function

where δ is a mapping from Q × (Γ1, Γ2, . . . . . . Γk) → (Q × (Γ1, Γ2, . . . . . . Γk) × [(L, R, H), (L, R, H) . . . . k times]. In general Q × Γk → (Q × Γk × (L, R, H)k).

Diagrammatically, a multi-tape Turing machine can be denoted as shown in Fig. 9.1.

Fig. 9.1 Multi-tape Turing Machine

Example 9.1

Design a multi-tape Turing machine for checking whether a binary string is a palindrome or not. Show an ID for 1001.

Solution: We are considering a Turing machine with two tapes. The input is written on the first tape. The machine works by the following process:

  1. Copy the input from the first tape to the second tape by traversing the first tape from left to right.
  2. Traverse the first tape again from right to left and point the head to the first symbol of the input on tape 1.
  3. Moves the two heads pointing on the two tapes in opposite directions checking that the two symbols are identical and erasing the copy in tape 2 at the same time.

Here, the moves on two tapes are described in a group.

The string is written on tape 1. Tape 2 is blank. The string may start with ‘0’ or may start with ‘1’. The machine is in state q0 initially. Traversing ‘0’ or ‘1’ in tape 1, the blank ‘B’ in tape 2 is replaced by ‘0’ or ‘1’, respectively, and both the head move to one cell right. The transitional functions are

When the head of the first tape finds ‘B’ at the right side, the string is totally traversed. The state is changed to q1 and head of the first tape starts to traverse to the left. The transitional functions are

Traversing the first tape from right to left, the head has to traverse ‘0’ and ‘1’ and the head on the second tape has no traversal. The transitional functions are

When the head of the first tape finds ‘B’ at the left side, the string is totally traversed from right to left. The state is changed to q2 and the head of the first tape starts to traverse to the right. The head of the second tape starts to traverse to the left. The transitional functions are

Now, both the heads are traversing the same string written on two tapes but in opposite directions. If both the heads traverse ‘0’, or both the heads traverse ‘1’, then it is allowed for them to traverse right or left, respectively. If one head traverses ‘0’ and the other traverses ‘1’ or vice versa, it stops on a state which signifies that the string is not a palindrome. If this situation does not arise and both the heads get blank ‘B’, then the machine halts on a state which signifies that the string is a palindrome. The transitional functions are

The transitional diagram describes it clearly.

ID for 1001

Example 9.2

Design a multi-tape Turing machine for L = anbncn.

Solution: We are considering a Turing machine with four tapes. The input is written on the first tape. The machine works by the following process

  1. Copy all ‘a’ on tape 2, all ‘b’ on tape 3, and all ‘c’ on tape 4.
  2. Traverse tape 2, tape 3, and tape 4 from right to left simultaneously and replace each symbol by a blank.
  3. If all the heads traversing tapes 2, 3, and 4 get B, then declare accept. If not, declare reject.

The transitional representation of the Turing machine is as follows.

The language acceptance power of a multi-tape Turing machine is the same as the single-tape Turing machine. Only the time complexity may be reduced.

If we take the example of checking whether a string of binary is a palindrome or not, then it can be easily justified.

Consider a single-tape Turing machine for checking an even length string.

  1. For checking a string of length n, it needs 2n + 1 steps. [(Making first symbol to B) + (n right traversal upto B) + (Left traversal with replacing rightmost symbol by B) + ((n − 1) left traversal upto B)]
  2. From the next traversal, the string of length n is truncated to length (n−2). The number of steps required is (2n − 3). By this process, the last step will be (2n − (2n −1)) = 1.
  3. The total number of steps required is (2n + 1) + (2n − 3) + …… + 1 = [(n + 2)(n + 1)]/2, means O(n2).

[1 is the (n + 2)/2th element of the series.]

If the string is traversed by a two-tape Turing machine,

  1. For copying the string to tape 2, it needs (n + 1) steps.
  2. For left traversal of the string on tape 1, it needs (n + 1) steps.
  3. For right traversal of tape 1 and left traversal of tape 2, it needs (n + 1) steps.
  4. There is a total of 3n + 1 steps, means O(n).

This proves the reduced complexity of the multi-tape Turing machine.

Every multi-tape Turing machine has an equivalent single-tape Turing machine.

Proof: Let MMT be a k tape Turing machine where k > 1. We have to construct a single-tape Turing machine MST which simulates M.

  • MST simulates the effect of k tapes (k > 1) by storing the information of k tapes on its single tape.
  • MST uses a special symbol # as a mark to separate the content of different tapes.
  • MST tracks the location of the heads of the MMT by marking an _ (underline) on the symbols where there were head positions in MMT.

The process is described in Fig. 9.2

Fig. 9.2 Conversion of a Multi-tape TM to a Single-tape TM

9.1.2  Multi-head Turing Machine

The name signifies that this type of Turing machine has multiple heads. All the heads are connected to the finite control. The transitional function for the multi-head Turing machine having n heads can be described as

where ∑i is the input symbol under head i and Γi is the symbol written by replacing ∑i. N means no movement of the head.

A diagrammatical representation of a multi-head Turing machine is given in Fig. 9.3.

Fig. 9.3 Multi-head Turing Machine

We have to be careful about two special cases in designing a multi-head Turing machine.

  1. A situation may arise when more than one heads are scanning a particular cell at the same time. But the symbol written by one head is different from the symbol written by the other head.

    In this situation, priority among the heads is defined. The change done by the head with the highest priority will remain.

  2. Another situation may arise when a cell under a head is the leftmost cell and the transitional function instructs the head to go left. This condition is called hanging.

Example 9.3

Design a multi-head Turing machine for checking whether a binary string is a palindrome or not. Show the ID for 1001 and 101.

Solution: Let us consider a Turing machine with two heads. The heads are pointing to the two ends of the string on the tape. Both the heads traverse the string in the opposite direction. The head 1 has the priority over head 2.

  1. If both of the heads get the same symbols, then it traverses the next input right or left by replacing the present symbol by B.
  2. If both the heads gets B, then halt and declare the string as a palindrome.

The transitional representation of the Turing machine is as follows.

ID for 1001

ID for 101

Every multi-head Turing machine has an equivalent single-head Turing machine.

Proof: This is proved by converting a multi-head Turing machine to a multi-tape Turing machine and then converting a multi-tape Turing machine to a single-tape and single-head Turing machine.

The conversion of a multi-head Turing machine to a multi-tape Turing machine is done using the following rules.

  • Initialize each tape of a multi-tape Turing machine by the input string.
  • Whenever head i is moved in a multi-head TM, move the head in the ith tape in the multi-tape TM.
  • Whenever any head in a multi-head TM writes a symbol in the input tape, write the same symbol at the same position on every tape in the multi-tape TM.

Convert the multi-tape TM to a single-tape TM.

(The conversion process of a multi-tape TM to a single-tape single-head TM is already discussed.)

This conversion is shown in Fig. 9.4 for the previous example of checking a palindrome.

Fig. 9.4 Conversion of a Multi-head TM to a Multi-tape TM

9.1.3  Two-way Infinite Tape

In general, in a Turing machine there is a left boundary. If the head crosses that boundary and wants to go left, then the situation is called a crash condition. But the head may traverse the right side up to infinity. In this sense, the input tape of the general Turing machine can be treated as a one-way infinite tape. A typical diagram of the input tape of a general Turing machine is given in Fig. 9.5.

Fig. 9.5 Typical Diagram of an Input Tape of a General Turing Machine

A Turing machine where there are infinite numbers of sequence of blank on both sides of the tape is called a two-way infinite tape Turing machine. A typical diagram of the input tape of a two-way infinite tape Turing Machine is given in Fig. 9.6.

Fig. 9.6 Typical Diagram of a Two-way Infinite Tape

Every two-way infinite tape Turing machine has an equivalent Turing machine by marking the left-hand side of the input to detect and prevent the head from moving off of that end.

9.1.4  K-dimensional Turing Machine

The input tape of two-dimensional Turing machine is extended to infinity in both sides, but in one direction. If the input tape can extend infinitely in more than one dimension, then the Turing machine is called a multi-dimensional Turing machine. In a general case, just consider k = 2, which means that the input tape is extended to infinity in X and Y direction. For this case, the read–write head can move in the left, right, up, and down directions. The transitional function for a K-dimensional Turing machine is

where L = Left, R = Right, U = Up, D = Down.

The diagram in Fig. 9.7 describes a two-dimensional Turing machine.

Fig. 9.7 K-dimensional (k = 2) Turing Machine

9.1.5  Non-deterministic Turing Machine

We are familiar with the term non-deterministic while discussing finite automata and pushdown automata. If we recall the transitional function of the non-deterministic finite automata, we will see that for a single state and a single input there may be more than one move.

Till now, we have seen different types of Turing machines, but all of them have a unique triplet combination of next state, tape symbol, and move. But in case of a non- deterministic Turing machine, for a pair of present state (q) and input tape symbol (Σ), there may be a finite set of triplets (Qi, Γi, Di ) for i = 1, 2, . . . . . In other words, for a combination of a single present state and a single input symbol, there may be more than one move. The transitional function of a non-deterministic Turing machine is

 

Q × E → power set of Q × Γ × (L, R, H)

Example 9.4

Design a Turing machine for 0n1m, where m, n > 0 and n may not be equal to m.

Solution: The string contains n number of ‘0’ and m number of ‘1’, but the number of ‘0’ and the number of ‘1’ may not be equal and there is at least one ‘0’ and one ‘1’. First, the Turing machine traverses (n − 1) number of 0 using the transitional function

 

δ(q0, 0) → (q0, 0, R)

 

After the last ‘0’, there are m number of ‘1’. If the machine starts to traverse ‘1’, it cannot traverse ‘0’ because all ‘0’ will appear before ‘1’ in the string. So, it needs a state change to traverse ‘1’. But here, there is another problem. From q0 by getting ‘1’ if the TM changes its state, then the condition that n > 0 is failed. In this case, the necessity of a non-deterministic TM is felt.

If we make another transition from q0 to a new state q1 by getting ‘0’, then both the conditions are fulfilled.

The remaining transitional functions of the Turing machine are

The transitional diagram gives it the look of a non-deterministic Turing machine.

Every non-deterministic Turing machine has an equivalent deterministic Turing machine.

Proof: For accepting a string w by a non-deterministic Turing machine (MNT), it constructs a tree with all possible branches. If the accept state is ever found by the deterministic Turing machine (MDT) on one of these branches, then it accepts. Otherwise simulation will not terminate. The process is as follows.

  1. Construct a tree T with all possible branches for accepting a string w.
  2. The root node of T is the start of the configuration and each node N has a configuration <current state of MNT, current contents of MNT’s tape, and position of the read head of MNT>
  3. Design a tree D by performing a breadth first search of T.

    (This strategy traverses all branches at the same depth before going to traverse any branch at the next depth. Hence, this method guarantees that D will visit each node of T until it encounters an accepting configuration.)

  4. Use three tapes to simulate D for MNT.

    – Tape 1, called input tape, always holds input w

    –Tape 2, called simulation tape, is used as MNT‘s tape when simulating M on a sequence of non-deterministic choices

    –Tape 3, called choice tape, stores the current sequence of non-deterministic choices.

  5. At initial stage, the input tape contains w, and the simulation tape and choice tape are kept blank
  6. Copy the contents of the input tape on the simulation tape.
  7. Use tape 2 to simulate MNT with input string w on one branch of its non-deterministic computation.

    – Before each step of MNT follow the next symbol on tape 3 to determine the choices to be made – among the allowed MNT’s transitional function.

    – If tape 3 becomes empty or if the present choice (for MNT ’s state and tape 3 input] is invalid, stop traversing the branch and go to step viii.

    – If an accepting configuration appears stop traversing; halt and declare accept.

  8. Replace the string on tape 3 with the lexicographically next string and simulate the next branch of MNT’s computation by going to stage (vi).

9.1.6  Enumerator

Enumerator is a type of Turing machine which is attached to a printer. It has a work tape and an output tape. The work tape is a write only once tape. At each step, the machine chooses a symbol to write from the output alphabet on the output tape. After writing a symbol on the output tape, the head placed on the output tape moves right by one position. The enumerator has a special state, say qp, entering which the output tape is erased and the tape head moves to the leftmost position and finally the string is printed. A string w is printed as output by the enumerator if the output tape contains w at the time the machine enters into qp.

The diagram of an enumerator is shown in Fig. 9.8.

Fig. 9.8 Enumerator

An enumerator is defined by 7 touples

 

(Q, Σ, Γ, δ, q0, B, qp)

 

where Q: Finite set of states

      Σ: Finite set of print alphabets

      Γ: Finite set of work tape symbols

      δ: Transitional function

      q0: Initial state

      B: A symbol of Γ called blank

      qp: Final state (print state)

where   δ is a mapping from Q × ∑ × Γ → (Q × ∑ × {L, R} × Γ × {L, R}).

9.2  Turing Machine as an Integer Function

An integer function is a function which takes its arguments as integers and returns the result in integer. If we consider integer addition, subtraction, multiplication, etc., we see that all these functions take the arguments in integer and produce the result in integer. Let an integer function be f (i1, i2 . . . . . . ik) = M. We have to solve this function using the Turing machine. First of all, the input tape must represent the input arguments. Let the number of ‘0’ be used to represent the arguments. But there must be a separator to differentiate the number of ‘0’ for each argument. In the Turing machine, generally, a blank ‘B’ is used as the separator. In some cases, other symbols may be used as a separator. Initially, the input tape will be 0i1B0i2……B0ik. After performing the integer function, the result will be M number of 0, which will remain on the tape.

The following are some examples of TM as integer functions.

Example 9.5

Addition of two integers. f(x, y) = x + y.

Solution: The input tape is 0xB0y. The calculation process is as follows.

  1. Traverse x number of ‘0’ up to ‘B’.
  2. On getting ‘B’, change the state and replace ‘B’ by 0.
  3. Traverse the second string. ‘B’ means it is the end of the second string. Change the state and traverse left.
  4. Replace the last ‘0’ of the second string by B and halt.

The transitional diagram of addition function is given in Fig. 9.9.

Fig. 9.9

Example 9.6

Compute the function f(x) = x + 2.

Solution: The input tape is 0x. The calculation process is as follows.

  1. Traverse x number of ‘0’ up to ‘B’.
  2. Change B by ‘0’ and change the state.
  3. Replace the second B by ‘0’ and halt.

The transitional diagram of the function is given in Fig. 9.10.

Fig. 9.10

Example 9.7

Subtraction of two integers

Solution: The input tape is 0x10y. The calculation process is as follows.

  1. Replace the first 0 by B, change the state, and traverse right. The transitional function is

     

    δ(q0, 0) → (q1, B, R)

     

    Traverse right for the remaining ‘0’s of the first string. Getting the separator ‘1’, change the state from q1 to q2. The transitional functions are

  2. Replace the leftmost ‘0’ for the second number by ‘1’, change the state, and traverse left to find the replaced B, using transitional functions

    Upon getting B, the state is changed to q0 using the function

     

    δ(q3, B) → (q0, B, R)

     

    From the second iteration onwards, q2 has to traverse ‘1’ using the transition function

     

    δ(q2, 1) → (q2, 1, r)

     

    If x > y, then the state q2 will get B at the last of the second number representation. x-y number of ‘0’ and y + 1 number of ‘1’ will remain. It changes its state and traverses left using the transitional function

     

    δ(q2, B) → (q4, B, L)

     

    Now, it replaces all the ‘1’ by B and traverses left to find B. The transitional functions are

    On getting B, it replaces it by ‘0’ and halts.

     

    δ(q2, B) → (q6, B, L)

     

    If x < y, all ‘0’ representing x will finish before y. In the state q0, the machine gets 1. It changes ‘1’ by B and traverses right with the state change.

     

    δ(q0, 1) → (q5, B, R)

     

    The state q5 replaces all ‘0’ and ‘1’ by B to make the tape empty, and upon getting B it halts.

Example 9.8

Compute the function

Solution: The input tape is 0x. The calculation process is

  1. Traverse x number of ‘0’ up to ‘B’.
  2. On getting B, change the state and traverse left.
  3. Replace the first ‘0’ by B with the state change and the second ‘0’ by B with the state change and halt.

The transitional diagram of the function is given in Fig. 9.11.

Fig. 9.11

Example 9.9

Multiplication of two integers f(x, y) = x * y.

Solution: Let x = 2 and y = 3. The input tape is in the form

Make the tape in the following form

by the transitional functions

Here, A denotes the beginning of the first number and the end of the second number.

The transitional diagram for multiplication operation is given in Fig. 9.12.

Fig. 9.12

Example 9.10

Th:e remainder after dividing one integer number by 2. f (x, y) = x % 2.

Solution: The remainder of the integer division 2 is either 1 or 0. The input tape is 0x. The calculation process is as follows.

  1. Traverse the string from left to right. Getting ‘B’, traverse left with a state change.
  2. Replace all the ‘0’ of the tape by ‘B’ with alternating change of state and traverse left.
  3. Getting ‘B’, either halt on the final state or traverse the right by replacing one ‘B’ by ‘0’ and halt depending on the state.

The transitional functions are

Example 9.11

Square of an integer. f(x) = x2.

Solution: The square of an integer means the multiplication of the number by the same number. The multiplication function is already described.

The input tape is in the form 1X. It has to be made in the form 1XB1X. To make this, the transitional functions are

9.3  Universal Turing Machine

From the discussions in the previous sections, it is clear that the Turing machine can perform a large number of tasks. The Turing machine can even perform any computational process carried out by the present day’s computer. What is the difference between a Turing machine and real computer? The answer is very simple. The Turing machine is designed to execute only one program but real computers are reprogrammable. A Turing machine is called a universal Turing machine if it simulates the behaviour of a digital computer. A digital computer takes input data from user and produces the output by using an algorithm. A Turing machine can be said to be a universal Turing machine if it can accept (a) the input data and (b) the algorithm for performing the task.

Each task performed by a digital computer can be designed by a Turing machine. So, a universal Turing machine can simulate all the Turing machines designed for each separate task.

How to design a universal Turing machine? The simple answer is to add all the Turing machines designed for each separate task. But, in reality, it is a complex one. We can do this by

  • Increasing the number of read–write heads (like multiple head TM)
  • Increasing the number of input tapes (like multiple tape TM)
  • Increasing the dimension of moving the read–write head (k-dimensional TM)
  • Adding special purpose memory like stack.

9.4  Linear-Bounded Automata (LBA)

An LBA is a special type of Turing machine with restricted tape space. The name ‘linear bounded’ suggests that the machine is linearly bounded. If we compare a LBA with a TM, then we see that the difference is in the operational tape space. For TM, the input tape is virtually infinite in both directions whereas the allowable input tape space of LBA is the linear function of the length of input string. The limitation of tape space makes LBA a real model of computer that exists, than TM in some respect. The diagram of an LBA is shown in Fig. 9.13.

Fig. 9.13 Linear-bounded Automata

An TBA is a 7-tuple non-deterministic Turing machine

 

TM = (Q, ∑, Γ, δ, q0, B, F)

 

where Q: Finite set of states

      Σ: Finite set of input alphabets with two end markers ‘[‘ and ‘]’

      Γ: Finite set of allowable tape symbols except two end markers ‘[‘ and ‘]’

      q0: Initial state

      B: A symbol of Γ called blank

      F: Final states

      δ: Transitional function

where δ is a mapping from Q × Γ → Q × 2Q × Γ × {L, R} with two more transitional functions δ(qi, [) → (qj, [, R) and δ(qi, ]) → (qj, ], L).

An LBA accepts context-sensitive language. It is powerful than the pushdown automata but less powerful than the Turing machine. The construction of an LBA for a context-sensitive language describes this clearly.

Example 9.12

Construct a linear-bounded automata for the following context-sensitive language.

 

L = {anbncn: n ≥ 0}

 

Solution: The design concept is

  1. On each pass, the machine matches the leftmost ‘a’, ‘b’, and ‘c’ and replaces them with ‘x’.
  2. If no ‘a’, ‘b’, and ‘c’ are left and it gets ‘[‘, then it halts.

The transitional functions are

9.5  Post Machine

The Post machine was proposed by a Polish mathematician Emil Post in 1936. A Post machine is similar to the pushdown automata but it has a queue instead of a stack. A Post machine is always deterministic. According to the property of the queue, any item is added from the rear and is deleted from the front. A Post machine is defined by a 7 tuple

 

M = (Q, Σ, Γ, δ, q0, z0, A)

 

where Q: Finite set of states

      Σ: Finite set of input alphabets

      Γ: Finite set of allowable queue symbols

      q0: Initial state

      z0: Queue end symbol (at initial state)

      A: set of add state. This concatenates a character with the string from the right end.

      δ: Transitional function.

It takes the current state, the symbol currently at the front of the queue, and moves to a state, giving an indication on whether to remove the current symbol from the front of the queue and the symbol to be added at the rear of the queue.

9.6.  Church’s Thesis

Alonzo Church, an American mathematician, proposed that any machine that can perform a certain list of operations will be able to perform all possible algorithms. Now, the question is ‘which machine is this?’. Alen Turing, a Ph.D scholar of Church, proposed that machine called the Turing machine. For writing a program, we need to construct an algorithm first. ‘No computational procedure is considered as an algorithm unless it is represented by the Turing Machine.’ This is known as the Church thesis or the Church–Turing thesis. This thesis cannot be proved; it is a generally accepted truth. For this reason, it is called a thesis and not a theorem.

What We Have Learned So Far

  1. A multi-tape Turing machine has multiple tapes and can be converted to a single-tape Turing machine
  2. A multi-tape Turing machine is less complex than a single-tape Turing machine.
  3. A multi-head Turing machine has multiple heads attached with a single finite control.
  4. Every multi-head Turing machine has an equivalent single-head Turing machine.
  5. A Turing machine where there are infinite numbers of sequence of blank on both sides of the tape is called a two-way infinite tape Turing machine.
  6. The input tape of a multi-dimensional Turing machine is extended to infinity in more than one dimension.
  7. An enumerator is a type of Turing machine attached to a printer.
  8. The allowable input tape space of the linear bounded automata is the linear function of the length of input string.
  9. A Post machine has a queue in comparison with a PDA which has a stack.

Solved Problems

  1. Design a multi-tape Turing machine for accepting the language anb2n, n > 0.

    Solution: Consider a Turing machine of four tapes. Tape 1 contains the input string in the form anb2n. Tape 2 is copied with n number of ‘a’ from anb2n. Tape 3 is copied with n number of ‘b’, and tape 4 is filled with the remaining n number of ‘b’.

    Traverse tape 2, tape 3, and tape 4 from the right to left simultaneously and replace each symbol by blank.

    If all the heads traversing tape 2, 3, and 4 get B at the same time, then declare as accept. If not, declare as reject.

    The transitional diagram is shown in the following figure.

  2. Design a multi-head Turing machine for accepting the language anbncn, n > 0.

    Solution: Consider a Turing machine with three heads. Initially, all the heads are placed on the first symbol. Place the first head on the first symbol (‘a’). Traverse the remaining two heads towards the right. Getting the first ‘b’, stop traversing the second head. Getting the first ‘c’, stop traversing the third head.

    The transitional representation of the Turing machine is as follows.

  3. Design a multi-tape Turing machine for L = {a, b}*, where N(a) = N(b).

    Solution: Consider a three tape Turing machine. The first tape contains the input. The second tape stores ‘a’ from the first. The third tape stores ‘b’ from the first. Then traverse the last two tapes to check whether the number of ‘a’ and ‘b’ is equal or not.

Multiple Choice Questions

  1. A multi-tape Turing machine has
    1. Multiple tape
    2. Multiple head
    3. Multiple finite control
    4. Multiple tape and head
  2. A multi-head Turing machine has
    1. Multiple tape
    2. Multiple head
    3. Multiple finite control
    4. Multiple tape and head
  3. In respect to the k-dimensional Turing machine, a simple Turing machine is
    1. 0 dimensional
    2. 1 dimensional
    3. 2 dimensional
    4. 3 dimensional
  4. A simple Turing machine is
    1. 1-way infinite tape
    2. 2-way infinite tape
    3. No way infinite tape
    4. none of these
  5. A Post machine has a
    1. Stack
    2. Linear list
    3. Queue
    4. Circular queue

Answers:

  1. d
  2. b
  3. b
  4. a
  5. c

GATE Questions

  1. Which of the following is true (A : Multi-tape TM, B: Multi-head TM, C: Non- deterministic TM, D: K-dimensional TM, E: Single tape TM).
    1. A, B > E
    2. C > E
    3. D > A, B > C > E
    4. A = B = C = D = E
  2. Which of the following has a read only tape?
    1. Single-tape TM
    2. Multi-tape TM
    3. Linear bounded automata
    4. None of these.
  3. Which one of the following conversions is impossible ?
    1. NTM → DTM
    2. Multi-tape TM → Single-tape TM
    3. Multi-head TM → Single-head TM
    4. NPDA → DPDA
  4. The movement of the head is limited to a certain region for which of the following machine
    1. K- dimensional TM
    2. Linear bounded automata
    3. Pushdown automata
    4. Two-way infinite tape
  5. In which of the cases stated is the following statement true?

    ‘For every non-deterministic machine M1, there exists an equivalent deterministic machine M2 recognizing the same language.’

    1. M1 is a non-deterministic finite automata
    2. M1 is a non-deterministic PDA
    3. M1 is a non-deterministic TM
    4. For no machine M1 use the above statement true.

Answers:

  1. d
  2. c
  3. d
  4. b
  5. a

Exercise

  1. Construct a multi-tape Turing machine for accepting L = 0n1n0n, n > 0.
  2. Construct a multi-head Turing machine accepting WWR, where w ∈ (a, b)+.
  3. Design a linear bounded automata accepting WWR, where w ∈ (a, b)+.
  4. Compute the reverse of a string w ∈ (a, b)+ using multi-tape Turing machine.