BU CS 332 – Theory of Computation
Lecture 11:
• TM Variants
Reading: Sipser Ch 3.2
• Closure Properties
Mark Bun March 1, 2020
The Basic Turing Machine (TM)
Tape 𝑎𝑏𝑎𝑎 Finite
…
Input
control
• Input is written on an infinitely long tape
• Head can both read and write, and move in both
directions
• Computation halts when control reaches
“accept” or “reject” state
3/3/2020 CS332 ‐ Theory of Computation 2
Example
𝑞0
⊔ → ⊔, 𝑅
accept
0 → 0,𝑅
⊔ → ⊔, 𝑅 𝑞1
0 → 0,𝑅 reject
Formal Definition of a TM
A TM is a 7‐tuple
• • • •
is a finite set of states
is the input alphabet (does not include ) is the tape alphabet (contains and )
is the transition function
• • •
…more on this later is the start state
3/3/2020
CS332 ‐ Theory of Computation
4
is the accept state
is the reject state ( )
TM Transition Function
means “move left” and means “move right”
means:
• Replace 𝑎 with 𝑏 in current cell
• Transition from state 𝑝 to state 𝑞
• Move tape head right
means:
• Replace 𝑎 with 𝑏 in current cell
• Transition from state 𝑝 to state 𝑞
• Move tape head left UNLESS we are at left end of tape, in
which case don’t move
3/3/2020 CS332 ‐ Theory of Computation 5
Configuration of a TM
A string with captures the state of a TM together with the contents of the tape
3/3/2020 CS332 ‐ Theory of Computation
6
…
Configuration of a TM: Formally
A configuration is a string where
• Tape contents = (followed by blanks • Current state =
• Tape head on first symbol of
and )
∗
3/3/2020 CS332 ‐ Theory of Computation
7
…
How a TM Computes
Start configuration:
One step of computation:
• • •
yields
if
yields yields
if if
Accepting configuration: Rejecting configuration:
= =
3/3/2020 CS332 ‐ Theory of Computation 8
How a TM Computes
• •
in state
OR
accepts input if there is a sequence of configurations such that:
•=
• •
yields for every
is an accepting configuration
3/3/2020
CS332 ‐ Theory of Computation
9
the set of all strings which accepts
is Turing‐recognizable if halts on halts on
for some TM
:
in state runs forever
Recognizers vs. Deciders
• •
in state
OR
• •
halts on
in state in state
the set of all strings which accepts
is Turing‐recognizable if halts on halts on
for some TM :
is (Turing‐)decidable if halts on
for some TM
3/3/2020
CS332 ‐ Theory of Computation 10
in state runs forever
which halts on every input
Back to Hilbert’s Tenth Problem
Computational Problem: Given a Diophantine equation, does it have a solution over the integers?
• is Turing‐recognizable
• is not decidable (1949‐70)
3/3/2020 CS332 ‐ Theory of Computation 11
TM Variants
3/3/2020 CS332 ‐ Theory of Computation 12
How Robust is the TM Model?
Does changing the model result in different languages being recognizable / decidable?
So far we’ve seen…
‐ We can require that FAs/PDAs have a single accept state
‐ (CFGs can always be put in Chomsky Normal Form)
‐ Adding nondeterminism does not change the languages recognized by finite automata
Turing machines have an astonishing level of robustness 3/3/2020 CS332 ‐ Theory of Computation 13
Extensions that do not increase the power of
the TM model
• TMs that are allowed to “stay put” instead of moving left or right
Proof that TMs with “stay put” are no more powerful: Simulation: Convert any TM with “stay put” into an
equivalent TM without
Replace every “stay put” instruction in with a move right instruction, followed by a move left instruction in
’
3/3/2020 CS332 ‐ Theory of Computation
14
Extensions that do not increase the power of
the TM model
• TMs with a 2‐way infinite tape, unbounded left to right Input
Tape …𝑎𝑏𝑎 …
Proof that TMs with 2‐way infinite tapes are no more
powerful:
Simulation: Convert any TM with 2‐way infinite tape into
a 1‐way infinite TM with a “two‐track tape”
3/3/2020 CS332 ‐ Theory of Computation 15
Formalizing the Simulation
New tape alphabet: New state set:
means “
, working on upper track” , working on lower track”
means “
New transitions:
𝑞, , 𝑏,𝑎 ,𝑅 Also need new transitions for moving right, lower track, hitting $,
If𝛿 𝑝,𝑎 𝑞,𝑏,𝐿,let𝛿′ 𝑝, , 𝑎,𝑎
initializing input into 2‐track format
3/3/2020 CS332 ‐ Theory of Computation 16
TMs are equivalent to…
• TMs with “stay put”
• TMs with 2‐way infinite tapes
• Multi‐tape TMs
• Nondeterministic TMs
• Random access TMs
• Enumerators
• Finite automata with access to an unbounded queue = 2‐ stack PDAs
• Primitive recursive functions
• Cellular automata …
3/3/2020 CS332 ‐ Theory of Computation 17
Church‐Turing Thesis
The equivalence of these models is a mathematical theorem
Church‐Turing Thesis: Each of these models captures our intuitive notion of algorithms
The Church‐Turing Thesis is not a mathematical statement!
3/3/2020 CS332 ‐ Theory of Computation 18
Multi‐Tape TMs
Finite control
𝑏𝑏𝑎𝑎𝑎 𝑎𝑏⊔𝑎𝑎 ⊔𝑏𝑎𝑎𝑐
Fixed number of tapes (can’t change during computation)
Transition function
3/3/2020 CS332 ‐ Theory of Computation 19
Multi‐Tape TMs are Equivalent to Single‐Tape TMs
Theorem: Every ‐tape TM with can be simulated by an equivalent single‐tape TM
Finite control
𝑏𝑏𝑎𝑎 𝑎𝑏⊔𝑎 ⊔𝑏𝑎𝑎
Finite control
𝑏𝑏𝑎𝑎#𝑎𝑏⊔𝑎#⊔𝑏𝑎𝑎𝑐# CS332 ‐ Theory of Computation 20
3/3/2020