In this post I’m going to explore some of the philosophical ramifications of the Church-Turing Thesis, if it were to actually hold true. And at least so far (with one interesting exception) it has held true. Though in the end, I suspect many readers will feel they need to ultimately reject the Turing Thesis. But even if it does ultimately prove false, the very fact that it holds true in every case we know how to currently devise still makes it an useful scientific principle, for now.
Is the Church-Turing Thesis True?
If you are ever the sceptic – and I certainly am – you probably want to know why we should even assume that the Church-Turing Thesis is true. It has, after all, never been proven true. So why should we simply assume it’s true — as Computational Theorists do?
To answer this question, I must refer you to my epistemology posts. This summary in particular will be helpful. Here we have our first interaction of epistemology and computational theory.
The basic principle is very simple. We do not need to prove the Church-Turing Thesis to be true because we can simply treat it like any other scientific theory or explanation. We can conjecture it is true and we can test it through experiment. We have done this (as described in this post) and it was not refuted. So we can now tentatively accept it as true and therefore embrace it as if it’s true until a better scientific theory comes along.
The idea that Computational Theory is really an empirical science will probably make you a bit dizzy for a while. That’s okay. This tends to happen when bad thinking habits fall away.
The Church Principle vs. The Turing Principle
Now that we are tentatively accepting the Church-Turing Thesis as wholly true (I know that sounds paradoxical, but as summarized in this post, it makes perfect sense) we can further discuss an important difference between how Church saw the Thesis vs. how Turing saw it.
Roger Penrose, in his book The Emperor’s New Mind, points out that Church and Turing did not agree upon how far-reaching the Church-Turing Thesis is. Church was more circumspect with it. He simply claimed that any sort of program (we call them ‘algorithms’) that can possibly exist can be run on a Turing Machine (or on the equivalent Church notation.) He simply states that there are no algorithms in existence that are not Turing compatible. This is what Penrose calls “The Church Principle.” We might summarize it like this:
There is no such thing as a computation or mathematical algorithm that can’t be run on a Turing Machine.
Alan Turing, however, noticed something that Church apparently did not or was unwilling to add to his conjectured explanation. Turing noticed that just as we can assume the Church-Turing Thesis to be true based on observation and a failure to refute it, so can we go one step further and conjecture that absolutely everything ever discovered by the physical sciences can be broken down into computations that are Turing compatible!
The Computational Nature of Reality
In other words, Turing used the Church-Turing Thesis to assert the Computational Nature of Reality. This is a principle so assumed by us modernly (our ancient counterparts assume otherwise) that we don’t even think about it anymore. We just assume that if we have a scientific theory (particularly a basic physical one) that it will be described mathematically (i.e. computationally.)
No one ever expects for scientists to one day announce “we’ve found this strange phenomenon that apparently can’t be described mathematically!” If that ever did happen it would blow our minds out the back of our heads. We just take for granted that reality can be described using math (i.e. computation) and that science describes all its most basic theories using math. And even most of its non-basic theories too we assume will be largely translated into math – including biology and even now psychology. In fact we often view the maturity of a scientific explanation as directly related to how much we’ve been able to describe it via mathematical laws.
Think of the example of Darwin’s theory of natural selection. In The Origin of the Species Darwin didn’t use any math at all. So people consider natural selection to be a non-mathematical theory. But that isn’t entirely correct. First of all, Darwin was very specific about how he felt natural selection worked. Precise and specific enough that had computers existed at the time, it would have been possible to create a program out of the steps he described. Secondly, when DNA was discovered it taught us that natural selection was essentially – well, exactly like the tape on a Turing machine! Our DNA is literally a chemical Turing machine that can be literally copied and simulated by modern computers. So biological natural selection is in fact wholly Turing compatible.
What if We Did Find a Natural Process that Exceeded Turing Machines?
Now let’s explore this idea further via a thought experiment. What if some scientist did one day announce that she has discovered a natural process that can outperform a Turing Machine as per our previous discussion about the limits of Turing Machines?
In fact, this has already happened once in a very limited form. Quantum Mechanics does in fact perform computations at speeds a Turing machine never can and can even perform some very limited esoteric functions that a Turing machine can’t. But when such a case arises, this doesn’t somehow invalidate the Church-Turing Thesis per say, but rather it just expands it.
Specifically the Church-Turing Thesis, once quantum mechanics is taken into consideration, became the Church-Turing-Deutsch Thesis. The reason it never truly invalidates the thesis is because for every new physical phenomenon you find that can outperform a Turing machine, you can then build a new type of computer using that physical phenomenon and that new type of computer becomes the new highest sort of computational machine. In the case of quantum mechanics, they simply invented the concept of the quantum computer.
The fact that invalidating a computational thesis really just expands it is precisely like any other scientific theory; you only invalidate the theory by replacing it with a new one.
This also places hard limits on what we can expect in nature. For example, one commenter suggested that a biological body can perform functions that an electronic computer can’t. As of yet, we have no evidence that is the case. So far biological functions really are just Turing compatible. But if we do find biological functions that can do something an electronic computer can’t, we’ll just invent a new type of biological computer and utilize the same chemical process biology does. The end result will just be a new Turing-like Thesis to replace the old one.
Non-Computational Phenomenon?
One possible escape from the above dilemma is to propose the idea that perhaps nature (let’s say biology) actually has some sort of non-computational phenomenon in it. In this case, when we discovered the non-computational phenomenon, perhaps we can’t then take it and create a new type of computer out of it.
Now it’s difficult for me conceive this as a possibility for the simple reason that I’m not clear how this fictional scientist could possibly even know that she had discovered a non-computational process for certain. And being a scientist, wouldn’t there be expectation that she’d write up a paper describing the laws on which this new non-computational process works? But to write such a paper describing the laws this process follows would take use of math to describe the laws precisely — and you see where I’m going with this — all math can be run on a Turing machine.
But for the sake of this hypothetical argument let’s pretend like this scientist somehow discovered a non-computational phenomenon. The simple truth is that we are now not talking so much about a non-computational phenomenon as we are talking about a non-lawful one. So let’s make up a rule to suggest this connection:
Science studies repeatable laws, which by definition can be described mathematically and therefore are computational by definition.
Given this rule, there is simply no way to describe the laws that this non-computational physical phenomenon follow because the way we describe such laws scientifically is mathematically. So if we find such a non-computational phenomenon, we have in fact found something inscrutable to science all together!
Now maybe many people would find this exciting. But I’d hope you’d also see why this would be a rather scary discovery. If there is one mathematically / scientifically inscrutable aspect of reality, then this implies that science only works by chance. The universe is not lawful and in so far as we’ve happened to discover lawfulness so far, this is only because we happened to explore a part of reality that happened to appear lawful. But this lawful part of reality must, of course, exist as part of an overall non-lawful reality. This may excite you personally, but it also means that reality is scarily incomprehensible to us.
In short, so long as any new scientifically discovered process is in fact logically and lawfully describable and therefore comprehensible, we are absolutely guaranteed that nothing in physical reality will never be non-computational!
The Turing Principle Defined At Last
Now if you’ve followed my line of logic and the thought experiments, you probably have already for yourselves derived what the Turing principle is. We might write it something like this:
All math we currently know plus all we will ever know can be programmed on a physical computer of some sort. Since all of nature can be described via math, that means we will never come across natural phenomenon that can’t be simulated on a computer.
However you might feel about the above Turing principle, there are some very cool ramifications that follow logical from it. Here are a few:
- All of physical reality can be described via computation and we understand all possible computations.
- Therefore we know we can comprehend all of reality. If it exists, we can understand it and comprehend it.
- There are no limits placed on human knowledge.
Though it’s beyond the scope of this post (I’ll do a follow-up post later on) there are also many obvious religious ramifications of the Turing Principle. Even ramifications about God Himself and our relationship to Him.
Now many will immediately see some possible negative ramifications for religion. Does this mean God’s knowledge is limited by the laws of computation? Does this mean there is no free will because the mind is purely computational?
But bear in mind that questions like this are only scary if we both assume the Turing Principle to be true and assume there were never be discovered a computational machine that is above a Turing machine. Since we’ve already discovered one (very limited) exception, I’d caution people against jumping for their knives right off the bat in what may or may not ultimately prove an impossible fight for religion comparable to evolution. (To be honest, it is not comparable to evolution. The Turing principle is on much stronger ground scientificaly than evolution since all science that succeeds, including evolution itself, are also confirmations of the Turing Principle.)
Further, not all the ramifications of the Turing principle are negative for religion, particularly for Mormonism. For example, the Turing principle must assert that there is no unbridgeable divide between God and Humankind. And it direclty backs up Joseph Smith’s claim that there is no such thing as immaterial matter. In fact, given Joseph Smith’s doctrine on that point, the Turing Principle is presumably compatible with all of Mormonism with the possible exception of the doctrine of Intelligences, as explained in D&C 93:29-31. But even here I’d suggest caution for two reasons. First, because it is not yet clear if any of our speculations about Intelligences are correct. Second, because even if Intelligences do end up being some non-computational thing, so long as they are physical — and Joseph Smith insists they are — they could also be incorporated into some future Super-Turing machine.
So I ask readers who want to fight against the Turing principle on religious grounds to instead accept it as a current best scientific assumption -but with the jury still out on whether or not it will ultimately prove correct once we factor God into the equation. (Pun intended.)
What If I Don’t Accept the Turing Principle?
Okay, what if you don’t like some of the ramifications of the Turing principle? Some people (including Roger Penrose) can’t accept it as true in its current Turing machine form. However, we need to keep epistemology in mind. While you are personally under no obligation to accept the Turing Principle, remember that the reason why Alan Turing conjectured it as an explanation about reality in the first place was precisely because it explained why…
a) All full-featured computational machines are equivalent
b) All of reality (so far) can be described via computation
And remember that those two points are really just two ways of looking at a single point. The explanation for why all of reality that we have ever discovered can be described via computations (i.e. math) is because all full-featured computational machines are equivalent – including any sort of computation nature does.
So you are indeed free to reject the Turing Principle if you wish for the very same reason you are free to reject any scientific theory if you wish. But keep in mind that this is our current best explanation. When you reject the Turing Principle you are not rejecting it by refuting it with a better explanation, you are merely being a Rejectionist and refusing to accept the best explanation but offering no alternative.
Perhaps there is nothing wrong with you doing this. Truth be told, if there was not at least some scientist out there rejecting the prevailing theories we’d never generate the conjectures necessary to make progress. But keep in mind the difference between a rejection of a theory due to the existence of an offered alternative and merely rejecting it without such an alternative.
Conclusion: What Would a Non-Computational World Look Like?
In conclusion I want to briefly consider what a non-computational reality would be like. Because we are modern people and because we take the existence of scientific explanations for granted now, it’s probably a bit hard for us to imagine what a non-computational reality would be like.
But for our ancestors, they lived in such a world. To the ancient pagans, the weather was not a computational process that can be fully explained; it was a matter of agency of capricious gods. What if our ancestors had turned out to be right? That is what a non-computational reality would have looked like.
Imagine such a world for a moment. All things that move or happen do so due to capricious choices of gods rather than due to comprehensible laws. It’s impossible to ever really know why the gods do what they do. Reality is simply incomprehensible. You can make a sacrifice to the gods, perhaps, but there is no guarantee it will make any sort of difference. The gods will do what the gods decide to do. It’s an unlawful reality where nothing really makes sense and there is no reason to believe that it should make sense.
To some people — I think maybe myself included — this does not sound like a very appealing world to live in. I think it is understandable that many would out of hand, and perhaps even with religious fervor, reject a non-scientific world view precisely because such a view comes across to them like the above world.