On reversible Turing machines and their function universality View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2016-08

AUTHORS

Holger Bock Axelsen, Robert Glück

ABSTRACT

We provide a treatment of the reversible Turing machines (RTMs) under a strict function semantics. Unlike many existing reversible computation models, we distinguish strictly between computing the function λx.f(x) and computing the function λx.(x,f(x)), or other injective embeddings of f. We reinterpret and adapt a number of important foundational reversible computing results under this semantics. Unifying the results in a single model shows that, as expected (and previously claimed), the RTMs are robust and can compute exactly all injective computable functions. Because injectivity entails that the RTMs are not strictly Turing-complete w.r.t. functions, we use an appropriate alternative universality definition, and show how to derive universal RTMs (URTMs) from existing irreversible universal machines. We then proceed to construct a URTM from the ground up. This resulting machine is the first URTM which does not depend on a reversible simulation of an existing universal machine. The new construction has the advantage that the interpretive overhead of the URTM is limited to a (program dependent) constant factor. Another novelty is that the URTM can function as an inverse interpreter at no asymptotic cost. More... »

PAGES

509-543

References to SciGraph publications

  • 1980. Reversible computing in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2007. A Universal Reversible Turing Machine in MACHINES, COMPUTATIONS, AND UNIVERSALITY
  • 2015. A Hierarchy of Fast Reversible Turing Machines in REVERSIBLE COMPUTATION
  • 1993. What Computing Is All About in NONE
  • 2011. A Simple and Efficient Universal Reversible Turing Machine in LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS
  • 2012. A Reversible Processor Architecture and Its Reversible Logic Design in REVERSIBLE COMPUTATION
  • 1996. A roadmap to metacomputation by supercompilation in PARTIAL EVALUATION
  • 2007. Reversible Machine Code and Its Abstract Processor Architecture in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 2010. Reversible Pushdown Automata in LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS
  • 2004. Derivation of Deterministic Inverse Programs Based on LR Parsing in FUNCTIONAL AND LOGIC PROGRAMMING
  • 2012. Time Complexity of Tape Reduction for Reversible Turing Machines in REVERSIBLE COMPUTATION
  • 2016. Reversible Shrinking Two-Pushdown Automata in LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS
  • 1993. An Introduction to Kolmogorov Complexity and Its Applications in NONE
  • 2011. What Do Reversible Programs Compute? in FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATIONAL STRUCTURES
  • 2013. One-Way Reversible Multi-head Finite Automata in REVERSIBLE COMPUTATION
  • 2015. Programming Techniques for Reversible Comparison Sorts in PROGRAMMING LANGUAGES AND SYSTEMS
  • 2003. A Program Inverter for a Functional Language with Equality and Constructors in PROGRAMMING LANGUAGES AND SYSTEMS
  • 2011. Clean Translation of an Imperative Reversible Programming Language in COMPILER CONSTRUCTION
  • 2004. An Algebraic Approach to Bi-directional Updating in PROGRAMMING LANGUAGES AND SYSTEMS
  • 2002. Principles of Inverse Computation and the Universal Resolving Algorithm in THE ESSENCE OF COMPUTATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00236-015-0253-y

    DOI

    http://dx.doi.org/10.1007/s00236-015-0253-y

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1043668207


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Copenhagen", 
              "id": "https://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Axelsen", 
            "givenName": "Holger Bock", 
            "id": "sg:person.015546427711.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015546427711.73"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Copenhagen", 
              "id": "https://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gl\u00fcck", 
            "givenName": "Robert", 
            "id": "sg:person.010754010217.31", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-29517-1_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000285532", 
              "https://doi.org/10.1007/978-3-642-29517-1_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-21254-3_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000989884", 
              "https://doi.org/10.1007/978-3-642-21254-3_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74593-8_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002680503", 
              "https://doi.org/10.1007/978-3-540-74593-8_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74593-8_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002680503", 
              "https://doi.org/10.1007/978-3-540-74593-8_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30477-7_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006188766", 
              "https://doi.org/10.1007/978-3-540-30477-7_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30477-7_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006188766", 
              "https://doi.org/10.1007/978-3-540-30477-7_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2015.07.046", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006378873"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1244381.1244404", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006492707"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-10003-2_104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006731052", 
              "https://doi.org/10.1007/3-540-10003-2_104"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-61580-6_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008923491", 
              "https://doi.org/10.1007/3-540-61580-6_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1515/9781400882618-009", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011817422"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2008.01.041", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012017670"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-40018-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012065324", 
              "https://doi.org/10.1007/978-3-540-40018-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-40018-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012065324", 
              "https://doi.org/10.1007/978-3-540-40018-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1012361330", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-3860-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012361330", 
              "https://doi.org/10.1007/978-1-4757-3860-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-3860-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012361330", 
              "https://doi.org/10.1007/978-1-4757-3860-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-13089-2_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014064203", 
              "https://doi.org/10.1007/978-3-642-13089-2_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-13089-2_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014064203", 
              "https://doi.org/10.1007/978-3-642-13089-2_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24754-8_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015138027", 
              "https://doi.org/10.1007/978-3-540-24754-8_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24754-8_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015138027", 
              "https://doi.org/10.1007/978-3-540-24754-8_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74510-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015349256", 
              "https://doi.org/10.1007/978-3-540-74510-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74510-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015349256", 
              "https://doi.org/10.1007/978-3-540-74510-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1366230.1366239", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018780610"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-36315-3_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019959784", 
              "https://doi.org/10.1007/978-3-642-36315-3_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-26529-2_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021275775", 
              "https://doi.org/10.1007/978-3-319-26529-2_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-2710-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024630189", 
              "https://doi.org/10.1007/978-1-4612-2710-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-2710-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024630189", 
              "https://doi.org/10.1007/978-1-4612-2710-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jlap.2009.02.006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028603771"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/777388.777391", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041853059"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-29517-1_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042081817", 
              "https://doi.org/10.1007/978-3-642-29517-1_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1232420.1232424", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047098083"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19805-2_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047299195", 
              "https://doi.org/10.1007/978-3-642-19805-2_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19805-2_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047299195", 
              "https://doi.org/10.1007/978-3-642-19805-2_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-20860-2_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048061754", 
              "https://doi.org/10.1007/978-3-319-20860-2_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19861-8_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048833860", 
              "https://doi.org/10.1007/978-3-642-19861-8_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-36377-7_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051401164", 
              "https://doi.org/10.1007/3-540-36377-7_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0129626409000171", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062907434"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/966049.777391", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063175618"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/rd.176.0525", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063180324"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/rd.53.0183", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063183065"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1364/on.11.2.000011", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1065242236"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-30000-9_44", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1084735782", 
              "https://doi.org/10.1007/978-3-319-30000-9_44"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2016-08", 
        "datePublishedReg": "2016-08-01", 
        "description": "We provide a treatment of the reversible Turing machines (RTMs) under a strict function semantics. Unlike many existing reversible computation models, we distinguish strictly between computing the function \u03bbx.f(x) and computing the function \u03bbx.(x,f(x)), or other injective embeddings of f. We reinterpret and adapt a number of important foundational reversible computing results under this semantics. Unifying the results in a single model shows that, as expected (and previously claimed), the RTMs are robust and can compute exactly all injective computable functions. Because injectivity entails that the RTMs are not strictly Turing-complete w.r.t. functions, we use an appropriate alternative universality definition, and show how to derive universal RTMs (URTMs) from existing irreversible universal machines. We then proceed to construct a URTM from the ground up. This resulting machine is the first URTM which does not depend on a reversible simulation of an existing universal machine. The new construction has the advantage that the interpretive overhead of the URTM is limited to a (program dependent) constant factor. Another novelty is that the URTM can function as an inverse interpreter at no asymptotic cost.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00236-015-0253-y", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1133515", 
            "issn": [
              "0001-5903", 
              "1432-0525"
            ], 
            "name": "Acta Informatica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "5", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "53"
          }
        ], 
        "name": "On reversible Turing machines and their function universality", 
        "pagination": "509-543", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "d001d88f0973036c4f7d691f87b4e3d239799d9906a41c7c80455190e88016d8"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00236-015-0253-y"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1043668207"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00236-015-0253-y", 
          "https://app.dimensions.ai/details/publication/pub.1043668207"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T23:17", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8693_00000482.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00236-015-0253-y"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00236-015-0253-y'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00236-015-0253-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00236-015-0253-y'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00236-015-0253-y'


     

    This table displays all metadata directly associated to this object as RDF triples.

    189 TRIPLES      21 PREDICATES      61 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00236-015-0253-y schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N6e29e00ec5134210a89097b5257952be
    4 schema:citation sg:pub.10.1007/3-540-10003-2_104
    5 sg:pub.10.1007/3-540-36377-7_13
    6 sg:pub.10.1007/3-540-61580-6_8
    7 sg:pub.10.1007/978-1-4612-2710-6
    8 sg:pub.10.1007/978-1-4757-3860-5
    9 sg:pub.10.1007/978-3-319-20860-2_2
    10 sg:pub.10.1007/978-3-319-26529-2_22
    11 sg:pub.10.1007/978-3-319-30000-9_44
    12 sg:pub.10.1007/978-3-540-24754-8_21
    13 sg:pub.10.1007/978-3-540-30477-7_2
    14 sg:pub.10.1007/978-3-540-40018-9_17
    15 sg:pub.10.1007/978-3-540-74510-5_9
    16 sg:pub.10.1007/978-3-540-74593-8_8
    17 sg:pub.10.1007/978-3-642-13089-2_31
    18 sg:pub.10.1007/978-3-642-19805-2_4
    19 sg:pub.10.1007/978-3-642-19861-8_9
    20 sg:pub.10.1007/978-3-642-21254-3_8
    21 sg:pub.10.1007/978-3-642-29517-1_1
    22 sg:pub.10.1007/978-3-642-29517-1_3
    23 sg:pub.10.1007/978-3-642-36315-3_2
    24 https://app.dimensions.ai/details/publication/pub.1012361330
    25 https://doi.org/10.1016/j.jlap.2009.02.006
    26 https://doi.org/10.1016/j.tcs.2008.01.041
    27 https://doi.org/10.1016/j.tcs.2015.07.046
    28 https://doi.org/10.1142/s0129626409000171
    29 https://doi.org/10.1145/1232420.1232424
    30 https://doi.org/10.1145/1244381.1244404
    31 https://doi.org/10.1145/1366230.1366239
    32 https://doi.org/10.1145/777388.777391
    33 https://doi.org/10.1145/966049.777391
    34 https://doi.org/10.1147/rd.176.0525
    35 https://doi.org/10.1147/rd.53.0183
    36 https://doi.org/10.1364/on.11.2.000011
    37 https://doi.org/10.1515/9781400882618-009
    38 schema:datePublished 2016-08
    39 schema:datePublishedReg 2016-08-01
    40 schema:description We provide a treatment of the reversible Turing machines (RTMs) under a strict function semantics. Unlike many existing reversible computation models, we distinguish strictly between computing the function λx.f(x) and computing the function λx.(x,f(x)), or other injective embeddings of f. We reinterpret and adapt a number of important foundational reversible computing results under this semantics. Unifying the results in a single model shows that, as expected (and previously claimed), the RTMs are robust and can compute exactly all injective computable functions. Because injectivity entails that the RTMs are not strictly Turing-complete w.r.t. functions, we use an appropriate alternative universality definition, and show how to derive universal RTMs (URTMs) from existing irreversible universal machines. We then proceed to construct a URTM from the ground up. This resulting machine is the first URTM which does not depend on a reversible simulation of an existing universal machine. The new construction has the advantage that the interpretive overhead of the URTM is limited to a (program dependent) constant factor. Another novelty is that the URTM can function as an inverse interpreter at no asymptotic cost.
    41 schema:genre research_article
    42 schema:inLanguage en
    43 schema:isAccessibleForFree false
    44 schema:isPartOf Nc16ca134b9274a5e82acc1c7ef90d63d
    45 Nfd2d4feb45b0430a8475afbd52276fd8
    46 sg:journal.1133515
    47 schema:name On reversible Turing machines and their function universality
    48 schema:pagination 509-543
    49 schema:productId N83f2756db6774bdda73c1a499158c7a6
    50 Nd1121c1cc2c04d01952967951a5bd194
    51 Ne8fa37794a4142ddbea089df57e5d26d
    52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043668207
    53 https://doi.org/10.1007/s00236-015-0253-y
    54 schema:sdDatePublished 2019-04-10T23:17
    55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    56 schema:sdPublisher N0a8ff37c863349a3999146496ec438bc
    57 schema:url http://link.springer.com/10.1007/s00236-015-0253-y
    58 sgo:license sg:explorer/license/
    59 sgo:sdDataset articles
    60 rdf:type schema:ScholarlyArticle
    61 N0a8ff37c863349a3999146496ec438bc schema:name Springer Nature - SN SciGraph project
    62 rdf:type schema:Organization
    63 N6e29e00ec5134210a89097b5257952be rdf:first sg:person.015546427711.73
    64 rdf:rest N8f68367222a946f3a89487e216c15988
    65 N83f2756db6774bdda73c1a499158c7a6 schema:name readcube_id
    66 schema:value d001d88f0973036c4f7d691f87b4e3d239799d9906a41c7c80455190e88016d8
    67 rdf:type schema:PropertyValue
    68 N8f68367222a946f3a89487e216c15988 rdf:first sg:person.010754010217.31
    69 rdf:rest rdf:nil
    70 Nc16ca134b9274a5e82acc1c7ef90d63d schema:issueNumber 5
    71 rdf:type schema:PublicationIssue
    72 Nd1121c1cc2c04d01952967951a5bd194 schema:name doi
    73 schema:value 10.1007/s00236-015-0253-y
    74 rdf:type schema:PropertyValue
    75 Ne8fa37794a4142ddbea089df57e5d26d schema:name dimensions_id
    76 schema:value pub.1043668207
    77 rdf:type schema:PropertyValue
    78 Nfd2d4feb45b0430a8475afbd52276fd8 schema:volumeNumber 53
    79 rdf:type schema:PublicationVolume
    80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Information and Computing Sciences
    82 rdf:type schema:DefinedTerm
    83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Computation Theory and Mathematics
    85 rdf:type schema:DefinedTerm
    86 sg:journal.1133515 schema:issn 0001-5903
    87 1432-0525
    88 schema:name Acta Informatica
    89 rdf:type schema:Periodical
    90 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    91 schema:familyName Glück
    92 schema:givenName Robert
    93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    94 rdf:type schema:Person
    95 sg:person.015546427711.73 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    96 schema:familyName Axelsen
    97 schema:givenName Holger Bock
    98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015546427711.73
    99 rdf:type schema:Person
    100 sg:pub.10.1007/3-540-10003-2_104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006731052
    101 https://doi.org/10.1007/3-540-10003-2_104
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/3-540-36377-7_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051401164
    104 https://doi.org/10.1007/3-540-36377-7_13
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/3-540-61580-6_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008923491
    107 https://doi.org/10.1007/3-540-61580-6_8
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/978-1-4612-2710-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024630189
    110 https://doi.org/10.1007/978-1-4612-2710-6
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/978-1-4757-3860-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012361330
    113 https://doi.org/10.1007/978-1-4757-3860-5
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/978-3-319-20860-2_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048061754
    116 https://doi.org/10.1007/978-3-319-20860-2_2
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-3-319-26529-2_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021275775
    119 https://doi.org/10.1007/978-3-319-26529-2_22
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-3-319-30000-9_44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084735782
    122 https://doi.org/10.1007/978-3-319-30000-9_44
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-3-540-24754-8_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015138027
    125 https://doi.org/10.1007/978-3-540-24754-8_21
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/978-3-540-30477-7_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006188766
    128 https://doi.org/10.1007/978-3-540-30477-7_2
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/978-3-540-40018-9_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012065324
    131 https://doi.org/10.1007/978-3-540-40018-9_17
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/978-3-540-74510-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015349256
    134 https://doi.org/10.1007/978-3-540-74510-5_9
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/978-3-540-74593-8_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002680503
    137 https://doi.org/10.1007/978-3-540-74593-8_8
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/978-3-642-13089-2_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014064203
    140 https://doi.org/10.1007/978-3-642-13089-2_31
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/978-3-642-19805-2_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047299195
    143 https://doi.org/10.1007/978-3-642-19805-2_4
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/978-3-642-19861-8_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048833860
    146 https://doi.org/10.1007/978-3-642-19861-8_9
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/978-3-642-21254-3_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000989884
    149 https://doi.org/10.1007/978-3-642-21254-3_8
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/978-3-642-29517-1_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042081817
    152 https://doi.org/10.1007/978-3-642-29517-1_1
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1007/978-3-642-29517-1_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285532
    155 https://doi.org/10.1007/978-3-642-29517-1_3
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1007/978-3-642-36315-3_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019959784
    158 https://doi.org/10.1007/978-3-642-36315-3_2
    159 rdf:type schema:CreativeWork
    160 https://app.dimensions.ai/details/publication/pub.1012361330 schema:CreativeWork
    161 https://doi.org/10.1016/j.jlap.2009.02.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028603771
    162 rdf:type schema:CreativeWork
    163 https://doi.org/10.1016/j.tcs.2008.01.041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012017670
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1016/j.tcs.2015.07.046 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006378873
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1142/s0129626409000171 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062907434
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1145/1232420.1232424 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047098083
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1145/1244381.1244404 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006492707
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1145/1366230.1366239 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018780610
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1145/777388.777391 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041853059
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1145/966049.777391 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063175618
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1147/rd.176.0525 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063180324
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1147/rd.53.0183 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063183065
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1364/on.11.2.000011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1065242236
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1515/9781400882618-009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011817422
    186 rdf:type schema:CreativeWork
    187 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
    188 schema:name DIKU, Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen, Denmark
    189 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...