On the non-existence of maximal inference degrees for language identification (Q685478): Difference between revisions

The authors prove that for every oracle \(A\) there is an oracle \(B\) and a language \(L\) which can be inferred by an inductive inference machine with oracle \(A\), but which cannot be inferred by any inductive inference machine with oracle \(B\). This holds for inference from text, and both for the EX- and the BC-criterion. The proof is based on the fact that the inferable languages are in a very strong sense not closed under union: There exist two disjoint inferable languages whose union is not inferable by any oracle machine.