# CS代考计算机代写 Computational Complexity and Computability

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.