Hacker News Reader

In case anybody interested in graphic lambda calculus, there are 5! X 5! = 14400 possible alternatives for the beta rewrite only. So it beats me why among all the possible calculi in CS the lambda calculus is special. I made a page which gives random alternatives http://imar.ro/~mbuliga/betarand.html

View on HN

An update: added more explanations about how these random variants of the beta rewrite are generated. You can see also the generated rewrites written in lambda calculus style, although they are graphical rewrites which go outside lambda calculus. I state again what I believe: that analogously with cellular automata, probably a big proportion of these random generated calculi are as rich as the original (Turing complete at least).

Because of the Curry-Howard-Lambek correspondence.

Agree, but I don't say that lambda calculus is not interesting, I say that there are so much more alternatives, unexplored. If we do the same with the IC of Lafont, I think that the possible (right patterns) of rewrites (which preserve the no of half-edges and nodes) are about 10^13.

A conjecture, which I don't know if it holds water, is that analoguous to CA, Wolfram style, perhaps 1/3 (or anyway a significant proportion) of the 10^13 possible graph rewrite systems, alternative to IC, are Turing universal.

Reply on news.ycombinator.com