1

The definition of the Church-Turing's thesis is an attempt at capturing the intuitive idea of effective computability or "things that can actually be calculated".

It has been said that it is not something to be proven, or refuted, but important assumptions underlying scientific work in many fields of research rely on some version of the thesis, one important case being the linguistic assumption that the semantics of natural languages can be formalized in any significant way.

Considering that it is unfalsifiable, should the Church-Turing's thesis be given such an important role in scientific research?

EDIT:

Thanks for the attention. In response to some of the criticism that the question has received, I'd like to add that,

  1. In many, many works in linguistics, psychology, cognitive science, philosophy, and obviously in most of what is applied computer science, a more or less conscious leap is made from thought-meaning-behavior... to computable to Turing-computable. It is to this last step that I am referring in this question. This way of thinking, while not necessarily reflective of our better understanding, still enjoys significant popularity within the scientific community (and yes, this is just my perception).
  2. The Church-Turing's thesis, not being entirely objective, can still be debated, objected to, even discredited and eventually considered useless (which I believe is what is going to happen, some day), but not strictly falsified.
André Souza Lemos
  • 1,154
  • 8
  • 22
  • No one believes that semantics of natural languages can be formalized. Even Davidson, who I think was most optimistic in this regard, treats it as a regulative ideal we should strive for rather than an assumption. Something like let's try to formalize as much as we can. The "law" of causality is also unfalsifiable (and probably false), yet to keep looking for causes where none as of yet were found is still mostly a good motto for science. Lawfulness or effective computability are good goals because they have high utility to us, as long as they do not collapse into wishful thinking. – Conifold Oct 04 '16 at 21:28
  • "No one believes" is a strong statement, especially in this community. What I believe is that this is something worth talking about. – André Souza Lemos Oct 04 '16 at 21:51
  • But you call it "important assumption underlying scientific work in many fields", which it isn't. "No one" is not much of a stretch, see Miller's Philosophy of Language. It simply isn't needed as an assumption to do linguistics of natural languages, or even to attempt formalizing aspects of it. – Conifold Oct 04 '16 at 22:29
  • to put it differently, people who *assume* that the semantics of natural languages can be formalized run the risk of not being taken seriously. –  Oct 04 '16 at 23:28
  • I'm not sure that you have correctly characterized CT. It was Turing, and only Turing, who captured the notion of "effective procedure" in formal terms. CT, if I'm not mistaken, says that other models, like lambda calculus, are equivalent to the Turing model. that's a very different thing. it's never been proven, but that does not mean it cannot be proven. nonetheless everybody believes it is true. –  Oct 05 '16 at 00:07
  • "many fields of research rely on some version of the thesis". can you give a specific example? I can't think of one. –  Oct 05 '16 at 00:18
  • @mobileink if you read the question carefully, you'll spot an example very easily. You (and others) may not agree that this is a valid example, but it is there. – André Souza Lemos Oct 05 '16 at 01:03
  • We may say that [Church-Turing Thesis](http://plato.stanford.edu/entries/church-turing/) is an hypotheses; we cannot mathematically prove it, because it states the equivalence between a "formal" concept and an intuitive one. Of course, it can be *falsified* (and some attempts have been produced). How ? showing a "computational procedure" that is intuitively "mechanical" but proving (in a precise mathematical way) that it is not e.g Turing computable. – Mauro ALLEGRANZA Oct 05 '16 at 07:00
  • You can see : [Laszlo Kalmar’s Objection to Church’s Thesis](http://www1.maths.leeds.ac.uk/pure/logic/computability/abstracts/ingramabstract3.pdf) as well as [On some recent criticism of Church's Thesis](http://projecteuclid.org/euclid.ndjfl/1093957577). – Mauro ALLEGRANZA Oct 05 '16 at 07:39
  • See also this [post](http://mathoverflow.net/questions/233234/are-there-finitistic-nonrecursive-functions-assuming-churchs-thesis-is-false). – Mauro ALLEGRANZA Oct 05 '16 at 07:40

2 Answers2

3

You want to be careful when you use the word science in the context of falsifiability. Falsifiability is a property of theories in empirical sciences, i.e. sciences that are based on observation of real world phenomenon.

In this sense, the Church-Turing thesis is not a scientific statement, it is a statement of logic and mathematics. Logic and math are independent of observation, and are therefore strictly speaking not part of science. 2+2=4 regardless of whether Newtonian mechanics is correct or whether Einstein's relativity is correct. (a-b)²= a² - 2ab + b² regardless of whether the earth is flat, or round, or there are 25 planets in the solar system or only 4.

In some other definitions, math and logic are sciences, but using the Falsification criteria of demarcation, they are not.

As for the fact that the Church-Turing thesis is used in various empirical sciences, it bears the same relation to these sciences that any theorem or conjecture of mathematic bears to them.

Alexander S King
  • 26,984
  • 5
  • 64
  • 187
  • You risk implying that computer science is not a science. – André Souza Lemos Oct 04 '16 at 21:53
  • Theoretical computer science *is not* an empirical science, it is definitely a branch of mathematics. It started out as a branch of math, with Turing setting out to solve one of Hilbert's problems. But now you're made me stumble upon a more interesting question...... – Alexander S King Oct 04 '16 at 21:58
  • 3
    I don't think that's right. A theorem of math can be proven from first principles. The C-T thesis is not a theorem and can not be logically proven. It is a statement of a belief about the world. There could not be two things in the world more different and dis-alike than a mathematical theorem and the Church-Turing thesis. – user4894 Oct 04 '16 at 23:08
  • @user4894 I never said it was a theorem. The Church-Turing thesis is the same type of statement as statements of mathematics in the sense of [Hume's fork](https://en.wikipedia.org/wiki/Hume%27s_fork), i.e. they are relations of ideas, not of facts about the world. You are confusing the original Church-Turing thesis, with [David Deutsch's updated physical version of the thesis](https://en.wikipedia.org/wiki/Church–Turing–Deutsch_principle), which is a statement of facts about the world. – Alexander S King Oct 04 '16 at 23:18
  • do you consider mathematics an empirical science? –  Oct 04 '16 at 23:31
  • sorry that was supposed to be addressed to @user4894 –  Oct 04 '16 at 23:32
  • I agree that CSIS not an empirical science. But "definitely a branch of mathematics" is a whole 'nother story. The concept of computation is based on the intuitive notion of "effective procedure", and i see no reason to treat that as a mathematical concept. –  Oct 04 '16 at 23:38
  • @mobileink I think I get your drift: Effective procedure is more of a human artifact, than of an independent truth, is that why you disagree? But then so is the Fourrier transform, or LU Matrix factorization, but those are still mathematical objects about which theorems can be stated, not physical objects, [see here](http://philosophy.stackexchange.com/questions/34073/for-a-mathematical-realist-is-there-a-distinction-between-real-mathematical-obj) – Alexander S King Oct 04 '16 at 23:42
  • there the part where you say it, and the part where you take it back, as somebody famous once said. geometry is also based on intuitions derived from the experience of living in space, just as computation is based on intuitions derived from the lived experience of calculating. so why shouldn't the latter be just as mathematical as the former? one possible answer: the theory of computation is a mathematical model of something non-mathematical. but I guess the same could be said of Euclid an geometry and space. –  Oct 04 '16 at 23:54
  • I'm inclined to think of mathematics, logic and computation as different views of one thing. there are problems with crowning any one of them and treating the others as derivative. Maybe they are ultimately independent? –  Oct 04 '16 at 23:56
  • 1
    @AlexanderSKing The classical C-T thesis says that a TM can compute anything that can be effectively computed *by a human*. That is an explicit statement *about the world*. Statements of math are NOT statements about the world. That is why I disagree with you. https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis – user4894 Oct 05 '16 at 01:41
  • 1
    @mobileink Math is often inspired by the real world. But a mathematical theorem is not about the world. The C-T explicitly *is* about the world in that it refers to the abilities of human beings. Mathematical theorems are only formal consequences of axioms and inference rules. They are not necessarily about the world. The C-T thesis *is* explicitly about the world. This is a huge distinction and one that Alexander S King is missing. – user4894 Oct 05 '16 at 01:43
  • @user4894 wikipedia may not be the definitive source, but even it uses the phrase "human being following an algorithm" for what it applies to in the real world. To me, this additional constraint is the key to interpreting CT as a formal result, albeit one that may both reflects stuff "in the real world" (i.e. it embodies a particular formalization of what an algorithm is) and may represent a real constraint on what can happen "in the real world" (maybe this is representative of what is possible ala Deutsch). – Dave Oct 05 '16 at 16:15
  • @user4894 UTM's are mathematical objects, λ-calculus is a formal system, i.e. a set of mathematical objects, Gödel's general recursive functions are mathematical objects. Classical C-T is a conjecture that a property of these three classes of mathematical objects applies to a larger set of mathematical objects as well. Classical C-T is problematic because this more general class is not well defined, not because of the empirical nature of the thesis. I agree with you that it can be interpreted as having empirical consequences, but then it becomes the Deutsch-C-T thesis, not classical C-T. – Alexander S King Oct 05 '16 at 16:28
  • @AlexanderSKing I'm not an expert so I'll have to leave it at what I've already said. I did give a careful reading to the SEP article http://plato.stanford.edu/entries/church-turing/. The word "human" occurs 48 times. It's hard not to read all this without coming to the conclusion that either C-T is very poorly phrased; or else it is in fact a statement about the world. – user4894 Oct 05 '16 at 19:30
  • @user4894: we'll have to agree to disagree. see r. soare's paper on the history of the concept of computability at http://www.people.cs.uchicago.edu/~soare/History/ for a refutation of your claim by one of the leading scholars in the field. –  Oct 05 '16 at 19:33
  • @Dave See my response to Alexander S. King. SEP's article on C-T uses the word "human" 48 times. I understand that C-T talks about a human executing an algorithm mechanically; but still, it's always a human. With that definition, it's hard to imagine even a Platonist making the claim that there is an effective procedure absent humans. There might be an algorithm out there in the Platonic realm of abstractions, but there is no human to execute it. C-T is very different in character than a mathematical theorem. But I'm no expert so I can't add any more to what I've said. – user4894 Oct 05 '16 at 19:33
3

The Church-Turing thesis is a non-provable thesis, rather than a theorem, because it is a claim that our informal, non-theoretical understanding of what counts as effectively computable is entirely captured by what is computable by a Turing machine, or equivalently, by a general recursive function. The term hypercomputer is used to denote a computing device that can compute things that are not Church-Turing computable, so another way to express the thesis is that it is the claim that there are no hypercomputers.

The claim that there are no hypercomputers is not unfalsifiable, but a negative claim like this can only be supported (not proved) by doing our level best to devise a hypercomputer and showing that it is unrealizable. Several theoretical models of hypercomputation have been proposed but none have been found to be feasibly realizable.

One might go further and argue that in order to implement a hypercomputer, it would have to operate in a way that is consistent with the laws of physics, and given what we currently know about physics, this is inherently implausible. A hypercomputer would have to be based on weird physics: even more weird than quantum mechanics, since quantum computers are consistent with Church-Turing. An ideal analog computer could potentially be a hypercomputer, but it would have to be able to process real numbers to infinite precision, which is not consistent with the picture of the universe that QM offers us.

So it is not unreasonable to accept that the Church-Turing thesis is correct and base scientific work on it, even though we cannot prove it.

Bumble
  • 20,757
  • 2
  • 27
  • 65
  • "The term hypercomputer is used to denote a computing device that can compute things that are not Church-Turing computable" I'm not sure about the term "hypercomputing", but I have a device that regularly computes things that are not computable by a Turing machine. it's sometimes called "input-output". –  Oct 05 '16 at 00:16
  • I'm not sure why you made this comment. Turing machines (or recursive functions for that matter) can have input and output. Hypercomputers are putative theoretical devices that can compute things that are not computable by Turing machines. – Bumble Oct 05 '16 at 02:54
  • Turing machines do not do io. this is well known. –  Oct 05 '16 at 03:06
  • You are using input/output in a strange way. The initial state of a TM tape is usually considered to be its input, and the final state its output. Turing himself used the terms input and output in this way to describe the workings of a TM, and others have done so since. It would be difficult to explain the concepts of a universal TM, or the halting problem, without reference to input... – Bumble Oct 05 '16 at 18:40
  • If you mean something stronger, like the ability of a machine to allow its tape to be rewritten by an external process while a computation is in progress, then such a machine would indeed not be a TM, but it would still be highly contentious to claim that it is not equivalent to any TM. So to say "Turing machines do not do IO" in this strong since is true, but it does not follow that you "have a device that regularly computes things that are not computable by a TM." – Bumble Oct 05 '16 at 18:40
  • I meant io on the ordinary programming sense. printf is not a Turing computable function. see for example Peter Wegner's work on interactive computation http://cs.brown.edu/~pw/ –  Oct 05 '16 at 19:04
  • I am familiar with Wegner's work, but I still regard his claims about having refuted the Church-Turing thesis as highly contentious. They do not appear to have achieved any consensus within the computability theory community. There is an entry on the Theoretical Computer Science portion of Stack Exchange that covers this issue: http://cstheory.stackexchange.com/questions/12377/applicability-of-church-turing-thesis-to-interactive-models-of-computation – Bumble Oct 05 '16 at 19:20
  • ha, I was just reading that thread! Actually I think robert soare is a better reference, see esp. his paper on the history of computability at http://www.people.cs.uchicago.edu/~soare/History/ –  Oct 05 '16 at 19:28