Computational Complexity and Computability
Lecture 4 – Turing Machine Variations
Koushik Pal
University of Toronto
January 20, 2021
Standard Model
Doubly infinite tape
Transition function: δ : Q × Γ → Q × Γ × {L, R}
… …
move left/right
⊔
a
b
e
t
⊔
Variations
TM
TM
TM
TM
TM
Nondeterministic TM
with stay option
with singly infinite tape with reset option
with multiple tapes
with multidimensional tape
Same Power
Definition
Two TMs M and M are said to be equivalent if they recognize the same language, i.e., L(M) = L(M).
N.B.: L(M) := {w ∈ Σ∗ | M accepts w}.
Definition
Two classes C and C of TMs are said to have the same (computation) power if for each TM M ∈ C there is an equivalent TM M ∈ C, and vice versa.
Technique to prove same power
To prove two classes have the same power, “simulate” an arbitrary machine of one class with a machine of the other class.
Stay Option
Transition function: δ : Q × Γ → Q × Γ × {L, R, S}
… …
move left/right/stay
⊔
a
b
e
t
⊔
Stay Option
Theorem
The class of TMs with stay option has the same power as the class of standard TMs.
Proof.
A standard TM is trivially a TM with stay option that never uses its S move.
Conversely, to simulate a TM with stay option on a standard TM, simulate L and R moves as usual, and replace an S move with an R move followed by an L move. More specifically,
TM with stay option q
a → b, S
a → b, R
q
′ x → L (∀x ∈ Γ ) q
Standard TM
q
q
Singly Infinite Tape
Semi-infinite tape
a
b
e
t
⊔
…
move left/right
Note: Need special care when trying to move head left of the leftmost cell.
Singly Infinite Tape
Theorem
The class of TMs with singly infinite tape has the same power as the class of standard TMs.
Proof.
Simulating a TM with singly infinite tape on a standard TM is trivial: follow the instructions as is.
To simulate a standard TM on a TM with a singly infinite tape, choose a reference point on the doubly infinite tape and split it into two halves – a left half and right half. The intention is to move “normally” on the right half and “in reverse” on the left half, and properly transition from one to the other at the border.
To do that, define
states qiL and qiR for each state qi of the standard TM, and
the tape language of the new TM as
Γ′ =Σ∪{⊔}∪(Σ∪{⊔})×(Σ∪{⊔})∪{($,$)}.
Singly Infinite Tape
⊔
a
b
e
s
t
⊔
Standard TM
reference point
… …
$
e
s
t
⊔
$
b
a
⊔
⊔
TM with singly infinite tape and multiple “tracks”
… …
($, $)
(e, b)
(s, a)
(t, ⊔)
(⊔, ⊔)
TM with singly infinite tape
…
Singly Infinite Tape
Transitions
R transition of the standard machine Standard TM q
a → b, R
q
(∀x ∈ Γ)
qR
(∀x ∈ Γ)
qL
TM with singly infinite tape qR qL
(a,x) → (b,x),R
(x,a) → (x,b),L
analogous for an L transition of the standard machine transition at the left end
TM with singly infinite tape qR qL
($,$) → ($,$),R
($,$) → ($,$),R
qL qR
Multiple Tapes
⊔
a
b
e
t
⊔
Tape Tape
… …
… …
.
… …
⊔
g
q
x
⊔
⊔
l
m
p
r
b
⊔
Tape k
Transition function: δ : Q × Γ k → Q × Γ k × {L, R, S}k δ(qi,a,…,ak) = (qj,b,…,bk,L,R,…,S,L).
Note: Initially, the machine starts with the input on the first tape and all other tapes being empty.
Multiple Tapes
Theorem
The class of TMs with multiple tapes has the same power as the class of standard TMs.
Proof.
A standard TM is trivially a TM with multiple tapes that doesn’t use its other tapes.
To simulate a TM M with multiple tapes on a standard TM S, copy the contents of each tape of M on the single tape of S separated by a delimiter (say, $). To track the location of the head on each tape, use new tape symbols which are old symbols with a “dot” on top, for example.
As an example, the initial configuration would be represented as:
… …
⊔
$
w ̇
w
…
wn
$
⊔ ̇
$
⊔ ̇
$
…
$
⊔
Multiple Tapes
A single move on S involves
scanning the tape from the first $, which marks the left-hand
end, to the (k + )st $, which marks the right-hand end;
determining the symbols under the heads, aka the symbols
with the dots;
making a second pass to update those entries according to the
way that M’s transition function dictates; and,
marking the appropriate symbols with a “dot” for the next
iteration.
Note: If at any point S moves one of the heads to the right/left onto a $, this action signifies that M has moved the corresponding head onto the previously unread blank portion of that tape. In that case, S writes a blank symbol on this tape cell and shifts the tape contents, from this cell until the rightmost/leftmost $, one unit to the right/left. Then it continues the simulation as before.
Computation Power is not same as Efficiency!
Consider a TM on the alphabet Σ = {, , §} for the language L = {y§y | y ∈ {,}∗}.
A standard TM takes Θ(n) steps by matching the first character with the first character, moving back, matching second with second, moving back, matching third with third, etc.
But a 2-tape TM takes Θ(n) steps by first copying the second half of the string after the delimiter to the second tape and matching character by character by using the two tape heads in one pass.