How to show that a function is recursive?

Question

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.

Answer 1

We will first define $h(c, x)$ which computes $log_2(x)$ by using $c$ as a counter, counting down starting from some large number until it hits $ 2^c \leq x \leq 2^{c+1}$.

First, let $h(0,x) = 0$. This is of course primitive recursive. Then we define the recursive step by setting: $h(n+1, x) = g(n, h(n,x), x)$, where g is defined as follows:

$ g(n, h(n,x), x) = \left. \begin{cases} n + 1, & \text{for } 2^{n+1} = x \\ \perp, & \text{for } 2^n < x < 2^{n+1} \\ h(n, x), & \text{for } x <= 2^n \end{cases} \right\}$

Function $g$ uses only comparison, addition, exponentiation, projection and 3 cases, all of which are primitive recursive, hence $h$ is also primitive recursive.

The only missing part is choosing the initial value of $c$ in h(c,x). We can just set $f(x) = h(x,x)$ since $\forall_{x \in \mathbb{N}}2^x \geq x$.