Nov. 3, 2021 (Wednesday) Chapter 3: Church-Turing Thesis
6 Variant 3: Multiple Tapes
6.1 Description of the variant
Let T2 denote a TM with two semi-infinite tapes and with the stay option. Assume that for T2,
Σ = {a, b}, and Γ = Σ ∪ {⊔}. T2 with two tapes has the following transition function.
Q× Γ× Γ→ Q× Γ× {L, R, S} × Γ× {L, R, S}
For T2, we assume that initially an input string is stored on the first tape, and all other tapes are
empty. For example, if the input string is abab, initially we have
b
Turing Machine
T2
tape 1
tape 2
aba
As an example, T2 can take the following transition if the current state is p, the current symbol
on tape 1 is a, and the current symbol on tape 2 is ⊔. This transition replaces a with b on tape
1, moves the tape head of tape 1 to the right, replaces ⊔ with a on tape 2, and does not move the
tape head of tape 2.
p q
a→ b,R, ⊔ → a, S
After taking the above transition, we have
Turing Machine
T2
tape 1
tape 2
abb b
a
8
6.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 multiple tapes, we can construct an equivalent standard TM. Let T2 denote a TM
with multiple tapes, and T1 denote the equivalent standard TM.
Mapping of the tapes: For this variant, we demonstrate the string mapping method, where a
string refers to all symbols from the left-most cell to the right-most non-blank cell (or the right-most
visited cell if it is further right) on a T2’s tape. T1 should remember two types of information:
• The symbols on each tape of T2: T1 uses its tape to store the concatenation of the strings on
all T2’s tapes, with symbol # as a delimiter to separate the strings on different T2 tapes.
• The position of each tape head of T2: T1 remembers them by introducing new symbols. If
Γ of T2 contains {a, b,⊔}, then Γ of T1 contains {a, b,⊔, a˙, b˙, ⊔˙,#}. A symbol with a dot is
used to mark the current position of the corresponding tape head. Note that, between any
two #’s, there is one and only one symbol with a dot.
For example, to remember the initial information of all tapes of T2 with an input string abab,
T1 has the following symbols on its tape.
#baba# #
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.
Let’s consider how T1 simulates the transitions of T2. If T2 has two tapes and Γ of T2 contains
{a, b,⊔}, then from any state p of T2, there are at most 9 transitions, as listed below.
δ(p, a, a) = (q1, ...)
δ(p, a, b) = (q2, ...)
δ(p, a,⊔) = (q3, ...)
δ(p, b, a) = (q4, ...)
δ(p, b, b) = (q5, ...)
δ(p, b,⊔) = (q6, ...)
δ(p,⊔, a) = (q7, ...)
δ(p,⊔, b) = (q8, ...)
δ(p,⊔,⊔) = (q9, ...)
9
We can design T1 according to the following flowchart to simulate the above 9 transitions from
state p of T2.
δ
find the symbol under
the second tape
head of T2
find the symbol under
the second tape
head of T2
find the symbol under
the second tape
head of T2
head of T2
under the first tape
find the symbolp
if it is a
if it is b
if it is
if it is b
if it is
if it is a
if it is b
if it is
if it is a
if it is b
if it is
if it is a
q2
q3
q4
q5
q8
q9
q7
q6
q1
update the tape
according to (p, b, a)
update the tape
according to (p, , a)
update the tape
according to (p, a, )
update the tape
according to (p, a, b)
update the tape
update the tape
according to (p, b, b)
update the tape
according to (p, b, )
update the tape
according to (p, , b)
update the tape
according to (p, , )
according to (p, a, a)δ
δ
δ
δ
δ
δ
δ
δ
7 Algorithms and The Church-Turing Thesis
As the (standard) Turing machine model is so powerful, it is generally accepted that any algorithm
that can be carried out at all (by a single person, a finite number of people, a computer, or a
computational model) can be carried out by a (standard) Turing machine. This statement is referred
to as The Church-Turing Thesis.
The above statement cannot be formally proved, and below is an informal summary of some
reasons why the statement is generally accepted.
• Many computational models (e.g., DFA/NFA/RE, CFG/PDA, TMVariants, Context-Sensitive
Grammars, Mul-Stack PDA, λ-calculus, µ-recursive functions, register machines, and quan-
tum computers) have been proposed, but none of them is more powerful than the standard
Turing machine model. Note that, many of them are just more efficient (i.e., more quickly
solve a problem) than the (standard) Turing machine model.
• We have not found out any type of algorithms that can be carried out by a single person, a
finite number of people, or a computer, but not by a (standard) Turing machine.
The importance of the Church-Turing thesis is that once we accept that it is true, we can then
study the computability theory: which problems can be solved by the most powerful model, and
which problems cannot be solved even by the most powerful model. In addition, we can formally
define an algorithm: An algorithm is a procedure that can be executed by a (standard) Turing
machine.
Textbook reading: Pages 176-177, and Pages 181-182 Section “Equivalence with other models”
10












































































































































学霸联盟