On reversible Turing machines and their function universality

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

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

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
• A program inverter for a functional language with equality and constructors.
• Fundamentals of reversible flowchart languages

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
• Title not available (Why is that?)
• Reversible computing from a programming language perspective
• Title not available (Why is that?)
• 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
• 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)