FIT2014 Theory of Computation Lecture 22 University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 22
Undecidability
slides by
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 23
Overview
I Halting Problem (or Entscheidungsproblem)
I Proof of its undecidability
I Using mapping reductions to prove undecidability
I Other undecidable problems
2 / 23
Undecidable languages exist
The set of all deciders is countable.
I {CWL-encodings of deciders} ⊆ {CWL} ⊆ Σ∗
I and Σ∗ is countable. (Lecture 5)
The set of all decidable languages is countable.
The set of all languages is uncountable. (Lecture 5)
Therefore undecidable languages exist.
3 / 23
Halting Problem: Definition
Halting Problem
Input: Turing machine P, input x
Question: If P is run with input x , does it eventually halt?
As a language:
HaltingProbem := {〈P, x〉 : when P is run with input x , it eventually halts.}
Theorem.
The Halting Problem is undecidable.
Proved by:
I Alonzo Church (1936): lambda calculus
I Alan Turing (1936-37): Turing machines
4 / 23
Halting Problem
Theorem.
The Halting Problem is undecidable.
Proof ingredients:
I contradiction
I diagonalisation
I a version of the Liar Paradox: “This sentence is false.”
5 / 23
Consider what happens when we run Turing machines (encoded as strings) on input strings.
3 = Halts; 7 = Doesn’t halt.
inputs to TMs
ε a b aa ab ba bb aaa aab . . .
Turing machines
ε 3 7 7 3 7 3 3 3 7 . . .
a 7 7 3 3 7 7 7 3 3 . . .
b 3 3 7 7 7 3 7 7 3 . . .
aa 3 7 3 3 7 7 3 3 7 . . .
…
…
…
…
…
…
…
…
…
… . . .
1 23
∆ → R
b → R
a → R
b → R
a → R
ababababbababbbbbbabaaabaaaab-
aaababababbaaabaabaaaab
7 3 7 3 7 3 7 3 3 . . .
…
…
…
…
…
…
…
…
…
…
. . .
E : 7 3 3 7 . . .
6 / 23
Halting Problem is Undecidable
Proof. (by contradiction)
Assume there is a Decider, D, for the Halting Problem.
So it can tell, for any P and x , whether or not P eventually halts after being given input x .
So it can tell, for any P, whether or not P eventually halts after being given input P !
Construct another program (Turing machine) E as follows . . .
7 / 23
Halting Problem is Undecidable (cont’d)
E
Input: P
Use D to determine what happens if P runs on itself.
If D says, “P halts, with input P” : loop forever.
If D says, “P loops forever, with input P” : Halt.
What happens when E is given itself as input?
If E halts, for input E : then E loops forever, for input E .
If E loops forever, for input E : then E halts, for input E .
Contradiction!
YouTube film of proof: https://www.youtube.com/watch?v=92WHN-pAFCs
8 / 23
Other Undecidable Problems
DIAGONAL HALTING PROBLEM
Input: Turing machine P
Question: Does P eventually halt, for input P ?
Above proof already shows this.
HALT FOR INPUT ZERO
Input: Turing machine P
Question: Does P eventually halt, for input 0?
Theorem.
HALT FOR INPUT ZERO is undecidable.
We’ll prove this by mapping reduction from the Diagonal Halting Problem.
9 / 23
Using mapping reductions
Recall:
If there is a mapping reduction f from K to L, then:
If L is decidable, then K is decidable.
If K is undecidable, then L is undecidable.
10 / 23
Proof. . . . that HALT FOR INPUT ZERO is undecidable:
Let M be any program, which we regard as an input to the Diagonal Halting Problem.
Define M ′ as follows:
M ′
Input: x
Run M on input M.
Observe:
I The construction M 7→ M ′ is computable.
I M halts on input M if and only if M ′ halts on input 0.
So, the function that sends M 7→ M ′ is a mapping reduction from
DIAGONAL HALTING PROBLEM to HALT FOR INPUT ZERO.
Therefore HALT FOR INPUT ZERO is undecidable.
11 / 23
Other Undecidable Problems
There’s nothing special about zero, here.
So we get a whole lot of undecidability results.
For example:
HALT FOR INPUT 42
Input: Turing machine P
Question: Does P eventually halt, for input 42?
Proof of undecidability is virtually identical to the previous one . . .
Use a mapping reduction, with 42 instead of 0.
12 / 23
Other Undecidable Problems
ALWAYS HALTS
Input: Turing machine P
Question: Does P always halt eventually, for any input?
Theorem.
ALWAYS HALTS is undecidable.
Proof is virtually identical to the previous one . . .
13 / 23
Proof. . . . that ALWAYS HALTS is undecidable:
Let M be any program, which we regard as an input to the Diagonal Halting Problem.
Define M ′ as follows:
M ′
Input: x
Run M on input M.
Observe:
I The construction M 7→ M ′ is computable.
I M halts on input M if and only if M ′ always halts.
So, the function that sends M 7→ M ′ is a mapping reduction from
DIAGONAL HALTING PROBLEM to ALWAYS HALTS.
Therefore ALWAYS HALTS is undecidable.
14 / 23
Other Undecidable Problems
SOMETIMES HALTS
Input: Turing machine P
Question: Is there some input for which P eventually halts?
Theorem.
SOMETIMES HALTS is undecidable.
Proof is virtually identical to the previous one . . .
15 / 23
Proof. . . . that SOMETIMES HALTS is undecidable:
Let M be any program, which we regard as an input to the Diagonal Halting Problem.
Define M ′ as follows:
M ′
Input: x
Run M on input M.
Observe:
I The construction M 7→ M ′ is computable.
I M halts on input M if and only if M ′ halts for some input.
So, the function that sends M 7→ M ′ is a mapping reduction from
DIAGONAL HALTING PROBLEM to SOMETIMES HALTS.
Therefore SOMETIMES HALTS is undecidable.
16 / 23
Other Undecidable Problems
NEVER HALTS
Input: Turing machine P
Question: Does P always loop forever, for any input?
Theorem.
NEVER HALTS is undecidable.
Proof. by a more general type of reduction, from SOMETIMES HALTS.
If D is a decider for NEVER HALTS, then switching Accept and Reject gives a decider
for SOMETIMES HALTS.
But we now know that SOMETIMES HALTS is undecidable.
Contradiction.
So NEVER HALTS is undecidable too.
17 / 23
Other Undecidable Problems
Input: Turing machine P and Q
Question: Do P and Q always both halt, or both loop?
i.e., is it the case that:
∀x : P halts on input x ⇐⇒ Q halts on input x . . . ?
Input: Turing machine P
Question: If P is run on the input “What’s the answer?”, does it output “42”?
18 / 23
Decidable or Undecidable?
Input: Turing machine P, input x .
Question: Does P accept x?
Input: Turing machine P, input x , positive integer t
Question: When P is run on x , does it halt in ≤ t steps?
Input: Turing machine P, positive integer s.
Question: Does P have ≤ s states?
Input: Turing machine P, positive integer k .
Question: Does P halt for some input of length ≤ k .
19 / 23
Other Undecidable Problems
Input: a Turing machine P
Question: Is Accept(P) regular?
i.e., is P equivalent to a Finite Automaton?
Input: a CFG
Question: is the language it generates regular?
Input: a CFG
Question: is there any string that it doesn’t generate? (over same alphabet)
Input: two CFGs.
Question: Do they define the same language?
20 / 23
Other Undecidable Problems
Input: a polynomial (in several variables)
Question: Does it have an integer root?
(Y. Matiyasevich, 1970)
Post Correspondence Problem
(a problem about string matching;
see Sipser, Section 5.2)
h
t
t
p
s
:
/
/
m
a
t
h
s
h
i
s
t
o
r
y
.
s
t
–
a
n
d
r
e
w
s
.
a
c
.
u
k
/
B
i
o
g
r
a
p
h
i
e
s
/
M
a
t
i
y
a
s
e
v
i
c
h
/
Yuri Matiyasevich (b. 1947)
h
t
t
p
s
:
/
/
m
a
t
h
s
h
i
s
t
o
r
y
.
s
t
–
a
n
d
r
e
w
s
.
a
c
.
u
k
/
B
i
o
g
r
a
p
h
i
e
s
/
P
o
s
t
/
Emil Post (1897–1954)
21 / 23
https://mathshistory.st-andrews.ac.uk/Biographies/Matiyasevich/
https://mathshistory.st-andrews.ac.uk/Biographies/Matiyasevich/
https://mathshistory.st-andrews.ac.uk/Biographies/Matiyasevich/
https://mathshistory.st-andrews.ac.uk/Biographies/Post/
https://mathshistory.st-andrews.ac.uk/Biographies/Post/
https://mathshistory.st-andrews.ac.uk/Biographies/Post/
Language classes
Decidable
CFLs
regular
languages
?
22 / 23
Revision
I Know and understand the Halting Problem
I Prove its undecidability
I Be able to use mapping reductions to prove undecidability
I Know examples of undecidable problems.
Reading: Sipser, pp. 201–209, 215–220, 234–236.
Preparation: Sipser, pp. 170, 209–210.
23 / 23