What Did Turing Establish About the Limits of Computers and the Nature of Mathematics?

Artist Stephen Kettle's stacked slate sculpture of Alan Turing.Artist Stephen Kettle's stacked slate sculpture of Alan Turing.Flickr Steve Parker (CC)

Editors’ Note: This is the fourth and last in a series of essays, written by Jack Copeland, spotlighting Alan Turing, who is considered the father of modern computing and whose work breaking German codes changed the course of World War II.

In the 1930s, a group of iconoclastic mathematicians and logicians launched the field we now call theoretical computer science. These pioneers embarked on an investigation to spell out the meaning and limits of computation. Pre-eminent among them were Alan Turing, Kurt Gödel, and Alonzo Church. These three men are pivotal figures in the story of modern science, and it’s probably true to say that, even today, their role in the history of science is underappreciated. The theoretical work they carried out in the ’30s laid the foundations for the computer revolution, and the computer revolution in turn fuelled the rocketing expansion of scientific knowledge that characterizes modern times. Previously undreamed of number-crunching power was soon boosting all fields of scientific enquiry, thanks in large part to these seminal investigations. Yet at the time Turing, Gödel, and Church would have thought of themselves as working in a most abstract field, far flung from practical computing. Their concern was with the very foundations of mathematics.

Gödel, a taciturn twenty-five-year-old mathematician from Vienna University, ushered in a new era in mathematics with his 1931 theorem that arithmetic is incomplete. In a sentence, what Gödel showed is that more is true in mathematics than can be proved. This sensational result shocked, and even angered, some mathematicians. It was thought that everything true could be proved, and moreover that everything that matters ought to be proved, because only rigorous proof by transparent and obvious rules brings certainty. But Gödel showed that, no matter how the formal rules of arithmetic are laid down, there would always be some mathematical truths—complicated relatives of simpler truths like 1+1=2—that cannot be proved by means of the rules. Paradoxically, the only way to eradicate incompleteness appeared to be to select rules that actually contradict one another.

Gödel’s epoch-making result seemed to leave one of mathematics’ most fundamental problems open, though—and that’s where Turing entered the picture. This unresolved problem was known as the Entscheidungsproblem, or decision problem. German mathematician David Hilbert had brought the Entscheidungsproblem into the spotlight. Hilbert, who was 50 years Turing’s senior, set the agenda for much of twentieth-century mathematics, in a speech he gave in Paris at the turn of the century, and by the 1930s he was virtually the pope of mathematics. Turing—untidy, irreverent, and scarcely older than an undergraduate—took on the Entscheidungsproblem, and proved Hilbert fundamentally wrong about the nature of mathematics.

Turing summarized the Entscheidungsproblem like this: Is there a “general mechanical process” for telling whether any given formula is provable? (Here “provable” means that the formula can be derived, step by logical step, using the rules and principles of Hilbert’s famous logico-mathematical calculus—known to math buffs as the “engere Functionenkalkül.”) Gödel gave a dramatic and easy-to-understand explanation of what Turing established about the Entscheidungsproblem. Gödel described an imaginary machine—a computing machine—looking something like a typewriter, except for having a crank-handle at the side. “Turning the handle” was Gödel’s metaphor for what we now call “executing an algorithm.” The user typed a mathematical, or logico-mathematical, formula at the keyboard and then turned the crank-handle round once. (The formula the user elected to type could be either true or false.) On Hilbert’s—essentially computational—view of the nature of mathematics, this computing machine could, in principle, be designed to behave as follows. When the crank was turned, the machine would sound its bell if the typed formula were a provable one; and if, on the other hand, the formula were not provable, then the bell would remain silent.

In a word, this machine is able to “decide”—in the sense of figure out or calculate—whether the typed formula is a provable one or not (hence the term “decision problem”). What Turing established is very simply stated: such a machine is impossible. Once you stray beyond the most elementary areas of mathematics (like Boolean algebra and the pure monadic functional calculus) it’s simply not possible to design a finite computing machine capable of deciding whether formulae are or are not provable. It was in a 1939 lecture in the United States that Gödel gave this summary of Turing’s result, and he rounded off his exposition with the dramatic remark that, at bottom, what this shows is that “the human mind will never be able to be replaced by a machine.” Had Turing been there, he might have objected that the issue about the mind is not quite so simple—but that’s another story.

