Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T03:34:15.098Z Has data issue: false hasContentIssue false

From Bi-Immunity to Absolute Undecidability

Published online by Cambridge University Press:  12 March 2014

Laurent Bienvenu
Affiliation:
Université Paris, 7 Denis Diderot, Case 7014, 75205 Paris Cedex 13, France, E-mail: laurent.bienvenu@liafa.univ-paris-diderot.fr
Adam R. Day
Affiliation:
Department of Mathematics, University of California, Berkeley, 970 Evans Hall, Berkeley, CA 94720-3840, USA, E-mail: adam.day@math.berkeley.edu
Rupert Hölzl
Affiliation:
Institut für Theoretische Informatik, Mathematik und Operations Research Fakultät für Informatik, Universität der Bundeswehr München, Werner-Heisenberg-Weg 39, 85577 Neubiberg, Germany, E-mail: r@hoelzl.fr

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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable