Cover Image
QR Code

FROM BI-IMMUNITY TO ABSOLUTE UNDECIDABILITY.

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 unde...

Full description

Published in:Journal of Symbolic Logic Vol. 78; no. 4; pp. 1218 - 1229
Main Authors: BIENVENU, LAURENT, DAY, ADAM R., HÖLZL, RUPERT
Format: Article
Published: Cambridge University Press Dec2013
Subjects:
Algebraic immunity
Algebraic attacks (Cryptography)
Boolean algebra
Turing (Computer program language)
Turing test
Online Access:View this record in EBSCOhost
fields @attributes:
  recordID: 1
pdfLink:
plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=93735892&site=ehost-live
header:
  @attributes:
    shortDbName: hlh
    uiTerm: 93735892
    longDbName: Humanities International Complete
    uiTag: AN
  controlInfo:
    bkinfo:
    jinfo:
      jid:
        00224812
        3TY
      jtl: Journal of Symbolic Logic
      issn: 00224812
      maglogo: N
    pubinfo:
      dt: Dec2013
      vid: 78
      iid: 4
      pid: 15979
      pub: Cambridge University Press
    artinfo:
      ui:
        93735892
        10.2178/jsl.7804120
      ppf: 1218
      ppct: 11
      formats:
      tig:
        atl: FROM BI-IMMUNITY TO ABSOLUTE UNDECIDABILITY.
      aug:
        au:
          BIENVENU, LAURENT
          DAY, ADAM R.
          HÖLZL, RUPERT
        affil:
          UNIVERSITÉ PARIS, 7 DENIS DIDEROT, CASE 7014. 75205 PARIS CEDEX 13, FRANCE
          DEPARTMENT OF MATHEMATICS, UNIVERSITY OF CALIFORNIA, BERKELEY, 970 EVANS HALL, BERKELEY, CA 94720-3840, USA
          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
      su:
        Algebraic immunity
        Algebraic attacks (Cryptography)
        Boolean algebra
        Turing (Computer program language)
        Turing test
      sug:
        subj:
          Algebraic immunity
          Algebraic attacks (Cryptography)
          Boolean algebra
          Turing (Computer program language)
          Turing test
      ab: 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.
      pubtype: Academic Journal
      doctype: Article
      src: R
    language: English
    refInfo:
    copyright:
      @attributes:
        flag: Y
      dt:
        @attributes:
          year: 2013
    holdings:
      @attributes:
        islocal: N