Reversible Turing Machines and Polynomial Time Reversibly Computable Functions

DOI10.1137/0403020zbMath0699.68067OpenAlexW1965297199MaRDI QIDQ3477963

G. Jacopini, Giovanna Sontacchi, Patrizia Mentrasti

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

reversibilityTuring machineone-way bijection

Mathematics Subject Classification ID

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

Related Items (4)

Generation of invertible functions ⋮ A class of recursive permutations which is primitive recursive complete ⋮ A class of reversible primitive recursive functions ⋮ A Hierarchy of Fast Reversible Turing Machines

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