4 ms·
«`lambda` and function application alone are Turing-complete, as McCarthy would have known. The credit here belongs with Turing and Church, not McCarthy» I hav
by WorldMaker 10y ago
«`lambda` and function application alone are Turing-complete, as McCarthy would have known. The credit here belongs with Turing and Church, not McCarthy»
I have sometimes pedantically quibbled with people that it is properly named the Church-Turing Theorem (of Computation) and that that distinction of including both esteemed mathematicians helps to push people towards the realization of how groundbreaking that effort was (two mathematicians separated by an ocean and using vastly different approaches to the mathematics of computation realizing how intricately linked they were), and also how the Lambda Calculus truly was integral in the definition of "Turing-complete".
Without Church's work on the Lambda calculus and without the Lambda calculus being so very different from the Turing "imperative" model of machine, we'd probably have a much narrower view of what "Turing-complete" even means, if we even had the concept at all.
- deleted 10y ago[deleted]