5
$\begingroup$

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 ?

$\endgroup$
2
  • $\begingroup$ 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/… $\endgroup$
    – Denis
    Apr 18, 2013 at 13:39
  • 2
    $\begingroup$ 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). $\endgroup$ Apr 18, 2013 at 14:03

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.