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

130

Nos dieron el siguiente ejercicio.

Dejar

f(n)={10n occurs in the decimal representation of π0else

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.fπf

Rafael
fuente
32
Perdóname por ser completamente ignorante, obviamente me estoy perdiendo algún punto fundamental de la pregunta, pero ¿no es 0 ^ n siempre 0? Dado que el lugar decimal 32 si pi es 0, ¿no significaría que f (n) siempre devuelve 1?
Cory Klein
69
@CoryKlein: Esta es una notación de lenguaje formal ; el superíndice aquí significa concatenación pliegue, es decir, . es solo un símbolo aquí, no un número. n a 5 = a a a a a 0nna5=aaaaa0
Raphael

Respuestas:

133

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.n0nπ

  • 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:N0Nπ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.Nnπ


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

JeffE
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Gilles
12
¿Qué pasaría si alguien probara que la afirmación "Por cada entero positivo n, la cadena 0 ^ n aparece en la representación decimal de π" no es demostrable? ¿Seguiríamos diciendo que este problema es decidible, a pesar del hecho de que ningún algoritmo correcto podría construirse?
Otros
44
@Otros sí, lo haríamos.
JeffE
1
@JeffE Muy bien. ¿Es posible una prueba en la lógica intuicionista? ¿O es necesaria la ley del medio excluido aquí?
Otros
@Otros Si entendí correctamente, la idea es la siguiente: si para cada definimos la máquina de Turing como en la primera parte de la respuesta, entonces sabemos que uno de ellos calcula esta función. No sabemos cuál (y si su declaración fue probada, incluso sabríamos que es imposible saber cuál) pero aún sabemos que existe una máquina de Turing , por lo que la función es computable. M NNMN
JiK
14

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 < NNTN(n)n<NNNTN(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.

JC
fuente
99
No todos los matemáticos aceptan esto, por ejemplo, los intuicionistas no.
reinierpost
Básicamente estás haciendo un largo ejemplo de la ley del medio excluido, , lol. En la lógica intuicionista o en cualquier tipo de sistema lógico basado en la teoría, esta prueba es rechazada. P¬P
Kaa1el
5

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π π π ππ
π
π

π 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 .π

Stephen Voris
fuente
10
En primer lugar, sabemos que la expansión binaria de no se repite ya que es irracional. En segundo lugar, hay números irracionales que no contienen ni 000 ni 111 en su expansión binaria, por ejemplo, el que corresponde a la secuencia Thue-Morse: 0.0110100110010110 ...πππ
Yuval Filmus
1
Ah, los peligros de los saltos inductivos: P Buena captura, gracias.
Stephen Voris
1
Por cierto, si la conclusión es incorrecta, ¿tiene más sentido para mí eliminarla o dejarla y reconocer a través de la edición que está equivocada?
Stephen Voris
44
@StephenVoris Depende de cuán educativo creas que es el error. Tenga en cuenta que la cuestión de si es lo normal (es decir, su base- de expansión contiene cada secuencia finita de dígitos ary infinitamente a menudo) es uno de los grandes problemas abiertos de la teoría de números. b bπbb
David Richerby
2
@DavidRicherby ¿Gran problema abierto, dices? Sí, eso es bueno saberlo. Creo que este es un error razonablemente educativo, ya que la evidencia de cuán complicado es el problema en el que se basa la pregunta del OP, obviamente también podría estar equivocado en eso, dado el voto negativo.
Stephen Voris