2

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.
  • 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 4 '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 4 '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 4 '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. – user20153 Oct 4 '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. – user20153 Oct 5 '16 at 0:07
4

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.

  • You risk implying that computer science is not a science. – André Souza Lemos Oct 4 '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 4 '16 at 21:58
  • 2
    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 4 '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, 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, which is a statement of facts about the world. – Alexander S King Oct 4 '16 at 23:18
  • do you consider mathematics an empirical science? – user20153 Oct 4 '16 at 23:31
2

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.

  • "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". – user20153 Oct 5 '16 at 0: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 5 '16 at 2:54
  • Turing machines do not do io. this is well known. – user20153 Oct 5 '16 at 3: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 5 '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 5 '16 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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