Church's thesis says that 'every effectively computable function is recursively computable'.
The meaning of the statement is clear enough. In more simpler words, it says that every function that have an algorithm is computable by Turing machine.
My question is that what is this statement and where does it come form? I mean, is that a mathematical statement? Is there any 'mathematical proof' for that?
April 1st 2011, 09:19 AM
Usually, it is considered a statement about mathematical notions but not itself a statement that admits of mathematical proof or disproof. It is a thesis not a theorem. In broad terms, it is the thesis that our everyday notion 'calculability' is captured by the formalization 'recursive functions' (equivalently, by Turing machines et. al). One may give arguments for or against the thesis but such arguments are not themselves mathematical proofs or disproofs.
Church's thesis has widespread support among mathematicians though there are a handful of dissenters.
Also, there might actually be some formalization of Church's thesis in some system somewhere, but I (with my quite limited knowledge) don't know of one. I just mention this so that my remarks above are not meant to categorically preclude that one could devise some system in which Church's thesis is itself formalized. But it's hard to imagine anyway, since, as far as I understand, the thesis is indeed that of matching an informal notion (calculability) with a formal one (recursiveness).