Other Models of Turing Machines

Chapter 10

Other Models of Turing Machines

11/19/03

Standard TM from Chapter 9 is not the only definition
There are other variations in TM definition which may sometimes appear very different, but can be shown to be equivalent to the Standard TM
Variations are based on number of tapes, format of tape, etc.
We shall show that it is possible to have a non-deterministic TM
General meaning of “Equivalence” of automata (Def 10.2)
Two automata are equivalent iff they accept the same language.
Equivalence of classes
Two classes of automata C1 and C2 are equivalent:
if  M1 C1, M2  C2, such that L(M1) = L(M2),
then we say that C2 is at least as powerful as C1
If the converse is also true, then we say that C1 and C2 are equivalent classes.

Establishing Equivalence

Use “simulation”
Given an automaton M
Then M^ can simulate a computation on M, if M^ can “mimic” M as follows:
Let d0, d1, …, dn be a sequence of instantaneous descriptions on M
ie., d0 |-M d1 |-M … |-M dn
Where the notationdi |-M dk represents an instantaneous description transition from di to dkfor machine M
Then M^ simulates this computation if it does:
d^0 |- M^* d^1 |- M^* … |- M^* d^n
where
d^0 , d^1 , … are instantaneous descriptions such that,
each d^k is associated uniquely with a configuration in M.
Correspondence is not guaranteed in intermediate configurations in
Note:
d^i |-M^* d^i+1 (where * represents a series of instantaneous descriptions)

Some notes:
By observing d^i for M^, we can tell what M would have done (di ).
It can be arranged for both M and M^ to accept the same language & and thus are equivalent.

Some Variations of the Standard Turing Machine

TM with Stay Option
Allow for the head to remain in place in addition to being able to move left or right
: Qx Qxx{L, R, S}
where L is move left, R is move right, and S is “Stay” in place.
Theorem 10.1
The class of TM’s with the Stay Option is equivalent to the Standard TM class.
This can be easily shown by simulating the TM with the stay option with a Standard TM and it is obvious that a Standard TM can be simulated on a TM with the stay option simply by not using the stay option. See the text for the proof.
Multi-track Tape TM
A trivial twist on the Standard TM
Example: For the Standard TM definition (Def 9.1), a tape symbol can be a composite of symbols rather than just one symbol.
For the Multi-track TM, each element of the composite is on a different track:
Example:
Think of the three symbols a, b, and c as an encoding of a single symbol analogous to an ASCII code.
See text for more complete proof.
Semi-infinite Tape TM
Simulating a semi-infinite tape TM on a standard TM can be done by limiting the machine to right moves only.
We can simulate a standard TM, M with M^ (semi-infinite) as follows:

