Infinite time recognizability from generic oracles and the recognizable jump operator

Infinite time recognizability from generic oracles and the recognizable jump operator

No Thumbnail Available

##### Files

There are no files associated with this item.

##### Date

2017

##### Authors

##### Editors

##### Journal ISSN

##### Electronic ISSN

##### ISBN

##### Bibliographical data

##### Publisher

##### Series

##### DOI (citable link)

##### International patent number

##### Link to the license

oops

##### EU project number

##### Project

##### Open Access publication

##### Collections

##### Title in another language

##### Publication type

Journal article

##### Publication status

Published

##### Published in

Computability ; 6 (2017), 3. - pp. 223-247. - ISSN 2211-3568. - eISSN 2211-3576

##### Abstract

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 non-meagerness instead of positive Lebesgue measure, have been shown to carry over to many models of transfinite computations in: Notre Dame Journal of Formal Logic , to appear, arXiv:1307.0160 [math.LO]. Here, we start exploring another analogue concerning recognizability rather than computability. For a notion of relativized recognizability (introduced in: Annals of Pure and Applied Logic 165 (9) (2014), 1353–1532, for ITRMs and generalized here to various other machine types), we show that, for Infinite Time Turing Machines (ITTMs), if a real x is recognizable relative to all elements of a non-meager 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 work in: Evolving Computability: 11th Conference on Computability in Europe , 2015, pp. 137–145, where we obtained the (unrelativized) result for ITRMs. We then introduce a jump operator for recognizability, examine its set-theoretical content and show that the recognizable jumps for ITRMs and ITTMs are primitive-recursively 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.

##### Summary in another language

##### Subject (DDC)

510 Mathematics

##### Keywords

Infinite Time Turing Machine, ordinal computability, recognizability, genericity, jump operator

##### Conference

##### Review

undefined / . - undefined, undefined. - (undefined; undefined)

##### Cite This

## ISO 690

CARL, Merlin, 2017.*Infinite time recognizability from generic oracles and the recognizable jump operator*. In: Computability.

**6**(3), pp. 223-247. ISSN 2211-3568. eISSN 2211-3576. Available under: doi: 10.3233/COM-160061

## BibTex

@article{Carl2017-08-07Infin-41224, year={2017}, doi={10.3233/COM-160061}, title={Infinite time recognizability from generic oracles and the recognizable jump operator}, number={3}, volume={6}, issn={2211-3568}, journal={Computability}, pages={223--247}, author={Carl, Merlin} }

## RDF

<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/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.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.uni-konstanz.de/server/rdf/resource/123456789/41224"> <dcterms:title>Infinite time recognizability from generic oracles and the recognizable jump operator</dcterms:title> <dc:contributor>Carl, Merlin</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/> <dcterms:issued>2017-08-07</dcterms:issued> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-02-05T13:39:30Z</dcterms:available> <dc:language>eng</dc:language> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-02-05T13:39:30Z</dc:date> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/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 non-meagerness instead of positive Lebesgue measure, have been shown to carry over to many models of transfinite computations in: Notre Dame Journal of Formal Logic , to appear, arXiv:1307.0160 [math.LO]. Here, we start exploring another analogue concerning recognizability rather than computability. For a notion of relativized recognizability (introduced in: Annals of Pure and Applied Logic 165 (9) (2014), 1353–1532, for ITRMs and generalized here to various other machine types), we show that, for Infinite Time Turing Machines (ITTMs), if a real x is recognizable relative to all elements of a non-meager 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 work in: Evolving Computability: 11th Conference on Computability in Europe , 2015, pp. 137–145, where we obtained the (unrelativized) result for ITRMs. We then introduce a jump operator for recognizability, examine its set-theoretical content and show that the recognizable jumps for ITRMs and ITTMs are primitive-recursively 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> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/41224"/> </rdf:Description> </rdf:RDF>

##### Internal note

##### xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

##### Examination date of dissertation

##### Method of financing

##### Comment on publication

##### Alliance license

##### Corresponding Authors der Uni Konstanz vorhanden

##### International Co-Authors

##### Bibliography of Konstanz

Yes