Reversible Turing Machines and Polynomial Time Reversibly Computable Functions

DOI10.1137/0403020MaRDI QIDQ3477963zbMATH OpenOpenAlexFDO

Authors G. Jacopini, Patrizia Mentrasti, Giovanna Sontacchi

Publication date 1990

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0403020

zbMATH Keywords

one-way bijectionreversibilityTuring machine

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Time/Space Trade-Offs for Reversible Computation
• A hierarchy of fast reversible Turing machines
• On reversible Turing machines and their function universality
• What do reversible programs compute?
• Reversible simulation of space-bounded computations

Cited in

(10)

• Generation of invertible functions
• A class of recursive permutations which is primitive recursive complete
• Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines
• A hierarchy of fast reversible Turing machines
• scientific article; zbMATH DE number 6691416 (Why is no real title available?)
• On reversible Turing machines and their function universality
• Time/Space Trade-Offs for Reversible Computation
• Logical Approaches to Computational Barriers
• The complexity of iterated reversible computation
• A class of reversible primitive recursive functions

This page was built for publication: Reversible Turing Machines and Polynomial Time Reversibly Computable Functions

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