Variants of Turing machines model:

1) Multiple tape Turing machines

2) Non-deterministic Turing machines
3) Enumerator
4) Linear bounded automaton
5) The universal Turing machine

1
 Equivalence of Turing Machine
variants:
Two models of TM variants are equivalent
if one can be simulated by the other

2
 Multitape Turing machine:
An ordinary Turing machine with several tapes.
• Each tape has its own head for reading and
writing.
• Initially the input appears on tape 1, and the
others start out blank.
• The transition function is changed to allow for
reading, writing, and moving the heads on
some or all of the tapes simultaneously.

3
 Formal definition of transition function
of multitape Turing machine
: Q x k → Q x k x {L, R, S}k, where k is the
number of tapes, S is stay put (do not move the head).

• The expression (qi, a1, . . . , ak) = (qj, b1, . . . , bk , L,

R, . . . , L) means that, if the machine is in state qi and
heads 1 through k are reading symbols a1 through ak,
the machine goes to state qj, writes symbols b1
through bk, and directs each head to move left or
right, or to stay put, as specified.

4
 Theorem: Every multitape Turing machine
has an equivalent single-tape Turing machine.
Proof : Convert a multi-tape TM M to an
equivalent single-tape TM S.
Simulate M with S.
• Let M has k tapes.
• S simulates the effect of k tapes by storing
their information on its single tape.
▪ S uses the new symbol # as a delimiter to
separate the contents of the different tapes.

5
 Proof: (cont.)

▪ S keeps track of the locations of the heads

by writing a tape symbol with a dot above it
to mark the place where the head on that
tape would be.
• These are "virtual" tapes and heads.
• The "dotted" tape symbols are new
symbols added to the tape alphabet.

6
Representing three tapes with one

7
 Nondeterministic Turing machine
It is a Turing machine in which at any point in a
computation the machine may proceed according to
several possibilities.
• The transition function for a nondeterministic Turing
machine has the form : Q x  → P(Q x  x {L, R})
(q, a)={(q1, b1, L), . . . (qk, bk, R)}
• The computation is a tree whose branches correspond
to different possibilities for the machine.
• If some branch of the computation leads to the accept
state, the machine accepts its input.

8
 Theorem : Every nondeterministic Turing
machine has an equivalent deterministic
Turing machine.
Idea of proof:
Simulate any nondeterministic TM N with a
deterministic TM D.
• Let D try all possible branches of N's
nondeterministic computation.
• If D ever finds the accept state on one of these
branches, D accepts.
• Otherwise, D's simulation will not terminate.

9
 Idea of Proof (cont.)

View N's computation on an input w as a tree.

• Each branch of the tree represents one of the
branches of the non-determinism.
• Each node of the tree is a configuration of N.
• The root of the tree is the start configuration.
• The TM D searches this tree for an accepting
configuration.

10
 Proof
The simulating deterministic TM D has three
tapes.
• Tape 1 always contains the input string and is
never altered.
• Tape 2 maintains a copy of N's tape on some
branch of its nondeterministic computation.
• Tape 3 keeps track of D's location in N's
nondeterministic computation tree.

11
Figure : Deterministic TM D simulating
nondeterministic TM N

12
 Data representation on tape 3
Tape 3 contains a string over ∑b. It represents the
branch of N's computation from the root to the node
addressed by that string, unless the address is invalid.

• Every node in the tree can have at most b children,

where b is the size of the largest set of possible
choices given by N's transition function.
• To every node in the tree, assign an address that is a
string over the alphabet ∑b = {1, 2, . . . , b}.

13
 Description of TM D
1.Initially tape 1 contains the input w, and tapes 2 and 3
are empty.
2.Copy tape 1 to tape 2.
3.Use tape 2 to simulate N with input w on one branch
of its nondeterministic computation.
• Before each step of N consult the next symbol on
tape 3 to determine which choice to make among
those allowed by N's transition function.
• If no more symbols remain on tape 3 or if this
nondeterministic choice is invalid, abort this
branch by going to stage 4.
14
 Description of TM D (cont.)
• Also go to stage 4 if a rejecting configuration is
encountered.
• If an accepting configuration is encountered, accept
the input.
4. Replace the string on tape 3 with the
lexicographically next string.
• Simulate the next branch of N's computation by
going to stage 2.

15
Corollary: A language is Turing-recognizable
if and only if some nondeterministic Turing
machine recognizes it.
Proof:
• Any deterministic TM is automatically a
nondeterministic TM, and so one direction of
this theorem follows immediately.

• The other direction follows from the theorem

that every nondeterministic TM has an
equivalent deterministic TM.

