BU CS 332 – Theory of Computation
Lecture 12:
• TM Variants
• Decidable Languages
Mark Bun March 4, 2020
Reading:
Sipser Ch 3.2, 4.1
Recognizers vs. Deciders
𝐿𝐿(𝑀𝑀) = the set of all strings 𝑤𝑤 which 𝑀𝑀 accepts
𝐴𝐴 is Turing-recognizable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀:
•𝑤𝑤∈𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞accept
•𝑤𝑤∉𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞rejectOR 𝑀𝑀 runs forever
𝐴𝐴 is (Turing-)decidable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀
which halts on every input
•𝑤𝑤∈𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞 accept
•𝑤𝑤∉𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞reject
3/4/2020 CS332 – Theory of Computation 2
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
𝑀𝑀′ = (𝑄𝑄′,Σ,Γ′,𝛿𝛿′,𝑞𝑞′,𝑞𝑞′ ,𝑞𝑞′ ) 0 accept reject
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
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
𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎𝑎𝑎 𝑎𝑎𝑏𝑏⊔𝑎𝑎𝑎𝑎 ⊔𝑏𝑏𝑎𝑎𝑎𝑎𝑐𝑐
Fixed number of tapes 𝑘𝑘 (can’t change during computation) Transitionfunction𝛿𝛿∶𝑄𝑄×Γ𝑘𝑘 →𝑄𝑄×Γ𝑘𝑘 × 𝐿𝐿,𝑅𝑅,𝑆𝑆 𝑘𝑘
Finite control
3/4/2020 CS332 – Theory of Computation 8
Theorem: Every 𝑘𝑘-tape TM 𝑀𝑀 with can be simulated by an equivalent single-tape TM 𝑀𝑀′
𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎 𝑎𝑎𝑏𝑏⊔𝑎𝑎 ⊔𝑏𝑏𝑎𝑎𝑎𝑎
𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎 𝑎𝑎𝑏𝑏⊔𝑎𝑎 ⊔𝑏𝑏𝑎𝑎𝑎𝑎𝑐𝑐#
Multi-Tape TMs are Equivalent to Single-Tape TMs
Finite control
Finite control
3/4/2020
CS332 – Theory of Computation 9
#
#
Simulating Multiple Tapes
Implementation-Level Description
Oninput𝑤𝑤=𝑤𝑤1𝑤𝑤2 …𝑤𝑤𝑛𝑛 ̇ ̇
1. Formattapeinto#𝑤𝑤̇ 𝑤𝑤 …𝑤𝑤 #⊔#⊔#…# 2. Foreachmoveof𝑀𝑀:1 2 𝑛𝑛
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
1 single-tape TM recognizing 𝐿𝐿1, 𝑀𝑀2 is a single-tape TM recognizing 𝐿𝐿2
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.
Transitionfunction𝛿𝛿∶𝑄𝑄×Γ →𝑃𝑃(𝑄𝑄×Γ × 𝐿𝐿,𝑅𝑅,𝑆𝑆 ) 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
𝑤𝑤1 𝑤𝑤2 𝑤𝑤3 𝑤𝑤4
Input 𝑤𝑤 to 𝑁𝑁 (read-only) Simulation tape (run 𝑁𝑁 on 𝑤𝑤 using
nondeterministic choices from tape 3) Address in computation tree
Finite control
𝑤𝑤1 ⊔
𝑤𝑤3 𝑤𝑤4
#
3/4/2020
CS332 – Theory of Computation 15
1
3
3
7
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
Decidable Languages
3/4/2020 CS332 – Theory of Computation 20
1928 – The Entscheidungsproblem The “Decision Problem”
Is there an algorithm which takes as input a formula (in first- order logic) and decides whether it’s logically valid?
3/4/2020 CS332 – Theory of Computation 21
Design a TM which takes as input a DFA 𝐷𝐷 and a string 𝑤𝑤, and determines whether 𝐷𝐷 accepts 𝑤𝑤
Let 𝐷𝐷 = (𝑄𝑄, Σ, 𝛿𝛿, 𝑞𝑞 , 𝐹𝐹). List each component of the tuple
Questions about regular languages
How should the input to this TM be represented?
separated by ;
0
• Represent 𝑄𝑄 by ,-separated binary strings
• Represent Σ by ,-separated binary strings
• Represent 𝛿𝛿 ∶ 𝑄𝑄 × Σ → 𝑄𝑄 by a ,-separated list of triples (𝑝𝑝, 𝑎𝑎, 𝑞𝑞), …
Denotetheencodingof𝐷𝐷,𝑤𝑤by 𝐷𝐷,𝑤𝑤
3/4/2020 CS332 – Theory of Computation 22
Representation independence
Computability (i.e., decidability and recognizability) is not affected by the choice of encoding
Why? A TM can always convert between different encodings
For now, we can take to mean “any reasonable encoding”
3/4/2020 CS332 – Theory of Computation 23
A “universal” algorithm for recognizing regular
𝐴𝐴 = 𝐷𝐷,𝑤𝑤 DFA𝐷𝐷accepts𝑤𝑤} DFA
languages
Theorem: 𝐴𝐴DFA is decidable
Proofsketch:DefineaTM𝑀𝑀whichoninput 𝐷𝐷,𝑤𝑤: 1. Check if 𝐷𝐷, 𝑤𝑤 is a valid encoding (reject if not)
2. 3.
Simulate 𝐷𝐷 on 𝑤𝑤, i.e.,
• Tape 2: Maintain 𝑤𝑤 and head location of 𝐷𝐷
• Tape 3: Maintain state of 𝐷𝐷, update according to 𝛿𝛿
Accept iff 𝐷𝐷 ends in an accept state
3/4/2020 CS332 – Theory of Computation 24
Other decidable languages
𝐴𝐴DFA = 𝐷𝐷, 𝑤𝑤 DFA 𝐷𝐷 accepts 𝑤𝑤} 𝐴𝐴NFA = 𝑁𝑁, 𝑤𝑤 NFA 𝑁𝑁 accepts 𝑤𝑤}
𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤}
3/4/2020 CS332 – Theory of Computation 25
CFG Generation
Theorem: 𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤} is Turing-
recognizable
Proof idea: Define a TM 𝑀𝑀 recognizing 𝐴𝐴
CFG
Oninput 𝐺𝐺,𝑤𝑤
1. Enumerate all strings that can be generated from G
(i.e., all length-1 derivations, all length-2 derivations, …) 2. If any of these strings equal w, accept
3/4/2020 CS332 – Theory of Computation 26
CFG Generation
Theorem: 𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤} is decidable
• Can have a rule 𝑆𝑆 → 𝜀𝜀
• Allremainingrulesoftheform𝐴𝐴→𝐵𝐵𝐵𝐵or𝐴𝐴→𝑎𝑎 • Cannot have 𝑆𝑆 on the RHS of any rule
Chomsky Normal Form for CFGs:
Lemma: Any CFG can be converted into an equivalent CFG in Chomsky Normal Form
Lemma: If 𝐺𝐺 is in Chomsky Normal Form, any nonempty string w that can be derived from 𝐺𝐺 has a derivation with at most2 𝑤𝑤 −1steps
3/4/2020 CS332 – Theory of Computation 27
CFG Generation
Theorem: 𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤} is decidable Proof idea: Define a TM 𝑀𝑀 recognizing 𝐴𝐴CFG
Oninput 𝐺𝐺,𝑤𝑤
1. Convert 𝐺𝐺 into Chomsky Normal Form 2.Enumerateallstringsderivablein≤2𝑤𝑤 −1steps 3. If any of these strings equal 𝑤𝑤, accept
3/4/2020 CS332 – Theory of Computation 28
Mid-Semester Feedback Form
https://forms.gle/LTBEY1BoSZh8nupV6
3/4/2020 CS332 – Theory of Computation 29