1
$\begingroup$

I am aware of the fact that, since the concept of "effectively calculable function" is not rigorous or formally definable, the Church-Turing thesis may not be proven by symbolic or formal reasoning alone.

My impression, though, is that under the domain of physics, philosophy, cognitive science or other disciplines, we may find empirical evidence that gives us a strong reason for accepting it, for instance in the field of numerical cognition. Even if those disciplines are not directly related to computer science, the importance of this thesis in CS make this, in my opinion, an important issue to consider for us; that's why I'm asking this question here. (If you feel like there are better SE suited for this questions, let me know please.)

So, what is the current state of the research for evidence to support the Church-Turing thesis? Are there any recent developments?

A good answer would also provide a list of all the major efforts to this day to empirically validate or refute the CT-Thesis, and the main problems posed by this issue. Investigations on the notion of "effectively calculable" in cognitive science, or what does it mean to "compute" in physics are also welcome.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

Proof is an inherently mathematical concept. "Effectively calculable function" has no definition in mathematics and you can't prove something that doesn't have a definition.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Excuse me, but can't you prove something in physics via experiments and observations? Maybe I am using the wrong word because I am not a native speaker. $\endgroup$
    – olinarr
    Commented Apr 4, 2019 at 13:30
  • 3
    $\begingroup$ @NetHacker No, experiments and observations can only give evidence for something. Very good experiments might give very good evidence. $\endgroup$
    – David Richerby
    Commented Apr 4, 2019 at 13:35
  • $\begingroup$ @NetHacker At least in (T)CS and maths, to "prove" something roughly means to provide a deduction of the result from a set of axioms, so that there can not be any doubt about its truth. Other disciplines instead may rely on some experimental evidence, or some convincing argument (which might get sometimes overturned later on by another more convincing argument -- see essentially all of philosophy). Some of these arguments might be called "proofs" by some, but they are not scientific proofs. That does not mean that they are worthless, only that science does not deal with them. $\endgroup$
    – chi
    Commented Apr 4, 2019 at 14:48
  • 2
    $\begingroup$ @NetHacker I see. In that case, perhaps CS.SE is not the right place for this question, since it looks like you want an answer from another viewpoint. I'm unsure. $\endgroup$
    – chi
    Commented Apr 4, 2019 at 15:08
  • 1
    $\begingroup$ @NetHacker Those look like good candidates, but I'd triple check their scope since this is a rather peculiar question. Also, Yuval's link above points to several nice answers on TCS.SE, so perhaps you should also clarify why those answers are not what you seek. $\endgroup$
    – chi
    Commented Apr 4, 2019 at 15:15

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.