From Bi-Immunity to Absolute Undecidability

Laurent Bienvenu, Adam R. Day, Rupert Hölzl

Journal of Symbolic Logic · 2009 · 16 citations · 4 references

DOIFull text

Open access

Concepts

Abstract

Abstract 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. Downey, Jockusch and Schupp [2] 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.

References

4