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...

$\endgroup$
  • $\begingroup$ You're confusing partial recursive with primitive recursive. $\endgroup$ – Yuval Filmus Jul 28 '18 at 20:47
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
$\endgroup$
  • $\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 '18 at 9:18
  • $\begingroup$ The two definitions are equivalent. $\endgroup$ – Yuval Filmus Jul 29 '18 at 10:31
  • $\begingroup$ So I can build $f^{-1}$ using primitive recursive functions and applying the $\mu-operator$, right? $\endgroup$ – tokenizer Jul 29 '18 at 10:37
  • $\begingroup$ All partially recursive functions have such a representation. $\endgroup$ – Yuval Filmus Jul 29 '18 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 '18 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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