He leído en una introducción a la primitiva recursiva de la función y de la Wikipedia que $$\log(b,n) = \lfloor \log_b(n) \rfloor$$ es primitiva recursiva. Pero, ¿cómo puede ser eso? Es allí cualquier fáciles de la prueba (y, por tanto, una definición de la función utilizando sólo las constantes, la proyección, la composición y la recursión primitiva)?
Gracias de antemano!
Es primitiva recursiva porque se puede dar un algoritmo para el cálculo es que sólo utiliza delimitada bucles: Encontrar el entero más grande $x$ tal que $b^x \le n$. El bucle nunca necesita ejecutar más de $n$ veces, por lo tanto es limitada. (Estamos suponiendo $b>1$, dado que el logaritmo no está definido de otra manera.)
Esto se puede traducir en una combinación de las funciones que se describen, con el bucle correspondiente a la primitiva recursividad, aunque puede ser un poco desordenado. Generalmente, cuando la comprobación de si algo es primitiva recursiva, es más fácil pensar en términos de limitada bucle de algoritmos.
Voy a tratar de esbozar una construcción. En primer lugar, tenga en cuenta que una función definida por primitiva recursiva de los casos de funciones recursivas primitivas es todavía primitiva recursiva (más fácil de probar).
Así, tratamos de definir este por la recursividad en $n$. Desde $\log_b(0)$ no es algo que queremos considerar, asumiremos $b,n > 0$. Vamos
$$\log(b,1) = 0$$
Que sin duda es primitiva recursiva. A continuación, definir
$$\log(b,n+1) = F(\log(b,n),b,n)$$
Donde $F$ es la siguiente función definida por casos. $F$ es de $\log(b,n)+1$, y comprueba si
$$b^{(\log(b,n) + 1)} > n+1$$
En otras palabras, se ve a si $\log(b,n) + 1$ es todavía disparo demasiado alto. Si es así, entonces nos quedamos con lo que tenemos: $\log(b,n)$. De lo contrario, el tiempo finalmente ha llegado a pasar hasta el $\log(b,n) + 1$, y por lo $F$ salidas.
No es difícil ver que $F$ es definido por la primitiva recursiva de los casos de primitivas de funciones recursivas, y así han demostrado que $\log(b,n)$ es primitiva recursiva.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
