If it can be done, it can be done by a computer.
The Church-Turing thesis is not the usual place to start an introduction to computational theory, but it is a useful place because it gives a feel for the way that CS theory approaches questions.
Let us consider the matter of computation, which is the ability to transform some input information into some output information. We’ll leave it as vague as that for now, where information might be anything from a statement of the average body-mass index of a yearling holmesina to the exact nerve signals needed to cause a healthy glyptodon to breathe. An example computation might be estimating the life expectancy of a minmi given a variety of fossil evidences.
For now we’re not going to worry about any particular computation. Instead we’ll ask, what tools do we need to perform the computation? Is there a language in which we can describe every task that can be performed? Is there a set of techniques we can combine to do absolutely everything?
The Church-Turing thesisNamed after Alan Turing and Alonzo Church in the 1930s states that yes, there is such a language, a set of techniques that can describe every computation. Turing posed the Turing Machine, Church had (several versions of) the λ-calculus; since then we’ve shown untold hundreds of other such basis sets, some of them quite silly (such as the computer game minesweeper). Such universal bases are commonly called Turing-complete. Demonstrating that any particular set of operations is Turing-complete is often a lengthy process, but is generally not overly difficult to follow with sufficient patience.
The Church-Turing thesis has not and can not be proven. The only way to know that every computation can be expressed in some language is to know what every computation is. But it is almost universally believed. We’ve found myriad ways of describing computations and all of them have been reducible to Turing machines. We have no evidence that any more powerful means of describing processes exists.
The task of describing a particular process in terms of some small Turing-complete language is usually rather painful. Almost universally, you work up in stages. First you show that minesweeper grids can be used to represent the notion of “and” and “not”. Then you show that “and” and “not” can be used to represent integers and addition and repetition. From there you build up the rest of arithmetic, and so on up the line until you get to whatever process you wanted to describe.
The fact that there is a Church-Turing thesis is the reason computing exists. If we were always finding new, more powerful process descriptions that could not be expressed in terms of simpler parts then we’d always be having to design new machines from scratch instead of refining the same simple designs for decades. From an engineer’s perspective, “it all boils down to transistors” is a beautiful guarantee.
The fact there is a Church-Turing thesis is also the reason that mathematics and theory in general exists. While mathematicians love to introduce new symbols as they go, they can do so because they’re all defined in terms of other simpler symbols down to a very small Turing-complete set. And those core ideas, in use since Euclid if not before, are sufficient to describe every process we can describe, thanks to the Church-Turing thesis.
I’ve often pondered on what the world would be like without the Church-Turing thesis. What if someone came along and said,
“I just figured out how to sckahrm! It allows me to do marvelous new things!”
We reply “Really? How do you sckahrm?”
And the answer is “It is literally impossible to describe! There is no conceivable way to reduce it to anything you know at all.”
Exciting as such a world might be, I’m relatively glad we do not But what if we do live in such a world? Would we scoff at any sckahrmer as a delusional crank? appear to live in such a world. It’s nice to have a sensible world that can be decomposed into nice little well-behaved chunks.
Looking for comments…