[srcreigh]

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

[dmytroi]

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 :)