PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 12:
• More on NTMs
• Church-Turing Thesis
• Decidable Languages
Reading:
Sipser Ch 3.2, 4.1
Mark Bun
March 3, 2021
Nondeterministic TMs
At any point in computation, may nondeterministically
branch. Accepts iff there exists an accepting branch.
Transition function 𝛿𝛿 ∶ 𝑄𝑄 × Γ → 𝑃𝑃(𝑄𝑄 × Γ × 𝐿𝐿,𝑅𝑅, 𝑆𝑆 )
3/3/2021 CS332 – Theory of Computation 2
Nondeterministic TMs
An NTM 𝑁𝑁 accepts input 𝑤𝑤 if when run on 𝑤𝑤 it accepts on
at least one computational branch
𝐿𝐿 𝑁𝑁 = {𝑤𝑤 ∣ 𝑁𝑁 accepts input 𝑤𝑤}
An NTM 𝑁𝑁 is a decider if on every input, it halts on every
computational branch
3/3/2021 CS332 – Theory of Computation 3
Nondeterministic TMs
Ex. NTM decider for 𝐿𝐿 = 𝑤𝑤 𝑤𝑤 is a binary number representing
the product of two integers 𝑎𝑎, 𝑏𝑏 ≥ 2}
On input 𝑤𝑤:
1. Nondeterministically guess 𝑎𝑎, 𝑏𝑏 ∈ {2, … ,𝑤𝑤}
2. Accept if 𝑎𝑎 × 𝑏𝑏 = 𝑤𝑤, reject otherwise.
Proof of correctness:
If 𝑤𝑤 ∈ 𝐿𝐿, there exist �𝑎𝑎, �𝑏𝑏 such that �𝑎𝑎 × �𝑏𝑏 = 𝑤𝑤. Computation
branch where we guessed 𝑎𝑎 = �𝑎𝑎, 𝑏𝑏 = �𝑏𝑏 accepts, so NTM accepts.
If 𝑤𝑤 ∉ 𝐿𝐿, all choices of 𝑎𝑎, 𝑏𝑏 reject, so NTM does not accept.
3/3/2021 CS332 – Theory of Computation 4
Simulating NTMs
Theorem: Every nondeterministic TM can be simulated by
an equivalent deterministic TM
Proof idea: “Tree of possible computations”
3/3/2021 CS332 – Theory of Computation 5
Simulating NTMs
Which of the following algorithms is always appropriate
for searching the tree of possible computations for an
accepting configuration?
a) Depth-first search: Explore as far as possible down
each branch before backtracking
b) Breadth-first search: Explore all the configurations at
depth 1, then all the configurations at depth 2, etc.
c) Either will always work
3/3/2021 CS332 – Theory of Computation 6
Simulating TMs
Theorem: Every nondeterministic TM can be simulated by
an equivalent deterministic TM
Proof idea:
Breadth-first search:
Systematically try all 1-step computations, all 2-step
computations, … and see if one of them accepts
3/3/2021 CS332 – Theory of Computation 7
Nondeterministic TMs
Theorem: Every nondeterministic TM can be simulated by
an equivalent deterministic TM
Proof idea: Simulate an NTM 𝑁𝑁 using a 3-tape TM
(See Sipser for full description)
3/3/2021 CS332 – Theory of Computation 8
𝑤𝑤1 𝑤𝑤2 𝑤𝑤3 𝑤𝑤4
Finite
control
𝑤𝑤1 ⊔ # 𝑤𝑤3 𝑤𝑤4
1 3 3 7
Input 𝑤𝑤 to 𝑁𝑁 (read-only)
Simulation tape (run 𝑁𝑁 on 𝑤𝑤 using
nondeterministic choices from tape 3)
Address in computation tree
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
…
3/3/2021 CS332 – Theory of Computation 9
Church-Turing Thesis
The equivalence of these models is a mathematical
theorem
Church-Turing Thesis v1: The basic TM (hence all of these
models) captures our intuitive notion of algorithms
Church-Turing Thesis v2: Any physically realizable model
of computation can be simulated by the basic TM
The Church-Turing Thesis is not a mathematical
statement!
3/3/2021 CS332 – Theory of Computation 10
Decidable Languages
3/3/2021 CS332 – Theory of Computation 11
1928 – The Entscheidungsproblem
3/3/2021 CS332 – Theory of Computation 12
The “Decision Problem”
Is there an algorithm which takes as input a formula (in first-
order logic) and decides whether it’s logically valid?
Questions about regular languages
• Given a DFA 𝐷𝐷 and a string 𝑤𝑤, does 𝐷𝐷 accept input 𝑤𝑤?
• Given a DFA 𝐷𝐷, does 𝐷𝐷 recognize the empty language?
• Given DFAs 𝐷𝐷1,𝐷𝐷2, do they recognize the same
language?
(Same questions apply to NFAs, regexes)
Goal: Formulate each of these questions as a language,
and decide them using Turing machines
3/3/2021 CS332 – Theory of Computation 13
Questions about regular languages
Design a TM which takes as input a DFA 𝐷𝐷 and a string 𝑤𝑤,
and determines whether 𝐷𝐷 accepts 𝑤𝑤
How should the input to this TM be represented?
Let 𝐷𝐷 = (𝑄𝑄, Σ, 𝛿𝛿, 𝑞𝑞0,𝐹𝐹). List each component of the tuple
separated by #
• Represent 𝑄𝑄 by ,-separated binary strings
• Represent Σ by ,-separated binary strings
• Represent 𝛿𝛿 ∶ 𝑄𝑄 × Σ → 𝑄𝑄 by a ,-separated list of triples
(𝑝𝑝,𝑎𝑎, 𝑞𝑞), …
Denote the encoding of 𝐷𝐷,𝑤𝑤 by 𝐷𝐷,𝑤𝑤
3/3/2021 CS332 – Theory of Computation 14
Example
3/3/2021 CS332 – Theory of Computation 15
𝑞𝑞0 𝑞𝑞1
𝑏𝑏 𝑏𝑏
𝑎𝑎
𝑎𝑎
Representation independence
Computability (i.e., decidability and recognizability) is not
affected by the precise choice of encoding
Why? A TM can always convert between different
(reasonable) encodings
We’ll take to mean “any reasonable encoding”
3/3/2021 CS332 – Theory of Computation 16
A “universal” algorithm for recognizing regular
languages
𝐴𝐴DFA = 𝐷𝐷,𝑤𝑤 DFA 𝐷𝐷 accepts 𝑤𝑤}
Theorem: 𝐴𝐴DFA is decidable
Proof: Define a 3-tape TM 𝑀𝑀 on input 𝐷𝐷,𝑤𝑤 :
1. Check if 𝐷𝐷,𝑤𝑤 is a valid encoding (reject if not)
2. Simulate 𝐷𝐷 on 𝑤𝑤, i.e.,
• Tape 2: Maintain 𝑤𝑤 and head location of 𝐷𝐷
• Tape 3: Maintain state of 𝐷𝐷, update according to 𝛿𝛿
3. Accept if 𝐷𝐷 ends in an accept state, reject otherwise
3/3/2021 CS332 – Theory of Computation 17
Other decidable languages
𝐴𝐴DFA = 𝐷𝐷,𝑤𝑤 DFA 𝐷𝐷 accepts 𝑤𝑤}
𝐴𝐴NFA = 𝑁𝑁,𝑤𝑤 NFA 𝑁𝑁 accepts 𝑤𝑤}
𝐴𝐴REX = 𝑅𝑅,𝑤𝑤 regular expression 𝑅𝑅 generates 𝑤𝑤}
3/3/2021 CS332 – Theory of Computation 18
NFA Acceptance
Which of the following describes a decider for 𝐴𝐴NFA =
𝑁𝑁,𝑤𝑤 NFA 𝑁𝑁 accepts 𝑤𝑤}?
a) Using a deterministic TM, simulate 𝑁𝑁 on 𝑤𝑤, always
making the first nondeterministic choice at each step.
Accept if it accepts, and reject otherwise.
b) Using a deterministic TM, simulate all possible choices
of 𝑁𝑁 on 𝑤𝑤 for 1 step of computation, 2 steps of
computation, etc. Accept whenever some simulation
accepts.
c) Convert 𝑁𝑁 to an equivalent DFA 𝑀𝑀. Simulate 𝑀𝑀 on 𝑤𝑤,
accept if it accepts, and reject otherwise.
3/3/2021 CS332 – Theory of Computation 19
Regular Languages are Decidable
Theorem: Every regular language 𝐿𝐿 is decidable
Proof 1: If 𝐿𝐿 is regular, it is recognized by a DFA 𝐷𝐷. Convert
this DFA to a TM 𝑀𝑀. Then 𝑀𝑀 decides 𝐿𝐿.
Proof 2: If 𝐿𝐿 is regular, it is recognized by a DFA 𝐷𝐷. The
following TM 𝑀𝑀𝐷𝐷 decides 𝐿𝐿.
On input 𝑤𝑤:
1. Run the decider for 𝐴𝐴DFA on input 𝐷𝐷,𝑤𝑤
2. Accept if the decider accepts; reject otherwise
3/3/2021 CS332 – Theory of Computation 20
Classes of Languages
3/3/2021 CS332 – Theory of Computation 21
regular
recognizable
decidable
Emptiness Testing
3/3/2021 CS332 – Theory of Computation 22
𝐸𝐸DFA = 𝐷𝐷 𝐷𝐷 is a DFA that recognizes the empty language}
Decidability of 𝐸𝐸𝐷𝐷𝐷𝐷𝐷𝐷
Theorem: 𝐸𝐸DFA = 𝐷𝐷 𝐷𝐷 is a DFA that recognizes ∅} is
decidable
Proof: The following TM decides 𝐸𝐸DFA
On input 𝐷𝐷 , where 𝐷𝐷 is a DFA with 𝑘𝑘 states:
1. Perform 𝑘𝑘 steps of breadth-first search on state
diagram of 𝐷𝐷 to determine if an accept state is
reachable from the start state
2. Accept if an accept state reachable; reject otherwise
3/3/2021 CS332 – Theory of Computation 23
3/3/2021 CS332 – Theory of Computation 24
𝐸𝐸𝐷𝐷𝐷𝐷𝐷𝐷 Example
New Deciders from Old
𝐸𝐸𝑄𝑄DFA = ⟨𝐷𝐷1,𝐷𝐷2⟩ 𝐷𝐷1,𝐷𝐷2 are DFAs and 𝐿𝐿(𝐷𝐷1) = 𝐿𝐿(𝐷𝐷2)}
Theorem: 𝐸𝐸𝑄𝑄DFA is decidable
Proof: The following TM decides 𝐸𝐸𝑄𝑄DFA
On input ⟨𝐷𝐷1,𝐷𝐷2⟩ , where 𝐷𝐷1,𝐷𝐷2 are DFAs:
1. Construct a DFA 𝐷𝐷 that recognizes the symmetric
difference 𝐿𝐿(𝐷𝐷1) △ 𝐿𝐿(𝐷𝐷2)
2. Run the decider for 𝐸𝐸DFA on 𝐷𝐷 and return its output
3/3/2021 CS332 – Theory of Computation 25
Symmetric Difference
𝐴𝐴 △ 𝐵𝐵 = 𝑤𝑤 𝑤𝑤 ∈ 𝐴𝐴 or 𝑤𝑤 ∈ 𝐵𝐵 but not both}
3/3/2021 CS332 – Theory of Computation 26
BU CS 332 – Theory of Computation
Nondeterministic TMs
Nondeterministic TMs
Nondeterministic TMs
Simulating NTMs
Simulating NTMs
Simulating TMs
Nondeterministic TMs
TMs are equivalent to…
Church-Turing Thesis
Decidable Languages
1928 – The Entscheidungsproblem
Questions about regular languages
Questions about regular languages
Example
Representation independence
A “universal” algorithm for recognizing regular languages
Other decidable languages
NFA Acceptance
Regular Languages are Decidable
Classes of Languages
Emptiness Testing
Decidability of 𝐸 𝐷𝐹𝐴
𝐸 𝐷𝐹𝐴 Example
New Deciders from Old
Symmetric Difference