Type of Publication:  Preprint 
Publication status:  Published 
Author:  Carl, Merlin 
Year of publication:  2015 
ArXivID:  arXiv:1508.06493 
Summary: 
By a theorem of Sacks, if a real x is recursive relative to all elements of a set of positive Lebesgue measure, x is recursive. This statement, and the analogous statement for nonmeagerness instead of positive Lebesgue measure, have been shown to carry over to many models of transfinite computations. Here, we start exploring another analogue concerning recognizability rather than computability. We introduce a notion of relativized recognizability and show that, for Infinite Time Turing Machines (ITTMs), if a real x is recognizable relative to all elements of a nonmeager Borel set Y, then x is recognizable. We also show that a relativized version of this statement holds for Infinite Time Register Machines (ITRMs). This extends our earlier work where we obtained the (unrelativized) result for ITRMs. We then introduce a jump operator for recognizability, examine its settheoretical content and show that the recognizable jumps for ITRMs and ITTMs are primitiverecursively equivalent, even though these two models are otherwise of vastly different strength. Finally, we introduce degrees of recognizability by considering the transitive closure of relativized recognizability and connect it with the recognizable jump operator to obtain a solution to Post's problem for degrees of recognizability.

Subject (DDC):  510 Mathematics 
Keywords:  infinite time machines, infinitary computability, recognizability, algorithmic randomness 
Bibliography of Konstanz:  Yes 
Files  Size  Format  View 

There are no files associated with this item. 
CARL, Merlin, 2015. Infinite Time Recognizability from Random Oracles and the Recognizable Jump Operator
@unpublished{Carl2015Infin32672, title={Infinite Time Recognizability from Random Oracles and the Recognizable Jump Operator}, year={2015}, author={Carl, Merlin} }
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22rdfsyntaxns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digitalrepositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.unikonstanz.de/rdf/resource/123456789/32672"> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:title>Infinite Time Recognizability from Random Oracles and the Recognizable Jump Operator</dcterms:title> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20160121T13:23:08Z</dc:date> <dc:language>eng</dc:language> <dc:contributor>Carl, Merlin</dc:contributor> <dcterms:isPartOf rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/39"/> <dc:creator>Carl, Merlin</dc:creator> <dcterms:abstract xml:lang="eng">By a theorem of Sacks, if a real x is recursive relative to all elements of a set of positive Lebesgue measure, x is recursive. This statement, and the analogous statement for nonmeagerness instead of positive Lebesgue measure, have been shown to carry over to many models of transfinite computations. Here, we start exploring another analogue concerning recognizability rather than computability. We introduce a notion of relativized recognizability and show that, for Infinite Time Turing Machines (ITTMs), if a real x is recognizable relative to all elements of a nonmeager Borel set Y, then x is recognizable. We also show that a relativized version of this statement holds for Infinite Time Register Machines (ITRMs). This extends our earlier work where we obtained the (unrelativized) result for ITRMs. We then introduce a jump operator for recognizability, examine its settheoretical content and show that the recognizable jumps for ITRMs and ITTMs are primitiverecursively equivalent, even though these two models are otherwise of vastly different strength. Finally, we introduce degrees of recognizability by considering the transitive closure of relativized recognizability and connect it with the recognizable jump operator to obtain a solution to Post's problem for degrees of recognizability.</dcterms:abstract> <dcterms:issued>2015</dcterms:issued> <dspace:isPartOfCollection rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/39"/> <bibo:uri rdf:resource="https://kops.unikonstanz.de/handle/123456789/32672"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20160121T13:23:08Z</dcterms:available> </rdf:Description> </rdf:RDF>