Bad oracles in higher computability and randomness (Q2022778)

A central idea in computability theory and related areas such as complexity theory is that of \textit{relativisations}. By this we mean that instead of just carrying out an algorithm on some type of computer, we can additionally give the computer access to a black box (a so-called \textit{oracle}) where it may look up information that would normally be beyond the scope of its own computation. In other words, in computability theory, the oracle is typically some non-computable binary sequence, while in complexity theory it is often a sequence of time or space complexity that exceeds the resources allocated to the algorithm in question. One question that then arises frequently is whether mathematical proofs of certain results or constructions of certain objects which work without the presence of oracles still work analogously when oracles are present. Maybe, the most famous negative result of this type is the result in complexity theory that the well-known complexity classes P and NP are equal relative to some oracles and different relative to others. In the field of computability theory and its subfield of algorithmic randomness, many results do relativise, for example the same construction that gives a universal Martin-Löf test will also give a Martin-Löf test that is universal relative to \textit{any} oracle. The present article deals with the setting of \textit{higher} computability theory, that is, very informally speaking, with a version of computability theory where algorithmic processes' runtimes may be infinite computable ordinal numbers. The theory of algorithmic randomness has been lifted to this level by a number of authors, such as \textit{G. Hjorth} and \textit{A. Nies} [J. Lond. Math. Soc., II. Ser. 75, No. 2, 495--508 (2007; Zbl 1118.03034)], \textit{C. T. Chong} and \textit{L. Yu} [J. Symb. Log. 80, No. 4, 1131--1148 (2015; Zbl 1386.03046)] and by the authors of the present article in earlier work [J. Math. Log. 17, No. 1, Article ID 1750004, 53 p. (2017; Zbl 1420.03100)]. In the present article, they add to their previous work by studying in particular the role of relativisation. They show that in the higher computability setting, the situation is much more complex than in standard computability theory: relativising does not work for all oracles; some oracles are ``bad''. For example, the authors show that there exist oracles relative to which no universal higher Martin-Löf test can exist. Such an oracle can even be higher \(\Delta^0_2\). Even the notion of reducibility between two sequences becomes subtle at the higher setting, as there it becomes necessary to distinguish between reductions that are consistent everywhere (that is, they map any two inputs that are extensions of each other to outputs that are extensions of each other) and reductions that are only required to be consistent for a fixed oracle. To illustrate this, the authors construct an oracle that higher computes a sequence but that cannot do so via an everywhere consistent reduction. Such an oracle can even be higher Martin-Löf random. The constructions use the new technique of \textit{threesh-bones}. On the other hand, the authors show that for every oracle \(A\) one can uniformly find a sequence that is higher \(A\)-left-c.e.\ and higher \(A\)-Martin-Löf random. They also show that there are no higher self-PA oracles, where a sequence \(A\) is called \textit{higher self-PA} if every nonempty higher \(A\)-co-c.e.\ closed subset of Cantor space contains a higher \(A\)-computable sequence.