Could the Church-Turing thesis be proven?

Logic & Philosophy of Mathematics
1

The Church-Turing thesis states that states that any mathematical function or problem that can be solved by an intuitive, step-by-step algorithm is computable by a Turing machine. Yet notice that this is a thesis, because even if a Turing Machine has a rigid mathematical definition, the intuitive, step-by-step algorithm, something that is “effectively calculable”, isn’t one. To prove the thesis, to basically start to talk about a Church-Turing theorem, both would have to be formal mathematical objects with rigid definitions.

Hence we can make the argument that potentially there might be something that isn’t limited to what Turing Machine can compute, hence we can assume hypercomputing or an Oracle Machine to exist. Still everything that we have now, including Quantum Computing, is in the bounds of what a Turing Machine can do. But we can make still assumptions, simply making a model with a “black box” where the hypercomputing happens and whopee! Hilbert’s Entscheidungsproblem, the Decisin problem, and Hilbert’s 10th problem could be solved. (Something that actually Matiyasevich proved in 1970: that Hilbert’s 10th problem is mathematically equivalent to the Halting Problem.)

So to put the above in other words, if you can prove the Church-Turing thesis, you also show that hypercomputing is either impossible would have to be something totally, totally different from computation of today.

If the Church-Turing thesis is proven to be a theorem, what would be the consequences?

The result would be that we have a new axiom of just what “effectively calculable” means and computable and calculable would be synonyms also in mathematics, not just in our ordinary language. Computation would be strictly defined and confined to what basically a Turing Machine in Turing’s paper from 1936 theoretically can do. That sounds at first very crushing to mathematics, until we ask us one important question: is all mathematics, all true mathematical statements calculable? We know it isn’t so, hence this might not be at all a setback. Calculation, arithmetic, was the natural way that mathematics develop, yet the logical field of mathematics cannot be limited to addition and substraction etc. Infinity and the infinitesimally small are an integral part of mathematics, yet they don’t fit into the system based on the natural numbers. Hence there’s a lot more to mathematics than just what is computable or recursive.

How might the proof go?

Here’s the point that shows just how awesome in my view the Church-Turing thesis is.

The thesis talks about what is computable, and we should prove it. Even if proving something mathematically and computing something mathematically are two different things, the two are quite interconnected to each other. Calculating something, y=f(x) or 1+5=6 is our standard way of giving mini-proofs in real life. You start with definitions and axioms of arithmetic and apply those fixed rules, you prove that 1+5=6. The principle here at hand is called the Curry–Howard correspondence, which tells us that writing a valid mathematical proof is structurally identical to writing a working computer program, and simplifying that proof is the exact same process as running a calculation. How close does that come to Turing Machines computing and the thesis itself?

But before continuing, I’d like to hear comments on the above, especially if I’ve understood something wrong or there’s a mistake. What do you think about the thesis, could be proven (or disproven)?

2 Likes
2

As I grok the thesis, it is very much an informal thesis. It cannot be proven.

It says : “Our intuitive fuzzy informal notion is captured by the Turing formalization.”

So this thesis can never be a theorem. Indeed, it’s even a “metaphysical” or “ontological” claim.

How does one come to endorse this thesis ? Well a careful study of the details of what Turing machines can do suggests that they can do anything that is “intuitively” rule-based. This same study shows the equivalence of the approaches of Church, Kleene, Markov, Post, etc…

In computability textbooks, we see formal proofs of the equivalence of these different formalizations. I can translate a Turing program into a Markov string algorithm, etc.

We also see “weaker” notions of computation such as the DFAs that are associated with regular languages.

You say “we know it isn’t so.” In my view, we have differing philosophies of mathematics. As far as I know, just about every mathematician accepts a criterion that is at least ideally computer checkable. So formal axioms of set theory lead to formal theorems that are interpreted —by some — as profound ontological claims. The more cautious reading is that a formalism “outputs” a string of symbols as a “theorem.” The rest is philosophy and — more importantly ? — application.

3

