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.
However, for purposes of computability theory and algorithmic information theory, such an existence statement is useless.
That is my point—stating that a function that maps a finite domain onto {0,1} is computable is trivially true and (as you said) useless. I was not really trying to be extra Platonist; I was just trying to point out that these sorts of finite mapping functions are not really interesting from a computability theory standpoint.
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.
If you can formalize how you will discover such theories (i.e. how the learning our way up the ordinal hierarchy part will work), I’ll be interested in seeing what you come up with.
If you can formalize how you will discover such theories (i.e. how the learning our way up the ordinal hierarchy part will work), I’ll be interested in seeing what you come up with.
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?
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.
That is my point—stating that a function that maps a finite domain onto {0,1} is computable is trivially true and (as you said) useless. I was not really trying to be extra Platonist; I was just trying to point out that these sorts of finite mapping functions are not really interesting from a computability theory standpoint.
If you can formalize how you will discover such theories (i.e. how the learning our way up the ordinal hierarchy part will work), I’ll be interested in seeing what you come up with.
That’s the tough bit.