Infinite computations with random oracles

Loading...
Thumbnail Image
Date
2013
Authors
Schlicht, Philipp
Editors
Contact
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
URI (citable link)
DOI (citable link)
ArXiv-ID
International patent number
Link to the license
EU project number
Project
Open Access publication
Restricted until
Title in another language
Research Projects
Organizational Units
Journal Issue
Publication type
Working Paper/Technical Report
Publication status
Published in
Abstract
We consider the following problem for various infinite time machines. If a real is computable relative to large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable?
We show that the answer is independent from $ZFC$ for ordinal time machines ($OTM$s) with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite time Turing machines ($ITTM$s), unresetting and resetting infinite time register machines ($wITRM$s, $ITRM$s), and $\alpha$-Turing machines ($\alpha$-$TM$s) for countable admissible ordinals $\alpha$.
Summary in another language
Subject (DDC)
510 Mathematics
Keywords
Conference
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690CARL, Merlin, Philipp SCHLICHT, 2013. Infinite computations with random oracles
BibTex
@techreport{Carl2013Infin-25589,
  year={2013},
  title={Infinite computations with random oracles},
  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/25589">
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/25589/2/Carl_255983.pdf"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Schlicht, Philipp</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/25589/2/Carl_255983.pdf"/>
    <dcterms:title>Infinite computations with random oracles</dcterms:title>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/25589"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:abstract xml:lang="eng">We consider the following problem for various infinite time machines. If a real is computable relative to large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable?&lt;br /&gt;We show that the answer is independent from $ZFC$ for ordinal time machines ($OTM$s) with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite time Turing machines ($ITTM$s), unresetting and resetting infinite time register machines ($wITRM$s, $ITRM$s), and $\alpha$-Turing machines ($\alpha$-$TM$s) for countable admissible ordinals $\alpha$.</dcterms:abstract>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:issued>2013</dcterms:issued>
    <dc:language>eng</dc:language>
    <dc:contributor>Schlicht, Philipp</dc:contributor>
    <dc:creator>Carl, Merlin</dc:creator>
    <dc:contributor>Carl, Merlin</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2014-01-13T14:17:33Z</dcterms:available>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2014-01-13T14:17:33Z</dc:date>
  </rdf:Description>
</rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Contact
URL of original publication
Test date of URL
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
Refereed

Version History

Now showing 1 - 1 of 1
VersionDateSummary
1*
2014-01-13 14:17:33
* Selected version