Transcript Halting Problem

Computability
CS 101E
Spring 2007
Michele Co
1
So Far In Class
• We’ve seen
constructs
–
–
–
–
–
the
following
programming
if, if-else, if-else-if
switch
for
These are powerful constructs that allow us to
express many computations
while
do-while
• And
– break
– continue
2
Can Computers be Programmed to
Solve Any Problem?
1. Yes
2. No
3. Maybe
61%
25%
M
ay
be
o
N
Ye
s
14%
3
Can Humans Solve Any Problem?
1. Yes
2. No
3. Maybe
70%
25%
M
ay
be
o
N
Ye
s
5%
4
Epimenides Paradox
This statement is false.
Proof:
1. Let A = This statement is false.
2. Assume A is false
– Then, A must be true
3. Assume A is true
– Then, A is false
No matter what truth value assigned, a
contradiction is reached!
5
The Halting Problem
6
The Halting problem
• Given a program P, and input I, will the
program P ever terminate?
– Meaning will P(I) loop forever or halt?
• Can a computer program determine this?
– Can a human?
• First shown by Alan Turing in 1936
– Before digital computers existed!
7
Solving the Halting Problem
• To “solve” the halting problem means we
create a method CheckHalt(P,I)
– P is the program we are checking for halting
– I is the input to that program
• And it will return “loops forever” or “halts”
• Note it must work for any program, not just
some programs
8
Can a human determine if a
program halts?
• Given a program of 10 lines or less, can a
human determine if it halts?
– Assuming no tricks – the program is
completely understandable
– And assuming the computer works properly,
of course
• And we ignore the fact that an int will max
out at 4 billion
9
haltingTest1
public class haltingTest1 {
public static void main(String [] args){
System.out.println("Alan Turing was a
genius.");
}
}
10
haltingTest2
public class haltingTest2 {
public static void main(String [] args){
for (int factor = 1; factor <= 10; factor ++)
{
System.out.println("Factor is: " + factor);
}
}
}
11
haltingTest3
public class haltingTest3{
public static void main(String [] args){
while(true) {
System.out.println("Hello world!");
}
}
}
12
haltingTest4
public class haltingTest4{
public static void main(String [] args){
int x = 10;
while ( x > 0 ){
System.out.println(“hello world”);
x++;
}
}
}
13
Can Computers be Programmed to
Solve Any Problem?
1. Yes
2. No
3. Maybe
75%
16%
M
ay
be
o
N
Ye
s
9%
14
Can Humans Solve Any Problem?
1. Yes
2. No
3. Maybe
74%
21%
M
ay
be
o
N
Ye
s
5%
15
Another Problem
Perfect Numbers
16
Perfect numbers
• Numbers whose divisors (not including the number) add
up to the number
– 6=1+2+3
– 28 = 1 + 2 + 4 + 7 + 14
• The list of the first 10 perfect numbers:
6, 28, 496, 8128, 33550336, 8589869056,
137438691328, 2305843008139952128,
2658455991569831744654692615953842176,
191561942608236107294793378084303638130997321
548169216
– The last one was 54 digits!
• All known perfect numbers are even; it’s an open (i.e.
unsolved) problem if odd perfect numbers exist
• Sequence A000396 in OEIS
17
Odd perfect number search
public class searchForOddPerfectNumber {
public static void main(String [] args){
int n = 1; // arbitrary-precision integer
while (true) {
int sumOfFactors = 0;
for (int factor = 1; factor < n; factor++) {
if ((n % factor) == 0) {
sumOfFactors =
sumOfFactors + factor;
}
// if
}
// for loop
// if it’s a perfect number
if (sumOfFactors == n)
break;
n = n + 2;
}
Using int for code clarity. Really need a larger
}
18
precision type... BigInteger or larger
}
Can Computers be Programmed to
Solve Any Problem?
1. Yes
2. No
3. Maybe
81%
14%
M
ay
be
o
N
Ye
s
5%
19
Can Humans Solve Any Problem?
1. Yes
2. No
3. Maybe
70%
27%
M
ay
be
o
N
Ye
s
3%
20
Where does that leave us?
• If a human can’t figure out how to do the
halting problem, we can’t make a
computer do it for us
• It turns out that it is impossible to write
such a CheckHalt() method
– But how to prove this?
21
CheckHalt()’s non-existence
• Consider P(I): a program P with input I
• Suppose that CheckHalt(P,I) exists
– Tests if P(I) will either “loop forever” or “halt”
• A program is a series of bits
– And thus can be considered data as well
• Thus, we can call CheckHalt(P,P)
– It’s using the bytes of program P as the input
to program P
22
CheckHalt()’s non-existence
• Consider a new method:
Test(P):
loops forever if CheckHalt(P,P) prints “halts”
halts if CheckHalt(P,P) prints “loops forever”
• Do we agree that Test() is a valid method?
• Now run Test(Test)
– If Test(Test) halts…
• Then CheckHalt(Test,Test) returns “loops forever”…
• Which means that Test(Test) loops forever
• Contradiction!
– If Test(Test) loops forever…
• Then CheckHalt(Test,Test) returns “halts”…
• Which means that Test(Test) halts
• Contradiction!
23
Why do we care about the halting
problem?
• It was the first algorithm that was shown to
not be able to exist
– You can prove an existential by showing an
example (a correct program)
– But it’s much harder to prove that a program
can never exist
24