¿Cómo se puede decidir si tiene alguna secuencia de dígitos?

Nos dieron el siguiente ejercicio.

Dejar

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Demuestre que es computable.$f$

¿Cómo es esto posible? Hasta donde yo sé, no sabemos si we contiene cada secuencia de dígitos (o cuáles) y un algoritmo ciertamente no puede decidir que alguna secuencia no está ocurriendo. Por lo tanto, creo que no es computable, porque el problema subyacente es solo semi-decidible.$\pi$$f$

Solo hay dos posibilidades a considerar.

• Para cada entero positivo , la cadena aparece en la representación decimal de . En este caso, el algoritmo que siempre devuelve 1 siempre es correcto.$n$$0^n$$\pi$

• Hay un número entero mayor tal que aparece en la representación decimal de . En este caso, el siguiente algoritmo (con el valor codificado) siempre es correcto:$N$$0^N$$\pi$$N$

  Zeros-in-pi(n):
   if (n > N) then return 0 else return 1
  

Tenemos ninguna idea de cuál de estas posibilidades es la correcta, o qué valor de es el más adecuado en el segundo caso. Sin embargo, uno de estos algoritmos está garantizado para ser correcto. Por lo tanto, hay un algoritmo para decidir si una cadena de ceros aparece en ; El problema es decidible.$N$$n$$\pi$

Tenga en cuenta la sutil diferencia con el siguiente bosquejo de prueba propuesto por gallais :

1. Tome una máquina de Turing aleatoria y una entrada aleatoria.
2. O el cálculo continuará para siempre o se detendrá en algún momento y hay una función computable (constante) que describe cada uno de estos comportamientos.
3. ???
4. ¡Lucro!

Alex ten Brink explica:

cuidado con lo que dice el teorema de detención: dice que no existe un programa único que pueda decidir si un programa determinado se detiene. Puede hacer fácilmente dos programas de manera tal que uno calcule si un programa determinado se detiene: el primero siempre dice 'se detiene', el segundo 'no se detiene': un programa siempre tiene la razón, simplemente no podemos calcular cuál de ellos es!

sepp2k agrega:

En el caso del ejemplo de Alex, ninguno de los algoritmos devolverá el resultado correcto para todas las entradas. En el caso de esta pregunta, uno de ellos lo hará. Puede afirmar que el problema es decidible porque sabe que hay un algoritmo que produce el resultado correcto para todas las entradas. No importa si sabes cuál es ese algoritmo. 10

Solo publico una pequeña explicación sobre la respuesta de JeffE.

Sabemos que existen dos funciones / casos que pueden calcular la función f (n):

1. Una función que siempre devuelve verdadero (para todo n, existe n número de ceros consecutivos)
2. Una función que devolverá verdadero si n es menor que un entero N, donde N se define como la longitud máxima de 0 consecutivos que existen en el número irracional dado (de lo contrario, devuelve falso).

Una y solo una de estas funciones puede ser correcta. No sabemos cuál, pero sabemos con certeza que existe una respuesta. La computabilidad requiere que exista una función que pueda determinar la respuesta dentro de una cantidad finita de pasos.

El número de pasos en el caso 1 está trivialmente ligado a solo devolver 1.

En el caso 2, el número de pasos también es finito. Para cada número entero , podemos construir una máquina Turing que acepte si y de lo contrario rechaza en tiempo finito. Por lo tanto, no saber un límite superior en no importa. Para cada existe una máquina de Turing, es decir, , que calcula correctamente si (no sabemos cuáles de estos son correctos, pero no importa, existe uno).T N ( n ) n < N N N T N ( n ) n < $N$$T_N(n)$$n < N$$N$$N$$T_N(n)$$n < N$

Si bien puede que no sea posible elegir entre los dos casos (aunque uno parece más probable que otro), sabemos que exactamente uno de ellos debe ser correcto.

Como nota al margen: nuestra solución supone que, si bien no podemos determinar qué función generará un valor correcto, la esencia de la computabilidad no depende de la capacidad de construcción de la prueba. La pura existencia es suficiente.

El paso 5 del siguiente intento de prueba no está justificado y, de hecho, es incorrecto : aquí se puede encontrar un contraejemplo . (gracias, Yuval; parecía la parte más esquemática del boceto). He dejado la respuesta aquí porque creo que el error es instructivo.

Primero: el par de respuestas de JeffE es suficiente; f es computable de cualquier manera.

Sin embargo, un breve desvío hacia un intento de esbozar una prueba por inducción: la
premisa R : no se repite. 1. Mire en la base 2. Esto es principalmente para reducir el número de casos. 2. No importa lo lejos abajo de la línea que vaya, siempre encontrará otro 1 en alguna parte: la alternativa es todo ceros, lo que significaría empieza a repetir, lo que va en contra de R . 3. Lo mismo va para ir por la línea y encontrar 0 . 4. Expanda a secuencias de dos dígitos: no puede dejar de encontrar 01 o 10 (es decir, lugares donde cambia), porque de lo contrarioπ π π $\pi$
$\pi$
$\pi$

$\pi$ comenzaría a repetirse en 1 's o en 0 ' s. Del mismo modo, no puede dejar de encontrar 11 o 00 , porque de lo contrario comienza a repetirse en 1010101 ...
5. El paso inductivo: cada secuencia finita tiene que aparecer un número infinito de veces, porque la alternativa es que comienza a repetirse en una de las secuencias más cortas, lo que contradice R .$\pi$