Funciones recursivas primitivas y funciones características. Métodos de prueba: ejemplos. Iluminación.

Question

Estoy desconcertante a través de una frase en un ejemplo en un libro de texto, mostrando que una función de $f$, definidas por los casos, es primitiva recursiva.

Deje $E$ el conjunto de incluso números naturales. La función de $f$ definido por

$$ f(n) = \begin{cases} \frac12n,&\text{if }n\in E\\\\ 3n + 1,& \text{if }n \notin E \end{casos}$$

es primitiva recursiva.

Ahora vamos a $g: \mathbb{N} \longrightarrow \mathbb{N}$ sea la función definida por

$$g(n)=\begin{cases} \frac12n,&\text{if }n\in E\\\\ \frac12(n-1),&\text{if }n\notin E\;. \end{casos}$$

Mi entendimiento es que la función de $g$ ha sido recogido, porque hace lo mismo que $f$, y también porque es más fácil convertir a la primitiva recursiva forma. Estoy en lo cierto?

Esta es la frase que es desconcertante mí:

'Observamos que $g(n+1) = g(n)$ si $n+1$ es impar y $g(n+1)=g(n)+1$ si $n+1$ es incluso'

Estoy seguro de que la idea detrás de esto es muy simple, y he tenido un momento de ceguera. Por ejemplo, la observación por medio de la sustitución, o estoy mirando mal camino? Algunos de iluminación sería fantástico - y cualquier alternativa de las pruebas. Sólo una nota final - iba a estar a la derecha en la comprensión de que hay un montón de diferentes maneras de escribir una función $f$, lo que determina si $n$ es par o impar (definida por dos de los casos)?

La prueba concluye: tenemos $n+1 = \operatorname{succ}(n)$, lo $g$ puede ser definido por las ecuaciones

$$\begin{align*} &g(0)=0\\ &g(n+1) = g(n) + \chi_E(\operatorname{succ}(n))\;. \end{align*}$$

Answer 1

Si $n+1$ es impar, entonces $g(n+1)=\frac12\big((n+1)-1\big)=\frac12n=g(n)$, mientras que si $n+1$ es incluso, a continuación,$g(n+1)=\frac12(n+1)=\frac12\big((n-1)+2\big)=\frac12(n-1)+1=g(n)+1$, ya que el $n$ es impar.

Sin embargo, $g$ $f$ claramente no son la misma función, como puede verse en la evaluación de los mismos en cualquier número natural impar. No estoy seguro exactamente lo que quieres decir por " una función de $f$, lo que determina si $n$ es par o impar (definida por dos casos)'. ¿Te refieres a una función de $f$ tal que mirando a $f(n)$ (tal vez en combinación con $n$), se puede deducir que la paridad de $n$, como $\chi_E$? O ¿simplemente significa que uno cuya definición requiere de dos casos, uno para cubrir impar argumentos y la otra para cubrir incluso los argumentos?