Why μ of partial recursive functions requires values of least zero's predecessors be defined 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?
 A: 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.
