On reversible Turing machines and their function universality

DOI10.1007/S00236-015-0253-YzbMATH Open1348.68051DBLPjournals/acta/AxelsenG16OpenAlexW2279321119WikidataQ62038220 ScholiaQ62038220MaRDI QIDQ303695FDOQ303695

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

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

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)

Cites Work

• Irreversibility and Heat Generation in the Computing Process
• Title not available (Why is that?)
• Title not available (Why is that?)
• Logical Reversibility of Computation
• Reversible computing and cellular automata -- a survey
• Title not available (Why is that?)
• Reversible arithmetic logic unit for quantum arithmetic
• Title not available (Why is that?)
• \(\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
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Functional and Logic Programming
• Programming Languages and Systems
• Programming Languages and Systems
• Fundamentals of reversible flowchart languages

Cited In (12)

• 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
• Title not available (Why is that?)
• Reversible computing from a programming language perspective
• Title not available (Why is that?)
• Logical Approaches to Computational Barriers
• Universality of Wolfram’s 2, 3 Turing Machine
• Title not available (Why is that?)

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)