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.