Hacker News Reader

I think interaction nets [0] is actually a simpler model and can simulate Turing Machine efficiently. I wish courses in Computability/Complexity theory would be taught in interaction nets instead of Turing Machines as the program written would be so much nicer and compose easily. It also has real-life uses in compiling functional languages. [1]

[0]: https://en.wikipedia.org/wiki/Interaction_nets [1]: https://github.com/HigherOrderCO/HVM

View on HN

How is this simpler?

It seems to me a more complex lambda calculus.

Symmetric interaction combinators (an instance of interaction nets like 2-state 3-symbol Turing machine is a particular type of Turing Machine) only has 3 agents and 3 rewriting rules. This makes it about as simple as lambda calculus with 3 possible terms (variable, application, and abstraction) and α-equivalence, β-reduction, and η-reduction. The advantage of interaction nets is that each rewriting rule is local and "atomic" unlike subsitution step in β-reduction which can take arbitrarily long time as it is defined recursively.

Reply on news.ycombinator.com