- Variation of Turing Machine

To simulate a two dimensional tape with a one dimensional tape, first we map the squares of the two dimensional tape to those of the one dimensional tape diagonally as shown in the following tables:

v | v | v | v | v | v | v | . . . | . . . |

h | 1 | 2 | 6 | 7 | 15 | 16 | . . . | . . . |

h | 3 | 5 | 8 | 14 | 17 | 26 | . . . | . . . |

h | 4 | 9 | 13 | 18 | 25 | . . . | . . . | . . . |

h | 10 | 12 | 19 | 24 | . . . | . . . | . . . | . . . |

h | 11 | 20 | 23 | . . . | . . . | . . . | . . . | . . . |

h | 21 | 22 | . . . | . . . | . . . | . . . | . . . | . . . |

. . . | . . . | . . . | . . . | . . . | . . . | . . . | . . . | . . . |

Here the numbers indicate the correspondence of squares in the two tapes:

v | 1 | v | 2 | 3 | h | 4 | 5 | 6 | v | 7 | 8 | 9 | 10 | h | 11 | . . . | . . . |

The head of a two dimensional tape moves one square up, down, left or right.

Let us simulate this head move with a one dimensional tape.

Let

For example, suppose that the head position is at 8 for the two dimensional tape in the above table, that is

If

Similarly formulas can be found for the head position on the one dimensional tape corresponding to move up, right or left on the two dimensional tape. Details are omitted. Thus some Turing machines with a one dimensional tape can simulate every move of a Turing machine with one two dimensional tape. Hence they are at least as powerful as Turing machines with a two dimensional tape. Since Turing machines with a two dimensional tape obviously can simulate Turing machines with a one dimensional tape, it can be said that they are equally powerful.

: Q ( {} )

A configuration for this kind of Turing machine must show the current state the machine is in and the state of each tape.

It can be proven that any language accepted by an n-tape Turing machine can be accepted by a one tape Turing machine and that any function computed by an n-tape Turing machine can be computed by a one tape Turing machine. Since the converses are obviously true, one can say that one tape Turing machines are as powerful as n-tape Turing machines.

: Q { H

where H

It can be easily seen that this type of Turing machines are as powerful as one tape Turing machines.

It turns out that this type of Turing machines are only as powerful as one tape Turing machines whose tape has a left end.

Formally a

As in the case of NFA, it is understood that a nondeterministic Turing machine at any configuration selects one combination of next state, tape symbol and head movement out of the set of triples without following any specific predetermined rule.

It can be shown that a nondeterministic Turing machine is only as powerful as a deterministic Turing machine.

For example consider the following nondeterministic Turing machine that accepts a

Given the string aa, it would proceed as follows to accept it:

( q

At the second and third configurations in the above sequence, it has two candidates for the next configuration: ( q

The tree for this case would be as follows:

One way to simulate a nondeterministic Turing machine, call it T

Many other variations of Turing machine are possible. However, it has been shown that none of them exceed the capability of basic deterministic Turing machine as far as accepting languages is concerned. In fact the Church's thesis conjectures that any so called computation done by humans or computers can be performed by a basic deterministic Turing machine.

Click True or Fals , then Submit.