1
$\begingroup$

Suppose we have a finite set of programs, say, something like every Turing machine with 2 states and 7 symbols. After running all of them for a very long time, we've narrowed it down to a small subset thereof. Of those remaining, let's suppose that at least one will run forever and at least one will eventually halt, and that they fall into that category where it is impossible to tell which without running them for arbitrarily many more steps.

As I understand it, if we're determined enough and ignore physical considerations of time and memory, we'll theoretically reach the halting points for all those which are going to halt, although we'll never know that for sure. But before we reach that point, e.g., one step before the longest-running program halts, it will be obvious that that program is about to halt; we'll be able to look at its current symbol, state, and transform table, and it will be clear what's next.

Arguably, that's effectively computing that final step. But in reality, I have a very hard time imagining a scenario in which it isn't obvious that it's winding down 2, 3, or many steps earlier. In particular, if it's one of those recursion-based algorithms typical of BB-champions, or something like a Collatz sequence, various indicators that had been growing and growing for much of its run will suddenly be shrinking, or otherwise changing behavior.

There must be a limit to how far out such behavior can be detectable, or the halting problem wouldn't exist. On the other hand, it seems likely to me that there's probably also an upper bound on how obfuscated its behavior can be, or more concretely, how many steps out from a halt we could theoretically determine it will halt, without needing to directly compute all the remaining steps.

My question is whether this seems correct, and if so, whether anybody's figured out results along these lines already.

$\endgroup$
5
  • 3
    $\begingroup$ I suspect that it will be challenging to turn this into a well-defined question, because you haven't defined "obviously", and important details are being swept under the rug into the ambiguity of what "obviously" means. $\endgroup$
    – D.W.
    Commented Dec 22, 2023 at 6:26
  • 2
    $\begingroup$ An example of "obvious" behavior: en.wikipedia.org/wiki/Borwein_integral $\endgroup$ Commented Dec 22, 2023 at 6:54
  • $\begingroup$ @D.W. I don't disagree, but I would clarify that rather than "obvious", I suppose I really mean "theoretically detectable". Before running any code, it is impossible in general to identify all halting programs; by running them, eventually you can identify all halting programs as such; therefore, at some point, for each program, it must change from non-identifiable to identifiable as eventually-halting. (Except yes, I suppose you could simply say that all halting programs are "identifiable" in that sense from the start, in that they can be run until they halt.) $\endgroup$
    – Trev
    Commented Dec 22, 2023 at 7:57
  • $\begingroup$ "There must be a limit to how far out such behavior can be detectable" At the very least, you'd need a TM with more states than the machine you are deciding the halting problem for. Similar to how you need a stronger theory to determine if the (weaker) theory is consistent. $\endgroup$
    – rus9384
    Commented Dec 22, 2023 at 9:09
  • $\begingroup$ Well of course it is detectable whether it will halt in the next 10 steps: you can just simulate further execution for 10 steps. You seem to want some definition that excludes that strategy, but still allows other strategies, and I'm saying that it is not clear how to do that -- it is not clear that "wish" is well-defined or meaningful. $\endgroup$
    – D.W.
    Commented Dec 24, 2023 at 22:34

1 Answer 1

4
$\begingroup$

What you are describing is indistinguishable from:

  1. making a (free) copy of the Turing machine (in its current state)
  2. running it for $n$ steps
  3. seeing if it halted.

I fail to see how this gives you any new capabilities. An analogy to your logic would be: "I can determine, what's gonna happen 10 minutes into the future, if I just wait 10 minutes.".

So to answer your question in the header: You can determine, if your Turing machine is halting $n$ steps ahead, by running $n$ computations ahead on a copy of it.

Predicting the halting problem is only "obvious" for obvious cases, but can be incomprehensibly hard in other cases (see this answer).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.