On reversible Turing machines and their function universality

DOI10.1007/S00236-015-0253-YMaRDI QIDQ303695zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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)

Recommendations

• Reversible Turing Machines and Polynomial Time Reversibly Computable Functions
• A Universal Reversible Turing Machine
• A simple and efficient universal reversible Turing machine
• Universal reversible Turing machines with a small number of tape symbols
• A hierarchy of fast reversible Turing machines
• An instruction set for reversible Turing machines
• On aperiodic reversible Turing machines (invited talk)
• On reversal bounded alternating Turing machines
• The group of reversible Turing machines
• Publication:4508548

Cites work

• scientific article; zbMATH DE number 3692653 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 1339873 (Why is no real title available?)
• scientific article; zbMATH DE number 517330 (Why is no real title available?)
• scientific article; zbMATH DE number 1953282 (Why is no real title available?)
• scientific article; zbMATH DE number 3305030 (Why is no real title available?)
• A Universal Reversible Turing Machine
• A hierarchy of fast reversible Turing machines
• A program inverter for a functional language with equality and constructors.
• A simple and efficient universal reversible Turing machine
• Functional and Logic Programming
• Fundamentals of reversible flowchart languages
• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• One-way reversible multi-head finite automata
• Programming Languages and Systems
• Programming techniques for reversible comparison sorts
• Reversible Machine Code and Its Abstract Processor Architecture
• Reversible arithmetic logic unit for quantum arithmetic
• Reversible computing and cellular automata -- a survey
• Reversible pushdown automata
• Reversible shrinking two-pushdown automata
• Time complexity of tape reduction for reversible Turing machines
• What do reversible programs compute?
• \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis

Cited in

(15)

• Simulating reversible computation with reaction systems
• Reversible Turing Machines and Polynomial Time Reversibly Computable Functions
• A class of recursive permutations which is primitive recursive complete
• The fixed point problem of a simple reversible language
• A Universal Reversible Turing Machine
• Towards a taxonomy for reversible computation approaches
• scientific article; zbMATH DE number 822043 (Why is no real title available?)
• Reversible computing from a programming language perspective
• scientific article; zbMATH DE number 7559463 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• What do reversible programs compute?
• A simple and efficient universal reversible Turing machine
• An instruction set for reversible Turing machines
• Universality of Wolfram’s 2, 3 Turing Machine
• scientific article; zbMATH DE number 6691416 (Why is no real title available?)

This page was built for publication: On reversible Turing machines and their function universality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q303695)