DIAGONALLY NON-COMPUTABLE FUNCTIONS AND BI-IMMUNITY CARL G. JOCKUSCH, JR. AND ANDREW E.M. LEWIS Abstract. We prove that every diagonally noncomputable function computes a set A which is bi-immune, meaning that neither A - Algorithmically random sequence - Document - PDFSEARCH.IO

First Page	Meta Content
	DIAGONALLY NON-COMPUTABLE FUNCTIONS AND BI-IMMUNITY CARL G. JOCKUSCH, JR. AND ANDREW E.M. LEWIS Abstract. We prove that every diagonally noncomputable function computes a set A which is bi-immune, meaning that neither A Add to Reading List Document Date: 2013-02-02 15:47:48 Open Document File Size: 321,71 KB Share Result on Facebook Facility Isaac Newton Institute / / Organization Isaac Newton Institute for the Mathematical Sciences / / Person CARL G. JOCKUSCH / JR. / ANDREW E.M. LEWIS / / Technology dom / / SocialTag Applied mathematics Computable function Turing reduction Reduction Algorithmically random sequence Function Computability theory Mathematics Computer science

DIAGONALLY NON-COMPUTABLE FUNCTIONS AND BI-IMMUNITY CARL G. JOCKUSCH, JR. AND ANDREW E.M. LEWIS Abstract. We prove that every diagonally noncomputable function computes a set A which is bi-immune, meaning that neither A Add to Reading List