Hacker News Reader

Comment by isaacfrond | Hacker News Reader

The problem is that with probability 1 a random problem will access an undefined memory position. Such program halt by definition.

This makes the result a lot less interesting. Sure random programs will typically halt before long, but with an illegal memory access ( in the parlance of the article, they read from the left of the turing tape)

View on HN

This is wrong and directly contradicted, unambiguously by the linked paper.

"For the purposes of defining the halting problem H, one should specify whether it officially counts as halting or not if the head should happen to fall off the left edge of the tape. Although the truth of the main theorem will not depend on these details, provided we adopt a uniform answer, let us be definite and regard such computations as having not officially halted, as the halt state was not reached."

There is no such notion of “undefined memory region” for a Turing Machine

Some models of the Turing machine have an infinite tape in only one direction. Some also don’t require every state to have an exhaustive set of transitions. Those models generally consider going off the end of the tape or failing to find a transition to be a halting state.

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.

It is true that some models define halting that way, but in this paper they explicitly do not.

The paper makes explicit how this is dealt with:

> For the purposes of defining the halting problem H, one should specify whether it officially counts as halting or not if the head should happen to fall off the left edge of the tape. Although the truth of the main theorem will not depend on these details, provided we adopt a uniform answer, let us be definite and regard such computations as having not officially halted, as the halt state was not reached.

Reply on news.ycombinator.com