1
$\begingroup$

One thing I was never clear on when taking Computational Complexity in college is whether the Church-Turing "thesis" is (or can be) proven.

Is it..

  • A theorem? If so, where's the proof?
  • A conjecture? If so, why isn't considered one of the great open problems? This seems even more important than P=NP
  • An axiom? If so, does that mean we can study mathematical systems where the thesis is not true?

The wikipedia page calls it a "conjecture", but then goes on to say

it cannot be formally proven, as the concept of effective calculability is only informally defined.

A statement which makes no sense to me. If we have a proof that the "thesis" is undecidable in some system, wouldn't that make it an axiom?

$\endgroup$
8
  • 4
    $\begingroup$ The Church-Turing thesis relates the informal notion of "algorithm" with the formal notion of Turing Computability. Since half of the statement is about something that is not mathematically defined, we cannot prove anything about it (not even undecidability). As soon as you define precisely what you mean by "algorithm", you are just studying the Turing-completeness of your particular definition. $\endgroup$
    – Denis
    Jul 20, 2022 at 9:05
  • 6
    $\begingroup$ So to answer your question, it's neither of a theorem/conjecture/axiom, because it's not a mathematical statement. If you say "math is beautiful", it's also not a theorem/conjecture/axiom, even though mathematicians are convinced it's true ;) $\endgroup$
    – Denis
    Jul 20, 2022 at 9:09
  • $\begingroup$ @Denis I'd say that the CTT is a statement about physics. We do not know if it is physically true or not, but all the currently available evidence (which is empirical) points to it being true. Maybe some day somebody finds a way to execute infinitely many compute steps in finite time. Then that would falsify the CTT. $\endgroup$ Jul 20, 2022 at 11:16
  • $\begingroup$ @MartinBerger If you take it as a statement of physics, it's unequivocally false. We do not have the physical resources to compute recursive functions of unrestricted growth rate, as the number of particles in the accessible part of the universe is limited. $\endgroup$ Jul 21, 2022 at 5:36
  • 1
    $\begingroup$ @BlueRaja-DannyPflughoeft we can easily define models of computation stronger than Turing-computability (e.g. machines with oracles), but the point of the C-T thesis is that they are not "realistic", ie cannot be implemented in real life, which is the informal notion that escapes a mathematical definition. $\endgroup$
    – Denis
    Jul 21, 2022 at 10:55

4 Answers 4

8
$\begingroup$

The Church-Turing thesis is not a theorem, conjecture, or axiom. For it to be one of these, it would need to be a mathematical statement that has the potential to have a rigorous proof. It does not.

The Church-Turing thesis is, in one common formulation:

every effectively calculable function can be computed by a Turing machine.

The problem is that "effectively calculable" does not have a rigorous mathematical definition. You can give it one, and then you have a theorem, such as the following:

every general recursive function can be computed by a Turing machine,

or

every $\lambda$-definable function can be computed by a Turing machine,

but this doesn't show that there aren't other ways of effectively calculating functions that cannot be computed by a Turing machine.

The above two theorems, by the way, are what led to the proposal of the Church-Turing thesis.

$\endgroup$
1
$\begingroup$

I would call it a law of nature. It is a general and fundamental description of how the universe works, that we believe (based on evidence) to be true.

For example, the Second Law of Thermodynamics states that entropy of closed systems does not increase on average. We have models of the universe in which we can prove the second law. But they are just models. One cannot prove that it is true or false about the actual universe. One can only try to find experimental evidence that refutes it, and fail. The same things are true for Church-Turing.

Another similar phenomenon also considered "laws" are things like Zipf's Law, i.e. an empirical statement about the world that seems to hold wherever we look so far.


Background: the Church-Turing thesis is the statement that anything that can be computed, can be computed by a Turing machine. The Turing machine is a formal mathematical model, so what it computes is well defined. However, "anything that can be computed" is not mathematically well-defined. For any particular model of computation one proposes - lambda calculus, mu-recursive functions, etc. - one can prove whether it is equivalent in power to Turing machines or not. But since "can be computed" isn't mathematically formalizable, Church-Turing can never be formally proven or disproven.

In fact, "can be computed" must be a statement about the physics of this universe. Because we can define physics under which Church-Turing is false, e.g. hypercomputation, but this universe doesn't satisfy them. It is also probably mathematically possible to define models of computation that are more powerful than Turing machines, but where it's not clear whether they can be physically implemented. For example, it isn't obvious that the unbounded minimization operator from mu-recursive functions is physically implementable (however, it is and they turn out to be equivalent to TMs).

We could falsify Church-Turing (rather than disprove it) if we proposed a formalized mathematical model of computation and: (a) proved that it was more powerful than a Turing machine, (b) showed that it could be physically implemented consistent with known laws of physics, and ideally (c) experimentally demonstrated this implementation.

$\endgroup$
4
  • 1
    $\begingroup$ This is definitely incorrect. Nothing about the theory of computation assumes a particular universe. It should be unequivocally true or false (or undecidable) within a certain set of axioms, regardless of whether those axioms actually hold in a given universe. $\endgroup$ Jul 21, 2022 at 7:50
  • 2
    $\begingroup$ @BlueRaja-DannyPflughoeft based on your response, you may have a misunderstanding of what the Church-Turing thesis is. $\endgroup$
    – usul
    Jul 21, 2022 at 18:29
  • $\begingroup$ I have added some background to explain my answer further. $\endgroup$
    – usul
    Jul 22, 2022 at 23:52
  • $\begingroup$ Re the update: I still disagree that "hypercomputation" has anything to do with physics or this universe. You can imagine it as a thought experiment (in the same way you can imagine "a set of all sets"), but if you attempt to actually formalize it, you run into a logical inconsistency (the Halting Problem proof). Thus it's not our universe preventing hypercomputation from existing, but mathematical logic itself. $\endgroup$ Jul 23, 2022 at 0:05
0
$\begingroup$

A thesis is a statement believed to be true like a conjecture / hypothesis, i.e, something that seems to be true but is rather informal stated. You can check here https://en.wikipedia.org/wiki/Thesis_(disambiguation) I think it can help you

$\endgroup$
0
$\begingroup$

I asked a related question on M.SE about ten years ago with some nice responses. My favorite thing I learned from that thread is Malament-Hogarth spacetime. The upshot is that we can philosophize about physical systems that solve undecidable problems, and so the Church-Turing thesis is really an assertion about Turing Machines vs a particular kind of computation, rather than any kind of computation that is conceivable in our universe. (I definitely disagree with the claim that it is "a law of nature.")

The idea behind MH spacetime is that, to solve the halting problem, I start my computer running on an input and I program it to turn on a light if and when it halts. Then I fire it into a black hole. If I ever see it turn on the light, I know it halts; if I see it cross the event horizon without turning on the light, then since an infinite amount of time has passed from the perspective of the computer, I know it doesn't halt.

Of course there are a few things about this system that are physically implausible, including that the light gets redshifted into oblivion and so it becomes very hard to detect. But in any case, it's convincing enough to me that this thought experiment is doing something different than your run-of-the-mill Turing machine.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.