0

I'm working through exercises in recursion theory and one such exercise is to prove the inverse of a 1-1 1-place partial recursive function $\psi$ is partial recursive, which was given with somewhat of a warning as to its difficulty. I've figured out if you can prove $dom(\psi)$ is recursive you can write $\psi^{-1}(x)=\mu z(z\in dom(\psi) \land \psi(z)=x)$ such that the predicate in the parenthesis is computable, so $\psi^{-1}$ is partial recursive. Though I have no idea even if $dom(\psi)$ is recursive much less how to prove it. Any ides?

Physical Mathematics
  • 4,453
  • 1
    The domain will not usually be recursive - every r.e. set is the domain of a partial recursive function. But what if you leave out that check in the definition of $\psi^{-1}$? – Carl Mummert Sep 11 '18 at 20:49
  • For $\mu z (P(z))$ to partial recursive we need P(z) computable. If we don't first check $z\in dom(\psi)$ we don't have P(z) computable for $\psi$ partial recursive. Hopefully, the 1-1 condition of $\psi$ forces $dom(\psi)$ to be recursive, though of course in general the domain of a partial recursive function isn't recursive. – Physical Mathematics Sep 11 '18 at 20:58
  • 1
    The 1-1 requirement doesn't force the domain to be recursive. But if $z$ is not in the domain, there's not really much harm in trying to compute $\psi(z)$, it just will never halt. You do need to modify the predicate inside the $\mu$ operator some to make it recursive, but worrying about the domain of $\psi$ won't help. Think algorithmically - if you wanted to test if $x = \psi(z)$ for some $z$, how could you go about it step by step? It may help me and others give more help if you include in the question some additional context about the text you're using or the model of computation. – Carl Mummert Sep 11 '18 at 21:00
  • I'm working with Prof. Steven Simpson and he's having me read his lecture notes at http://www.personal.psu.edu/t20/courses/math497/. I haven't been able to figure out a (good) way to test if $x=\psi(z)$ for some $z$ while guaranteeing $\mu z (P(z))$ halts whenever $x=\psi(z)$ for some $z$. The only idea that I have would be to check $\psi(0)$ and run that computation for some finite number of steps, $m$, and check $\psi(1)$ and run that for $m$ steps, and go back to $\psi(0)$, do $m$ steps, then to $\psi(2)$, and so on. Seems like that could work, but not sure how to formalize it. – Physical Mathematics Sep 11 '18 at 21:11
  • The question is #4 on p.16 of lecture notes on the linked page. – Physical Mathematics Sep 11 '18 at 21:14
  • That is exactly the method I would use. I think some of the ideas are in section 8 a few pages later. The key point is that, if you know the number $s$ of steps you are willing to run, you can decide computably whether "$\phi(x) = z$ and the computation stops in less than $s$ steps". – Carl Mummert Sep 11 '18 at 21:20

0 Answers0