Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The statement that "f is generally recursive iff it is Turing computable" is a theorem that can be proven, because we can rigorously define what it means to be Turing computable (computable by a Turing machine which is precisely defined) and generally recursive (which is the smallest set of functions closed under projection, composition, primitive recursion and minimalization). The theorem was proven by Turing and Kleene soon after the concept of Turing computable was introduced.

But if you remove the word "Turing" it is no longer a theorem. It becomes a thesis because we don't have a definition of what it means to be computable. It is in fact an innovation of Turing to identify computable with Turing computable, but that's by no means universal.



I think it's clearer to understand the Church-Turing thesis as two theses, not one. Turing's thesis was that (intuitive) computability equals (formalizable) Turing computability.

So you could completely ignore the recursive functions part (and so, Church's Thesis) and there would still be the same sort of lay confusion about the computability thesis.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: