Hacker News Reader

It’s the simplest model which can simulate all useful models of computation we have so far.

So, if you want to prove something about the limits of computation, a Turing machine is usually the right choice.

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

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.

I was referring to the instantiation of a TM as having a one sided tape.

Reply on news.ycombinator.com