instance

Construct

instance

Figure 8.7: If we could solve problem Рз, then we could use its solution to solve problem Pi

In order to make a proof that problem P2 is undecidable, we have to invent a construction, represented by the square box in Fig. 8.7, that converts instances of Pi to instances of P2 that have the same answer. That is, any string in the language Pi is converted to some string in the language P2, and any string over the alphabet of Pi that is not in the language Pi is converted to a string that is not in the language P2. Once we have this construction, we can solve Pi as follows:

1. Given an instance of Pi, that is, given a string w that may or may not be in the language Pi, apply the construction algorithm to produce a string

2. Test whether x is in P2, and give the same answer about w and Pi.

If w is in Pi, then x is in P2, so this algorithm says yes. If w is not In P], then x is not in P2, and the algorithm says no. Either way, it says the truth about w. Since we assumed that no algorithm to decide membership of a string in Pi exists, we have a proof by contradiction that the hypothesized decision algorithm for P2 does not exist; i.e., F3 is undecidable.

Example 8.1: Let us use this methodology to show that the question does program Q, given input y, ever call fimction f 00 is undecidable. Note that Q may not have a function foo, in which case the problem is easy, but the hard cases are when Q has a function foo but may or may not reach a call to foo with input y. Since we only know one undecidable problem, the role of Pi in Fig. 8,7 will be played by the hello-world problem. P2 will be the calls-foo problem just mentioned. We suppose there is a program that solves the calls-foo problem. Our job is to design an algorithm that converts the hello-world problem into the calls-foo problem.

That is, given program Q and its input y, we must construct a program R and an input г such that R, with input z, calls foo if and only if Q with input у prints hello, world. The construction is not hard:

whether a given program and input results in hello, world as the first output, we were really talking about strings consisting of a С source program followed by whatever input file(s) the program reads. This set of strings 13 a language over the alphabet of ascii characters.

Can a Computer Really Do All That?

If we examine a program such as Fig. 8.2, we might ask whether it really searches for counterexamples to Fermats last theorem. After all, integers are only 32 bits long in the typical computer, and if the smallest counterexample involved integers in the billions, there would be an overflow error before the solution was found. In fact, one could argue that a computer with 128 megabytes of main memory and a 30 gigabyte disk, has only 2563012800O00Q gtates, and is thus a finite automaton.

However, treating computers as finite automata {or treating brains as finite automata, which is where the FA idea originated), is unproductive. The number of states involved is so large, and the limits so unclear, that you dont draw any useful conclusions. In fact, there is every reason to believe that, if we wanted to, we could expand the set of states of a computer arbitrarily.

For instance, we can represent integers as linked lists of digits, of arbitrary length. If we run out of memory, the program can print a request for a human to dismount its disk, store it, and replace it by an empty disk. As time goes on, the computer could print requests to swap among as many disks as the computer needs. This program would be far more complex than that of Fig. 8.2, but not beyond our capabilities to write. Similai-tricks would allow any other program to avoid finite limitations on the size of memory or on the size of integers or other data items.

If Q has a function called f oo, rename it and all calls to that function. Clearly the new program Qi does exactly what Q does.

2. Add to Qi a function f oo. This function does nothing, and is not called. The resulting program is Q-z.

3. Modify Q2 to remember the first 12 characters that it prints, storing them in a global array A. Let the resulting program be Q3.

4. Modify so that whenever it executes any output statement, it then checks in the array A to see if it has written 12 characters or more, and if so, whether hello, world are the first 12 characters. In that case, call the new function f 00 that was added in item (2). The resulting program is R, and input z is the same as y.

Suppose that Q with input у prints hello, world as its first output. Then R as constructed wiU cafi f 00. However, if Q with input у does not print hello, world as its first output, then R will never call f 00. If we can decide whether R with input z calls f 00, then we also know whether Q with input у (remember у - z) prints hello, world. Since we know that no algorithm to

The Direction of a Reduction Is Important

It is a comnion mistake to try to prove a problem P3 undecidable by reducing P2 to some known undecidable problem Pi; i.e., showing the statement if Pi is decidable, then P2 is decidable. That statement, although surely true, is useless, since its hypothesis Л is decidable is false.

The only way to prove a new problem P2 to be undecidable is to reduce a known undecidable problem Pi to P2. That way, we prove the statement if P2 is decidable, then P) is decidable. The contrapositive of that statement is if Pi is undecidable, then P2 is undecidable. Since we know that P] undecidable, we can deduce that P2 is undecidable.

decide the hello-world problem exists, and all four steps of the construction of R from Q could be carried out by a program that edited the code of programs, our assumption that there was a calls-foo tester is wrong. No such program exists, and the calls-foo problem is undecidable. □

8Л.4 Exercises for Section 8Л

Exercise 8.1 Л t Give reductions from the hello-world problem to each of the problems below. Use the informal style of this section for describing plausible program transformations, and do not worry about the real limits such as maximum file size or memory size that real computers impose.

*! a) Given a program and an input, does the program eventually halt; i.e., does the program not loop forever on the input?

b) Given a program and an input, does the program ever produce any output?

! c) Given two programs and an input, do the programs produce the same output for the given input?

8.2 The Turing Machine

The purpose of the theory of undecidable problems is not only to establish the existence of such problems - an intellectually exciting idea in its own right - but to provide guidance to programmers about what they might or might not be able to accomphsh through programming. The theory also has great pragmatic impact when we discuss, as we shall in Chapter 10, problems that although decidable, require large amounts of time to solve them. These problems, called intractable problems, tend to present greater difficulty to the programmer