Today, I want to talk about computation. That word probably sounds like it has something to do with computers, and in a way it does, but computation is really a fundamental concept, part of the deep mysteries of the universe, one that transcends any particular technology. If you showed me some alien civilization on a distant planet, I would not be surprised to find that they had something resembling computers, yet that those computers worked in ways rather different from ours. That would not surprise me at all.
What I would bet a great deal of money on, however, is that any such alien civilization had discovered exactly the same notion of computation that we are going to be talking about today.
The story of computation can begin at many different points in time, but I've chosen to start in 1936, the year Alan Turing published his landmark paper, On Computable Numbers, with an Application to the Entscheidungsproblem. Please forgive my German.
The name Alan Turing may be familiar for several reasons. You may have heard of the Turing test, which Turing proposed roughly 75 years ago as a criterion for artificial intelligence. His idea was that once a computer could converse with a human being so convincingly that the human could not tell whether they were speaking to a machine or to another person, that computer would have passed the Turing test. By that measure, there is no question that modern AI has indeed passed it.
You may also know Turing through his code-breaking work at Bletchley Park during World War II, or through the persecution he suffered at the hands of the British government for his homosexuality and the posthumous pardon that followed. Some of these stories were depicted, with varying degrees of accuracy, in the film The Imitation Game. All of those accounts concern exactly the same Alan Turing.
It has been genuinely gratifying to watch Turing's name recognition grow over the course of my lifetime. Computer scientists tend to feel that Alan Turing's name deserves to be as widely known as, say, Albert Einstein's. We are not quite there yet, but the progress over the last couple of decades has been encouraging.
Many computer scientists, myself included, view Turing's 1936 paper as literally the birth of computer science as a scientific discipline. That is a pretty big deal, and a couple of things about this fact are genuinely wild.
First, 1936 predates computers in any form we would now recognize. The first serious efforts to build general-purpose computers came roughly a decade later, in the late 1940s. If you have heard of ENIAC or EDVAC, the projects John von Neumann was involved in, those are two examples. Turing's paper rewinds ten years before any of that, to a time when nobody was even trying to build a computer.
In fact, in 1936 the word "computer" already existed, but it referred to a job description, a profession held by human beings. Even in the 1930s there was considerable demand for systematic large-scale calculation, whether in astronomy, the military, or business planning, and the people employed to perform those calculations were called computers. That is what the word meant in that era.
So the first wild thing is that computer science was invented as an academic and scientific discipline a full decade before actual computers existed. The second wild thing is that Turing accomplished this essentially as a byproduct of solving a mathematical problem, one that loomed large among mathematicians but would have seemed completely esoteric to anyone else. That problem is the one named in the title of his paper: the Entscheidungsproblem, which translates literally as "decision problem." Before getting into what Turing did in that paper, it is worth spending a moment on the mathematical backstory, what the problem actually was, and why anyone cared about it.
Much of the backstory here concerns a famous German mathematician of the late nineteenth and early twentieth centuries named David Hilbert. Among other things, Hilbert keenly understood the role of open problems in mathematics. It is difficult to overstate how much the field of mathematics revolves around big open problems. In 1900, Hilbert gave a keynote address at the International Congress of Mathematicians in Paris, one of the first ICMs, in which he presented a list of twenty-three unresolved mathematical problems, problems where we did not know whether a given statement was true or false, and if true, did not know how to prove it. He issued this list as a challenge to the entire field.
Open problems have been a tremendous organizing force for mathematical disciplines, giving everyone a yardstick by which to measure progress and to recognize a genuine breakthrough, namely, when one of these major open problems gets resolved. Even when mathematicians conjecture statements that ultimately turn out to be false, the effort still generates an enormous amount of scientific progress. In homage to Hilbert's 1900 list, the Clay Institute issued seven Millennium Problems in 2000, again meant to inspire the full field of mathematics to rally around solving deep, open questions. One of those seven is the P versus NP question, which we will return to in the fourth episode.
Several of the problems on Hilbert's 1900 list concerned, in some sense, establishing that we are doing mathematics the right way. Hilbert speculated that the way we prove statements true should be what he called complete, meaning that whenever a mathematical assertion is in fact true, there should exist a proof, a finite sequence of logical steps, that establishes it. In other words, every true statement should have a proof that demonstrates its truth.
Beyond completeness, Hilbert also asked whether there might be a mechanical method, an automated procedure, for arriving at these proofs of true statements. This aspiration became part of what is known as the Hilbert Program, seeds of which appeared in the 1900 address and which he continued to develop throughout the early twentieth century. It culminated in his 1928 book Principles of Mathematical Logic, in which he articulated very precise conjectures about the nature of mathematics as we know it, including what is now called the decision problem.
Turing's paper belongs to this broader intellectual context; it was published a full eight years after Hilbert's program was set out in book form. In between Hilbert and Turing stands another name you may have heard: Kurt Gödel, the famous logician who in 1931 proved what is now known as Gödel's incompleteness theorem. This was a landmark result, and it demonstrated that the first of Hilbert's conjectures was simply wrong.
What Gödel showed is that the formal systems we use to write down mathematics and construct proofs are not sufficient to establish all true statements. There are statements we regard as true that nevertheless elude proof within those systems. In a precise sense, the number of true statements outnumbers the number of proofs we can produce. This property is what mathematicians mean when they say that mathematics is incomplete: there exist true statements for which no proof will ever be found.
That was a profound blow, and it basically shattered a large part of Hilbert's vision for what mathematics could achieve. Gödel's incompleteness theorem also resonated far beyond mathematics, most famously in philosophy, through the Lucas–Penrose interpretation, which holds that there are aspects of human thought that cannot be simulated by any computer. That claim remains hotly debated, and it would make for a fascinating discussion in its own right, though it lies somewhat outside our present scope.
For now, the key point is that by 1931 Gödel had dismantled one pillar of Hilbert's program. We move forward five years, from 1931 to 1936, to see what came next.
What was left for Turing to do after Gödel's incompleteness theorem? In mathematics, when something you hoped was true turns out not to be, the natural next question is: what would be the next best thing? What is the most one could hope for, given what we now know? There will always be statements that are true and provable: one plus one equals two, for instance. But Gödel exhibited other statements that are true yet unprovable.
This brings us to the automated part of Hilbert's program: the idea that there should be a mechanical way of generating proofs of true statements. Given Gödel's result, the best one could still hope for is that whenever a proof exists, even if not every true statement has one, there would be an automated method for finding it. That is precisely the decision problem that Turing addressed. Gödel's result did not rule out the possibility that, for any provably true statement, a mechanical procedure could generate its proof, and this is exactly what Turing showed is also not the case, in his famous 1936 paper.
What would it mean to disprove the decision problem? One must show that there are true statements that have proofs, yet whose proofs elude any mechanical method one might use to find them. The difficulty is that the phrase "any mechanical method" was not a mathematically well-defined concept, at least not before Turing's paper.
To make sense of what it would mean to show that a decision problem is unsolvable, one must necessarily commit to a mathematical formalization of what mechanical procedures, or, in our context, computers, can do. In order to show limitations on computation, in order to show that there are things computers cannot do, you must first formalize what it is that they can do. This brings us to the first great reason why Turing's 1936 paper is so important: his mathematical formalization of what mechanical procedures, or what we would call computers, are capable of.
How did he formalize that? This is where Turing machines enter the story. By all accounts, when Turing conceived of the Turing machine, he was inspired by the human computers we discussed earlier, literally people like you and me, working with a large scratch pad and a pen, carrying out calculations. He asked: what if we imagine a long roll of paper, extending as far as you like? Different locations on this paper can be read and written, and there is a person working somewhere along it, performing calculations.
That person might look at a number, decide to change it, say, replacing a one with a four, and then move along the roll to examine what is written a little further down. That, in essence, is a Turing machine. A program is specified by a small list of rules that determine what the person should do upon seeing a given symbol. If you are carrying out addition, that is one set of rules; if you are carrying out multiplication, that is a different set of rules, producing different calculations on the long roll of paper.
A single step of a Turing machine consists of exactly this: examining the current location on the tape, optionally using the rules to overwrite the symbol there with a new one, and then optionally moving one position to the right or to the left. Throughout this process, the machine maintains a bounded amount of internal memory to keep track of what it has seen and done. And that, honestly, is a Turing machine.
A Turing machine might strike you as pretty quaint, especially when you consider that you may have a fancy new MacBook Pro sitting on your desk. It might seem as though that laptop is a little more useful, a little more powerful than a Turing machine. In an obvious sense that is true, but in a much deeper, more fundamental sense, the MacBook Pro you are using is not more powerful than a Turing machine. We believe that Turing machines are as powerful as any reasonable model of computation, including very direct models of the computers we use today.
That belief, that Turing machines capture computation in its full generality, is known as the Church-Turing thesis. We will return to it at the end of this episode. At first this might seem crazy. You might be thinking: "You're telling me that cartoon machine is as powerful as my shiny new laptop?" Let me mention a couple of things that may make the gap seem smaller than it initially appears.
The first thing to notice is that you really can program a Turing machine. Recall that the human computer looks at a value on a piece of paper, decides on a new value to write, and moves either left or right: that is one step. All of those decisions, what new value to write and which direction to move, are defined by a set of rules. For addition you would use one set of rules; for multiplication you would use a different set. The rules can be whatever you want, and they can be arbitrarily complex. You could have a million rules specifying all manner of actions to take under different circumstances.
There are therefore a literally infinite number of possible programs you could run on a Turing machine, corresponding to the different rules this calculator could use to update the values on the paper. The key point is that a Turing machine is not limited to one type of calculation; it can perform whatever calculations you can write down rules to describe.
The second point, and this may or may not resonate with you depending on whether you have seen examples, is that even if you fix the program, even if you fix the set of rules, sometimes for very short lists of rules, iterating those rules over and over again can produce remarkably complex phenomena. John Conway's Game of Life is a great example: very simple rules, applied repeatedly, lead to extremely complex and visually striking behaviors. One could even regard biological evolution as complexity, remarkable complexity, including ourselves, arising from the application of simple rules repeated over millions of years.
It gets even more striking. This is outside our scope, but if the idea of complexity emerging from tiny, simple programs intrigues you, look up the busy beaver function, which is defined in terms of Turing machines and illustrates just how extraordinary their behavior can be, even for very simple families of rules. Those are two reasons why, even if you are not yet convinced that Turing machines are as powerful as your laptop in some deep, fundamental sense, you might at least concede that they can do a great deal. In principle, you can program them in many different ways, and even simple programs can exhibit complex behavior.
Once you accept that, you might start worrying in the opposite direction. Given that there are so many different things a Turing machine can do, so many programs you can run, and given that those programs can generate such complex behavior, how would you ever establish limitations on what they can do? How would you argue that no Turing machine, no program, no matter how clever or sophisticated, could carry out some task of interest? That seems like an extraordinarily ambitious claim.
This is the second reason why Turing's 1936 paper is so important. Not only did he propose a mathematical formalization of what mechanical procedures, computers as we would say, can do, he also showed that there exist problems known as undecidable problems, which computers will never be able to solve. These are not merely strange, artificial problems we would never care about; they are problems we would genuinely and ideally want to solve, yet they are fundamentally unsolvable by computers: not just today's computers, but the computers of tomorrow, of a thousand years from now, of a million years from now. They are problems that fundamentally elude computation in its full generality.
I find this genuinely poignant. If you go back to the absolute first day of our discipline, computer science in some sense, you find that from day one, we have known disappointment. We have known that, for all the amazing things computers can do, there are limits. That limitation was established at the exact same moment the concept of computation was first formalized. That is part of the enduring legacy of computer science as a discipline.
One thing you might wonder, as you think about this a little more, is whether we should really be surprised that there are problems that elude computation by Turing machines. There are lots of Turing machines. The set of rules can be any finite set of rules, as long as you want, so there are a tremendous number of programs out there. But then you might say that there also seems to be a tremendous number of tasks we might ask computers to carry out, a vast number of problems that, if you wanted, you could try to get Turing machines to solve. Perhaps the number of problems in the world actually outnumbers the number of Turing machines, and so just by that counting argument, there must exist unsolvable problems.
Turing's paper, however, proves something far more interesting than merely the existence of unsolvable problems, what he calls undecidable problems. Even very practically motivated problems, problems useful enough to build a company around, can turn out to be unsolvable by computers. A natural example is the problem of finding bugs in programs. Those of you who have tried to program know how easy it is to make mistakes, and automated tools that point out errors in your code would be enormously valuable. Speaking in 2026, a great deal of code is being generated by AI, and tools to verify the correctness of that automatically generated code represent an extraordinarily practical problem.
A very special case of finding bugs in a program is something called the halting problem. Suppose I give you a computer program, say, 200 lines of Python or any other language you might be familiar with, and I ask you a single question: if you ran this program, would it complete? Would it halt? Or would it run forever, caught in an infinite loop? That is the halting problem. I give you a piece of code, and I want from you a simple yes or no: will it halt, or will it not?
Your first instinct might be to simply run the program and see what happens. If it halts, you can report that with confidence. But what if ten minutes pass and it is still running? You wait overnight, and it is still running. You wait a year, and it is still running. At that point, it seems like it must be in an infinite loop, but remember, even very short programs can exhibit tremendously complex behavior. The busy beaver functions I mentioned earlier are the classic example: very short computations that run for an obscene number of steps. The bottom line is that even after running a program for a year without it halting, you have no way of knowing whether it will halt tomorrow.
This shows that the obvious approach to the halting problem, mere simulation of the program, cannot work, because you can never be certain the program is in an infinite loop and will never halt. The real question, then, is whether some more clever method exists. Perhaps instead of running the program, you stare at those 200 lines of code, analyze them carefully, and reason your way to an answer. That is precisely what the halting problem asks: given a piece of code, determine by any means available whether it will halt.
The halting problem, Turing showed, is undecidable. There is literally no automated procedure that will take your 200 lines of code and always correctly tell you whether or not it will halt. This is not a limitation of our intelligence, nor a limitation of current technology. A thousand years from now it will remain true that there is no automated procedure for solving the halting problem. This is part of the nature of the universe.
To see the connection between the undecidability of the halting problem and the decision problem that Hilbert posed: if you are trying, in an automated way, to find a proof for some true statement, one approach is to simply try all proofs systematically, first all proofs that are one line long, then all proofs that are two lines long, then three lines long, and so on. But this runs into the same fundamental difficulty. If you have successfully verified that no proof of at most 10,000 lines establishes a given statement, you cannot directly conclude that the statement is unprovable, because there might be a proof of just 10,001 lines that does establish it.
In the same spirit that you cannot solve the halting problem through mere simulation, or, indeed, through any other method, the same holds for the decision problem. You cannot determine provability simply by trying longer and longer proofs, nor, as follows from Turing's work, can you do it via any other method. This does not mean we can never prove anything. Everything learned in a mathematics course consists of proofs of true statements, and the situation is analogous with the halting problem: there are many individual programs whose behavior is immediately obvious. A straight-line program with no loops clearly halts; a program that immediately enters an infinite loop clearly does not.
The point, however, is that there is no general automated procedure guaranteed to tell you, given an arbitrary piece of code, whether it halts or not. Similarly, there is no general automated procedure that takes an arbitrary mathematical statement as input and determines whether it is provable. Turing's development of undecidability, the idea that there are natural problems computers will never be able to solve, is so important that it is worth spending time on the key ideas behind it.
There is tremendous conceptual beauty in Turing's arguments, and I want to bring that out in the following discussion. I would break it down into three big ideas in Turing's argument about why the halting problem is unsolvable. The first step concerns the concepts of universality and simulation.
One of the first observations Turing makes in his paper is that there is, in effect, one Turing machine to rule them all. Thus far, we have been thinking about Turing machines tasked with carrying out specific tasks: adding two numbers, multiplying two numbers. But the key observation is that Turing machines are powerful enough to simulate other Turing machines.
To make this concrete, imagine that in addition to, say, two numbers written on the tape, you are also given a description of some other Turing machine, call it M. The machine receiving this input is called the universal Turing machine, MU. The universal Turing machine expects to be given a description, a set of rules, of some other Turing machine M, and it then simulates M on whatever the remaining input is.
For example, suppose the universal Turing machine is running and needs to decide what to do with a symbol on the tape. Rather than consulting its own fixed rules, it looks up the rules of M that were provided as part of the input and acts accordingly. That is what it means for one Turing machine to simulate another: given a description of M, the universal Turing machine can faithfully carry out M's computation.
This idea is actually deeply familiar from everyday computing. The universal Turing machine is essentially the operating system of your computer, whether macOS, Windows, or otherwise. The operating system is the master program that manages and executes all other programs, whether a spreadsheet application or a PDF reader. Just as your operating system can run any program, the universal Turing machine can simulate any Turing machine. That is what it means for modern computers to be general purpose.
There is one more profound idea embedded here, and it is already present in Turing's 1936 paper, a full decade before physical computers existed. That idea is programs as data. The contents of a computer's memory might represent something like a bank balance, or they might represent instructions, code to be executed. Modern computers treat these identically, and that concept is already implicit in the universal Turing machine: what is written on the tape might be ordinary data, or it might be code to be run. Code as data, already there in 1936.
There is something genuinely special about computer science. Forgive the bias. I have devoted my life to this discipline, but allow me to cheerlead for a moment. We have had computers our whole lives, so we take their general-purpose nature for granted, yet it is really quite remarkable. You do not buy one computer to browse the web, a separate computer to read PDF files, and another to do spreadsheet work. You have one machine, and it does all of those things.
You are probably thinking that this is simply obvious, that of course it works that way. But consider kitchen appliances. Even in a small kitchen with very limited counter space, we somehow find room for both an oven and a toaster oven, two devices that do essentially the same thing, warm up food, differing only in that one is better for bagels and one is better for steaks. We dedicate two separate areas of our kitchen to nearly identical functionality. Yet no one ever buys two different computers for two different computing tasks. One computer does it all.
This is not unrelated to why computer science is a genuine academic discipline while toaster science is not. Toasters represent the narrow application of general-purpose ideas from physics and engineering. Computer science is about computation itself, something that literally transcends any particular technology and touches on fundamental mysteries of the universe.
It took a while for this view to become mainstream. People were already building computers in the 1940s to carry out various tasks, and the first academic departments of computer science appeared in the mid-1960s. Yet even in the 1970s, the field's legitimacy was contested. Harry Lewis, a professor at Harvard who later taught Bill Gates, Mark Zuckerberg, and others, had a difficult time convincing his colleagues that computer science made sense as a discipline. The objection he heard repeatedly was: "We don't have a department of microscope science for biologists, and we don't have a department of telescope science for astronomers, so why should we have a department of computer science?"
As late as the 1970s, computer science was not widely recognized as a scientific discipline in its own right. In the 2020s, it unquestionably is. That completes the first part of Turing's argument about the undecidability of the halting problem.
The second part of the argument is the deft application of a proof technique known as diagonalization. This technique was either invented or discovered, depending on your philosophical inclinations, by Georg Cantor in 1891. Cantor was interested in proving that there are more real numbers than integers. If you have never encountered this idea before, you might wonder what that even means: there are infinitely many integers, and there are infinitely many real numbers, so in what sense can one infinity be larger than another?
There are, in fact, different levels of infinity, and the set of real numbers has a strictly higher infinite cardinality than the set of integers. One intuitive way to see this is to recall that real numbers have infinite decimal expansions. Pi, for instance, is 3.14159265358979… going on forever, whereas every integer has only finitely many digits. By virtue of possessing infinitely many digits, real numbers are, in a meaningful sense, fundamentally more numerous than integers. One of Cantor's proofs of this fact is the technique now known as diagonalization.
Mathematics is not usually thought of as a field prone to controversy, but Cantor's diagonalization proof was flatly rejected by many mathematicians of his time. It combined proof by contradiction with reasoning about infinite objects, which struck a number of mathematicians as quite dubious. David Hilbert, whom we encountered earlier, was, however, a genuine admirer of Cantor's argument. Hilbert famously declared in 1926, "No one shall expel us from the paradise that Cantor has created." Indeed, one of the goals of Hilbert's program for formalizing mathematics was to produce a rigorous justification of the legitimacy of Cantor's diagonalization argument.
This makes it particularly ironic that diagonalization turned out to be the central proof technique used to dismantle Hilbert's program, as practiced by both Gödel and Turing. Gödel, as discussed earlier, proved the incompleteness theorem: that there exist true mathematical statements which are not provable. He established this using diagonalization. The very technique Hilbert had hoped to vindicate was the one that revealed the incompleteness of the formal system he had championed.
The key to Gödel's argument was a form of self-referentiality: he showed that statements about integers in arithmetic could themselves be encoded as integers, so that a number could serve simultaneously as an ordinary number and as an encoding of an assertion about numbers. Turing recognized the same pattern in his own work. The universal Turing machine, a Turing machine capable of simulating any other Turing machine, provided Turing with an analogous form of self-referentiality, just as Gödel had integers that encode statements about integers.
Turing saw that diagonalization, having served Gödel in taking down the completeness conjecture, could equally serve him in taking down the Entscheidungsproblem. Through diagonalization, Turing demonstrated the existence of an explicit computational problem that is provably undecidable, one for which no mechanical procedure can ever determine the answer. That brings us to the third and final major idea in this argument.
The conceptual idea in Turing's argument is to show that not only the one explicit, peculiar problem identified through diagonalization is undecidable; so too are natural problems that we would genuinely want to solve. In particular, the halting problem is undecidable. The third step of the argument is to transfer the undecidability already established in the second step to the target problem, the halting problem. This transfer is an idea known as a reduction, and reductions are one of the most central concepts in the foundations of computer science. We will encounter them again when we discuss NP-completeness, but here their role is to transfer undecidability from one problem to another.
We are all deeply familiar with reductions from everyday life, and what the term means in the context of computation is essentially the same. Suppose it is the 1980s and you have gone from work to happy hour at a bar half a mile away. When happy hour wraps up, you need to get home, but you have no automated way of generating directions. You do, however, know how to get home from work. You do it every day. So you reduce the task of getting home from happy hour to the task of getting home from work: you simply retrace your steps back to the office and then follow your usual routine. The reduction is just the walk from the bar back to work, and it provides the bridge between the problem you need to solve and the problem you already know how to solve.
For another example, suppose you are a Microsoft Excel wizard but someone hands you data in Google Sheets. There is a straightforward reduction: export the Google Sheets data into Excel and then apply everything you already know. The problem you need to solve is performing sophisticated analysis in Google Sheets; the problem you already know how to solve is performing that same analysis in Excel; and the reduction is simply the act of exporting. In general, a reduction is a way of solving one problem by doing a small amount of additional work to convert it into a problem you already know how to solve.
Visually, think of two problems, A and B. A reduction from A to B means that if you know how to solve B, then, by virtue of the reduction, you also know how to solve A. In the spreadsheet example, B is performing magic in Excel, the reduction is exporting from Sheets to Excel, and the result is that you can now perform that same magic in Google Sheets. In the happy-hour example, B is getting home from work, the reduction is retracing your steps, and the result is that you can get home from the bar.
The way reductions are used here, however, is logically equivalent but runs in the opposite direction, the contrapositive, and most people find it considerably less intuitive. Suppose problem A cannot be solved. If a reduction from A to B exists, then problem B cannot be solved either. The reasoning is simple: if you could solve B, then using the reduction you could solve A as well, but A is unsolvable, so that is a contradiction. Reductions therefore have the effect of spreading undecidability from one problem to another, in exactly the same direction as the reduction itself.
Let me state the argument once more, because it typically takes a few repetitions to fully internalize. If problem A is unsolvable and there exists a reduction from A to problem B, then B must be unsolvable as well. If you could solve B, the reduction would give you a procedure for solving A; since A cannot be solved, neither can B. This is precisely the structure of Turing's third step.
In Turing's argument, problem A is the peculiar undecidable problem produced by diagonalization in the second step, and problem B is the halting problem. As long as one can exhibit a reduction from the peculiar problem to the halting problem, the argument is complete: undecidability has already been established for A, and the reduction spreads it to B. There is indeed such a reduction, reasonably straightforward, though the details will not be covered here, and it is this reduction that constitutes the third and final step of Turing's proof that the halting problem is undecidable.
Now that we've covered that, I want to move on to how we should interpret Turing's result: the undecidability of the halting problem. I've been discussing the result with a particular interpretation in mind: that by virtue of being unsolvable by Turing machines, which is the mathematical statement Turing proved, I'm interpreting it as being unsolvable by computers. You might feel there's a gap there. The worry is whether we can be so sure that the Turing machine model, this picture of a human with a long roll of paper and a pen, truly captures everything that computation, in its full glory, might be able to do. This really comes down to how we feel about Turing's definition of a Turing machine, and whether we share his belief that Turing machines capture everything that is possible through computation in any form.
Definitions like Turing's play an incredibly important role in mathematics. The spotlight usually goes to the big theorems, Fermat's Last Theorem, that kind of thing, while definitions are often below the fold. But they are absolutely crucial to everything that happens in mathematics. As such, when you encounter a mathematical definition, you should poke it, prod it, criticize it, and question it. You can ask whether it is too strong, whether it includes too many things or too few, and whether it genuinely captures the real-life concept it attempts to formalize.
Before we do that with Turing's definition, I want to pause and note that it takes real courage to write down a mathematical definition like this, to take a seemingly messy real-world concept like "automatable," or "solvable by a mechanical process," and translate it into cold, rigid mathematics. That is genuinely difficult. Whenever someone makes such an attempt, we should applaud it, and then immediately proceed to interrogating the definition. This will be even more obvious when we discuss P and NP-completeness in a couple of episodes. Those are similarly courageous attempts to take messy real-world concepts and turn them into mathematics around which we can build theories.
In general, one thing you worry about with a definition is that it is too broad, that things are covered under it which you think should be excluded. We will worry about that later when we discuss Turing machines that can solve problems efficiently, not just in principle. At the moment, however, we are more concerned about Turing's definition being overly narrow. The worry is this: the mathematics tells us that Turing machines cannot solve the halting problem, but can we really leap to the conclusion that a modern laptop also cannot? Perhaps there are more powerful forms of computation not captured by Turing's model.
The widespread belief among computer scientists is that Turing was right, that Turing machines genuinely capture any reasonable model of computation. If Turing machines cannot solve some problem, neither can any other technology that will ever be invented. The way you build mathematical evidence for that claim is, again, through simulation. We discussed simulation earlier in the context of the universal Turing machine simulating other Turing machines. A good way to argue that Turing machines are as powerful as anything else is to enumerate every other notion of computation you can think of, and then show, one by one, that whatever any competing model can do, a Turing machine can do as well, by constructing a Turing machine that simulates it exactly.
If you carry out that simulation for model after model that anyone can dream up, and it works every time, you start to wonder whether there really is anything beyond Turing machines. That is precisely the state of the art. Every other reasonable model of computation that people have proposed, including modern computers with their RAM-based architecture, has turned out to be simulable by a Turing machine. Any computation those models can perform, Turing machines can perform as well. At this point, you might be wondering what some of these other models of computation look like, and, for that matter, who Church was.
Why is it called the Church-Turing thesis and not just Turing's thesis? It turns out there was a logician, Alonzo Church, then at Princeton, who was motivated by the exact same reasons: Hilbert's 1928 book and its open problems. He also set out to disprove the decision problem. In fact, Church beat Turing to the punch by a few months. The two worked nearly independently, but Church's result came first.
Turing only learned of Church's work after completing his own, but was encouraged to publish his paper regardless, fortunately, as it turned out. Turing's methodology was very different from Church's, and in many ways more direct. Even at the time, it seemed clear that the formalism Turing had developed might have many other applications, and of course we now know for a fact that it does.
Church did not invent Turing machines; instead, he developed his own model of computation, which he called the lambda calculus, and which itself has many applications. It corresponds less obviously to the mechanistic processes of computers as we know them, but in the appendix of Turing's 1936 paper, he includes a proof of simulation. The lambda calculus is another model for expressing computations, and it turns out that Turing machines can simulate any computation expressible in the lambda calculus, and vice versa.
We now know that this equivalence holds for many different ways of expressing computation. There is even a phrase for it: Turing-complete, which describes any method of expressing computations that is as general as Turing machines, and therefore as general as everything else we know about.
Let me leave you with one final story about Church. This is admittedly lazy storytelling, telling stories about bizarre things that mathematicians have done is like shooting fish in a barrel. But there is one about Church that I first read as a graduate student, over 25 years ago, and for whatever reason it has always stuck with me. I learned it from the recounting of the famous mathematician Gian-Carlo Rota, who did important work in combinatorics, among other areas, and was himself a PhD student at Princeton at the time.
Rota observes: "It cannot be a complete coincidence that several outstanding logicians of the 20th century found shelter in asylums at some time in their lives. Cantor, Zermelo, Gödel, Peano, and Post are some." Indeed, one could devote an entire episode to the different ways that different logicians lost their minds. It is a striking recurrence in that corner of mathematics.
Rota goes on to say that Alonzo Church was among the saner of them, though in some ways his behavior must be classified as strange even by mathematicians' standards. He describes taking the graduate logic course from Church at Princeton, and this is the passage I never forgot: "Every lecture began with a 10-minute ceremony of erasing the blackboard until it was completely spotless. This ritual could not be disposed of. Often it required water, soap, and a brush, and was followed by another 10 minutes of total silence while the blackboard was drying."
The students, out of exasperation, eventually began arriving 15 minutes before Church later in the semester, determined to do all the preparatory work themselves, to ensure the board was spotless before he arrived. It made no difference whatsoever. Church would still take his full 10 minutes and erase the entire blackboard with soap and water every single time.
I don't have time to recount the whole Rota article, but it is worth noting that Rota writes all of this with genuine fondness for Church, and with deep appreciation for the imprint Church left on his thinking in that course. Strange, yes, but all part of the mathematical experience. I'll leave you with that for today.