$\mu$-definición recursiva de ulam (3n+1) función de

Question

$\newcommand{\ulam}{\operatorname{ulam}}$

El ulam función se define como $$ \ulam(x) = \begin{cases} 1 & x = 1 \\ \ulam\left( \frac{x}{2}\right) & x \text{ even}\\ \ulam(3x+1) & x\text{ odd}\end{cases}$$

Quiero mostrar que la $\ulam$ es $\mu$-recursiva mediante el uso de primitivas de funciones recursivas y el $\mu$ opterator - no, por ejemplo, mediante la definición de una máquina de Turing.

Esta es una solución que tengo - pero no entiendo completamente y podría ser, más que nada mal.

$$\begin{eqnarray*} f_p(x) & := & \begin{cases}\frac{x}{2} & x \text{ even} \\ 3x + 1 & x \text{ odd} \end{casos} \\ f_b(x) & := & \begin{cases}0 & x = 1 \\1 & x \neq 1\end{casos} \\ g(0,x) &=& x \\ g(n+1,x) &=& f_p(g(n,x)) \\ h(n,x) &=& f_b(g(n,x)) \\ \ulam(x) &=& g(\mu(h)(x),x) \end{eqnarray*}$$

Yo no entiendo cuál es el $\mu$ operador en común, pero aún hay un vacío en mi mente "encontrar el más mínimo argumento que devuelve cero" y una aplicación concreta de tales "ulam".

Podría usted por favor, comprobar la solución y tratar de explicar a mí?

Gracias de antemano!

Answer 1

Para calcular los $\ulam(x)$ usando la definición original, calcular un montón de otros valores de $\ulam$ hasta llegar a $\ulam(1)$ y, a continuación, regrese $1$. Por ejemplo, $$\begin{aligned} \ulam(3) &= \ulam(10) \\&= \ulam(5) \\&= \ulam(16) \\&= \ulam(8) \\&= \ulam(4) \\&= \ulam(2) \\&= \ulam(1) = 1.\end{aligned}$$ Since the 3n+1 Conjecture is still open, we don't know whether this process always ends and thus $ulam$ is the constant function with value $1$ o si la secuencia de cálculos que a veces se va para siempre y nunca da una respuesta.

La definición alternativa de dar procede como sigue. La primitiva de la función recursiva $g(n,x)$ da $n$th entrada a $\ulam$ en el cálculo anterior, donde el $0$th entrada es $x$. Por ejemplo, $g(0,3) = 3$ y, a continuación, $$\begin{aligned} g(1,3) &= f_p(3) = 10, \\g(2,3) &= f_p(10) = 5, \\g(3,3) &= f_p(5) = 16, \\ g(4,3) &= f_p(16) = 8, \\ g(5,3) &= f_p(8) = 4, \\g(6,3) &= f_p(4) = 2, \\ g(7,3) &= f_p(2) = 1,\end{aligned}$$ and then the values keep repeating $4,2,1$ ad infinitum.

Para calcular los $\ulam(x)$ usted necesita para detener tan pronto como llegue a $1$ y, a continuación, devolver el valor de $1$. Por definición de $f_b$, $h(n,x) = 0$ si $g(n,x) = 1$ e $h(n,x) = 1$ en todos los demás casos. Por lo tanto, $(\mu h)(x)$ es el primer número $n$ tal que $g(n,x) = 1$, e $(\mu h)(x)$ es indefinido si no hay tal $n$. Por lo tanto, si $(\mu h)(x)$ se define a continuación, $\ulam(x) = 1$ debido a que el cálculo de $\ulam(x)$ se detiene después de $(\mu h)(x)$ pasos y vuelve $1$, y si $(\mu h)(x)$ es indefinido, a continuación, el cálculo de $\ulam(x)$ nunca se detiene y $\ulam(x)$ es por lo tanto indefinido. En cualquier caso, el cálculo de $g((\mu h)(x),x)$ tiene el mismo resultado que el de $\ulam(x)$.