BU CS 332 – Theory of Computation
Lecture 12:
• TM Variants
Reading:
Sipser Ch 3.2, 4.1
• Decidable Languages
Mark Bun March 4, 2020
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/4/2020
CS332 ‐ Theory of Computation 2
in state runs forever
which halts on every input
TM Variants
3/4/2020 CS332 ‐ Theory of Computation 3
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/4/2020 CS332 ‐ Theory of Computation 4
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/4/2020 CS332 ‐ Theory of Computation 5
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
• “Turing‐complete” programming languages (C, Python, Java…)
…
3/4/2020 CS332 ‐ Theory of Computation 6
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/4/2020 CS332 ‐ Theory of Computation 7
Multi‐Tape TMs
Finite control
𝑏𝑏𝑎𝑎𝑎 𝑎𝑏⊔𝑎𝑎 ⊔𝑏𝑎𝑎𝑐
Fixed number of tapes (can’t change during computation)
Transition function
3/4/2020 CS332 ‐ Theory of Computation 8
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 9
3/4/2020
Simulating Multiple Tapes
Implementation‐Level Description
On input
1. Format tape into
2. For each move of :
Scan left‐to‐right, storing current symbols in finite control Scan left‐to‐right, writing new symbols,
Scan left‐to‐right, moving each tape head
If a tape head goes off the right end, insert blank If a tape head goes off left end, move back right
3/4/2020 CS332 ‐ Theory of Computation 10
3/4/2020 CS332 ‐ Theory of Computation 11
Why are Multi‐Tape TMs Helpful?
To show a language is Turing‐recognizable or decidable, suffices to construct a multi‐tape TM
Very helpful for proving closure properties
Ex. Closure of recognizable languages under union. Suppose 𝑀 is a
single‐tape TM recognizing 𝐿, 𝑀 is a single‐tape TM recognizing 𝐿
3/4/2020 CS332 ‐ Theory of Computation 12
Nondeterministic TMs
At any point in computation, may nondeterministically branch. Accepts iff there exists an accepting branch.
Transition function
Ex. NTM for is a binary number representing the product of two positive integers
3/4/2020 CS332 ‐ Theory of Computation 13
Nondeterministic TMs
Theorem: Every nondeterministic TM has an equivalent deterministic TM
Proof idea:
Systematically try all 1‐step computations, all 2‐step computations, … and see if one of them accepts
3/4/2020 CS332 ‐ Theory of Computation 14
Nondeterministic TMs
Theorem: Every nondeterministic TM has an equivalent deterministic TM
Proof idea: Simulate an NTM 𝑤 𝑤 𝑤 𝑤
using a 3‐tape TM
Finite control
𝑤 ⊔
# 𝑤 3 7
𝑤
Input 𝑤 to 𝑁 (read‐only) Simulation tape (run 𝑁 on 𝑤 using
3/4/2020
CS332 ‐ Theory of Computation 15
1 3
nondeterministic choices from tape 3) Address in computation tree
3/4/2020 CS332 ‐ Theory of Computation 16
Enumerators
Finite control
Work tape “Printer”
• Starts with two blank tapes • Prints strings to printer
strings eventually printed by
• May never terminate (even if language is finite) • May print the same string many times
3/4/2020 CS332 ‐ Theory of Computation 17
Enumerable = Turing‐Recognizable
Theorem: A language is Turing‐recognizable some enumerator enumerates it
Start with an enumerator for and give a TM
3/4/2020 CS332 ‐ Theory of Computation
18
Enumerable = Turing‐Recognizable
Theorem: A language is Turing‐recognizable some enumerator enumerates it
Start with a TM for and give an enumerator
3/4/2020 CS332 ‐ Theory of Computation 19
Mid‐Semester Feedback Form
https://forms.gle/LTBEY1BoSZh8nupV6
3/4/2020 CS332 ‐ Theory of Computation 20