Why μ of partial recursive functions requires values of least zero's predecessors be defined

Question

The definition of partial recursive function says that given a partial recursive function $G(x,y)$, a new partial recursive function can be generated as$$F(x)\simeq\mu y[G(x,y)=0]$$ $F(x)$ is equal to the least $y$ such that $G(x,y)=0$ and for all $y'$ less than $y$, $G(x,y')$ is defined and is not zero, otherwise $F(x)$ is undefined. I don't think the $\forall y'<yG(x,y')\neq\bot$ requirement is needed. Suppose $G$ is implemented by a register machine program $P$. In searching for the least zero, one can use dovetailing technique by executing the first instruction of $P(x,0)$, then the first two instructions of $P(x,0)$ and $P(x,1)$ and so on, until $0$ is reached. Am I right?

Answer 1

The problem is that when you find the first $y$ such that $P(x, y) = 0$ using dovetailing technique, it doesn't mean that there is no $z < y$ with $P(x, z) = 0$. There are two cases:

• such $z < y$ exists, but the computation for $P(x, z)$ just takes more time than for $P(x, y)$ (and the only way to "check" this is to wait for the convergence of $P(x, t)$ for all $t < y$);
• there is no such $z$, and $y$ is indeed the least such number.

There is the halting problem inside. Let's show that there is a partial recursive $G(x, y)$ such that $F(x) = \min(y)[G(x, y) = 0]$ defined as "the least $y$ such that $G(x, y) = 0$" is not recursive.

Consider the following function $$ G(x, y) = \begin{cases} 0,& \text{if } y = 1 \text{ or } (y = 0 \text{ and } \varphi_x(x)\!\downarrow),\\ \uparrow,& \text{otherwise.} \end{cases} $$

Clearly, $$F(x) = \begin{cases} 0,& \text{if } \varphi_x(x)\!\downarrow,\\ 1,& \text{otherwise}, \end{cases}$$ which is the characteristic function of the halting set $K = \{x \mid \varphi_x(x)\!\downarrow\}$. Given that $K$ is not recursive, we have that $F(x)$ is not recursive too.