Results 1 to 2 of 2

Thread: Church's thesis

  1. #1
    Dec 2010

    Church's thesis

    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?

    Last edited by CaptainBlack; Apr 1st 2011 at 09:33 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Feb 2010
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Mar 2nd 2012, 06:25 PM
  2. Ms thesis
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: Jan 24th 2010, 07:13 AM
  3. my thesis
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: Jul 9th 2006, 03:19 AM

Search Tags

/mathhelpforum @mathhelpforum