6 ms·
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
by howling 3y ago
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 https://en.wikipedia.org/wiki/Interaction_nets
[1]: https://github.com/HigherOrderCO/HVM https://github.com/HigherOrderCO/HVM
- fooker 3y agoHow is this simpler? It seems to me a more complex lambda calculus.
- howling 3y agoSymmetric 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.