Journal of Symbolic Logic · 2009 · 16 citations · 4 references
Natural SciencesComputer ScienceMathematicsAlgorithmsDiscrete MathematicsSet TheoryBoolean AlgebraCoding TheoryComputability TheoryDensityTruth-functional LogicTuring DegreesUndecidability
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.
4
Generic-case complexity, decision problems in group theory, and random walks
Ilya Kapovich, Alexei Myasnikov, Paul E. Schupp et al. · Journal of Algebra · 2003 · 189 citations
Generic complexity of undecidable problems
Alexei Myasnikov, Alexander Rybalov · Journal of Symbolic Logic · 2008 · 36 citations
Carl G. Jockusch · Mathematical logic quarterly · 1969 · 32 citations