It was precisely in order to prove the impossibility of this decision-machine that Turing dreamed up his universal computing machine—his ingeniously simple digital processor with an indefinitely extendable memory. By using programs stored in its memory, the universal machine can carry out every possible computation, Turing argued. Scarcely more than a decade later, on the back of wartime technology, Turing’s invention moved out of the realm of purely theoretical constructs, to become real hardware. As we now know, the electronic universal machine went on to transform science and society both. But when Turing invented it, he wasn’t thinking about electronic computers at all. Strangely enough, he was intent on proving the existence of mathematical realms that in a certain sense lie beyond the range of any computer, no matter how powerful.

Gödel’s own greatest gift to computer science—the branch of mathematics known as recursive function theory—was also a product of this curiosity-driven exploration of mathematics’ deepest foundations. Recursive function theory is essentially the theory of computer programs, yet when Gödel invented it, he wasn’t thinking about what we now call computing at all. He was working on the proof of his incompleteness theorem, and experiencing the first hazy glimpses of an unknown mathematical world—the strange and exciting landscape that lies beyond the computable.

Would you yourself be inclined to say that computers could perform any and every well-defined mathematical task? If not in practice, then at any rate in principle? In practice, some tasks would involve such vast amounts of processing that the fastest computers would take zillions of years to complete them, and moreover the numbers involved would get so large as to swamp any realistic amount of memory. But let’s use the term “digital super-optimism” for the view that computers can, in principle, do anything and everything mathematical—if only their human programmers are able to devise the right programs, and if only enough memory and processing power are on tap. In fact, even infinite tasks can be programmed, so long as it’s assumed that the computer running the program has access to unlimited memory (as the abstract universal Turing machine does). One example of an easily programmed infinite task is to calculate x2 for x = 1, then x = 2, then x = 3, and so on, ever onwards through the integers. There is no end to this program’s calculations. Whatever gigantic number x you might consider—a billion times the number of nanoseconds in a billion years, for instance—the program will eventually reach that number and calculate its square.

Turing showed, however, that digital super-optimism is false. It is definitely not the case that all well-defined mathematical tasks can be done by computer—not even in principle. Some tasks just can’t be performed by computing machines, no matter how good the programmers or how powerful the hardware. Turing was the first to describe examples of tasks like this, and in discovering them he blazed a trail through the new landscape glimpsed by Gödel—the unknown world of uncomputability.

Some of Turing’s examples are simpler than others, and the simplest one is quite surprisingly straightforward. The task is this: to work out, about any given computer program (in some specific programming language, C++ for instance) whether or not running the program will involve outputting a given keyboard character, say “#.” It might seem a relatively easy task for someone who understands the programming language to scan through the lines of a program and figure out whether any instruction is going to result in the computer’s outputting the character “#.” Yet Turing showed that no computer can perform this task. (The reason, essentially, is that the scope of the task covers all computer programs, including the program of the very computer attempting the task.) Another example of an uncomputable task is provided by Turing’s result about the decision-machine: no computer can decide if arbitrarily selected formulae are provable or unprovable in Hilbert’s engere Functionenkalkül.

Between them, Gödel and Turing delivered a double blow to Hilbert’s account of the nature of mathematics, from which it never recovered. Gödel’s incompleteness result devastated Hilbert’s theory that mathematics is essentially about proof, and five years later Turing showed that there is much more to mathematics than just computation.

In the autumn of 1936 Turing left England for the USA, planning to write a PhD thesis at Princeton University. His supervisor there was Church, third of the three central figures in the 1930s attack on computation. Church was a few years older than Turing and a young turk in the Princeton mathematics department. At the end of the 1920s he had spent six months studying with Hilbert’s group in Germany. Church’s leading contribution to the 1930s revolution—he called it the ‘lambda calculus’, after a letter from the Greek alphabet—later became part of computer programming’s basic toolset.

