Nov. 1, 2021 (Monday) Chapter 3: Church-Turing Thesis
3 Variants of Standard Turing Machines
Let T1 denote a standard TM, which has the following transition function.
Q× Γ→ Q× Γ× {L, R}
If the input string is abab, initially we have the following symbols on its tape.
(left, right)
a b a b
Turing Machine T1
There are some variants of the standard Turing machines.
• Stay Option: In addition to moving to the left or to the right, the tape head can stay at
the current position.
• A Bi-infinite Tape: The tape is infinite in both directions.
• Multiple Tapes: A Turing machine has multiple tapes, each with its own tape head.
• A Multi-Dimensional Tape: A Turing machine has a d-dimensional tape. For example, a
Turing machine with a two-dimensional tape can move its tape head in four different directions
(left, right, up, and down).
• Nondeterministic Turing machines: A Turing machine may split into multiple copies to
try different possibilities.
Which model is the most powerful one, in terms of the class of languages recognized by the
model? It is easy to see that a standard TM is a special case of all above TM variants. Therefore,
all above models are at least as powerful as the standard TM model.
4 Variant 1: Stay Option
4.1 Description of the variant
Let T2 denote a TM with the stay option. We assume that for T2, Σ = {a, b}, and Γ = Σ ∪ {⊔}
T2 has the following transition function. e.g., δ(p, a) = (q, b, S)
Q× Γ→ Q× Γ× {L, R, S}
4
If the input string is abab, initially we have
(left, right, stay)
a b a b
Turing Machine T2
4.2 Is this variant more powerful?
No, this variant is not more powerful than the standard TM model. Because we can construct an
equivalent standard TM for a TM with the stay option.
Let T2 denote a TM with the stay option, and let T1 denote the equivalent standard TM for T2.
We construct T1 by modifying T2. We only need to modify T2’s transitions with the stay option as
follows, and keep all other T2’s transitions.
q
, L
p q
a b, S
a b, R
tmp
b b, L
a a, L
T2:
T1: p
Consider whether we can move to the left first, and then move back to the right. No! Because
if the tape head is currently on the left-most cell, then we have a problem!
Finally, we can see that
• Since the standard TMmodel is a special case of this variant, the class of languages recognized
by all standard TMs ⊆ the class of languages recognized by all TMs with the stay option.
• Since we can construct an equivalent standard TM for a TM with the stay option, the class
of languages recognized by all standard TMs ⊇ the class of languages recognized by all TMs
with the stay option.
Therefore, the class of languages recognized by all standard TMs = the class of languages recognized
by all TMs with the stay option. That is, this variant has the same power as the standard TM
model.
5
5 Variant 2: A Bi-infinite Tape
5.1 Description of the variant
Let T2 denote a TM with a bi-infinite tape. We assume that for T2, Σ = {a, b}, and Γ = Σ ∪ {⊔}.
T2 has the following transition function.
Q× Γ→ Q× Γ× {L, R}
With a bi-infinite tape that is infinite in both directions, T2 can move to any direction at any
position. Recall that a standard TM cannot move to the left, if its tape head is currently on the
left-most cell. We assume that initially the tape head stays on the left-most symbol of an input
string. For example, if the input string is abab, we have
T2
a b a b
Tape infinite in both directions
Turing Machine
5.2 Is this variant more powerful?
No, this variant is not more powerful than the standard TM model. To prove this, we show that
for any TM with a bi-infinite tape, we can construct an equivalent standard TM. Let T2 denote a
TM with a bi-infinite tape, and let T1 denote the equivalent standard TM for T2.
Mapping of the tapes: We need to find a mapping between the tapes of T1 and T2, so that we
can use T1’s tape to store the information of T2’s tape. There are two possible mappings.
• Cell-to-cell mapping: each cell on T2’s tape is mapped to a unique cell on T1’s tape.
• String mapping: T1’s tape stores the string on T2’s tape (from the left-most non-blank/visited
symbol to the right-most non-blank/visited symbol on T2’s tape).
For this variant, we demonstrate the cell-to-cell mapping. Initially, the tape head of T2 stays
on the left-most symbol of an input string. We use this initial head position as a reference point.
We map all the cells on the right-hand side of the reference point to the even-position cells of T1’s
tape, and all the cells on the left-hand side of the reference point to the odd-position cells (except
the first cell) of T1’s tape.
For example, to remember the initial information of the tape of T2 with input string abab, T1
should have the following symbols on its tape.
6
coressponding T2 cell
a b a b
1−3−4−5 −2 −1 2 3 4 5
reference point
Tape of T2
5
# a b a b
−11 2 −2 3 −3 4 −4
Tape of T1
Machine: Machine T1 consists of two sub-machines. The first sub-machine converts an input string
from the original format to the new format. The second sub-machine then simulates machine T2.
The following shows how T1 simulates a T2 transition that moves its tape head one cell to the
left. Because T1 behaves differently depending on whether the tape head is on the left or right sides
of the reference point, T1 uses the following 7 states to simulate states p and q of T2.
• states Lp and Rp of T1 corresponds to state p when T2’s tape head is on the left-hand and
right-hand sides of the reference point, respectively.
• state Lq and Rq of T1 corresponds to state q when T2’s tape head is on the left-hand and
right-hand sides of the reference point, respectively.
• states tmp1 and tmp2 are temporary states of T1.
, R
, L
p q
a b, L
a b, R
tmp1
b b, R
a b, L
# #, R
Rqtmp2Rp
Lp Lq
a a, R
b b, L
a a, L
T2:
T1:
Similarly, T1 can also simulate a T2 transition that moves its tape head one cell to the right.
Textbook reading: None
7































































































































