PDA

View Full Version : Church'e thesis


Agaton
Mar31-11, 12:31 PM
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?

Thanks

SW VandeCarr
Mar31-11, 02:24 PM
It has the status of a conjecture or hypothesis. Apparently it cannot be proven formally. It has been shown to be equivalent to Turing's Thesis re the Turing Machine.

It seems it could also be regarded as a definition of a computable function, but I'll let others comment on that.