Before Turing’s departure from England, he and Church had almost simultaneously proposed two different mathematical definitions of the idea of computation. Gödel was not at all impressed with Church’s definition, bluntly telling Church that his approach was ‘thoroughly unsatisfactory’. Turing’s definition, on the other hand, Gödel found “most satisfactory.” Even the modest young Turing admitted that his definition was “possibly more convincing” than Church’s. It was clear from the start that his and Church’s relationship was not going to fit into the usual student–supervisor pattern.

For his thesis topic Turing chose another of Hilbert’s pontifical claims about the nature mathematics—and once again he showed that mathematical reality is not as Hilbert thought. This time the disagreement concerned what mathematicians call intuition. Most people are able to see by intuition that elementary geometrical propositions are true—for instance, that a straight line and a circle can intersect no more than twice. There’s no need to go through a train of logical steps to convince yourself that this proposition is true. Simple “seeing,” in contrast to following a conscious train of logical deductions (if this then that, and if that then such-and-such) is the hallmark of intuition. “The activity of the intuition,” Turing explained, “consists in making spontaneous judgments which are not the result of conscious trains of reasoning.” The more skilled the mathematician, the greater is his or her ability to apprehend truths by intuition.

Hilbert labelled intuition a ‘mysterious art,” believing it has no proper place in modern mathematics. He said that mathematicians should proceed “according to formulable rules that are completely definite.” In short, intuition was bad form, and refined mathematics consisted of applying rules, Hilbert believed. This was a view belonging to a previous, more uncomplicated, era. Gödel had shown in his 1931 incompleteness theorem that mathematics cannot be reduced to a system of rules, and now Turing, in his 1938 doctoral dissertation, pushed things along still further. He argued that mathematics is too unruly for intuition’s role even to be circumscribed, let alone eliminated as Hilbert had wished.

As the elimination of intuition was not attainable, Hilbert might conceivably have been willing to settle for regulating intuition’s role—for restricting its use to delivering a few clearly delimited steps in what are otherwise completely rule-governed trains of inference. Turing attacked that idea too: no bounds can be set on the need for intuition. Mathematical thinking, he summed up, should be regarded “as the exercise of a combination of two faculties, which we may call intuition and ingenuity.”

Questions for Discussion

1.     Does it matter that arithmetic is incomplete?

2.     Was Gödel right to say that “the human mind will never be able to be replaced by a machine?”

3.     What practical implications does the existence of uncomputability have for computing?

4.     Is the entire physical universe computable?

5.     Is it possible to create a “universal debugger”—a computer program that takes computer programs as input and locates any bugs in them?

6.     Can there be a different kind of information-processing machine—a “hypermachine”—that is able to do some of the tasks computers cannot?

7.     Do Turing’s ideas about intuition have any implications for how we should teach mathematics to children?

