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)

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

thelopa

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.

l33t233372

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

fooker

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.

howling

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