Type of Publication:  Journal article 
Publication status:  Published 
Author:  Carl, Merlin; Fischbach, Tim; Koepke, Peter; Miller, Russell; Nasfi, Miriam; Weckbecker, Gregor 
Year of publication:  2010 
Published in:  Archive for Mathematical Logic ; 49 (2010), 2.  pp. 249273.  ISSN 09335846.  eISSN 14320665 
DOI (citable link):  https://dx.doi.org/10.1007/s001530090167x 
Summary: 
Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard registermachine commands.At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all 11 sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRMclockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not n ∈ r with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs.

Subject (DDC):  510 Mathematics 
Keywords:  Ordinal computability; Hypercomputation; Infinitary computation; Register machine 
Files  Size  Format  View 

There are no files associated with this item. 
CARL, Merlin, Tim FISCHBACH, Peter KOEPKE, Russell MILLER, Miriam NASFI, Gregor WECKBECKER, 2010. The basic theory of infinite time register machines. In: Archive for Mathematical Logic. 49(2), pp. 249273. ISSN 09335846. eISSN 14320665. Available under: doi: 10.1007/s001530090167x
@article{Carl201003basic41223, title={The basic theory of infinite time register machines}, year={2010}, doi={10.1007/s001530090167x}, number={2}, volume={49}, issn={09335846}, journal={Archive for Mathematical Logic}, pages={249273}, author={Carl, Merlin and Fischbach, Tim and Koepke, Peter and Miller, Russell and Nasfi, Miriam and Weckbecker, Gregor} }
<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/41223"> <dc:contributor>Koepke, Peter</dc:contributor> <dc:creator>Miller, Russell</dc:creator> <dcterms:issued>201003</dcterms:issued> <dc:creator>Carl, Merlin</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/39"/> <dc:creator>Fischbach, Tim</dc:creator> <dcterms:title>The basic theory of infinite time register machines</dcterms:title> <dc:creator>Nasfi, Miriam</dc:creator> <dc:language>eng</dc:language> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20180205T13:36:14Z</dcterms:available> <dspace:isPartOfCollection rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/39"/> <dc:contributor>Miller, Russell</dc:contributor> <bibo:uri rdf:resource="https://kops.unikonstanz.de/handle/123456789/41223"/> <dc:creator>Koepke, Peter</dc:creator> <dcterms:abstract xml:lang="eng">Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard registermachine commands.At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all 11 sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRMclockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not n ∈ r with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs.</dcterms:abstract> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20180205T13:36:14Z</dc:date> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:contributor>Carl, Merlin</dc:contributor> <dc:contributor>Nasfi, Miriam</dc:contributor> <dc:contributor>Weckbecker, Gregor</dc:contributor> <dc:contributor>Fischbach, Tim</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Weckbecker, Gregor</dc:creator> </rdf:Description> </rdf:RDF>