[jimhefferon]

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.''

[generalizations]

I'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.)

[jimhefferon]

> Is it possible

Yes, the set of functions computable with mu recursion, or with lambda calculus, is the same as the set of functions computable with a Turing machine. (Turing in his original paper showed that the set is the same for his system and Church's, and the proofs for mu recursion and many other systems are well-known.)

> I'll totally agree that from a teacher's perspective, the Turing machine is the better explanation.

When I learned this, the instructor did not use Turing machines. They used mu recursion. That has the advantage that you don't first define a machine and then derive the set of functions, instead you go straight to the functions. But I agree that Sipser (which I understand to be the most popular text today) defines a computable function as one that is computed by Turing machine, and to my mind that has the advantage of honestly suggesting to students what they are about.

[generalizations]

Thanks, I think I understand now. I thought there was a distinction between the mathematical idea of what computation is, and the engineering we've invented to implement that computation, and so I didn't really get the significance/literalness of what you were saying about mechanization.

It does seem weird to me though that we're letting our engineering limitations determine how we think about these things mathematically.

[nl]

It's not as simple as engineering limitations determining how we think.

Turing machines do have mathematical advantages in some areas. See this siblings comment: https://news.ycombinator.com/item?id=28541800

[cybernautique]

I'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

[Karrot_Kream]

I guess I'm confused as to why this is more than simply an interesting formalism. Complexity theory and models of computation are largely based around the Turing Machine model. Lambda calculus is an effective lens to design programming languages and prove equivalence between programs. We know by way of the Church-Turing Thesis that these two models are equivalent. The Turing Machine model is both better studied from a computation perspective and has much more practical realization; what's the point in creating something like this? It feels a bit like silly lambda calculus fetishism, but again maybe the value here is the actual computation formalism itself.

[cybernautique]

For me, personally, I really like the lambda calculus as a tool to organize and better my computational thinking.

I came into programming/computer science from a mathematics degree; I read some old treatises on recursion theory[1] and fell in love. I couldn't ever quite wrap my head around the Turing Machine formalism, but kept at it for a while. Finding Barendregt's paper [2] was a huge shock! I grasped it much quicker. So, yes, lambda calculus and the Turing Machine formalism are equivalent in explanatory power, but there are also reasons someone might prefer one to the other. So, yes, for me, the value _is_ the formalism.

As to why I think the Rekursiv would provide a good platform for implementing lambda calculus on the bare-metal, that's entirely due to Rekursiv's memory model advantage and the fact that it has a user-writable ISA. Why would someone choose to implement the lambda calculus on bare-metal? You call it "fetishism," I call it fun!

More generally, I just really like the idea of having a machine with a user-writable ISA.

[1] Theory of Recursive Functions and Effective Computability: https://openlibrary.org/books/OL2738948M/Theory_of_recursive...

[2] Introduction to Lambda Calculus: https://www.cse.chalmers.se/research/group/logic/TypesSS05/E...

[Karrot_Kream]

FWIW Nothing wrong with having fun with computing, and implementing lambda calculus on bare-metal can be as fun as any other computational exploration, so good on ya!

Thanks for clearing up that it's the formalism you find interesting. Also, to offer a counterpoint, I'm also from a math background, but I was more of an analysis person (as much as one can be in mathematics where it's all related) than an algebra person, and when I did some FP research, it often felt like where all the algebraists go to play computer science. I feel like analysts are underrepresented in PLT (and overrepresented in complexity theory!) but this is already going off-topic, so cheers.

[cybernautique]

Nah mate, s'all good! It's great to hear your feedback; I am very much of the algebraist spirit myself (I barely passed my Rudin-based real analysis course). Our experiences definitely align. FP feels much more like my favorite parts of math.

Out of curiosity, can you identify any areas in PLT that could be made more analyst-friendly?

Intuitively, it feels that PLT is almost necessarily of the algebraist; to me, one of the big divides is the discreteness of algebra vs the continuity of analysis. Would it help if there was a PLT that exhibited a greater degree of continuousness? If so, what do you think that might look like?

[jecel]

I always mention the Rekursiv in my talk about Smalltalk computers. Its problem was being a CISC in the era of RISC. The Manchester Mushroom from just a little later had initially the same problem but went through a major redesign when they saw the JIT compilers for Self on the Sun Sparc processor.

[cybernautique]

I'd never heard of the Mushroom! Thank you for making me aware of it! A quick DDG search returned no results; I'd appreciate any links you have on the topic!

I'd also love to see your talk! Do you think a RISC Rekursiv could be achieved? What value, if any, do you think such might have in our current world?

[jecel]

This is the current Mushroom page:

http://www.wolczko.com/mushroom/

The slides for my 2019 talk about Smalltalk computers (in LibreOffice and PDF formats):

http://www.merlintec.com/download/2019_slides_jecel_fast1v2....

http://www.merlintec.com/download/2019_slides_jecel_fast1v2....

and the video (1 hour and 13 minutes):

https://www.youtube.com/watch?v=tATpzsyC6OA

If you replace the Rekursiv's special microcode memory with a cache to allow microcode to live in main memory you will essentially have a RISC version of the machine. I have adopted this solution in several of my own designs.

[cybernautique]

Absolutely fascinating stuff! Thank you for the links, friend, and welcome to a highly-treasured spot on my hard drive; all of these materials are going directly to my ~/Research directory! Computer architectures are an area I'd love to enter when I'm more experienced, so these are an incredible source of inspiration.

I'm also deeply in love with the merlintec website. It's refreshing to see a website which has persisted since 1999(!), and without a lick of JavaScript it would seem!

Could I purchase a Merlin 6 or a Pegasus 2000?

Speaking of which, the way that the Pegasus 2000's eGUI documentation[1] is written is incredibly dear. The "world" and "heaven" analogies are great!

[thom]

Thanks 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]

Absolutely! 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!

[WorldMaker]

That's the central argument in the Church-Turing Theory isn't it? Church felt very strongly that the difference between his and his students' "elegance" and Turing's "practical" was a difference only in abstraction and that the two models were equivalent and translatable (you can write in one abstraction and convert it to the other).

That theory continues to bear fruit as the history of programming languages is almost entirely about bringing new and "better" abstractions to problems and then translating them to "dumber, more practical" machines. We have programming languages today modeled directly off the elegance of (though now sometimes still a few steps removed from being direct implementations of) the lambda calculus and mu-recursive functions, and the amazing thing is that they work great even given how "dumb" and "inelegant" our machines can be in practice.

[acchow]

> 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'?

See also https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

[dwohnitmok]

> 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'?

This is already proven to be the case. Mu-recursion (which IIRC is not Godel's general recursive functions, despite what Wikipedia says; Kleene was the originator of the mu operator. Godel's general recursive functions are defined in a separate, but yet again equivalent way that directly extends primitive recursion), Turing machines, and the lambda calculus are all proven to be exactly equivalent to each other. The fact that these three independent approaches to computability are all equivalent is why we have strong informal justification that the Church-Turing Thesis (a non-mathematical statement) holds.

Separately, there's a sentiment that I've seen come up several times on HN that somehow the lambda calculus, mu-recursion, or general recursion is more "mathematical" and Turing machines are less "mathematical."

I want to push back on that. The mathematical field of computability is based almost entirely off of Turing machines because there are many classes of mathematical and logical problems that are easy to state with Turing machines and extremely awkward/almost impossible to state with the lambda calculus and mu-recursion (this is consistent with my previous statement that the three are all equivalent in power because computability theory often deals with non-computable functions, in particular trying to specify exactly how non-computable something is). The notion of oracles, which then leads to a rich theory of things like Turing jumps and the arithmetical hierarchy, is trivial to state with Turing machines and very unwieldy to state in these other formalisms.

Likewise the lambda calculus and mu-recursion (but not general recursion) provide a very poor foundation to do complexity theory in CS. Unlike Turing machines, where it is fairly easy to discern what is a constant time operator, the story is much more complicated for the lambda calculus, where to the best of my knowledge, analyzing complexity in the formalism of the lambda calculus, instead of translating it to Turing machines, is still an open problem.

There is indeed a mathematical elegance to Turing machines that makes it so that most of the mathematics of computability is studied with Turing machines rather than the lambda calculus.

The lambda calculus on the other hand is invaluable when studying programming language theory, but we should not mistake PLT to be representative of the wider field of mathematics or theoretical CS.

EDIT: I should perhaps make clear that if I put on my mathematical hat, mu-recursive functions seem like the most familiar formalism, because they align with a common way families of things are defined in mathematics (specify individual members and then generate the rest through some relationship). However, I would contend that for the majority of mathematicians outside of computability theory, the lambda calculus and Turing machines seem equally "strange."

[earleybird]

In 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]

You seem like someone who might have a good book about this bit of history? Or perhaps a blog?

[jimhefferon]

About the Theory of Computation in general. A draft: https://hefferon.net/computation/index.html :-)

[cfcf14]

Wonderful explanation, thank you.