# Significance of the Halting problem on non-finite inputs

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.

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?
• @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.) – Noah Schweber Sep 7 '19 at 3:00