5 ms·
The question in the air in 36-ish was something like, "OK, clearly we can mechanically compute things like the sum of two numbers or the prime factorization of
by jimhefferon 5y ago
The question in the air in 36-ish was something like, "OK, clearly we can mechanically compute things like the sum of two numbers or the prime factorization of a number. But are there other things that can be computed with a discrete and deterministic mechanism?" (At the time they called these "effective" functions.)
Church had piles of stuff that he and his students produced that were computable with the lambda calculus. Basically, all of the natural number functions that a person thinks are intuitively mechanically computable, those folks had showed how to lambda compute. With this evidence, he proposed to Godel (they were working together at Princeton at the time), who was considered the world's expert, taking "lambda-calculable" as a mathematically precise version of "mechanically computable." But Godel was notoriously careful, and he did not accept the thought as perfectly clear.
That is, they had a subset of the things that could be mechanically computed. But was it the entire set? Or was there something that some discrete and deterministic mechanism could be made to do that would lead to more than Church's set?
Imagine you are Dedekind and you are looking at the primitive recursive functions and (1) any such function is intuitively mechanically computable, and (2) you are able to work out how to define a pile of things like prime factorization of an integer using this system. You might well conjucture that this is it. But we know (and Godel and Church and Turing knew) that this is not it, that you need to add unbounded search of some kind (this is what minimization does) to get more things that are intuitively mechanically computable.
I agree that the minimization operator is not as easy to picture with gears and levers as some of the other operations. But the issue in 36 was that a person could worry that there was even more. Just as minimization is not as easy to picture and the need for it didn't hit Dedekind with great force, could there be something else out there that we have all missed?
That worry disappeared when Godel read Turing's masterful analysis. It convinced him that this is what a machine can do.
He wrote,
"That this really is the correct definition of mechanical computability
was established beyond any doubt
by Turing.'' Church felt the same way, writing
that Turing machines have
"the advantage of making the
identification with effectiveness
...
evident immediately.''
- cfcf14 5y agoWonderful explanation, thank you.
- generalizations 5y agoI'm still a little confused. It seems like Turing came up with something that works, and clearly fulfills precisely what Godel and Church and Turing were all looking for; but it also seems like it's a mathematically inelegant solution. Is it possible that in the future we'll find a way to show that Gödel's mu-recursive functions or Church's lambda calculus also precisely describe 'what a machine can do'? If so, it seems that from a mathematical standpoint, either of those would be a better foundation to start from. (I'll totally agree that from a teacher's perspective, the Turing machine is the better explanation.)
- cybernautique 5y agoI'm convinced that David Harland's Rekursiv[1:] machine _is_ the manner by which lambda et al. might be implemented at the machine level. Unfortunately, Rekursiv seems to have died an ignominious death, with the last Rekursiv chip having fallen off the side of a steamboat (apocrypha; I remember having read this, but I'm unable to find the original citation.) The Rekursiv advantage is its ability to do recursion on the bare-metal. It's described as an object-oriented architecture. Its memory was a persistent store of objects, with each object having its size, type, and position known in memory. [1] https://en.wikipedia.org/wiki/Rekursiv https://en.wikipedia.org/wiki/Rekursiv
- thom 5y agoThanks for this link, really interesting stuff. For a while there was a fashion in OS research for orthogonal persistence but this is much deeper and more elegant.
- cybernautique 5y agoAbsolutely! As mentioned, I'm very much a novice of computer architecture. It kinda blew my mind that Rekursiv was unique in its abilities. Also fascinating are LISP Machines, which seem to have received quite a bit of love from HN already. If I may ask, from your perspective, what's more elegant about Rekursiv's design? Is it the philosophy or implementation? I'd also love any links to orthogonal persistence!
- earleybird 5y agoIn a nutshell, Church asserted effective computability by saying "look what you can do with the lambda calculus". Turing took the philosophical approach saying "this is what it means to compute". To Godel, Church's argument was incomplete. Turing provided the direct argument. Godel was convinced.
- lordnacho 5y agoYou seem like someone who might have a good book about this bit of history? Or perhaps a blog?
- jimhefferon 5y agoAbout the Theory of Computation in general. A draft: https://hefferon.net/computation/index.html https://hefferon.net/computation/index.html :-)