The Recognizability Strength of Infinite Time Turing Machines with Ordinal Parameters

Carl, Merlin; Schlicht, Philipp

The Recognizability Strength of Infinite Time Turing Machines with Ordinal Parameters

Files

There are no files associated with this item.

Date

2017

Authors

Carl, Merlin

Schlicht, Philipp

DOI (citable link)

10.1007/978-3-319-58741-7_20

Collections

Mathematik und Statistik

Publication type

Contribution to a conference collection

Publication status

Published

Published in

Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, proceedings / Kari, Jarkko et al. (ed.). - Cham : Springer, 2017. - (Lecture Notes in Computer Science ; 10307). - pp. 198-209. - ISSN 0302-9743. - eISSN 1611-3349. - ISBN 978-3-319-58740-0

Abstract

We study infinite time Turing machines that attain a special state at a given class of ordinals during the computation. We prove results about sets that can be recognized by these machines. For instance, the recognizable sets of natural numbers with respect to the cardinal-detecting infinite time Turing machines introduced in [Hab13] are contained in a countable level of the constructible hierarchy, and the recognizable sets of natural numbers with respect to finitely many ordinal parameters are constructible.

Subject (DDC)

510 Mathematics

Conference

13th Conference on Computability in Europe, CiE 2017, Jun 12, 2017 - Jun 16, 2017, Turku, Finland

Cite This

ISO 690

CARL, Merlin, Philipp SCHLICHT, 2017. The Recognizability Strength of Infinite Time Turing Machines with Ordinal Parameters. 13th Conference on Computability in Europe, CiE 2017. Turku, Finland, Jun 12, 2017 - Jun 16, 2017. In: KARI, Jarkko, ed. and others. Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, proceedings. Cham:Springer, pp. 198-209. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-58740-0. Available under: doi: 10.1007/978-3-319-58741-7_20

BibTex

@inproceedings{Carl2017-05-12Recog-43665,
  year={2017},
  doi={10.1007/978-3-319-58741-7_20},
  title={The Recognizability Strength of Infinite Time Turing Machines with Ordinal Parameters},
  number={10307},
  isbn={978-3-319-58740-0},
  issn={0302-9743},
  publisher={Springer},
  address={Cham},
  series={Lecture Notes in Computer Science},
  booktitle={Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, proceedings},
  pages={198--209},
  editor={Kari, Jarkko},
  author={Carl, Merlin and Schlicht, Philipp}
}

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/43665">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:issued>2017-05-12</dcterms:issued>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/43665"/>
    <dc:creator>Schlicht, Philipp</dc:creator>
    <dc:creator>Carl, Merlin</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-11-06T09:24:15Z</dcterms:available>
    <dc:contributor>Schlicht, Philipp</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:abstract xml:lang="eng">We study infinite time Turing machines that attain a special state at a given class of ordinals during the computation. We prove results about sets that can be recognized by these machines. For instance, the recognizable sets of natural numbers with respect to the cardinal-detecting infinite time Turing machines introduced in [Hab13] are contained in a countable level of the constructible hierarchy, and the recognizable sets of natural numbers with respect to finitely many ordinal parameters are constructible.</dcterms:abstract>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dc:language>eng</dc:language>
    <dc:contributor>Carl, Merlin</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-11-06T09:24:15Z</dc:date>
    <dcterms:title>The Recognizability Strength of Infinite Time Turing Machines with Ordinal Parameters</dcterms:title>
  </rdf:Description>
</rdf:RDF>

Bibliography of Konstanz

Yes