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

Although it is commonly taught in undergrad classes as "stating that Turing machines and lambda calculus are equivalent" (which to be clear, it does), the premise of the Church-Turing Thesis is that all computable functions can be computed with Turing machines/lambda calculus.

The Church-Turing Thesis is unproven, but these days almost universally beleived to be true. Wikkpedia has a fairly decent coverage of all this stuff, if anyone is new to this topic.



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

Search: