1
$\begingroup$

I'm stuck on this problem:

Given $f:\mathbb{N} \rightarrow \mathbb{N}$ a partial recursive function that is also injective and total. Prove that the function $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ $$f^{-1} = \left\{\begin{array}{rcl} x & \mbox{if} & f(x) = y \\ \uparrow & \mbox{otherwise}\end{array}\right.$$ is partial recursive.

So to prove that a function is partial recursive I have to show that I can build it from basic recursive functions (successor, projection and constant) by applying composition, primitive recursion and then minimization.

I don't know what form $f$ has, but I think I can use it to construct $f^{-1}$. The only problem is that I don't know what to write...

Improve this question
$\endgroup$
1
  • $\begingroup$ You're confusing partial recursive with primitive recursive. $\endgroup$
    – Yuval Filmus
    Jul 28, 2018 at 20:47

1 Answer 1

Reset to default
1
$\begingroup$

You can partially compute $f^{-1}(y)$ as follows:

for $x$ from $0$ to $\infty$:

  if $f(x) = y$ then return $x$

If you don't like for loops, you can use the following implementation:

  1. $x \gets 0$
  2. if $f(x) = y$ then return $x$
  3. $x \gets x + 1$
  4. goto step 2
Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you, it makes a lot of sense but I'm really confused. I can see that what you wrote can be implemented by a Turing machine, but still by some definitions I know that: 1). The class $PR$ of partial recursive functions is the minimum set of $P$ primitive recursive functions closed by $\mu -operator$ 2) $\Phi:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive if and only if is computable by a Turing machine. What is the relationship between those two definitions? $\endgroup$
    – tokenizer
    Jul 29, 2018 at 9:18
  • $\begingroup$ The two definitions are equivalent. $\endgroup$
    – Yuval Filmus
    Jul 29, 2018 at 10:31
  • $\begingroup$ So I can build $f^{-1}$ using primitive recursive functions and applying the $\mu-operator$, right? $\endgroup$
    – tokenizer
    Jul 29, 2018 at 10:37
  • $\begingroup$ All partially recursive functions have such a representation. $\endgroup$
    – Yuval Filmus
    Jul 29, 2018 at 10:42
  • $\begingroup$ So is it right to express it like this: $f^{-1}(y,z)=\mu x<z (*(\bar{sg}(-(f(x),y)),*(\bar{sg}(-(y,f(x))), y)))$. Where $*$ is the primitive recursive function that computes the multiplication, $sg(x)$ returns the sign of $x$ (0 if $x \leq 0$ or 1 if $x > 1$), and $-$ is the function that computes the difference. $\endgroup$
    – tokenizer
    Jul 29, 2018 at 11:12

Your Answer

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

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