Comment by rstuart4133 | Hacker News Reader

Comment by rstuart4133 | Hacker News Reader

Parent Full thread

Actually, it's possible to determine if any machine with a finite (bounded) number of states (ie, finite memory) halts given a finite (bounded) input. You just enumerate all the states. If for some input there is a sequence of states that loops without consuming input, it's infinite, otherwise not.

In practice it may not there may not be enough resources to build something to enumerate all the states on all inputs, but we are talking theoretically here. Theoretically, there is no halting problem in a finite world. And we humans live in what looks to be a locally finite world, so it doesn't apply to us.

The halting problem is actually a statement on whether it's possible to always determine if a finite set of rules that have infinite memory will halt on all inputs. The answer is famously no. Thus the halting problem illustrates a property of infinities. It's a subtlety that's rarely mentioned.

It is an interesting property. One thing it says to me is there are things in an infinite world a finite computation machine (like our human brains) will never be able to understand. While locally (say within the Milky Way) we live in a finite world the Universe itself may well be infinite. Ergo, there may be some aspects of the Universe we can never understand, and some things may happen that we can never predict.

It’s not so simple, even finite halting code has to handle the self recursion reversal trick somehow. Aka the finite bounds must exclude the “if H(X,I) loop forever; else halt” code because H would still be broken.

You could try defining H to only work on input machines smaller than itself. However there’s still problems.

If you don’t limit input size (aka the I in H(M,I) does machine M halt on input I), your code would still get tricked if M is just a tiny emulator and the input is the whole self defeating H program. So M and I both must be limited.

Anyway that’s not to say a finite H would work even if the input size is limited. You’d have to prove it’s impossible to self recurse - so you’d need good compression.

That’s all assuming self recursion is the only problem with the halt programs. Maybe it’s not, and it seems difficult to rule out other problems and see how they’d affect finitely bound TMs.

I’m just spitballing here. For a while I was infatuated by the idea of snuffing out self recursion or otherwise somehow making a variant of halting programs possible. But self referential poison seems really, really tough to prove the non existence of.

Anyways, I’m of the attitude that the proof for halting problem undecidability is a dumb trick. I’m simply fine with a halting program that doesn’t work correctly in self referential cases. As above though, that just leaves the whole problem vague aka don’t know about other issues and there’s the problem of actually solving it anyways (aka solving all of mathematics at once).

Let's take the _complete_ program state (input, output, RAM, program counter, stack, registers, rand gen entropy source state, etc) and for every possible such state make a node in a graph. Then when we execute a given program for a given state, we get one edge to the next program state node. Then deciding if program halts or not is answering a question if graph has a node with no outgoing edges. It's also possible to build such graphs for programs that never halt. That's the basic idea behind TLA+.

So it's definitely possible to decide halt problem for a bounded computer (any physical computer), it's just not practical in most cases, e.g. amount of memory needed to store graph of all states be bigger than amount of matter in the universe, etc.

I don’t think that works for the self recursion trick. It’s a logical problem more than a representation problem. Even if you had a machine to decide halting status quickly, it’d be broken; representing computation as a graph can’t help.

The inputs to a halting decider TM is an infinite set (all TMs and all inputs to them) so that’s another reason why a finite graph can’t be represented. Even something like integer addition isn’t a finite graph if you enumerate all inputs

Self recursion is not solvable if assuming stack is unlimited, which is never a case in reality. Stack on real computers is usually limited to a fixed size (100-1000kb). Another way to look at it, take all possible bits on a real computer, so all of RAM, all of storage, etc and then iterate over all possible values of it, it will be 2^bits possible values, sure it's a large value but it's still bounded. So it's possible to iterate over all possible states of any program on bounded computer in a bounded time. Hence why it's possible to decide if any program halts on any real computer in bounded time.

Sure one can say input is coming from a network stream then what? For practical issues then we can limit input size to N bits ... For theoretical issues we can discuss if there is a difference between halting or waiting for more input :)

Reply on news.ycombinator.com