16
 Nondeterministic Turing machine
Decider
A nondeterministic Turing machine is called a
decider if all branches halt on all inputs.

• If modified so that a nondeterministic TM N

always halts on all branches of its
computation, the deterministic TM D will
always halt.

17
 Corollary: Decidable language

A language is decidable if and only if some

nondeterministic Turing machine decides it.

18
 Enumerator :
It is a Turing machine with an attached printer.
• The Turing machine can use that printer as an
output device to print strings.
• Every time the Turing machine wants to add a
string to the list, it sends the string to the
printer.
Turing-recognizable language is also called
recursively enumerable language from this type
of Turing machine variant ,viz., enumerator.
19
Enumerator : (Schematic diagram)

20
 Enumerator : (cont.)

• An enumerator E starts with a blank input tape.

• If the enumerator doesn't halt, it may print an
infinite list of strings.
• The language enumerated by E is the
collection of all the strings that it eventually
prints out.

21
Theorem: A language is Turing-recognizable if
and only if some enumerator enumerates it.
Proof :
1. Show that if there is an enumerator E that
enumerates a language A, a TM M recognizes A.
The TM M works in the following way.
M = "On input w:
1. Run E. Every time that E outputs a string, compare
it with w.
2. If w ever appears in the output of E, accept."
Clearly, M accepts those strings that appear on E's
list.

22
 Proof : (cont.)

2. Show If TM M recognizes a language A, we

can construct the following enumerator E for
A. Say that s1, s2, s3, . .. is a list of all possible
strings in ∑*.
E = "Ignore the input.
1. Repeat the following for i = 1,2,3, . . .
2. Run M for i steps on each input, s1, s2,. . . si.
3. If any computations accept, print out the
corresponding sj."
23
 Proof : (cont.)

• If M accepts a particular string s, it will appear

on the list generated by E.
• It will appear on the list infinitely many times
because M runs from the beginning on each
string for each repetition of step 1.
• This procedure gives the effect of running M
in parallel on all possible input strings.

24
 Linear bounded automaton
A linear bounded automaton is a Turing machine with a
limited amount of memory.
• For an input of length n, the amount of memory
available is linear in n.
• The tape head isn't permitted to move off the portion
of the tape containing the input.

25
 Linear bounded automaton as
decider
During simulation of string,
• The LBA may halt and accept or reject the
string,
Or
• Detect looping by simulating the LBA for the
number of steps predetermined for it.

26
Lemma: Maximum number of steps
of simulation of LBA is qngn
Proof:
Let M be an LBA with a tape of length n , states
q and symbols in the tape alphabet g.
Then there are
• gn possible number of strings of tape symbols
and
• qngn distinct configurations of M (maximum
number of steps of simulation of LBA ).
(number of location of head = tape length n)
27
 Use of Linear bounded automaton

• Every CFL can be decided by an LBA.

• The LBAs can be used as deciders for
languages ADFA , ACFG, EDFA, and ECFG .

28
 The universal Turing machine

A Turing machine that is capable of simulating

any other Turing machine from the description of
that machine.
• Input of Universal Turing Machine is
description of transitions of TM M and its
input string.

29
 Contents of Universal Turing
machine
Universal turing machine is three tape multitape
turing machine
• Tape 1 contains description of TM M
• Tape 2 contains tape contents of M
• Tape 3 contains state of M

30
 Encoding of Turing machine M
Describe Turing machine as a string of symbols.

31
 Alphabet Encoding

Symbols: a b c d 

Encoding: 1 11 111 1111

Fall 2006 Costas Busch - RPI 32

 State Encoding

States: q1 q2 q3 q4

Encoding: 1 11 111 1111

33
Head Move Encoding

Move: L R

Encoding: 1 11

34
 Transition Encoding

Transition:  (q1, a) = (q2 , b, L)

Encoding: 1 0 1 0 11 0 11 0 1

separator

35
 Turing Machine Encoding
Transitions:
 (q1, a) = (q2 , b, L)  (q2 , b) = (q3 , c, R)

Encoding:
1 0 1 0 11 0 11 0 1 00 11 0 110 111 0 111 0 11
separator
36
 Tape 1 - Binary encoding of the
simulated machine M

Tape 1
1 0 1 0 11 0 11 0 10011 0 1 10 111 0 111 0 1100

Head location

37
 The set of Turing machines as
language
• A Turing Machine is described with a binary
string of 0’s and 1’s
• Each string of this language is the binary
encoding of a Turing Machine
L = { 010100101, (Turing Machine 1)
00100100101111,
111010011110010101, (Turing Machine 2)
…… }

38