4
$\begingroup$

My understanding is that the thesis is essentially a definition of the term "computable" to mean something that is computable on a Turing Machine.

Is this really all there is to it? If so, what makes this definition so important? What makes this definition so significant as to warrant having it's own name?

In most other branches of mathematics, a definition is an important part of the scaffolding, but not a result onto itself. In the case of the Church Turing Thesis, it seems like there must be more, but all I can see is the definition.

So, what is the significance of the Church-Turing Thesis?

$\endgroup$
2
  • $\begingroup$ Not exactly ... The rigorous definition of Turing machine gives as the precise mathematical concept of "Turing computable". The same for the many other equivalent definitions : recursive function, etc. It is quite obvious that any Turing computable fucntion or relation is intuitively effectively (i.e.mechanically) computableThe Church-Turing thesis is the "unprovable" assertion that all functions intuitively computable are Turing computable, i.e. that the mathematically rigorous def of Tuting computability (and its equivalents) exhasut the intuitive content of "mechanically" computable. $\endgroup$ – Mauro ALLEGRANZA Apr 28 '15 at 11:53
  • $\begingroup$ As far as I can see, the thesis is not importand because of its definition, but because it provides a bridge between the real world, where functions are effectively computable or not, and the theoretical world of mathematics, in which we have a strict definition of what "computable" means. $\endgroup$ – 5xum Apr 28 '15 at 11:55
3
$\begingroup$

The idea is that we have an informal notion of "computable" - that is, "something that can be computed". (This is explicitly not a precise definition). We also have a formal definition of "computable", that is, "computable by a Turing machine". The Church-Turing thesis is that these two notions coincide, that is, anything that "should" be computable is in fact computable by a Turing machine. (It's pretty clear that anything that is computable by a Turing machine is computable in the more informal sense).

Put another way, the Church-Turing thesis says that "computable by a Turing machine" is a correct definition of "computable".

$\endgroup$
1
  • $\begingroup$ One might add that another reason why we can believe that "computable by a Turing machine" is the correct definition of "computable", because "GOTO" and "WHILE" computabilities are equivalent to Turing-computability. So three different approaches lead to the same kind of computability, which is why we can believe that they describe the "correct" definition of computability. $\endgroup$ – TheWaveLad Apr 28 '15 at 12:01
3
$\begingroup$

The answer from user73985 explains the content of the Church-Turing thesis, but I'd like to add a few words about its value; why do we want it.

The first benefit that we get from this thesis is that it lets us connect formal mathematical theorems to real-world issues of computability. For example, the theorem that the word problem for groups is Turing-undecidable has the real-world interpretation that no algorithm can solve all instance of the word problem.

The second benefit is in mathematics itself, specifically in computability theory. Published proofs that something is Turing-computable almost never proceed by exhibiting a Turing-machine program, or indeed a program in any actual computing language. Sometimes, if the matter is simple enough, they provide some sort of pseudo-code. Most often, though, they merely give an informal description of an algorithm. It is left to the reader to see that this actually does give an algorithm (in the intuitive sense) and therefore, by the Church-Turing thesis, could be simulated by a Turing machine. The usual situation is that, although experts in Turing-machine programming would (if they existed) be able to routinely convert the intuitive algorithm into a Turing machine program, the program would be too large and complicated to be worth writing down.

$\endgroup$
2
  • $\begingroup$ Isn't this a bit of a tautology? you can't prove the thesis, since the informal notion of computability isn't well defined without the thesis. Then, you use the thesis to "bridge" between the formal and the informal, even though you don't actually know the bridge exists! $\endgroup$ – nbubis Apr 28 '15 at 12:44
  • $\begingroup$ @nbubis I"ll go out on a limb and say that I do know the bridge exists, i.e., I do know that the Church-Turing thesis is true. Of course, as you said, I can't prove that mathematically, since it involves the non-mathematical notion of intuitive computability. But I know lots of things that I can't prove mathematically, for example, the fact that I'm typing this comment. There is, of course, an issue about the use of such non-mathematical knowledge in a mathematical proof; hence the last sentence in my answer: You could give a mathematical proof instead, but it would be messy. $\endgroup$ – Andreas Blass Apr 28 '15 at 12:49

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.