Show that the function floor-log is primitive recursive

Question

I have been stuck on this problem for a while and I was hoping someone could help me with it. This is for my computer science automata and formal languages class.

Given an integer $b$ greater than or equal to $2$ and a positive integer $x$, let $n$ be the greatest natural number such that be $b^n\le x$. I basically have to prove that a function floor-log that takes two inputs $b$ and $x$ and outputs $n$ is primitive recursive.

Additionally, Given any input that doesn't meet the preconditions, a value of 0 or 1 for the first input(b), or a value of 0 for $x$ should output 0.

I realize I have to use some combination of bounded sums and raise-to-power function but I can't figure out how to do that.

Answer 1

To prove that a certain function is primitive recursive, as you probably know, you need to be able to describe the function using only the basic primitive recursive functions.

This gives us a definition that could look like:
$$\mathrm{floorlog}(b,x) = \left\{\begin{array}{ll} \mathrm{null}(x) & b = 0 \\ g(b-1, \mathrm{floorlog}(b-1, x), x) & b > 0 \end{array}\right.$$ NOTE: $\mathrm{null}(x) = 0$. $$g(k,l,m) = \left\{\begin{array}{ll} \mathrm{succ}(\mathrm{null}(\mathrm{proj}^1_2(l,m))) & k = 0 \\ h(k-1, g(k-1,l,m), l, m) & k > 0 \end{array}\right.$$ NOTE: $\mathrm{succ}(\mathrm{null}(\mathrm{proj}^1_2(l,m))) = 1$. $$ h(q,r,s,t) = f(proj^4_4(q,r,s,t), proj^3_4(q,r,s,t), \mathrm{succ}(\mathrm{succ}(proj^1_4(q,r,s,t))))$$ NOTE: this isn't anything else as $h(q,r,s,t) = f(t, s, q + 2)$. $$f(x,y,z) = \left\{\begin{array}{ll} \mathrm{null}(\mathrm{proj}^1_2(y,z)) & x = 0 \\ etc\ldots & x > 0 \end{array}\right.$$

then you just need to check whether $b^n > x$ and increment the $n$ accordingly. The point I'm trying to make is that proving this using the given definitions is quite a lot of work (and I must admit I stopped trying because I didn't see it anymore for a second).

Another way to prove this is to write a program that uses only a clean for-loop. With clean, I mean that you don't mess with the loop variables (because actually you're writing a while-loop in disguise then). I suppose this shouldn't be too much of a problem now...

Hope this helps

Answer 2

Here is one method. Given $b> 1$ and $n \geq 2$, start computing $b^0, b^1, b^2, \ldots, b^n$. At some point, you will find a $k \in \{0, \ldots, n\}$ such that $b^k \leq n$ and $b^{k+1} > n$. Then return $k$.

The underlying mathematical fact is that $0 \leq \operatorname{floorlog}(b,n) < n$, so we can use $n$ itself as a convenient bound for a bounded search.

The operation I described is a bounded search (bounded by $n$), and the test at each stage is primitive recursive, so the overall function is primitive recursive. In particular, for $b > 1$ and $n > 2$, we can define the function using the bounded $\mu$ operator and a primitive recursive predicate: $$ \operatorname{floorlog}(b,n) = (\mu. k < n) [ b^k \leq n \land b^{k+1} > n]. $$