A class of recursive permutations which is primitive recursive complete

DOI10.1016/j.tcs.2019.11.029zbMath1481.03031OpenAlexW2990494648WikidataQ126641588 ScholiaQ126641588MaRDI QIDQ1989331

Luca Roversi, Mauro Piccolo, Luca Paolini

Publication date: 21 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2318/1734163

zbMATH Keywords

recursion theoryreversible computationprimitive recursive functionscomputable permutationsunconventional computing models

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Other nonclassical models of computation (68Q09)

Related Items (5)

Towards a taxonomy for reversible computation approaches ⋮ Certifying expressive power and algorithms of reversible primitive permutations with \textsf{Lean} ⋮ Unnamed Item ⋮ Splitting Recursion Schemes into Reversible and Classical Interacting Threads ⋮ Certifying algorithms and relevant properties of reversible primitive permutations with \textsf{Lean}

Uses Software

• Theseus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On reversible Turing machines and their function universality
• Higher-dimensional word problems with applications to equational logic
• A class of reversible primitive recursive functions
• On the representation of partial recursive functions as superpositions
• Reversible computing and cellular automata -- a survey
• The pillars of computation theory. State, encoding, nondeterminism
• Generation of invertible functions
• Classical recursion theory. The theory of functions and sets of natural numbers
• Representation of partial recursive functions with certain conditions in the form of superpositions
• Linear programs in a simple reversible language.
• Towards an algebraic theory of Boolean circuits.
• Interactions between computer science and biology
• Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics
• Towards a Reversible Functional Language
• Information effects
• On quantum lambda calculi: a foundational perspective
• What Do Reversible Programs Compute?
• Reversibility and adiabatic computation: trading time and space for energy
• Reversible Turing Machines and Polynomial Time Reversibly Computable Functions
• Time/Space Trade-Offs for Reversible Computation
• A Certified Study of a Reversible Programming Language
• Mathematics of Program Construction
• AN ELEMENTARY THEORY OF THE CATEGORY OF SETS
• On primitive recursive permutations and their inverses
• Logical Reversibility of Computation
• General Recursive Functions

This page was built for publication: A class of recursive permutations which is primitive recursive complete