The thesis is defined for the Turing machine. Suppose George does things by going for long walks in the park. Then the thesis asks, can something that can be done by taking long walks in the park be done by George?

Yes, of course, no?

4

Thank you for the comments!

This was what I tried to describe in the first paragraph. It is (partly) informal. And thus what it would need to become a theorem would be basically a new axiom.

There are true but unprovable mathematical statements and objects. The undecidability results of Gödel, Turing or Tarksi aren’t just upheld by some mathematical schools of thought and not others.

When you say “about every mathematician accepts a criterion that is at ideally computer checkable”, what do you mean here?

Actually the thesis attempts to bridge our pre-existing intuitive idea we have about a step-by-step calculation, using an algorithm, to a strict mathematical model. So in your example the issue would be defining long walks in the park and hence what isn’t a long walk in the park, I guess.

Computers before were people that used algorithms and made calculations to fulfill some task. Now it’s done by machines that run software, that basically are algorithms (algorithm is an abstract definition here). Hence when you write a short program for your electronic computer to do something, it really performs that like a Turing Machine.

And even now if you have what is called machine learning, it doesn’t change this: the software just includes learning algorithms that allow computers to analyze massive amounts of data and build their own decision-making rules. But there’s the catch, the computers have to have those instruction algorithms to make their own decision-making rules.

A computer cannot guess, or improvise on its own. It requires strict, step-by-step instructions to turn raw data into useful actions. You cannot give a computer the an order like “Do something else” without defining exactly what to do when issued this order. “Do something else” simply isn’t an algorithm. An algorithm requires exact, mechanical instructions that leave zero room for guesswork or personal judgment.

Hence if someone asks you “Do something else that you never have done before”, you first think of everything you done and then can decide to do something else. Here you aren’t following an algorithm. You are basically using negative self-reference (which lies in the heart of Turing’s and Gödel’s results). A computer cannot do that.

1 Like
5

I guess it’s not clear what that axiom would contain. If we want to reason “exactly” about computation, we need an exact definition. The thesis is just an expression of the belief that our exact formal specification of algorithm “captures” our pre-formal intuitive concept.

We have “already” injected the intuitive fuzzy concept into “exact reasoning” via Turing machines, etc. And — as you know — this allowed for a strong case to be made for the limitations of algorithmic decision making.

What does “true” mean here ? Has a “mathematical true reality” been revealed ? The phrase “true but unprovable statement” is one way to interpret the proof. Reasonable, sure, but still a metaphysical addition.

In practice, informal proofs suffice. But in theory an informal proof can be formalized. Each tiny step can be specified. This is what makes mathematics so “objective.”

6

To disprove the thesis you should find a way to compute a function that a Turing machine cannot compute, and then convince the mathematical community that your way can be considered a “computation” (at least, I believe, it should give always the same result for the same input and should not require any kind of “guessing”).

To prove the thesis you should prove that there is no way to compute a function that a Turing machine cannot compute, such that the new way of computation can be considered to be really a “computation” by the mathematical community.

The principle here at hand is called the Curry–Howard correspondence, which tells us that writing a valid mathematical proof is structurally identical to writing a working computer program, and simplifying that proof is the exact same process as running a calculation. How close does that come to Turing Machines computing and the thesis itself?

The the Curry–Howard correspondence refers to the dependent type theory as the model for computation, that is strictly less powerful then Church’s pure lambda calculus. And the lambda calculus is equivalent (as computing power) to a Turing machine. So, everything that can be computed by a function expressed in dependent type theory can be computer even by a Turing machine

2 Likes
7

I agree. The difficult task of getting mathematicians to agree on what is a “computation” or simply what an algorithm is, is the problem.

The problem with algorithm starts from it being this fundamentally intuitive, real-world concept rather than a pure mathematical object. It’s too vague. But my question here is: does that actually matter?

I would argue that simply using any kind of algorithm, is what here defines “computation”. It is quite irrelevant from what a human or an electronic computer network can do or follow, the effectively calculable. The only important definition here has to be that the commands in the algorithm are exact, mechanical instructions that leave zero room for guesswork or personal judgment. The algorithm’s commands cannot be vague or leave something open for interpretation. Above all, they cannot be something like “do something else” and then not have instructions on how to “do something else”.

