I have a problem for the comprehension of how to prove that a function $ \log_2 : \mathbb{N} \rightarrow \mathbb{N}$ defined as: $$\log_2 (x)= \begin{cases} y & \text{if $x=2^y$} \newline \bot & \text{otherwise} \end{cases}$$ is recursive. I think that I need to use minimization operator but I don't know how to do that.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Once you have proved that $|x-2^y|=0$ is a decidable predicate, the function $$\log_2(x) \equiv \mu y(|x-2^y| = 0)$$ should match the description of the function given and proves that it is recursive.
Edit: To show that $|x-2^y|=0$ is decidable, show that $\overline{\text{sg}}(|x-2^y|)$ is recursive, which requires you to show that $|x-z|$, $2^y$, and $1 - \text{sg}(z)$ are recursive, then use substitution.
$|x-z|$ can be defined as $(x-z) + (z-x)$ where cut-off substraction is used in the latter and you can use $x^y$ is a primitive recursive function to show that $2^y$ is recursive. $\text{sg}(z)$ is computable by noting that $\text{sg}(0)=0$ and $\text{sg}(z+1) = 1$.