What is the relationship between invertible primitive recursive functions (that is, a primitive recursive function that is an isomorphism) and all primitive recursive functions? Can every primitive recursive function be mimicked in some way (like Bennett’s result about reversible computation) by a reversible/invertible primitive recursive function? Using pairing functions and Godel numbering can we look at all invertible primitive recursive functions from N to N?

Also, has anyone ever looked at the group of all invertible primitive recursive functions from N to N? Are there generators to this group? Can we talk about properties of this group? What is the relationship with its supergroup of all recursive isomorphisms? What about its relationship with the monoid of all primitive recursive functions from N to N? What about the monoid of all recursive functions from N to N?

  • 4
    $\begingroup$ The question is too general, especially the second paragraph. Perhaps you should ask for a reference covering this topic, but you certainly should not expect anyone to answer questions like "can we talk about the properties of this group", unless you expect a yes/no answer. $\endgroup$ Nov 19, 2012 at 13:36

2 Answers 2


Yes, people have looked at this and related groups, though not a whole lot as far as I can tell. For example:

Morozov, A. S. Turing reducibility as algebraic embeddability. Siberian Math. J. 38 (1997), no. 2, 312–313. Let $G_d$ denote the group of permutations of $\mathbb{N}$ computable below the Turing degree $d$. Morozov shows that $d_1 \leq_{T} d_2$ if and only if $G_{d_1} \hookrightarrow G_{d_2}$. (Note that a permutation and its inverse always have the same Turing degree. This no longer holds if we restrict to primitive recursive or poly-time reductions.)

Kent, C. F. Constructive analogues of the group of permutations of the natural numbers. Trans. Amer. Math. Soc. 104 (1962) 347–362.

In fact, if I recall correctly, the primitive recursive permutations generate the group of all computable permutations. (If you restrict attention to the group of permutations $\pi$ such that both $\pi$ and $\pi^{-1}$ are primitive recursive, you get a smaller group.) Furthermore, every computable permutation can be written as a word of length six in the primitive recursive permutations and their inverses. I think the same result holds if you replace "primitive recursive" by "polynomial time." [I don't recall the reference just now, but I have a physical copy of the paper at home. I will post the reference when I return from traveling.]

Slightly different but related:

Combarro, E. F. Classification of subsets of natural numbers by computable permutations. Siberian Math. J. 45 (2004), no. 1, 125–135.

The group of computable permutations is not finitely generated (Is that what you meant by "Are there generators to this group?" Every group has generators, for example, the entire group...). If it were, then there would be a c.e. set $I$ of indices such that the set $\{\varphi_i : i \in I\}$ was exactly the set of computable permutations (where $\varphi_i$ is the $i$-th computable function in some acceptable enumeration). It then takes a little argument to show that this cannot happen (start from the fact that the set of all indices of computable permutations is $\Pi^0_2$-complete).


I'm not sure if what you are interested in has been studied, but here are a few concepts that may be related to what you are looking for.

  1. Invertible terms in the $\lambda$-calculus. By Bergstra and Klop. An effort is made to characterize by semantic means the $\lambda$-terms that admit an inverse. This is classical research from the 80s, when emphasis was on trying to understand the $\lambda$-calculus through domain models.

  2. Lenses. This concept was introduced by Phil Wadler I believe (though probably by many others as well). It involves two types $a$ and $b$ and transformations between them, though they are not necessarily bijections.

  3. On Reversible Combinatory Logic. By di Pierro, Hankin and Wiklicky. They define a calculus in which each small-step is reversible, to model a type of quantum computation.

Hope this helps!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.