4 ms·
> Language can't be small, if it's universal enough t, u := x | λx.t | (t u) Small language (three production rules), definitely universal. Of course the sem
by chewxy 7y ago
> Language can't be small, if it's universal enough
t, u := x | λx.t | (t u)
Small language (three production rules), definitely universal.
Of course the semantics is a lot more complicated than most people expect. But it IS syntactically very simple
- shmerl 7y agoTheoretical cases that are unusable in practice aren't interesting in the above context. We are talking about practical languages. It's not about Turing completeness.
- chewxy 7y agos := a | (s s) common lisp syntax. Even simpler, but that shifts much of abstraction capabilities to the operational semantics.