Church-Turing: the “Fundamental Thesis of Computer Science”
An abstracted way to think about computer science – and of machines and engineering in general – is as a theory of automation. The mathematical abstraction of the machine is the algorithm, which is intuitively thought of as a set of instructions or computational paradigm. Pondering some examples of real-world machines help us pin down another characteristic of importance to an algorithm: the machines are often not completely autonomous, they need to take inputs, so algorithms can be considered procedures to execute functions.
Historically, the theory of machines was often formulated in terms of simple machines. The Ancient Greeks formulated the theory in terms of the “six simple machines” (the inclined plane, lever, wedge, wheel and axle, pulley, and screw); the Ancient Indians formulated the theory in terms of mechanisms that operate on “pressure, weight and rotation”. Note that these were mechanistic descriptions (and not very fundamental ones, due to the lack of a serious theory of mechanics).
In general, these areas of machine theory fall into the general subject of control theory.
If I had to distinguish computer science from engineering/machine theory – I would say that computer science is interested in the generality of machines. Computers are different from jackhammers, because the architecture of a computer allows the simulation of “any possible algorithm” that the jackhammer – or any other machine – could follow.
The computer is therefore fundamentally about control – any kind of actions you may want to encode in a machine, a computer is literally the best thing you can ask for to do so, because it is the device that can produce any physically-possible-to-encode sequence of actions in the machine.
The Church-Turing thesis should therefore be seen as the fundamental thesis of computer science – the precise specification of what machines/algorithms can do. It leads to the notion of Turing completeness, i.e. a particular machine actually acting as a universal computer (and a particular such instance is the universal Turing machine).
The Church-Turing thesis is the statement that the Turing machine – or equivalently, mu-recursion, or lambda calculus – can compute anything that can be computed at all. That it’s the “best we can do”, the ultimate limit (for which reason the thesis is sometimes known as the maximality thesis).
(Take a moment to appreciate how this means we’ve actually achieved optimization here. The computers we use are literally universal – given enough memory and time. They are truly the pinnacle of human invention, to date.)
Note that this is a physical limitation, one that depends very specifically on the universe we live in. For example, a universe with time travel (the ability to send signals back in time) will be able to trivially solve the halting problem. The Church-Turing thesis is not a mathematical fact; it is a physical one. It can be considered an axiom of computer science, and if one day we do find a system that computes a larger set of computation – called a hypercomputer – then we’d find that some significant portion of computer science, such as the very notion of a Turing machine, is not relevant to our universe.
A particular result that will be helpful in convincing us of the thesis is that the mu, lambda and Turing notions of computability are indeed equivalent. This is important, because at least to me, lambda calculus and mu recursion are far more intuitive than the Turing machine; I can really see that mu recursion is what I’m doing when I’m executing an algorithm, and I can really see that lambda calculus is the “natural” sense in which one would try to describe functions if they can be described at all.
We will see this result in the next article.