It doesn't have to form the table; a Turing machine of a length on the order of 2^n can have the answer to the question "does this Turing machine halt" built-in (hard coded) for all 2^n Turing machines of length n or smaller. Such a Turing machine exists for any value of n, but finding this Turing machine is not possible for an arbitrary value of n. Functions on a finite domain are essentially all Turing computable, so the fact that a Turing machine exists that can solve the halting problem for all Turing machines of length n or less is not surprising.

Oh, you mean classical existence. Yes, it is classically trivial that there exists some Turing machine blah blah blah, simply by the fact that classically, a Turing machine must either halt in finite time or never halt. However, for purposes of computability theory and algorithmic information theory, such an existence statement is useless.

My apologies, but are you making the statement just to be extra platonist about these things?

My point is that the fact that a theory exists that can solve some size n of halting problem is trivially true (if by theory you mean more-less the same thing as Turing machine) but this fact is also useless, since there is no way to discover that theory (Turing machine) for an arbitrary value of n.

And I am speaking in a constructive sense of existence, intending to say that we can in fact discover such theories: by learning our way up the ordinal hierarchy, so to speak.