¿Por qué $f_1(n)$ no es computable pero $f_2(n)$ sí lo es?

Question

Tengo las siguientes dos funciones, donde la primera no es computable y la segunda sí lo es.

$$f_1(n)= \begin{cases} 1 & ,\text{si en la representación decimal de n aparece en la expansión de la fracción decimal de} \ \pi \\ 0 & ,\text{en otro caso} \end{cases} $$

Por ejemplo, si tenemos $\pi = 3.1415926 ...$. Entonces $f_1(14195) = 1$ pero no sabemos si $f_1(333)$ tiene solución.

$$f_2(n)= \begin{cases} 1 & ,\text{si en la representación decimal de pi, hay n 7's consecutivos } \ \\ 0 & ,\text{en otro caso} \end{cases} $$

Estoy teniendo una pesadilla tratando de entender por qué una es computable y la otra no lo es. Si tomamos que $n =3$, entonces para $f_2$, estamos tratando de determinar si $777$ aparece en la representación decimal de $\pi$. Pero en $f_1$ ya vimos que determinar si $f(333)$ tiene solución no es computable.

¿Cómo son estas dos funciones diferentes?

PD - el $n$ utilizado en $f_1(n)$ no es el mismo que el utilizado en $f_2(n)$.

Answer 1

Empezamos con $f_2(n)$. Tenemos dos casos:

Caso 1: Hay secuencias arbitrariamente largas de $7$'s consecutivos en $\pi$, entonces $f(n)=1, \forall n$, y esto es claramente computable.

Caso 2: Existe una secuencia más larga de longitud $k$ de $7$'s consecutivos en algún lugar de $\pi$ y $k$ está fijo. Por lo tanto, $$ f_2(n)=\left\{\begin{array}{ll} 1, & \text{si } n \leq k \\ 0, & k < n\end{array}\right. $$ Esto también es claramente computable.

La función puede ser generalizada (por ejemplo, la aparición de la secuencia $333$ también es computable).

$f_1(n)$, por otro lado, pretende calcular si una secuencia arbitrariamente larga de números aparece en $\pi$ (por ejemplo, $1415926\cdots$). ¡Esto es una diferencia dramática! Ahora, recapitulemos la siguiente definición:

Def.: Una función (total) $f: \Sigma^* \to \Sigma^*$ es computable si hay una máquina de Turing $M$ que se detiene en cada entrada $\omega$ con $f(\omega)$ como su salida en la cinta.

Para $f_2(n)$, esto es claro a partir de los casos proporcionados. Ahora, para $f_1(n)$, asumimos que tenemos una secuencia $\omega$ que no está en $\pi$ (y no quiero discutir si $\pi$ contiene todos los posibles números o no), entonces no hay forma de construir una máquina de Turing que se detenga en $\omega$ (porque para que nuestra máquina de Turing se detenga, necesitamos recorrer todo $\pi$), y por lo tanto $f_1$ no es computable.

Nota importante para $f_2$: Solo demostramos que $f_2$ es computable. Qué función realiza el trabajo real es desconocido (pero tampoco es importante para este problema).