1
$\begingroup$

The Halting problem is decidable on machines with finite memory. One can enumerate all the states and continually check for a repeated state, albeit being inefficient. (https://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls)

What I struggle to understand is the significance of machines with infinite memory. Why would it be necessary to model a computer having infinite memory? Any program that terminates must have finite memory.

I acknowledge that finding at which point to set the finite bar is a challenge, but I am not convinced that this task is impossible. For instance, for a program with a binary encoding of size $n$, set an upper limit of memory to $2^n$, which is sufficient to encode any possible information contained therein.

$\endgroup$
2
$\begingroup$

For instance, for a program with a binary encoding of size $n$, set an upper limit of memory to $2^n$, which is sufficient to encode any possible information contained therein.

Really? Consider the program which on input $n$ searches through $\mathbb{N}$ for $n$ distinct twin prime pairs, and halts as soon as it finds that many (and obviously runs without ever halting otherwise). Why does that memory bound work here?

The point is that we're considering unbounded searches, and even if an unbounded search halts we don't necessarily know ahead of time how long it will take. Attempts to impose a bound "right away" will lead to searches we care about yielding the wrong answer.

And beyond that, we're generally more interested in the behavior of a program in general than in any of its specific instances - with respect to the program above, we'd love to know if each of its instances halts, but no particular instance is very interesting.

$\endgroup$
  • $\begingroup$ So determining a search bound is impossible for a finite program. Does there exist some simple demonstration of this concept? Or related things I can read? It is highly non-intuitive to me. $\endgroup$ – user1318416 Sep 7 at 2:57
  • 1
    $\begingroup$ @user1318416 Consider the program which, on input $n$, runs the $n$th program until (if ever) it halts, at which point it halts too (and otherwise obviously doesn't halt). If we could bound the runtime of this program, we'd be able to solve the halting problem. (See also the busy beaver function, per Fabio Somenzi's comment.) $\endgroup$ – Noah Schweber Sep 7 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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