CPS 1 - Spring, 1997 - Ramm 4/23/97 #38

Announce
- Missing Textbook? Identify ...

Chapter 13. Noncomputability

Certain Problems Not Suited for Computer Solution
- However, computers have very real limitation.
Existence of Noncomputable Functions
- Hard to come up with function that computer can't produce.
  - Program must be of finite size; Requires infinite table
Programs that Read Programs
- Not Halting for All Inputs is usually considered a Bug
Solving the Halting Problem
- Gets more and more involved...

Consider Following Program: Does it Halt For All Input?

program J;
var
	x: integer;
begin
readln(x);
while x > 1 do
	begin
	if (x div 2) * 2 = x then {x is even}
		x := x div 2
	else
		x := 3 * x + 1;
	writeln(x);
	end;
readln;
end.

Try It!
- Mathematicians have proven that no one, finite program can check this for all possible programs
Examples of non-computable problems
- Cannot generally prove equivalence
Proofs by Contradiction (Indirect Proof)
Proving non-computability
- Now write program:
```
program contrary;
var
	p, answer: string;

begin
readln(p)
selfhalt(p, answer)
if answer = 'Halts on self' then
	while true do
		answer := 'x';

end.
```
"Feed" it this program.
Paradox!
- If halt program decides it doesn't halt, it quits immediately.
Therefore halt cannot exist!
Whole classes of programs on program behavior are non-computable.
What Does It All Mean?
- Probably can't do things we don't know how to do...