Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a question about primitive recursive functions. Maybe it's trivial, if it is I will move it into math.stackexchange.

Is there a primitive recursive function $f$ which is a bijection of $N$ onto $N$ such that $f^{-1}$ is not primitive recursive ?

share|improve this question
    
Exercise 5.6 in this book claims that bijective primitive functions are a group, i.e. such a function $f$ exists: books.google.co.il/… –  Denis Apr 18 '13 at 13:39
2  
DK, you mean to say that they are not a group. Frank, the inverse of Ackermann is primitive recursive, but this is not a bijection. But you can fix it up via the even/odd trick as in my argument and also as in DK's link (and those arguments are fundamentally similar). –  Joel David Hamkins Apr 18 '13 at 14:03

2 Answers 2

up vote 9 down vote accepted

The answer is yes. First, let $g$ be a total computable function whose rate of growth is too fast for it to be primitive recursive, such as the diagonal Ackermann function. Now, define $f(k)=2n$, if $k$ is the number coding up (in some canonical way) the computation of $g(n)$. That is, $k$ should encode a list of the entire computation sequence for $g(n)$, including snapshots of the configuration of each stage of computation, what is on the tape, where the head is, the state and so on. Now, for numbers $k'$ that are not codes of computations, we let $f(k')$ be the smallest odd number not yet used. Thus, we have a bijection $f:\mathbb{N}\to\mathbb{N}$.

Furthermore, $f$ is primitive recursive, because for a given $k$, we can bound the length of time it takes to compute $f(k)$---the algorithm need only unpack $k$ and verify whether it is a proper code or not, and then do some easy computations on the side.

Meanwhile, the inverse function is not primitive recursive. The point here is that $k$ is far larger than $n$. We cannot get from $n$ or $2n$ to a code $k$ for the computation of $g(n)$, because we assumed that the growth rate of $g$ was too high for it to be primitive recursive.

share|improve this answer

More concisely, it is not far from the truth to say that the purpose of (adding) the minimalisation operation for general recursion is to define inverse functions. That this is Difficult is put to practical use in many methods of encryption.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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