Hi, Jose Antonio and other AIT readers, and I hope that all are well.
I hope that I have understood what you seek and that my answer is relevant, correct and clear.
Let D be a data-set and P be a pattern.
If we are doing inference relative to a (Bayesian) choice of (universal) Turing machine - let's
call it U - then the answers to the question(s) will sometimes depend upon the choice of U.
There will be cases where we can prove that D does have pattern P.
There will be cases where we can prove that D does not have pattern P.
The halting problem (or Entscheidungsproblem) is undecidable (Turing, 1936). And, in turn,
there will be cases where (using UTM, U), for some D and P, we can't prove whether or not
D has pattern P.
There will also be cases of D where we can't decide whether or not D has any pattern (i.e.,
for all patterns P', we can't prove that D has pattern P'; and for at least one pattern P'', we
can't prove that D does not have pattern P'').
To see this described formally, then, as above, I first mention Turing (1936).
More recently than (Turing, 1936), with a view to data-sets and inferences (or
patterns), I would refer you to
paper) to sec. 4, p275, col. 1, C6 and the non-computability of K_T (S).
I hope that I have understood what you seek and that my answer above is relevant,
correct and sufficiently clear.
This all said (at least partly by way of theory), in practice, many data-sets have patterns
and we can often do many useful things with a pattern in a data-set even if we possibly
don't have the best possible pattern.
As a simple case in point, Einsteinian special relativity currently appears to be a better
theory than Newtonian mechanics but we can still do many useful things with Newtonian
mechanics (and we can indeed see Newtonian mechanics as something of a small-speed
approximation to Einsteinian special relativity).
That's probably an okay time to stop.
In the rest of this e-mail, which you can safely ignore, we assume that determining
whether a pattern is in a dataset is decidable in general - and then see the resultant
paradox and contradiction.
For what it's worth, I'd now like to use our inference techniques to make an
uncomputable sequence. Put another way, we assume that determining whether a
pattern is in a dataset is decidable - and, in turn, that finding the best pattern in a
dataset is decidable (or determining whether or not a pattern is the best pattern in a
dataset is decidable) - and then see where this leads us. (As we shall see below, it
will lead us to a paradox and contradiction.) We start with a problem which can be
viewed as infinitely iterated matching pennies, or what has previously been called the
elusive model paradox. We have a matcher and a mismatcher, where the matcher is
like a tennis receiver or soccer goalie/goalkeeper trying to match where the server /
/ striker directs the ball; and the mismatcher is like a tennis server or soccer striker
trying to place the ball where the receiver / goalkeeper does not go.
Having set things up (as above), the argument continues as follows. After many iterations,
the mismatcher should be able to infer the matcher's algorithm (with very high probability)
and (vice versa) the matcher should be able to infer the mismatcher's algorithm (with very
high probability). In turn, the mismatcher can then make sure of a mismatch (with very
high probability) and the matcher can then make sure of a match (with very high probability).
This gives a paradox - and the resolution of the paradox is that the inference/s is/are (in
general) not computable.
Various people to have written on this - in one form or another - include M Scriven (1965),
D K Lewis and Jane Shelby Richardson (1966), A P Dawid (approx 1985), D L Dowe (2008,
2011),
I hope that all of this helps.
Keep well, cheers and best from David D