The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us

6. Computing Impossibilities

6 I whispered, “I am too young,” And then, “I am old enough”; Wherefore I threw a penny To find out if I might love. “Go and love, go and love, young man, If the lady be young and fair.” Ah, penny, brown penny, brown penny, I am looped in the loops of her hair. O love is the crooked thing, There is nobody wise enough To find out all that is in it, For he would be thinking of love Till the stars had run away And the shadows eaten the moon. Ah, penny, brown penny, brown penny, One cannot begin it too soon. —William Butler Yeats (1865–1939), “Brown Penny” The only way of finding the limits of the possible is by going beyond them into the impossible. —Arthur C. Clarke (1917–2008) In the end, we self-perceiving, self-inventing, locked-in mirages are little miracles of self-reference. —Douglas R. Hofstadter, I Am a Strange Loop Computers can do many wonderful things. However, there are many tasks that they cannot perform. Computers cannot determine whether a painting is beautiful; they do not “understand” moral issues; and they cannot fall in love. Such “human” processes are beyond computation. Computing Impossibilities 136 Chapter 6 Whether a painting is beautiful is subject to taste, and computers don’t have taste. They also don’t have a sense of ethics to deal with moral questions . All of these questions are subjective and computers don’t do well with subjective questions. In this chapter, we will explore certain problems that have objective answers but that nevertheless cannot be solved by computers. It is important to note that these tasks do not require a long time to compute (as in the last chapter); rather, they can never be done. Nor is this a problem related to our current level of computer technology. No computer , regardless of how fast and powerful, will ever be able to solve these problems. Section 6.1 starts with a short discussion of programs, algorithms, and computers. A problem that cannot be solved by any computer, the Halting Problem, is introduced in section 6.2. I show that it is not solvable by any computer. This is not to be taken on faith. Rather, I carefully go through the proof that demonstrates any computer’s inability to solve this problem. With the unsolvability of the Halting Problem in hand, I move on to section 6.3, where I show that many other problems are unsolvable. Section 6.4 describes a hierarchy or classification of unsolvable problems. I conclude with section 6.5, which addresses more philosophical questions like the relationship of brains, minds, and computers. 6.1 Algorithms, Computers, Machines, and Programs We have all experienced computers “getting stuck” or entering into an “infinite loop.” Try as we like, our computers get looped in the loops of their programs. Once in an infinite loop, they never leave. Microsoft Windows taunts us with the words “Not Responding.”1 Wouldn’t it be nice to buy a piece of software with the reassurance that this could never happen? It would be great if there were some method to determine if a program will halt (or terminate) in a normal manner as opposed to entering into an infinite loop. Alas, no such method exists. This is one of the first problems shown to be unsolvable by a computer. Even though the question of whether a program will halt is objective and not subjective, there is no way a computer can solve it. Before we begin, some terminology is in order. A computer is a physical machine that executes algorithms. Programs are exact descriptions of algorithms. When we say that there is no algorithm that solves a par- Computing Impossibilities 137 ticular problem, we also mean that there is no program, computer, or machine that can perform that task. We are describing a limitation of mechanized processes and we will employ all four of these words interchangeably. In my discussion of whether a program does or does not halt, rather than talking about all programs, I restrict myself to special types of programs that only deal with whole numbers. Before suspecting that I am trying to trick you by only looking at this restricted set of programs, you should keep two things in mind. First, I am going to show that even for this restricted set of programs, no computer...