4 ms·
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 t
by xorand 7y ago
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 http://imar.ro/~mbuliga/betarand.html
- danharaj 7y agoBecause of the Curry-Howard-Lambek correspondence.
- xorand 7y agoAgree, 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.
- xorand 7y agoAn 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).