From bi-immunity to absolute undecidability. (English) Zbl 1349.03044

Summary: An infinite binary sequence \(A\) is absolutely undecidable if it is impossible to compute \(A\) on a set of positions of positive upper density. Absolute undecidability is a weakening of bi-immunity. R. G. Downey et al. [J. Math. Log. 13, No. 2, Article ID 1350005, 43 p. (2013; Zbl 1326.03048)] asked whether, unlike the case for bi-immunity, there is an absolutely undecidable set in every non-zero Turing degree. We provide a positive answer to this question by applying techniques from coding theory. We show how to use Walsh–Hadamard codes to build a truth-table functional which maps any sequence \(A\) to a sequence \(B\), such that given any restriction of \(B\) to a set of positive upper density, one can recover \(A\). This implies that if \(A\) is non-computable, then \(B\) is absolutely undecidable. Using a forcing construction, we show that this result cannot be strengthened in any significant fashion.


03D28 Other Turing degree structures
03D35 Undecidability and degrees of sets of sentences


Zbl 1326.03048
Full Text: DOI arXiv Euclid