On reversible Turing machines and their function universality

DOI10.1007/s00236-015-0253-yzbMath1348.68051OpenAlexW2279321119WikidataQ62038220 ScholiaQ62038220MaRDI QIDQ303695

Holger Bock Axelsen, Robert Glück

Publication date: 22 August 2016

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-015-0253-y

zbMATH Keywords

reversibility\(r\)-Turing completenessreversibilizationRTM injectivityRTM-universalityTuring machine inversionuniversal reversible Turing machine

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Turing machines and related notions (03D10)

Related Items

Towards a taxonomy for reversible computation approaches, Reversible computing from a programming language perspective, Simulating reversible computation with reaction systems, The fixed point problem of a simple reversible language, A class of recursive permutations which is primitive recursive complete, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of reversible flowchart languages
• Reversible computing and cellular automata -- a survey
• \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis
• Reversible Shrinking Two-Pushdown Automata
• A Hierarchy of Fast Reversible Turing Machines
• Time Complexity of Tape Reduction for Reversible Turing Machines
• What Do Reversible Programs Compute?
• A Simple and Efficient Universal Reversible Turing Machine
• Reversible arithmetic logic unit for quantum arithmetic
• One-Way Reversible Multi-head Finite Automata
• Programming Techniques for Reversible Comparison Sorts
• Reversible Machine Code and Its Abstract Processor Architecture
• Reversible Pushdown Automata
• A Universal Reversible Turing Machine
• Irreversibility and Heat Generation in the Computing Process
• Functional and Logic Programming
• Programming Languages and Systems
• Logical Reversibility of Computation
• Programming Languages and Systems