example, (qi, a) = (qk, c L) would map into:
^ (qi^, (a,b) ) = (qk^, (c,b), L)
^ (qk^, (#,#) ) = (pk^, (#,#), R)

Mult-tape TM

Useful for defining the “universal TM” – later.
: Q x n  Q x n x {L, R}n, …

Where n is the set of all n-tuples of  = xx … x
and

for n = 2, we have {L, R}n = {L,L L,R R,L R,R}, where n = # tapes

Example:

for (q0, a, e) = (q1, x, y, L, R)

Equivalence: simulation of a standard TM is easily done on a multi-tape TM.
Simulation of a multi-tape TM on a standard TM can easily be done with a 2n track tape machine for an n-tape TM (previously shown to be equivalent to a standard TM).
Each tape on the n-tape maps into a pair of tracks on the 2n-track machine.
the first track of a pair is the same as the corresponding tape on the n-tape TM
and
the second track of a pair is all blanks except for a “1” in the position of the head on the corresponding tape.
The state for the multi-track is the same as for the multi-tape for the same head configuration.
See text for details
Since the multi-track TM is equivalent to the Standard TM, then so is the multi-tape.

The Universal Turing Machine (Section 10.4)

Up to now, all TM’s were special purpose hard wired machines.
Once the “algorithm” is defined via the  functions, the TM can only do this one particular algorithm (hardwired). An algorithm was implemented in “hardware”: one machine, one algorithm.
We now define a re-programmable TM: the Universal TM.
This should remove any doubts about Turing’s Thesis
The Universal TM is a three tape TM

This single machine can simulate any defined Standard TM.
The Universal TM Mu is an automaton that, given as input the description of any Standard TM M, and a string w, can simulate the computation of M on w.

A standard (canonical) way of describing any standard TM
Assume that the states of M are: Q = {q1, q2, …, qn}
with q1 the initial state, and q2 the single final state.
let  = { a1, a2,…, an}

where a1 represents the blank symbol
Now encode both the states and the tape symbols with a unary representation of the subscript of that item:

For example:

q1 is represented by a 1

q2 by 11

q3 by 111

etc.
and similarly

a1 is represented by a 1

a2 is represented by 11, etc.

In addition represent “move left” by 1 and “move right” by 11

Use 0 to separate fields of 1’s.

Now any TM can be completely defined by  only.

Example: (q1, a2) = (q2, a3, L) is a quintuple, which can be encoded as:

… 10110110111010 …

q1 a2 q2 a3 L

Mu then can has an input alphabet that includes {0, 1} and is a multiple tape machine as shown:

Operation of Mu

For any M and w

Mu first looks at the contents of tapes 2 and 3 to determine the configuration of M
Then it consults tape 1 to see what M would do for this configuration.
Finally tapes 2 and 3 are modified to reflect results of the move, ie., write on M’s tape and go to next state.

where Tape 1 will keep the encoded delta function of M
Tape 2 will contain the contents of M’s tape (initially w)
Tape 3 keeps track of the current internal state of M

Some Observations about Turing Machines
Because of our method of constructing a Universal TM, we observe that all TM’s can be represented by finite strings of 1’s and 0’s
Definition: The set of all strings on {0,1}, ie., {0,1}* is countably infinite iff there is a 1:1 correspondence to the positive integers.
See Figure 10.17 – counting the rational numbers
Any set is countable if we can produce a method by which its elements can be written in some sequence – all elements would appear somewhere in this sequence.
This means that ordering is important. See the example of proving that the set of all rational numbers is countable section 10.4.
This method is called an enumeration procedure – a mechanical process, which means it can be done with a Turing Machine (as per Turing’s Thesis).

Any set for which an enumeration procedure (ie., a TM) exists is countable, because the enumeration procedure gives the required sequence. … Question what if there is no mechanical enumeration procedure? What if we cannot find a TM to do the job?
The mechanical procedure is a sufficient condition for proving a set is countable. We shall see that not every countable set has a mechanical procedure or a TM for doing it!
The converse is not necessarily true: finding the mechanical procedure is easier said than done! Top of page 269 (3rd ed) hints at this.

Definition 10.3 – how a TM can implement an enumeration procedure:
Let S be a set of strings on some alphabet , ie., S *. Non-trivially S is an infinite set.
If  an enumeration procedure for S, then there is a TM that can carry out the sequence:
q0 |-* qsx1#s1 |-* qsx2#s2 |-* …
where xi* - {#}, and si S
such that any si S is generated in a finite number of steps.
when the TM is in state qs, it means that the string following the # sign must be in S.
See example 10.3 for enumerating the words in {a, b, c}
What is wrong with listing all words stating with a, then those starting with b, ... in alphabetical order – as in a dictionary ... seems like this is what everybody does – is everyone wrong?
Enumeration on a TM gives the required sequence to be countable.
This enumeration procedure on a TM is not an algorithm since it will not terminate, but it is a well defined processes.
Theorem 10.3
The set of all Turing machines, although infinite, is countable.
We can encode each TM using 0 and 1. With this encoding, we construct the followingenumeration procedure:
Generate the next string in {0, 1}+in proper order
Check this string to see if it defines a TM, if so write it on the tape in the form of definition 10.3 above. If not ignore it.
Go to step 1.
Some stray thoughts: The TM is the mother of all languages in Chomsky’s Hierarchy. Is the set of all languages countable? Is the power set of +, where  = {a, b} countable? Up to now we only considered power sets of finite sets, + is infinite. . Is a TM really the mother of all languages?

Some Loose Ends

Non-deterministic Turing Machines (NTM)
Same definition as for deterministic version, except for 
: Qx 2Qxx{L, R}
The range of  is a set of possible transitions any of which can be chosen by the machine.
Example: (q0, a) = { (q1, b, R), (q2, c, L) } is a non-deterministic move, and represents the pair of moves:
q0aaa |- bq1aa
and
q0aaa |- q2caa
A nondeterministic TM accepts w if there exists any possible sequence of moves (even only one) such that:
q0w |-* x1qf x2
where qf is a final state
As long as the above holds, other (alternate) moves leading to non-final states or infinite loops are irrelevant – acceptance only depends on the existence of one “path” to qf.
Every NTM,  an equivalent DTM ==> NTM’s are a subset of DTM’s
Theorem 10.2: The class of nondeterministic TM’s and the class of deterministic TM’s (Standard TM’s) are equivalent.

Idea of the proof:
The proof of equivalence involves spawning self-replicating machines to simulate the alternate paths. A two-dimensional TM is used (which is equivalent to a standard TM, see section 10.2). Each time an alternate path is generated by a  transition, a new machine is replicated for this path: the tape content for this path is replicated along with a special adjacent track showing the position and state of the head for the newly replicated machine. See Figure 10.15. The simulating machine now searches for all “active track pairs”. These are tracks with a replicated machine ready to make a “next move”. They will be “bracketed” or bounded by special markers to be identifiable. Each active track is then “executed” for one move creating new machines as needed.

Conversely, certainly an NTM could simulate a DTM by simple not using nondeteterminism – similar to NFAs being special cases of DFAs.

Also see definition 10.2 on equivalence of classes of Automata.

Linear Bounded Automata (LBA)
Restrict the use of the TM tape
The tape has an “input field” delimited by the symbols [ on the left and ] on the right
All computation must be done in this field. and “[“ and “]” are not modifiable:
(qi, [ ) = (qk, [, R)
(qi, ] ) = (qk, ], L)
The LBA inserts a language between CFL’s and the most general languages of TM’s, namely context sensitive languages in Chomsky’s hierarchy. See later.

Chapter 10 Turing machine variations Fall 03 page