Hacker News new | ask | show | jobs
by dmytroi 1111 days ago
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.
1 comments
srcreigh 1109 days ago
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

link
dmytroi 1108 days ago
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 :)

link