[liadmat]

The halting problem also makes an assumption on the program's size. In practice we probably only care about programs under, say, a billion petabytes (or any other finite limit you can think of). In theory you can have a Turing machine that solves this regardless of the program's structure.

[schoen]

If you mean "programs that can only use a billion petabytes of storage", then that's true, but if you mean "programs whose code is less than a billion petabytes long", it's not true. (Someone recently calculated a result that I think can be interpreted directly as an actual decidability bound, and it's dramatically shorter than that.)

[liadmat]

I meant that there exists a TM which solves HP for programs smaller than a given size. This makes it computable. Now, just because we can prove the existence of a TM, doesn't mean we can find it. It's true that for programs which use a finite amount of storage we can actually describe the algorithm for the TM, but that's not what I meant.

[schoen]

This seems to be a weird issue conceptually:

http://mathoverflow.net/a/153106

Because of the list of correct answers for a finite subset of the Halting Problem is finite, the Turing machine you mention does exist, but we not only can't find it, we can't know when we've found it!

Where the Math Overflow post mentions that "experts could compute the particular value of n", there has recently been such a bound published in a thesis, such that we can be confident that we can never construct or recognize the solutions beyond that point (using a particular axiomatization of mathematics).

You referred to the idea that "you can have a Turing machine that solves this", and we can agree on that with the caveat that, above certain problem instance sizes, you can't know or verify in any way that you have such a Turing machine!