It's not a math theorem. From http://mathworld.wolfram.com/Church-TuringThesis.h... | Hacker News

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

waynecochran on Jan 30, 2019 | parent | context | favorite | on: Some Fundamental Theorems in Mathematics

It's not a math theorem.

From http://mathworld.wolfram.com/Church-TuringThesis.html

    There has never been a proof, but the evidence for 
    its validity comes from the fact that every 
    realistic model of computation, yet discovered, 
    has been shown to be equivalent.

http://people.seas.harvard.edu/~salil/cs121/fall12/lecnotes/...

    The Church–Turing Thesis is an extramathematical 
    proposition, not subject to formal proof.

tshaddox on Jan 31, 2019 [–]

You're right. The thesis is that nothing in the real world can compute a function that a Turing machine cannot, which is not proven (and it's not clear how it even could be proven). What is proven formally is the equivalence of several different formulations.

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