学霸联盟

Nov. 1, 2021 (Monday) Chapter 3: Church-Turing Thesis
3 Variants of Standard Turing Machines
Let T1 denote a standard TM, which has the following transition function.
Q× Γ→ Q× Γ× {L, R}
If the input string is abab, initially we have the following symbols on its tape.
(left, right)
a b a b
Turing Machine T1
There are some variants of the standard Turing machines.
• Stay Option: In addition to moving to the left or to the right, the tape head can stay at
the current position.
• A Bi-infinite Tape: The tape is infinite in both directions.
• Multiple Tapes: A Turing machine has multiple tapes, each with its own tape head.
• A Multi-Dimensional Tape: A Turing machine has a d-dimensional tape. For example, a
Turing machine with a two-dimensional tape can move its tape head in four different directions
(left, right, up, and down).
• Nondeterministic Turing machines: A Turing machine may split into multiple copies to
try different possibilities.
Which model is the most powerful one, in terms of the class of languages recognized by the
model? It is easy to see that a standard TM is a special case of all above TM variants. Therefore,
all above models are at least as powerful as the standard TM model.
4 Variant 1: Stay Option
4.1 Description of the variant
Let T2 denote a TM with the stay option. We assume that for T2, Σ = {a, b}, and Γ = Σ ∪ {⊔}
T2 has the following transition function. e.g., δ(p, a) = (q, b, S)
Q× Γ→ Q× Γ× {L, R, S}
4
If the input string is abab, initially we have
(left, right, stay)
a b a b
Turing Machine T2
4.2 Is this variant more powerful?
No, this variant is not more powerful than the standard TM model. Because we can construct an
equivalent standard TM for a TM with the stay option.
Let T2 denote a TM with the stay option, and let T1 denote the equivalent standard TM for T2.
We construct T1 by modifying T2. We only need to modify T2’s transitions with the stay option as
follows, and keep all other T2’s transitions.
q
, L
p q
a b, S
a b, R
tmp
b b, L
a a, L
T2:
T1: p
Consider whether we can move to the left first, and then move back to the right. No! Because
if the tape head is currently on the left-most cell, then we have a problem!
Finally, we can see that
• Since the standard TMmodel is a special case of this variant, the class of languages recognized
by all standard TMs ⊆ the class of languages recognized by all TMs with the stay option.
• Since we can construct an equivalent standard TM for a TM with the stay option, the class
of languages recognized by all standard TMs ⊇ the class of languages recognized by all TMs
with the stay option.
Therefore, the class of languages recognized by all standard TMs = the class of languages recognized
by all TMs with the stay option. That is, this variant has the same power as the standard TM
model.
5
5 Variant 2: A Bi-infinite Tape
5.1 Description of the variant
Let T2 denote a TM with a bi-infinite tape. We assume that for T2, Σ = {a, b}, and Γ = Σ ∪ {⊔}.
T2 has the following transition function.
Q× Γ→ Q× Γ× {L, R}
With a bi-infinite tape that is infinite in both directions, T2 can move to any direction at any
position. Recall that a standard TM cannot move to the left, if its tape head is currently on the
left-most cell. We assume that initially the tape head stays on the left-most symbol of an input
string. For example, if the input string is abab, we have
T2
a b a b
Tape infinite in both directions
Turing Machine
5.2 Is this variant more powerful?
No, this variant is not more powerful than the standard TM model. To prove this, we show that
for any TM with a bi-infinite tape, we can construct an equivalent standard TM. Let T2 denote a
TM with a bi-infinite tape, and let T1 denote the equivalent standard TM for T2.
Mapping of the tapes: We need to find a mapping between the tapes of T1 and T2, so that we
can use T1’s tape to store the information of T2’s tape. There are two possible mappings.
• Cell-to-cell mapping: each cell on T2’s tape is mapped to a unique cell on T1’s tape.
• String mapping: T1’s tape stores the string on T2’s tape (from the left-most non-blank/visited
symbol to the right-most non-blank/visited symbol on T2’s tape).
For this variant, we demonstrate the cell-to-cell mapping. Initially, the tape head of T2 stays
on the left-most symbol of an input string. We use this initial head position as a reference point.
We map all the cells on the right-hand side of the reference point to the even-position cells of T1’s
tape, and all the cells on the left-hand side of the reference point to the odd-position cells (except
the first cell) of T1’s tape.
For example, to remember the initial information of the tape of T2 with input string abab, T1
should have the following symbols on its tape.
6
coressponding T2 cell
a b a b
1−3−4−5 −2 −1 2 3 4 5
reference point
Tape of T2
5
# a b a b
−11 2 −2 3 −3 4 −4
Tape of T1
Machine: Machine T1 consists of two sub-machines. The first sub-machine converts an input string
from the original format to the new format. The second sub-machine then simulates machine T2.
The following shows how T1 simulates a T2 transition that moves its tape head one cell to the
left. Because T1 behaves differently depending on whether the tape head is on the left or right sides
of the reference point, T1 uses the following 7 states to simulate states p and q of T2.
• states Lp and Rp of T1 corresponds to state p when T2’s tape head is on the left-hand and
right-hand sides of the reference point, respectively.
• state Lq and Rq of T1 corresponds to state q when T2’s tape head is on the left-hand and
right-hand sides of the reference point, respectively.
• states tmp1 and tmp2 are temporary states of T1.
, R
, L
p q
a b, L
a b, R
tmp1
b b, R
a b, L
# #, R
Rqtmp2Rp
Lp Lq
a a, R
b b, L
a a, L
T2:
T1:
Similarly, T1 can also simulate a T2 transition that moves its tape head one cell to the right.
Textbook reading: None
7