This may already seem ridiculous, but we can take the craziness one step further. Remember that computer programs are themselves stored on the computer's disk as files. Often, these programs have a name that ends in “.exe,” which is short for “executable”—this just means that you can “execute,” or run, the program. So because computer programs are just files on the disk, we can feed one computer program as input to another computer program. As one specific example, the Microsoft Word program is stored on my computer as the file “WINWORD.EXE.” So by running my spreadsheet program with the file WINWORD.EXE as input, I can produce the wonderful garbage you see in the figure on the facing page.
Microsoft Excel examines Microsoft Word. When Excel opens
the file WINWORD.EXE, the result is—unsurprisingly—garbage.
Again, it would be well worth trying this experiment for yourself. To do that, you will need to locate the file WINWORD.EXE. On my computer, WINWORD.EXE lives in the folder “C:Program FilesMicrosoft OfficeOffice12,” but the exact location depends on what operating system you are running and what version of Microsoft Office is installed. You may also need to enable the viewing of “hidden files” before you can see this folder. And, by the way, you can do this experiment (and one below) with any spreadsheet and word processing programs, so you don't need Microsoft Office to try it.
One final level of stupidity is possible here. What if we ran a computer program on itself? For example, what if I ran Microsoft Word, using the file WINWORD.EXE as input? Well, it's easy enough to try this experiment. The figure on the next page shows the result when I try it on my computer. As with the previous few examples, the program runs just fine, but the output on the screen is mostly garbage. (Once again, try it for yourself.)
So, what is the point of all this? The purpose of this section was to acquaint you with some of the more obscure things you can do when running a program. By now, you should be comfortable with three slightly strange ideas that will be very important later. First, there is the notion that any program can be run with any file as input, but the resulting output will usually be garbage unless the input file was intentionally produced to work with the program you chose to run. Second, we found out that computer programs are stored as files on computer disks, and therefore one program can be run with another program as its input file. Third, we realized that a computer program can be run using its own file as the input. So far, the second and third activities always produced garbage, but in the next section we will see a fascinating instance in which these tricks finally bear some fruit.
Microsoft Word examines itself. The open document is the file WINWORD.EXE, which is the actual computer program run when you click on Microsoft Word.
SOME PROGRAMS CAN'T EXIST
Computers are great at executing simple instructions—in fact, modern computers execute simple instructions billions of times every second. So you might think that any task that could be described in simple, precise English could be written down as a computer program and executed by a computer. My objective in this section is to convince you that the opposite is true: there are some simple, precise English statements that are literally impossible to write down as a computer program.
Some Simple Yes-No Programs
To keep things as simple as possible in this section, we will consider only a very boring set of computer programs. We'll call these “yes-no” programs, because the only thing these programs can do is pop up a single dialog box, and the dialog box can contain either the word “yes” or the word “no.” For example, a few minutes ago I wrote a computer program called ProgramA.exe, which does nothing but produce the following dialog box:
Note that by looking in the title bar of the dialog box, you can see the name of the program that produced this output—in this case, ProgramA.exe.
I also wrote a different computer program called ProgramB.exe, which outputs “no” instead of “yes”:
ProgramA and ProgramB are extremely simple—so simple, in fact, that they do not require any input (if they do receive input, they ignore it). In other words, they are examples of programs that really do behave exactly the same every time they are run, regardless of any input they may be given.
As a more interesting example of one of these yes-no programs, I created a program called SizeChecker.exe. This program takes one file as input and outputs “yes” if that file is bigger than 10 kilobytes and otherwise outputs “no.” If I right-click on a 50-megabyte video file (say, mymovie.mpg), choose “Open with…,” and select SizeChecker.exe, I will see the following output:
On the other hand, if I run the same program on a small 3-kilobyte e-mail message (say, myemail.msg), I will, of course, see a different output:
Therefore, SizeChecker.exe is an example of a yes-no program that sometimes outputs “yes” and sometimes “no.”
Now consider the following slightly different program, which we'll call NameSize.exe. This program examines the name of its input file. If the file name is at least one character long, NameSize.exe outputs “yes”; otherwise, it outputs “no.” What are the possible outputs of this program? Well, by definition, the name of any input file is at least one character long (otherwise, the file would have no name at all, and you couldn't select it in the first place). Therefore, NameSize.exe will always output “yes,” regardless of its input.
By the way, the last few programs mentioned above are our first examples of programs that do not produce garbage when they are given other programs as input. For example, it turns out that the size of the file NameSize.exe is only about 8 kilobytes. So if I run SizeChecker.exe with NameSize.exe as the input, the output is “no” (because NameSize.exe is not more than 10 kilobytes). We can even run SizeChecker.exe on itself. The output this time is “yes,” because it turns out that SizeChecker.exe is larger than 10 kilobytes—about 12 kilobytes, in fact. Similarly, we could run NameSize.exe with itself as input; the output would be “yes” since the file name “Name-Size.exe” contains at least one character. All of the yes-no programs we have discussed this far are admittedly rather dull, but it's important to understand their behavior, so work through the table on the facing page line by line, making sure you agree with each output.
AlwaysYes.exe: A Yes-No Program That Analyzes Other Programs
We're now in a position to think about some much more interesting yes-no programs. The first one we'll investigate is called “AlwaysYes.exe.” This program examines the input file it is given and outputs “yes” if the input file is itself a yes-no program that always outputs “yes.” Otherwise, the output of AlwaysYes.exe is “no.” Note that AlwaysYes.exe works perfectly well on any kind of input file. If you give it an input that isn't an executable program (e.g., address-list.docx), it will output “no.” If you give it an input that is an executable program, but isn't a yes-no program (e.g., WINWORD.EXE), it will output “no.” If you give it an input that is a yes-no program, but it's a program that sometimes outputs “no,” then AlwaysYes.exe outputs “no.” The only way that AlwaysYes.exe can output “yes” is if you input a yes-no program that always outputs “yes,” regardless of its input. In our discussions so far, we've seen two examples of programs like this: ProgramA.exe, and NameSize.exe. The table on the next page summarizes the output of AlwaysYes.exe on various different input files, including the possibility of running AlwaysYes.exe on itself. As you can see in the last line of the table, AlwaysYes.exe outputs “no” when run on itself, because there are at least some input files on which it outputs “no.”
program run input file output
ProgramA.exe address-list.docx yes
ProgramA.exe ProgramA.exe yes
ProgramB.exe address-list.docx no
ProgramB.exe ProgramA.exe no
SizeChecker.exe mymovie.mpg (50MB) yes
SizeChecker.exe myemail.msg (3KB) no
SizeChecker.exe NameSize.exe (8KB) no
SizeChecker.exe SizeChecker.exe (12KB) yes
NameSize.exe mymovie.mpg yes
NameSize.exe ProgramA.exe yes
NameSize.exe NameSize.exe yes
The outputs of some simple yes-no programs. Note the distinction between programs that always output “yes,” regardless of their input (e.g., ProgramA.exe, NameSize.exe), and programs that output “no” either sometimes (e.g., SizeChecker.exe) or always (e.g., ProgramB.exe).
In the next-to-last line of this table, you may have noticed the appearance of a program called Freeze.exe, which has not been described yet. Freeze.exe is a program that does one of the most annoying things a computer program can do: it “freezes” (no matter what its input is). You have probably experienced this yourself, when a video game or an application program seems to just lock up (or “freeze”) and refuses to respond to any more input whatsoever. After that, your only option is to kill the program. If that doesn't work, you might even need to turn off the power (sometimes, when using a laptop, this requires removing the batteries!) and reboot. Computer programs can freeze for a variety of different reasons. Sometimes, it is due to “deadlock,” which was discussed in chapter 8. In other cases, the program might be busy performing a calculation that will never end—for example, repeatedly searching for a piece of data that is not actually present.
AlwaysYes.exe outputs
input file output
address-list.docx no
mymovie.mpg no
WINWORD.EXE no
ProgramA.exe yes
ProgramB.exe no
NameSize.exe yes
SizeChecker.exe no
Freeze.exe no
AlwaysYes.exe no
The outputs of AlwaysYes.exe for various inputs. The only inputs that produce a “yes” are yes-no programs that always output “yes”—in this case, ProgramA.exe and NameSize.exe.
In any case, we don't need to understand the details about programs that freeze. We just need to know what AlwaysYes.exe should do when it's given such a program as input. In fact, AlwaysYes.exe was defined carefully so that the answer is clear: AlwaysYes.exe outputs “yes” if its input always outputs “yes”; otherwise, it outputs “no.” Therefore, when the input is a program like Freeze.exe, AlwaysYes.exe must output “no,” and this is what we see in the next-to-last line of the table above.
YesOnSelf.exe: A Simpler Variant of AlwaysYes.exe
It may have already occurred to you that AlwaysYes.exe is a rather clever and useful program, since it can analyze other programs and predict their outputs. I will admit that I didn't actually write this program—I just described how it would behave, if I had written it. And now I am going to describe another program, called YesOnSelf.exe. This program is similar to AlwaysYes.exe, but simpler. Instead of outputting “yes” if the input file always outputs “yes,” YesOnSelf.exe outputs “yes” if the input file outputs “yes” when run on itself; otherwise, YesOnSelf.exe outputs “no.” In other words, if I provide SizeChecker.exe as the input to YesOnSelf.exe, then YesOnSelf.exe will do some kind of analysis on SizeChecker.exe to determine what the output is when SizeChecker.exe is run with SizeChecker.exe as the input. As we already discovered (see the table on page 185), the output of SizeChecker.exe on itself is “yes.” Therefore, the output of YesOnSelf.exe on SizeChecker.exe is “yes” too. You can use the same kind of reasoning to fill in the outputs of YesOnSelf.exe for various other inputs. Note that if the input file isn't a yes-no program, then YesOnSelf.exe automatically outputs “no.” The table above shows some of the outputs for YesOnSelf.exe—try to verify that you understand each line of this table, since it's very important to understand the behavior of YesOnSelf.exe before reading on.
YesOnSelf.exe outputs
input file output
address-list.docx no
mymovie.mpg no
WINWORD.EXE no
ProgramA.exe yes
ProgramB.exe no
NameSize.exe yes
SizeChecker.exe yes
Freeze.exe no
AlwaysYes.exe no
YesOnSelf.exe ???
The outputs of YesOnSelf.exe for various inputs. The only inputs that produce a “yes” are yes-no programs that output “yes” when given themselves as input—in this case, ProgramA.exe, NameSize.exe, and SizeChecker.exe. The last line in the table is something of a mystery, since it seems as though either possible output might be correct. The text discusses this in more detail.
We need to note two more things about this rather interesting program, YesOnSelf.exe. First, take a look at the last line in the table above. What should be the output of YesOnSelf.exe, when it is given the file YesOnSelf.exe as an input? Luckily, there are only two possibilities, so we can consider each one in turn. If the output is “yes,” we know that (according to the definition of YesOnSelf.exe), YesOnSelf.exe should output “yes” when run on itself. This is a bit of a tongue twister, but if you reason through it carefully, you'll see that everything is perfectly consistent, so you might be tempted to conclude that “yes” is the right answer.
But let's not be too hasty. What if the output of YesOnSelf.exe when run on itself happened to be “no”? Well, it would mean that (again, according to the definition of YesOnSelf.exe) YesOnSelf.exe should output “no” when run on itself. Again, this statement is perfectly consistent! It seems like YesOnSelf.exe can actually choose what its output should be. As long as it sticks to its choice, its answer will be correct. This mysterious freedom in the behavior of YesOnSelf.exe will soon turn out to be the innocuous tip of a rather treacherous iceberg, but for now we will not explore this issue further.
The second thing to note about YesOnSelf.exe is that, as with the slightly more complicated AlwaysYes.exe, I didn't actually write the program. All I did was describe its behavior. However, note that if we assume I did write AlwaysYes.exe, then it would be easy to create YesOnSelf.exe. Why? Because YesOnSelf.exe is simpler than AlwaysYes.exe: it only has to examine one possible input, rather than all possible inputs.
AntiYesOnSelf.exe: The Opposite of YesOnSelf.exe
It's time to take a breath and remember where we are trying to get to. The objective of this chapter is to prove that a crash-finding program cannot exist. But our immediate objective is less lofty. In this section, we are merely trying to find an example of some program that cannot exist. This will be a useful steppingstone on the way to our ultimate goal, because once we've seen how to prove that a certain program can't exist, it will be reasonably straightforward to use the same technique on a crash-finding program. The good news is, we are very close to this steppingstone goal. We will investigate one more yes-no program, and the job will be done.
The new program is called “AntiYesOnSelf.exe.” As its name suggests, it is very similar to YesOnSelf.exe—in fact, it is identical, except that its outputs are reversed. So ifYesOnSelf.exe would output “yes” given a certain input, then AntiYesOnSelf.exe would output “no” on that same input. And if YesOnSelf.exe outputs “no” on an input, AntiYesOnSelf.exe outputs “yes” on that input.
Whenever the input file is a yes-no program, AntiYesOn-Self.exe answers the question:
Will the input program, when run on itself, output “no”?
A concise description of the behavior of AntiYesOnSelf.exe.
Although that amounts to a complete and precise definition of AntiYesOnSelf.exe's behavior, it will help to spell out the behavior even more explicitly. Recall that YesOnSelf.exe outputs “yes” if its input would output “yes” when run on itself, and “no” otherwise. Therefore, AntiYesOnSelf.exe outputs “no” if its input would output “yes” when run on itself, and “yes” otherwise. Or to put it another way, AntiYesOnSelf.exe answers the following question about its input: “Is it true that the input file, when run on itself, will not output ‘yes'?”
Admittedly, this description of AntiYesOnSelf.exe is another tongue twister. You might think it would be simpler to rephrase it as “Will the input file, when run on itself, output ‘no'?” Why would that be incorrect? Why do we need the legalese about not outputting “yes,”
instead of the simpler statement about outputting “no”? The answer is that programs can sometimes do something other than output “yes” or “no.” So if someone tells us that a certain program does not output “yes,” we can't automatically conclude that it outputs “no.” For example, it might output garbage, or even freeze. However, there is one particular situation in which we can draw a stronger conclusion: if we are told in advance that a program is a yes-no program, then we know that the program never freezes and never produces garbage—it always terminates and produces the output “yes” or “no.” Therefore, for yes-no programs, the legalese about not out-putting “yes” is equivalent to the simpler statement about outputting “no.”
Finally, therefore, we can give a very simple description of AntiYesOnSelf.exe's behavior. Whenever the input file is a yes-no program, AntiYesOnSelf.exe answers the question “Will the input program, when run on itself, output ‘no'?” This formulation of AntiYesOnSelf.exe's behavior will be so important later that I have put it in a box above.
Given the work we've done already to analyze YesOnSelf.exe, it is particularly easy to draw up a table of outputs for AntiYesOnSelf.exe. In fact, we can just copy the table on page 187, switching all the outputs from “yes” to “no” and vice versa. Doing this produces the table above. As usual, it would be a good idea to run through each line in this table, and verify that you agree with the entries in the output column. Whenever the input file is a yes-no program, you can use the simple formulation in the box on the previous page, instead of working through the more complicated one given earlier.
Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers Page 20
