1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.