You don’t need anything else, just to use the definition of algorithm being “a finite set of commands that followed through will perform the task at hand”, and you already have undecidability, the Halting Problem. Hence we can skip the point of being “effectively calculable”. The possibility or impossibility of a human or an electronic computer network being able tofollowing them is irrelevant, because mathematics is theoretical, not something physical. We can show that there exists the non-algorithmic.

Anything that is non-algorithmic, which refers to processes or truths that cannot be resolved by a finite sequence of step-by-step computational, is out of bounds of a Turing machine. Non-algorithmic mathematical objects or concepts are called undecidable problems or uncomputable functions.

1 Like
8

A computer can’t do something that can’t be set down as instructions. If whatever it is that you’re interested in can be then the computer will be able to do it.

AFAIK something that isn’t instructions is a different kettle of fish and may require us to look at it more closely.

9

Exactly, but notice what you can do. You can at least theoretically know all the things you have done, think of these actions, and then do something else that you haven’t done. That’s basically using negative self reference.

This actually comes very close to what Roger Penrose has said. He has claimed (still living, 95 years!) that the human mind can step outside those rules to grasp mathematical truths through genuine insight and awareness. Hence the human mind isn’t a Turing Machine. I agree with Penrose.

One thing that sometimes people start to argue is that how can we know we aren’t still using underlying algorithms and we are just “more advanced” Turing Machines? This philosophical question impliest that we don’t understand or are aware of these underlying “algorithms”. The issue here then goes out of reach into metaphysics, to a meta-level we cannot answer. Yet in reality we can understand the rules we follow and through learning change those rules we use. We do step outside the rules and think are they valid etc.

Yet it’s not at all clear if electronic machines, computer networks or AI, are indeed limited to being just Turing Machines. But in order for them to overcome this, they will need to use intuition, not just compute. Will imitation and using learning algorithms do the trick? It’s an interesting question.

Yet here the important factor is the definition of an algorithm as I wrote above: the step-by-step commands have to be exact, mechanical instructions that leave zero room for guesswork or personal judgment. If you have vagueness, the command can be interpreted various ways or the command simply leaves the actor freedom of choice, basically then instructions are non-algorithmic.

Is there a place in mathematics for the non-algorithmic, uncomputable math? Yes, but there’s really that downside: it really isn’t computable. Or the models will be vague: we cannot exactly compute, but we can assume something. Yet when this non-algorithmic mathematics is taken into consideration in the foundations of math, I believe we can have a better understanding of mathemtics. Because if we assume that all mathematics traces back to the computable, then that is the reason we have paradoxes.

10

I believe the important point of the definition - the reason why they choose the Turing machine model (that seems technical and complicated) to define the concept of algorithm, that seem to be much simpler do describe - is the necessity to exclude infinite sets of rules: what if you have a well-defined procedure that allows you to decide deterministically what next step to take in a program based on the current status, and you require the program to terminate in a finite amount of steps, but the the list of rules that can be matched upon is not finite?
You cannot state: the set of rules that is used to determine the next state has to be “computable” - that would be a circular definition.
But on the other side you want to be able to use variables in your set of rules, and these variables can range over infinite sets (such as the states of the memory).
So, if you try to give the definition of what “computable” means using the language of set theory, you discover that it’s not so simple: there are even questions about: which variant of set theory should you be allowed to use? should the axiom of choice be allowed?

In the end, you realize that the concept of “computability” should be more “fundamental” then the set of rules used for set theory itself. And then, if you don’t want to use the language of set theory, what language can you use? The idea was: an idealized physical machine. In reality, you could argue that even this definition is too comprehensive: it admits the use of an infinite amount of memory. However you cannot really use an infinite amount of memory in a finite amount of time, so this model seems to define the most extensive set of “things” that you can call algorithms.

