3 ms·
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 premi
by jlgreco 14y ago
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.