The halting problem is undecidable --- but can it be solved for most inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural fram
ework of optimal machines (considered in algorithmic information theory) using the notion of Kolmogorov complexity. We also consider some related questions about this framework and about asymptotic properties of the halting problem. In particular, we show that the fraction of terminating programs cannot have a limit, and all limit points are Martin-Lof random reals. We then consider mass problems of finding an approximate solution of halting problem and probabilistic algorithms for them, proving both positive and negative results. We consider the fraction of terminating programs that require a long time for termination, and describe this fraction using the busy beaver function. We also consider approxima
We investigate the role of continuous reductions and continuous relativisation in the context of higher randomness. We define a higher analogue of Turing reducibility and show that it interacts well with higher randomness, for example with respect to
van-Lambalgens theorem and the Miller-Yu / Levin theorem. We study lowness for continuous relativization of randomness, and show the equivalence of the higher analogues of the different characterisations of lowness for Martin-Lof randomness. We also characterise computing higher $K$-trivial sets by higher random sequences. We give a separation between higher notions of randomness, in particular between higher weak-2-randomness and $Pi^1_1$-randomness. To do so we investigate classes of functions computable from Kleenes~$O$ based on strong forms of the higher limit lemma.
A set C of reals is said to be negligible if there is no probabilistic algorithm which generates a member of C with positive probability. Various classes have been proven to be negligible, for example the Turing upper-cone of a non-computable real, t
he class of coherent completions of Peano Arithmetic or the class of reals of minimal degrees. One class of particular interest in the study of negligibility is the class of diagonally non-computable (DNC) functions, proven by Kucera to be non-negligible in a strong sense: every Martin-Lof random real computes a DNC function. Ambos-Spies et al. showed that the converse does not hold: there are DNC functions which compute no Martin-Lof random real. In this paper, we show that such the set of such DNC functions is in fact non-negligible. More precisely, we prove that for every sufficiently fast-growing computable~$h$, every 2-random real computes an $h$-bounded DNC function which computes no Martin-Lof random real. Further, we show that the same holds for the set of reals which compute a DNC function but no bounded DNC function. The proofs of these results use a combination of a technique due to Kautz (which, following a metaphor of Shen, we like to call a `fireworks argument) and bushy tree forcing, which is the canonical forcing notion used in the study of DNC functions.
We use the framework of reverse mathematics to address the question of, given a mathematical problem, whether or not it is easier to find an infinite partial solution than it is to find a complete solution. Following Flood, we say that a Ramsey-type
variant of a problem is the problem with the same instances but whose solutions are the infinite partial solutions to the original problem. We study Ramsey-type variants of problems related to Konigs lemma, such as restrictions of Konigs lemma, Boolean satisfiability problems, and graph coloring problems. We find that sometimes the Ramsey-type variant of a problem is strictly easier than the original problem (as Flood showed with weak Konigs lemma) and that sometimes the Ramsey-type variant of a problem is equivalent to the original problem. We show that the Ramsey-type variant of weak Konigs lemma is robust in the sense of Montalban: it is equivalent to several perturbations of itself. We also clarify the relationship between Ramsey-type weak Konigs lemma and algorithmic randomness by showing that Ramsey-type weak weak Konigs lemma is equivalent to the problem of finding diagonally non-recursive functions and that these problems are strictly easier than Ramsey-type weak Konigs lemma. This answers a question of Flood.
The paper considers quantitati