A previous definition was the one of pure lambda calculus (by Alonzo Church). After the proof that lambda calculus is equivalent (as computing power) to Turing machines, Turing machines remained as the “canonical” definition, even if it seems to be a rather awkward way to define a mathematical concept.

However, in the end the particular use of the Turing machine in the definition of “computation” does not really matter: you could use Visual Basic with a machine made by a Pentium processor and infinite amount of ram, but that would be a VERY complex model to use in a formal proof :slight_smile:

2 Likes
12

What do you mean by “effectively calculable”? When you write “a finite set of commands” you should define what a command is. Usually (consider for example the algorithm for the multiplication of two integers A and B) to specify a command you need to refer to the current status of the computation (for example: look at the current digit of the number B and the current digit of the number A) - so, in the command you are speaking about a data-structure based on some kind of memory - in the case of multiplication made by pen and paper the memory is the paper that at every given step has some digits written to it and a set of indexes to the last written digits. So, that’s the same kind of specification as the one using a Turing machine. How can you skip the point of being “effectively calculable”?

13

I agree. Church-Turing thesis basically is about the fundamentals of math, hence if you can make it to a theorem, you basically show that there are new axioms.

Important fundamental truths in mathematics come up in many different fields of mathematics. Turing made his thought experiment with a machine, which actually is a basis for the real electronic machines that we call computers. Other undecidability results differ from it, but do make a similar point just from different perspectives.

The objective is to give the most simple understandable example in mathematics, not something where we introduce the complexities of the real world (for instance start thinking of Turing Machine or Oracle Machines and hypercomputing from the realm of physics). That dooms the discussion to go into other topics than math very easily.

The most simple way to portray the issue is perhaps that incommensurability exists in mathematics, hence not all mathematics emerges from calculation/computation. And if you assume that math does emerge from natural numbers and calculation, you will end up with paradoxes.

A clear instruction what to do that does not leave room for interpretation or freedom of choice when performing the action. (Perhaps the more exact definition would be an “algorithmic command”).

Commands that do leave that room are simply non-algorithmic. A step-by-step process with non-algorithmic commands is not an algorithm.

This is an important question. I’ll try to make my point.

Basically “effectively calculable” and “an algorithm” are the same issue in the way that the algorithm is the method (the step-by-step instructions) and the “effectively calculable” is the property of a mathematical function or problem. All algorithms are effectively calculable and all mathematical functions or problems that are effectively calculable can be solved/proven by an algorithm.

Basically they are two sides of a coin here. Why then talk about the two sides of the coin and not the coin?

Why I emphasive here the algorithm part is simply we can easily describe to “effectively calculable” a lot more, which makes it so open ended. I’ll attempt to give an example of what I’m going after with this:

Assume there’s a non-algorithmic mathematical statement or problem, which you, somehow by intuition, give either an answer to or prove to true (or false). By using intuition I mean that you didn’t deduce from existing facts the answer, but thought of something new that you never had thought before or had known before. Still, you will have to give a proof for this. Then someone looks at your proof and argues then that you simply followed an algorithm and hence the problem was “effectively calculable” in the first place. This way of thinking totally misses the point between the algorithmic and the non-algorithmic.

I think that some counterarguments to Roger Penrose follow this.

When Penrose argues that people aren’t Turing Machines because not all human thinking can be deduced to computation, some make the counterargument that the algorithms that people follow are simply so complex that we don’t understand them yet. This misses the Penrose’s point altogether. We do understand our “algorithms” that we use and can think about their validity and have the intuition to change them. The counterargument simply goes to the metaphysical realm, because it assumes us to follow step-by-step rules that we aren’t aware of. Meta-algorithms are in the realm of metaphysics, even if they are an interesting ontological idea.

Now I don’t know if I made my case clearly enough as this is a difficult topic, but hopefully you can see my point here. But thanks for bringing this up!

15

They are not even Turing machines. At least I think it’s worth pointing out that unlimited memory is already a huge idealization.

If we put an upper bound on memory, then the “magic” of computability theory evaporates.

All “actual” digital computers are finite. This leaves us with intractable problems, sure, but not with the famous theoretical problems.