Hacker News Reader

Comment by l33t233372 | Hacker News Reader

It’s unclear to me why restricting ourselves to that model is useful here

Changing the model wouldn't change anything. A turing machine is equivalent to any computational machine you want to put in there. It doesn't matter what the machine is. The turing machine is the goto because it was first used for them.

Any other machine that can simulate a turing machine can simulate failing in those same ways. You can't escape the problems of turing completeness without losing it.

It does matter, the second and last sentence of the abstract is "The proof is sensitive to the particular computational models."

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 was referring to the instantiation of a TM as having a one sided tape.

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.

Reply on news.ycombinator.com