An Obituary for Machines of Loving Grace
Back in the 1960's (which, as you may remember, was before the hippies discovered ecology and technology became a dirty word to establishment intelligentsia) a group of society intellectuals made a somewhat original approach to The Problem Of Convincing Americans That The Welfare State Is Good For Them. Calling themselves Committee for the Triple Revolution, they argued that contemporary welfare recipients were simply the vanguard of a mode of existence about to become universal. Soon, they said, machines would be able to do everything that people were still paid for doing. Since everybody was going to join the crowd on welfare in a few years it would be better if everyone forgot about the work ethic; that way, they told us, nobody was going to be ashamed of not working, and everyone would relax and enjoy the millennium to come. Soon, clergymen were preaching sermons about a world where people would not be distracted from the appreciation of God's bounty by having to solve the crass problems of worldly existence. The problems would be taken care of by machines of loving grace, machines which would take the world's burdens on their shoulders. Then, one day, the Triple Revolution vanished and was never heard from again.
I cannot tell you exactly how the bubble burst, but my guess is that one day a member of the Committee finally got around to asking an engineer to endorse its scheme; the engineer told him that the scheme won't work, and told him why. This article is about that hypothetical engineer's reasons: a family of theorems in which the thesis, that one can build a machine to solve any problem that people can solve, is shown to be false. In proving these theorems, nothing is assumed about machines except that they are determinate. A determinate entity is an entity whose state and input at any given moment uniquely determine its state in the next. Such an entity can be simulated with any desired degree of accuracy by an appropriate computer program.
TURING'S THEOREM
The first theorem of the type which we are about to examine was proved in 1936 by A.M. Turing[1]. Turing's theorem is available in several books[2], and there would be no point in presenting here the entire proof. In its original version, the theorem dealt with a mathematical model of a computer called a "Turing Machine". Its method, however, is quite general, and can be used to prove equivalent theorems for all deterministic computer languages, including languages yet to be written.
In simulating the behavior of an entity, a computer goes through a program consisting of a series of discrete statements, corresponding to the entity's states. If we want to use a program to determine a certain result we must include, in addition to statements that the program will have to go through to obtain an answer, two other groups of statements: those that can be reached only if the answer is "yes" (corresponding to the definite-yes statements), and those that can be reached only if the answer is "no" (the definite-no statements). A machine is said to have solved a problem, or answered a question, if it reaches and permanently (or at least long enough to effect a response) remains in one of the two groups of definite-states.
If we can write a program simulating an entity which can solve some problem or answer some question, then we can have a program which can answer that question (or solve that problem). Computer programs may answer two types of questions: those having one specific referent, the identity of which is implicit in the program; and those referring to one of a class of objects, the description of a particular member of the class being provided to the computer as input. One class of objects which may be described in a form appropriate for input to a computer is the class of computer programs. It is therefore possible for computer programs to answer questions about computer programs.
Consider any particular program written to answer questions about programs. One of the most interesting questions we can ask about such a program is this: will it answer the question it is supposed to answer, when that question is asked about itself? Or, to phrase it in a more technical way: will the given program reach one of its definite statements if it is given its own description as input? We will now compare results when machine and human both attempt to answer this question about a particular hypothetical program. We will assume, in order to show false by reductio ad absurdum, the hypothesis that one can write a program ("program A") which will be able to answer this question in every case in which a human can answer it.
Now we proceed to find a program such that a human can answer the given question about it, but program A cannot. Such a program can be obtained—and this is the core of the proof—by modifying the hypothetical program A. A, being deterministic, can enter one of the definite-yes statements in only two ways: from an immediately preceding statement, or from a transfer statement elsewhere in the program. One can therefore obtain a "program B", which can never enter a definite-yes statement, by modifying program A as follows: 1) An instruction to transfer back to the very beginning of the program is inserted in front of every definite-yes section of the program, and 2) Such an instruction is substituted for every transfer to a definite-yes statement. The above modifications will prevent B from ever reaching a definite-yes statement. Since A and B are both deterministic, B will still reach a definite-no statement whenever A does. This is the only kind of definite statement which B can reach.
Will A reach a definite statement about B? If A were to reach a definite-yes statement, then B would never reach a definite statement at all, an answer of "yes" would be false, and A would not be able to reach a definite-yes statement: a contradiction. Now suppose A were to reach a definite-no statement about B. Then B would reach this very same definite-no statement, so that the answer "no" would be false, and A would not be able to reach a definite-no statement: contradiction again. Thus, A cannot reach either kind of definite statement about B. This means that A cannot tell whether or not B will ever reach a definite statement about itself. But we can. If A will never reach a definite statement about B, neither will B. The assumption—that one could write a program, called A, which would answer the question "will the following program reach one of its definite statements if it is given its own description as input?" whenever we could answer it—is thus shown by contradiction to have been false. We humans, then, can indeed solve problems no deterministic entity could ever solve.
INTELLECTUAL AMMUNITION, REVISITED
By this time, the reader has probably asked himself, "so what?". The Committee for the Triple Revolution has been defunct for years. Faced with the fanatical anti-industrial bent of today's collectivists, one almost wishes it were still around. The only technology today's collectivists approve of is the behavioral technology of B.F. Skinner's WALDEN TWO and BEYOND FREEDOM AND DIGNITY. What good is it, now, to know one can do some things no machine can?
As it happens, a lot of good. Remember, the only thing we assumed about the hypothetical machine A was that it was determinate. It could solve any problem any determinate thing could solve. By solving a problem that A could not solve, we can prove, with mathematical rigor, that we, humans, are not deterministic. That ought to be worth something. Collectivism is based on a denial of individual choice. Such a denial can be justified only by claiming that there is no such thing as individual free choice in the first place. For this reason every collectivist ideology, from Marx to Skinner, has been based on a firm belief in determinism. A good argument against determinism would clearly be useful in countering these ideologies.
The construction of such an argument has been attempted before. Nathaniel Branden, writing in the "Intellectual Ammunition Department" of the OBJECTIVIST NEWS LETTER[3], demonstrated that knowledge would not be possible to a determinate entity. Accordingly, anyone claiming knowledge of determinism was caught in the fallacy of self-exclusion. Branden's approach, while elegant, left something to be desired. One critic noted that "Branden's argument…has disposed of determinists, but not of determinism. Branden has ended the debate by showing that, even if determinism were true, it could never be known to be true. He has not shown determinism to be false."[4]
Turing's theorem suffers from no such shortcoming. It attacks determinism on the latter's home turf, and destroys it. Turing's theorem can knock out a key tenet from under collectivist ideologies. Once understood, it should become one of the most powerful weapons in the intellectual arsenal of every libertarian.
Adam Reed is a Ph.D. candidate in mathematical psychology at the University of Oregon. He holds B.S. and M.S. degrees in electrical engineering and biology from MIT. His article "Resolving Disputes in a Free Society" appeared in the March 1973 issue of REASON.
NOTES AND REFERENCES:
[1] A.M. Turing, "On computable numbers, with an application to the Entscheidungs problem," PROCEEDINGS OF THE LONDON MATHEMATICS SOCIETY, (SER.2) 42:230-65 (1936), 43:544 (1937).
[2] The following three books cover the range: Davis for mathematicians, Minsky for people with any kind of technical background, and Arbib for those with nothing except intelligent minds. Martin Davis, COMPUTABILITY & UNSOLVABILITY (New York: McGraw-Hill 1958), 210 pp.; Marvin L. Minsky, COMPUTATION: FINITE AND INFINITE MACHINES (Englewood Cliffs: Prentice-Hall 1967), 317 pp.; Michael A. Arbib, BRAINS, MACHINES, AND MATHEMATICS (New York: McGraw-Hill 1964), 152 pp.
[3] Nathaniel Branden, "Determinism (Intellectual Ammunition Department)" OBJECTIVIST NEWSLETTER, 3:3 (January 1964).
[4] R.E. Merrill, personal communication.