Microsoft PowerPoint – CS332-Lec10-ann
BU CS 332 – Theory of Computation
Lecture 10:
• Turing Machines
• TM Variants and Closure
Properties
Reading:
Sipser Ch 3.1‐3.3
Mark Bun
February 24, 2021
The Basic Turing Machine (TM)
2/24/2021 CS332 ‐ Theory of Computation 2
Tape 𝑎 𝑏 𝑎 𝑎
Finite
control
…
• Input is written on an infinitely long tape
• Head can both read and write, and move in both
directions
• Computation halts as soon as control reaches
“accept” or “reject” state
Input
0 → 0,𝑅
⊔ → ⊔,𝑅
accept
reject
0 → 0,𝑅
⊔ → ⊔,𝑅
Example
𝑞0 𝑞1
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
• is the start state
• is the accept state
• is the reject state ( )
2/24/2021 CS332 ‐ Theory of Computation 4
Configuration of a TM: Formally
A configuration is a string where and ∗
• Tape contents = (followed by blanks )
• Current state =
• Tape head on first symbol of
2/24/2021 CS332 ‐ Theory of Computation 5
…
Example:
How a TM Computes
Start configuration:
One step of computation:
• yields if
• yields if
• If we are at the left end of the tape in configuration ,
what configuration do we reach if ?
2/24/2021 CS332 ‐ Theory of Computation 6
How a TM Computes
Start configuration:
One step of computation:
• yields if
• yields if
• yields if
Accepting configuration: =
Rejecting configuration: =
2/24/2021 CS332 ‐ Theory of Computation 7
How a TM Computes
accepts input if there is a sequence of configurations
such that:
• =
• yields for every
• is an accepting configuration
the set of all strings which accepts
is Turing‐recognizable if for some TM :
• halts on in state
• halts on in state OR
runs forever on
2/24/2021 CS332 ‐ Theory of Computation 8
Recognizers vs. Deciders
the set of all strings which accepts
is Turing‐recognizable if for some TM :
• halts on in state
• halts on in state OR
runs forever on
is (Turing‐)decidable if for some TM
which halts on every input
• halts on in state
• halts on in state
2/24/2021 CS332 ‐ Theory of Computation 9
Recognizers vs. Deciders
Which of the following is true about the relationship
between decidable and recognizable languages?
a) The decidable languages are a subset of the
recognizable languages
b) The recognizable languages are a subset of the
decidable languages
c) They are incomparable: There might be decidable
languages which are not recognizable and vice versa
2/24/2021 CS332 ‐ Theory of Computation 10
Example: Arithmetic on a TM
The following TM decides :
On input string :
1. Check is formatted correctly
2. For each appearing in :
3. For each appearing in :
4. Attempt to cross off a . If none exist, reject.
5. If all ’s are crossed off, accept. Else, reject.
2/24/2021 CS332 ‐ Theory of Computation 11
Example: Arithmetic on a TM
The following TM decides :
On input string :
1. Scan the input from left to right to determine whether
it is a member of ∗ ∗ ∗
2. Return head to left end of tape
3. Cross off an if one exists. Scan right until a occurs.
Shuttle between ’s and ’s crossing off one of each
until all ’s are gone. Reject if all ’s are gone but some
’s remain.
4. Restore crossed off ’s. If any ’s remain, repeat step 3.
5. If all ’s are crossed off, accept. Else, reject.
2/24/2021 CS332 ‐ Theory of Computation 12
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)
2/24/2021 CS332 ‐ Theory of Computation 13
TM Variants
2/24/2021 CS332 ‐ Theory of Computation 14
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 NFAs have a single accept state
‐ Adding nondeterminism does not change the languages
recognized by finite automata
‐ Bonus problem on test: Allowing DFAs to have multiple
passes over their input does not increase their power
Turing machines have an astonishing level of robustness
2/24/2021 CS332 ‐ Theory of Computation 15
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
• Primitive recursive functions
• Cellular automata
…
2/24/2021 CS332 ‐ Theory of Computation 16
Extensions that do not increase the power of
the TM model
• TMs that are allowed to “stay put” instead of moving
left or right
How would you show that TMs with stay put are no more
powerful than ordinary TMs?
2/24/2021 CS332 ‐ Theory of Computation 17
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 ’
2/24/2021 CS332 ‐ Theory of Computation 18
Extensions that do not increase the power of
the TM model
• TMs with a 2‐way infinite tape, unbounded left to right
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”
2/24/2021 CS332 ‐ Theory of Computation 19
Tape 𝑎 𝑏 𝑎 …
Input
…
Formalizing the Simulation
New tape alphabet:
New state set:
means “ , working on upper track”
means “ , working on lower track”
New transitions:
If 𝛿 𝑝,𝑎 𝑞, 𝑏, 𝐿 , let 𝛿′ 𝑝, , 𝑎 ,𝑎 𝑞, , 𝑏,𝑎 ,𝑅
Also need new transitions for moving right, lower track, hitting $,
initializing input into 2‐track format
2/24/2021 CS332 ‐ Theory of Computation 20
Multi‐Tape TMs
2/24/2021 CS332 ‐ Theory of Computation 21
𝑏 𝑏 𝑎 𝑎 𝑎
Finite
control
𝑎 𝑏 ⊔ 𝑎 𝑎
⊔ 𝑏 𝑎 𝑎 𝑐
Fixed number of tapes (can’t change during computation)
Transition function
Multi‐Tape TMs are Equivalent to Single‐Tape TMs
Theorem: Every ‐tape TM with can be simulated by an
equivalent single‐tape TM
2/24/2021 CS332 ‐ Theory of Computation 22
𝑏 𝑏 𝑎 𝑎
Finite
control
𝑎 𝑏 ⊔ 𝑎
⊔ 𝑏 𝑎 𝑎
⊔ 𝑏 𝑎 𝑎 𝑐 #𝑎 𝑏 ⊔ 𝑎 #𝑏 𝑏 𝑎 𝑎 #
Finite
control