Definition: A **decision problem**
is a problem that requires a yes or no answer.

Definition: A decision problem
that admits no algorithmic solution is said to be **undecidable**.

- No undecidable problem can ever be solved by a computer or computer
program of any kind. In particular, there is no Turing machine to
solve an undecidable problem.
- We have not said that undecidable means we don't know of a
solution today but might find one tomorrow. It means we can
**never**find an algorithm for the problem. - It is not obvious how to show no solution can exist.
- We can do so by constructing a logical paradox.
- Once we've seen one problem that is undecidable, it is often easy to show that other similar problems must also be undecidable.

- We can do so by constructing a logical paradox.

The halting problem takes two inputs:

- an arbitrary program P
- P's input D

The decision problem is: does P halt on input D?

Sometimes the problem is trivial:

/* Always halts regardless of input */ D := 1;

Sometimes the problem is easy, but dependent on the input:

/* Halts only if D is > 0 and even */ repeat D := D - 2 until D = 0;

Sometimes the problem is very very hard:

/* Halts iff Fermet's Last Theorem is false */ Fermat(D:integer); a := 1; done := false; while not done do for b := 1 to a do for c := 2 to a+b do if a**D + b**D = c**D then done := true; a := a + 1; end while;

Can we build a program that solves the halting problem for any program?

- It is important that we pose the problem with
respect to
**any**program, not the handful of programs we know. - By Church's thesis, it doesn't matter which machine model we assume, or what language we use to write the program.

That is, is there a program that takes two inputs (P and D)
and stops with the answer **yes** if P halts on input D,
or stops with the answer **no** if P does
not halt on input D?

If we had such a program, we could use it to check for infinite loops in programs.

Unfortunately no such program exists; the halting problem is undecidable!

Proof by contradiction: Assume we have a procedure HALTS that takes as input a program P and input data D and answers yes if P halts on input D and no otherwise.

- Of course we can't just have HALTS simulate P on input D, since if P doesn't halt, we'll never know exactly when to quit the simulation and answer no.

Since there are no assumptions about the type of inputs we expect, the input D to a program P could itself be a program.

- Compilers and editors both take programs as inputs.
- Given a Pascal compiler written in Pascal, we might want to know if the compiler halts when given itself as input.

Given the program HALTS, we can construct a new (more limited) program that tests whether a program P halts when the input data is a copy of P.

procedure NEWHALTS(P); if HALTS(P,P) then writeln('Yes'); else writeln('No');

Given NEWHALTS, we can construct another program that does just the opposite of NEWHALTS:

procedure OPP(P); if NEWHALTS(P) outputs 'Yes' then loop forever else halt;

What happens when we call OPP(OPP)?

- Inside OPP, we call NEWHALTS(OPP),
which calls HALTS(OPP,OPP).
If OPP halts when fed OPP
as input then the call OPP(OPP)loops forever.
- If OPP doesn't halt when fed OPP as input,
then the call OPP(OPP) halts.
- OPP(OPP) can neither halt nor loop forever.

This is a contradiction! Since our only assumption was the existence of HALTS, procedure HALTS cannot exist.

The halting problem can be used to show that other problems are undecidable.

**Totality Problem:**
A function (or program) F is said to be **total**
if F(x) is defined for all x (or similarly, if F(x) halts for all x).
Determining whether or not a function F is total
is undecidable.

**Proof:** Suppose that it is decidable. Assume there is a procedure
TOTAL that takes as input a program P and outputs 'Yes' if P halts on
all inputs and 'No' otherwise.

We can use the procedure TOTAL to solve the halting problem for a program P and its input D by writing a procedure that simulates P(D).

procedure SIMPD(i); /* Ignores input i */ P(D);

Using SIMPD, we can solve the halting problem as follows:

procedure HALTS(P,D); if TOTAL(SIMPD) outputs 'Yes' then writeln('YES') else writeln('No);

Since SIMPD is total iff P(D) halts, we have constructed a solution to the halting problem. Since such a solution cannot exist, our assumption that TOTAL exists is false.

**Equivalence Problem:**
Given two programs P and Q, do they compute the same function?
(ie, is P(x) = Q(x) for all x?) This problem is also undecidable.

**Proof:** Consider the following program

procedure TOTALP(x); P(x); writeln('YES');

If P(x) halts, then TOTALP(x) halts and outputs Yes.

procedure CONST(x); /* Ingore input and always output true */ writeln('Yes');

CONST prints Yes for all inputs. If CONST = TOTALP, then TOTALP outputs Yes for all inputs, which implies that P(x) halts on all inputs, which implies that P(x) is total.

Thus, if we can determine whether CONST = TOTALP, we can solve the totality problem. Therefore, the equivalence problem is undecidable.

Note that this means that in general, you can't tell whether an original program P and an optimized version P' produced by an optimizing compiler compute the same thing.

A **computable** function
is one that always halts and gives an answer, either yes or no.
A **partially computable** function halts and gives a yes
on those inputs for which 'yes' is the correct solution, but never halts
on other inputs.

Example: The halting problem is partially computable. To determine HALTS(P,D), simply call P(D). Then, HALTS(P,D) halts and outputs Yes if P(D) halts, and loops otherwise.

If a problem is computable or partially computable, then anytime an algorithm halts, the answer can be checked in a finite amount of time and space.

Example: If the halting problem HALTS(P,D) halts and says Yes, it is easy to check that P(D) halts by showing a simulation of P(D). Thus, whenever HALTS(P,D) halts, we know that a hand simulation will halt, and be a proof that HALTS(P,D) = true.

If a problem is not even partially computable, there is no way of checking even a YES answer.

Example: The equivalence problem is not partially computable. Suppose EQUALS(P,Q) is true. How would you check it? There are an infinite number of inputs to each, and they can't all be checked.

The recursion theorem states that for any algorithm that operates on a sequence of characters, there is an algorithm that does the same thing to itself.

Example: There exists an algorithm that accepts a program as input and prints the program as output. By the recursion theorem, there is a program that prints itself.

Here is a Pascal program that almost does the trick. Can you find and fix the problem?

program Z(output); var A: array [1..240] of char; procedure P(i,j,k:integer); begin for k := i to j do write(A[k]); end; begin A := 'program Z(output); var A:array[1..240] of char; procedure P(i,j,k:integer); begin for k := i to j do write(A[k]); end; begin A := ; P(1,129,0); P(1,129,0); P(130,188,0); P(130,188,0) end.'; P(1,129,0); P(1,129,0); P(130,188,0); P(130,188,0) end.

The recursion theorem has practical significance. We can use it to prove that there is no program to automatically supply an adequate set of test data for a program that fully exercises the program.

Theorem: There is no algorithm Test(P) that given program P produces a set of test inputs I that adequately tests program P.

Proof by contradiction: Assume algorithm Test exists.

Consider the following program:

/* Procedure to increment a variable */ procedure Inc(x:integer); /* Get set of test inputs for P */ I := Test(P); if x in I then print x+1 else print 0; end;

This procedure operates correctly (it outputs x+1) for every value in the test suite, and incorrectly (it outputs 0) for all the other possible inputs.

The recursion theorem states there is another program Inc2 that operates exactly like Inc, when P is a copy of Inc2. Inc2 uses Test to generate test data for itself, but it prints the wrong answer for every input not included in the test data. Clearly then, the test data is not adequate, so Test does not exist.

Conclusion: automatic testing can't be guaranteed to always work, even if it can be used to generate some useful test cases.