The basic theory of infinite time register machines

Cite This

Files in this item

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. 249-273. ISSN 0933-5846. eISSN 1432-0665. Available under: doi: 10.1007/s00153-009-0167-x

@article{Carl2010-03basic-41223, title={The basic theory of infinite time register machines}, year={2010}, doi={10.1007/s00153-009-0167-x}, number={2}, volume={49}, issn={0933-5846}, journal={Archive for Mathematical Logic}, pages={249--273}, author={Carl, Merlin and Fischbach, Tim and Koepke, Peter and Miller, Russell and Nasfi, Miriam and Weckbecker, Gregor} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dc:contributor>Koepke, Peter</dc:contributor> <dc:creator>Miller, Russell</dc:creator> <dcterms:issued>2010-03</dcterms:issued> <dc:creator>Carl, Merlin</dc:creator> <dcterms:isPartOf rdf:resource=""/> <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="">2018-02-05T13:36:14Z</dcterms:available> <dspace:isPartOfCollection rdf:resource=""/> <dc:contributor>Miller, Russell</dc:contributor> <bibo:uri rdf:resource=""/> <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 ITRM-clockable 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="">2018-02-05T13: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>

This item appears in the following Collection(s)

Search KOPS


My Account