Hacker News Reader

Comment by an-allen | Hacker News Reader

When I took Fundamentals of Programming Languages 20 years ago - I nearly failed the class. Lambda calculus was simply too esoteric for me to appreciate and much less understand intuitively.

Fast forward 20 years, and I see the fundamentals of Alonzo Church’s system in every computation problem I encounter. It’s one of those concepts that age like wine. The only other concept I put on the same level is Shannons “informational entropy” and maybe Wolfram’s Ruliad.

View on HN

It's kind of interesting that the history is in the order it is. I could completely imagine it being reversed: first, 1000 programming languages are invented, then later, in an attempt to put order to this madness, and understand whether some of them are in a fundamental sense equivalent to others or not, you invent minimalist languages like Turing machines or the lambda calculus, and start developing a theory of reductions.

Kind of odd that the Turing machines and lambda calculus predate almost all the others! I mean there are good reasons for it, especially if you try to put yourself in a 1930s mathematics mindset (which is why it actually happened that way), but it is, I'd submit, a bit surprising to learn from a 2020s perspective if you didn't already know it.

Interesting thought. Perhaps we'll discover a language that is in some way of higher order than Turing complete.

There are certain concurrent properties that cannot be modeled with a Turing machine: https://en.wikipedia.org/wiki/Unbounded_nondeterminism

There is also a very interesting intersection between the history of the Actor Model and Lambda Calculus: https://research.scheme.org/lambda-papers/

> Interesting thought. Perhaps we'll discover a language that is in some way of higher order than Turing complete.