Microsoft PowerPoint – CS332-Lec12-ann
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
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
On input :
1. Nondeterministically guess
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
𝑤 𝑤 𝑤 𝑤
Finite
control
𝑤 ⊔ # 𝑤 𝑤
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 , 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 . 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
Theorem: 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
3/3/2021 CS332 ‐ Theory of Computation 18
NFA Acceptance
Which of the following describes a decider for
?
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 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