×

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.

MSC:

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

Citations:

Zbl 1326.03048
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid