程序代写代做代考 AI algorithm CS 3800: Theory of Computing Undecidability

Undecidability: # Languages > # TMs
Saw:
• The set 𝕃 of all languages is uncountable. • The set 𝕄 of all TMs is countably infinite.
Theorem: Some language L ∈ 𝕃 is not decidable or even recognizable.
Proof: Assume otherwise that each L is recognizable. Let f : 𝕃 → 𝕄 be a one-to-one function defined by
f(L) = smallest TM M that recognizes L So |𝕃| ≤ |𝕄|. Contradiction.

Specific Undecidable Problems
We saw that there exist undecidable languages.
• But are these languages we care about?
• Can we find a specific language and show it is undecidable?
• Yes! Most problems that require you to reason about the language of a TM M given its code are undecidable.

Specific Undecidable Problems
Given a description of a TM and a string w: • Decide if M accepts w.
• Decide if M halts on the input w.
• Decide if M halts on the empty input 𝜀.
• Decide if L(M) = ∅. • ….
All are undecidable!

The TM Self-Acceptance Problem
“TM Self-Acceptance”
SATM = { : M is a TM that accepts }
“TM Self-Unacceptance”
• •
•
SUTM = { : M is a TM that does not accept }
A Turing Machine M is “self-accepting” if it accepts given the
string as an input.
To decide the language SATM need to design an algorithm that looks at some code and decides if M is self- accepting.
SATM , SUTM are complements of each other (assume every string denotes some TM). One is decidable iff the other is.

Theorem: SUTM is an undecidable language.
SUTM = { : M is a TM that does not accept }
Proof: By contradiction. Assume we have a “decider” D (a TM that always halts) for SUTM.
D accepts ⇔ M does not accept What happens when we run D()?
D accepts ⇔ D does not accept Contradiction!

The TM Acceptance Problem “TM Acceptance” problem:
ATM = { : M is a TM and M accepts w}
Recall we showed STM is undecidable:
SATM = { : M is a TM that accepts }
Theorem: The language ATM is undecidable. Proof: If we had a decider DA for ATM we could
construct a decider for DS for SATM : DS() { Output DA() }

Reductions Reduce a problem A to a problem B:
Show how to solve A given a way to solve B.
(Tells us that solving B cannot be “much easier” than solving A. )
If A and B are languages, we reduce A to B
by constructing decider DA for A using a hypothetical decider DB for B as a “subroutine”.
By reducing A to B we show:
• If B decidable then A decidable. (algorithms class)
• If A undecidable then B undecidable. (this class)

Reduce SATM to ATM
ATM = { : M is a TM and M accepts w}
SATM = { : M is a TM that accepts }
Previously showed that SATM undecidable.
To show ATM undecidable reduce SATM to ATM.
Construct a decider DS for SATM using a “supposed” decider DA for ATM as a subroutine:
DSTM() { Output DATM() }

Halting Problem
H = { : M is a TM and M halts on w }
Theorem: H is undecidable. Proof:ReduceATM toHwhere
ATM = { : M is a TM and M accepts w}
Construct decider DATM using decider DH as a subroutine. DATM() {
Run DH() and, if it rejects, output reject;
Else run M(w) and output whatever it outputs. }

Another Reduction Definition: Acceptance of empty string
ETM = { : M is a TM and M accepts 𝜀 }
Theorem: ETM is undecidable. Proof: Reduce ATM to ETM where
ATM = { : M is a TM and M accepts w} Construct decider DATM using decider DETM as a subroutine.
DATM() { Create ;
Output DETM() }
M’w(x) { // ignores x Run M(w) and output what it outputs; }
Key point: M’w(𝜀) accepts iff M(w) accepts.

One More Reduction
R = { : M is a TM and L(M) is regular } Theorem: R is undecidable.
Proof: Reduce ATM to R by constructing a decider DATM using a decider DR as a subroutine.
DATM( ) { Create ;
Run DR(M’w); }
M’w(x) {
If x is of form 0n1n
output accept; else output M(w); }
Key point: L(M’w) is regular iff M(w) = accept

Rice’s Theorem
Informal: Any non-trivial property of the language of a TM is undecidable.
Theorem:
Let P be some set of TMs such that:
• P contains some but not all TMs: ∃ M ∈ P and ∃ M ∉ P
• Whenever L(M) = L(M’) then M ∈ P ⇔ M’ ∈ P. In other words, only depends on language.
Then the language L = { : M ∈ P } is undecidable. • Examples: L(M) = ∅ or L(M) = {𝜀} or 01 ∈L(M)

Undecidability in Logic Given a first-order logic statement in number theory
Th(N, + , x) decide if the statement is true or not.
 Variables x, y, z… take values in N = {1,2,3,…}
 Operations: +, ×
 Equality Relation: = (can also give < , > )
 Logical quantifiers ∃, ∀ and connectives Λ , V, ¬

Undecidability in Logic
Given a first-order logic statement in number theory Th(N, + , x) decide if the statement is true or not.
•
•
•
∀ x, y ∃ z : x + z = y
– False; if x = 7, y = 5 then no such z exists.
∀ q ∃ p ∀ x, y : (p > q ) ∧ (x,y > 1 ⇒ xy ≠ p) – True; says there are infinitely many primes.
∀ q ∃ p ∀ x, y :
(p > q ) ∧ (x,y > 1 ⇒ (xy ≠ p ∧ xy ≠ p+2 ) ) – Twin Prime Conjecture; remains open!

Theorem: Th(N, + , x) is undecidable. Proof Sketch:
Reduce ATM to Th(N, + , x).
Gödel Church Turing Algorithm gets and constructs a statement
𝜑𝑀,𝑤 which is true if and only if M accepts w.
• Design a way to encode TM computations as natural numbers x.
• Design a formula 𝜓𝑀,𝑤(x) = “x represents an accepting computation of M on w.”
• Set𝜑𝑀,𝑤 = ∃x :𝜓𝑀,𝑤(x)

Corollary:
There is no decidable “set of axioms” A for Th(N, + , x).
– Can decide if a ∈ A
– Any true statement 𝜑 can be proved from the axioms.
Proof Sketch:
If there was a decidable set of axioms A for Th(N, + , x), then
could decide if 𝜑 is true:
• Try all strings 𝜋 one-by-one
– Check if 𝜋 is a valid proof of 𝜑 using axioms a ∈ A. If so, accept. – Check if 𝜋 is a valid proof of ¬𝜑 using axioms a ∈ A. If so, reject.

Undecidability in Logic
But people solve undecidable problems all the time (e.g., prove theorems in number theory).
Aren’t they just applying some complex algorithm?
• Even if a problem is undecidable: some algorithms can solve some instances, but no algorithm can solve all the instances.
• There is much research on “heuristics” that solve many useful instances of undecidable problems:
– program verification, virus checkers, theorem provers…

Hilbert’s 10th Problem
Posed by Hilbert in 1900: Design an algorithm which is given a multivariate polynomial p, and decides if p has an integer root or not.
e.g. p(x,y,z) = 6x3yz + 3xy2 – x3 – 10 has a root x=5, y=3, z =0
Decide the language:
H10 = {

: p polynomial with integer root }
Theorem [Matijasevic 1970]: H10 is undecidable. Proof: A complicated reduction.

Summary
• There are more languages than Turing Machines (uncountable vs. countable infinity) so some languages must be undecidable.
• Most problems where you’re given a TM and need to figure out something about the language of the TM are undecidable.
• Some important problems in mathematics are undecidable.
• Reduce an undecidable problem A to another problem B to
show B undecidable.
– Surprising connections between seemingly unrelated problems.