Discrete Mathematics for Computer Science

320 CHAPTER 5 Analysis of Algorithms

Now ask: Does NegSelfRef halt on input NegSelfRef? Substituting NegSelfRef for A,

we derive that NegSelJRef(NegSelfRef) halts if and only NegSelfRef(NegSelfRef) does not

halt. This is (blatantly!) a contradiction, so no such H exists.

Once one problem was proved to be undecidable, researchers used a technique called

reduction to show that many other problems are also undecidable. The technique used is to

assume that problem P is decidable by an algorithm T and then use T (technically, writing

another algorithm calling T as a subfunction) to solve the halting problem, contradicting a

known result. (Similar techniques are used to show that if CNF satisfiability is testable in

polynomial time, so is every other N'P problem. See Section 2.5.6.

Another basic theorem of Turing was the existence of a universal Turing machine. In

the terminology used here, that translates into a program Interpret, which accepts as input

a string A%%In and, essentially, runs algorithm A on input In. This is now a familiar idea.

BASIC and LISP interpreters do this, and it is similar to programs that compile and then

run other programs. Turing's viewpoint looks slightly different: There is a single machine

that can take a set of instructions as input and simulate any other machine. Such a machine

is, of course, just a general-purpose, programmable computer. Turing's idea foreshadowed

the modem computer, for which the program is input as just another set of data. Proving

the theorem requires extensive work (essentially, writing the interpreter and showing that

it works), and we shall not do it here.

Theorem 2. (Existence of Universal Algorithm, Turing) There is an algorithm Inter-

pret where, for each pair of strings A and In, Interpret(A%%In) = A(In).

In Chapter 4, we discussed two ways in which functions can be defined to be partial:

1. The person specifying the function did not specify its value in all cases.


2. The rule defining the function somehow specified that the function be partial.


3. One could question how different these two ways are. In particular, if a function is
   specified by a rule that makes it partial, is that merely because the wrong rule was
   chosen to specify the function? Before we answer this question, however, we need to
   formalize the ideas.

Definition 4. An algorithm A 2 extends an algorithm A 1 if, for all input strings In, if

AI halts on input In, then A 2 also halts on input In and A 2 (In) = AI(In). A 2 is a total

algorithm for A 1 if A 2 (In) = A 1 (In) whenever A 1 returns TRUE, FALSE, or the empty

string and A 2 returns TRUE or FALSE for every other input.

Given any algorithm A, can one always find an algorithm B extending A where B

defines a total algorithm?

Theorem 3. There is an algorithm A that cannot be extended to a total algorithm.

Proof Let A be the following algorithm, taking one string In as input:

otherOutput = Interpret(In%%In)

/* remember that the line above might never finish */

If otherOutput = the empty string then

output "0"

else

output the empty string.

Note what A does: It treats its input In as if it is an algorithm and tries to run In on input

In. If running In on input In halts-that is, if In(In) is defined-then A returns something