17 Responses

  1. spacecalculus says:

    Do Turing’s ideas about intuition have any implications for how we should teach mathematics to children?

    Mathematics, algorithms, computers are models of human intellect engineering movement to the energy source. 

  2. spacecalculus says:

    Yes, there will be a different kind of information-processing machine⎯a “hypermachine”⎯that is able to do some of the tasks computers cannot.


    E = hν

    • Jack Copeland says:

      Hi spacecalculus, Thanks for your comments.

      I would say that there “might” in the future be hypermachines, rather than “will be”. Seems to me that it is an open empirical question.

  3. blindboy says:

    I think we know enough to be sure that the human mind has no resemblance to the machines that we are now capable of building. Any attempt to model it with existing technology will therefore fail. Consider the fact that the brain is as much a chemical system as a network of nervous tissue and it gives you some idea of how far we have to go. But, that said, I cannot see any fundamental reason to prevent the development of a true thinking system. There is something deeply recursive in the way thoughts arise and it may be that we can uncover some mathematical relationships within the structues of the brain that give rise to that flow of ideas and images we call thought.

    • Jack Copeland says:

      I don’t think we do know enough to be sure of that. After all, factory-made computers are chemical systems too. You might be looking at the wrong level. The resemblance between the human mind and the systems we are now capable of building could be that they are computers–although computers implemented in very different physicochemical ways.

  4. kulkarni says:

    The solution for Hilbert’s decision problem is found. I have found the formula that can be used to replace the logic by arithmetic. 

    We can replace logical test containing thousands of if else by single 

    mathematical equation. This converts logical operation to arithmetic operation.

    In other words we can convert decision algorithm into simple

    algorithm without decision trees. 

    This article is posted to brainstorm ideas link  http://brainstorm.ubuntu.com/idea/30683/  We can make elegant programming that saves time 

    memory and energy. 

    The complex program can be executable in an ordinary processor.  Therefore it can be useful for mobile tablet and all computers.

    • Jack Copeland says:

      Your post has been truncated. Please repeat.

      • kulkarni says:

        I have found the formula that can be used to reduce the
        logic to arithmetic in decision algorithm.The
        general formula is recently found. But for the value c=1/e the
        decision problem was posted to the vixra preprint archive link in
        2011 http://vixra.org/abs/1109.0054
        The general formula is
        where c belongs to (-infinity, infinity) and Y belongs to (-infinity, infinity)
        Now Y2=|Y1/logY1|
        For n terms
        Taking limit as n tends to infinity we get the
        following result.
        For Y greater than c then Yn=e and Z=f
        Y=c then Yn=1/e and Z=g
        For Y less than c then Yn=0 and Z=h
        where the
        function Z is given by
        By using this formula we
        can make elegant programming that saves time energy and the complex
        programme can be executable in ordinary processor. Therefore it can be
        useful for mobile tablet and all computers.

    • Jack Copeland says:

      Turing showed that Hilbert’s decision problem is in general unsovable. Special cases of the decision problem are certainly solvable; e.g. the monadic predicate calculus is decidable, and so is full predicate calculus minus contraction. What form of desision problem are you claiming to have solved?

      • kulkarni says:

        By using the formula Z we can convert non closed form expression into closed form expression. In logical language it is a first order logic. In otherwords, for n number of inputs  is there any mathematical formula that answer’s yes or no. Now it is possible by using the formula Z which is mentioned in the previous post.

        • Jack Copeland says:

          For some reason the machinery has truncated your reply again and I can read only the first 14 words of it.

          But here is a general question. What (if anything) is wrong with the following argument? Turing proved that Hilbert’s Entscheidungsproblem is unsolvable; therefore kulkarni has not solved Hilbert’s Entscheidungsproblem (at best kulkarni has found a decidable fragment of the full first order predicate calculus).

  5. Dr.GSPANGLOSS says:

    It is my understanding that Godel philosophical view on mathematics was in line with the idea that mathematical concepts exist in some form of Platonic realm(Mathnematical truths are discovered ,not invented),and that Godel described himself as a Mystic. In what respect did Turing’s philosophy regarding the ability of humans to understand mathematical concepts differ greatly from Godel’s ? Belief in the existence of a Platonic realm , and humanity’s ability to access it , would entail the belief that computers are unable to do likewise, unless our brains functioned akin,or identically to , a computer’s. Our early ancestors arrived at the idea of counting(most likely for practical reasons) , and many generations passed before someone took notice that these quantatative entities held specific properties which allowed the formation of idiosyncratic groups (odd and even numbers,Prime numbers,etc), and in addition, many inter-group connections existed,which can only be described as intuitively obvious, and many others were subsequently shown “waiting” to be discovered.At an early age many children are capable of grasping these concepts. Thus,if these non-physical connections were discovered , then it doesn’t take a leap of faith to infer  that these relationships existed prior to Homo  Sapiens’s arrival on earth, and continue to exist in a “Platonic Realm”(May be a basic property of the Universe?). I believe one can argue that the idea of counting is purely a human invention .But did the idea arise from empirical evidence ,or is the idea purely a human construct? it is much more difficult a task to argue that the properties held by the respective groups and the connections between groups , were and are purely a human invention , and not a discoverable property inherent to the Universe(s). Our present understanding of what constitutes the “Physical “Universe may be in it’s infancy(Dark Energy,Dark Matter,Multiverse(?),unknown unknown’s ). Perhaps a more pertinent question may be;Can computers(Webs etc)be programed , to discover something New about our Universe ?About infinity? In principle,can a computer be programmed to doubt, and then infer that  the only thing it cannot doubt ,is that it doubts, and then surmise that it exist?Or will it be caught in an infinite loop of regressive doubts?As presently understood, consciousness is an emergent property , and thus will  require a falsifiable, predictive “Theory of Emergence” , in order to understand how it arises,arises,arises…etc. If Strong AI is subsequently proved true, would it then make less consistent,and thus less tenable ,  the argument that God(A supreme intelligence) does not  exist ,since a purposeful conscious Power,would have endeavored to ,and subsequently created a purposeful conscious power, in his image ?If a computer could be programmed to “Know thy self”,and ” to thy own self be true”,would it conclude that it had no Creator? Is Qualia quantifiable  ?

    • Jack Copeland says:

      Gödel said ” The brain is a computing machine connected with a spirit.” Turing, on the other hand, seems to have been a materialist.

      Your question “In what respect did Turing’s philosophy regarding the ability of humans to understand mathematical concepts differ greatly from Gödel’s?” is a very interesting one and deserves a lengthy answer. Oron Shagrir and I have a chapter on that  topic in our book Computability: Turing, Gödel, Church, and Beyond, which will be published by MIT Press in a few weeks. Enjoy!

  6. Dr.GSPANGLOSS says:

    Intuition is a subconscious process , which “emerges” from neuronal networks (modules) established prior to birth,and the subsequent remodeling of these electrochemical connections by  subtraction,addition ,and recombination of these connections ,throughout the lifetime of an individual. Soon after birth(perhaps in utero ) ,this remodeling  is based predominantly on external stimulation, but at some point ,the  Mind Bank has sufficient information to create new patterns based on stored memories , despite potentially deleterious reduction of external stimulation. Recent studies using fMRI’s lend strong evidence for supporting the hypothesis that all conscious activity is first subconscious (There is a part of “I”  ,that knows what “I” am going to do , prior to “I” being aware of it).  Anyone having achieved moderate proficiency in any human activity, or watched a world class athlete perform , and contemplated on these achievements should not be surprised by these results. So it is not the unconscious   electrochemical self modeled by computer’s ,or information networks  , that I think is unachievable ,but instead , self -reflection emerging from creations of man…. Whether or not by intent of God , the initial  conditions present during the Evolution of the human mind , may never be reproducible in a lab, and thus creation of Man’s mind, by humankind, may lie beyond the boundary of the  knowable……Regarding children,notwithstanding the limits of formal logic ,and the intuitive nature of the human mind, logical connections ( EXPLAINATION,LANGUAGE) should always be addressed ,and reinforced , while  teaching of mathematics to children ,  in addition to applications to “real” world problem solving. If not ,many will simply memorize algorithms.

  7. Dr.GSPANGLOSS says:

    To teach math,Metaphors and Analogies  in words and pictures are invaluable . Will computers ever be able to select from a list of computer programs using mathematical modeling  , without aesthetic considerations, the candidates most likely to succeed in solving, and adding further understanding to the greatest mysteries of our Universe, as detailed in the previous  BQOL–I think not.

    • Jack Copeland says:

      I think you are using ‘intuition’ in a sense that is different from Turing’s.

      But I agree that much of our cognitive activity appears to be non-conscious.

      However, this does not seem to me to constitute an argument against the possibility of AI (as I think you are suggesting). Rather it makes AI’s task easier, if anything. If thought were essentially conscious, that would create a difficulty for AI, since it is totally unclear how artificial consciousness could be created. However, artificially replicating non conscious cognition seems more approachable.