Results 1 to 2 of 2

Math Help - Church's thesis

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    12

    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?

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

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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: March 2nd 2012, 07:25 PM
  2. Ms thesis
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: January 24th 2010, 08:13 AM
  3. my thesis
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: July 9th 2006, 04:19 AM

Search Tags


/mathhelpforum @mathhelpforum