What is a description of all total recursive functions $g(x)$ for which the operator$$\Phi_g: \mathcal{F}_2 \to \mathcal{F}_1$$defined by the formula$$\Phi_g(f)(x) := g(\mu y(f(x, y) = 0))$$is effective?
5
-
$\begingroup$ Incidentally, this was asked at MSE: math.stackexchange.com/questions/2069149/…. $\endgroup$– Noah SchweberCommented Jan 4, 2017 at 21:40
-
2$\begingroup$ Could you define your terms and notation? What is $\mathcal{F}_i$ (set of total functions of $i$ variables, or partial ones, or something else), and what does it mean for an operator to be effective? $\endgroup$– Noah SchweberCommented Jan 4, 2017 at 21:54
-
1$\begingroup$ Isn't this always effective? If I have an algorithm for $g$ and $f$, then I can compute $g(\mu y(f(x,y)=0)$ by just trying out all the $y$'s until I find one. I assume that $\mu y$ means the least one such that $f(x,y)=0$ and $f(x,y')$ converges for all $y'<y$. $\endgroup$– Joel David HamkinsCommented Jan 4, 2017 at 21:57
-
1$\begingroup$ And if you don't have that meaning for $\mu$, but want to take just the least $y$ with $f(x,y)=0$, then the only $g$ for which the operator will be effective is when $g$ is the empty function, which never converges, since otherwise the question of the value and existence of $\mu y(f(x,y)=0)$ is not semi-computable for that interpretation of $\mu$. $\endgroup$– Joel David HamkinsCommented Jan 4, 2017 at 23:44
-
1$\begingroup$ I've voted to close this as unclear. I don't understand the question, and it seems others also have points of confusion. @Andrew - you can easily edit the question to add more detail. $\endgroup$– Carl MummertCommented Jan 24, 2017 at 13:00
Add a comment
|