¿Cuándo y por qué una máquina de Turing no puede resolver el problema de la parada?

Question

Entiendo y acepto perfectamente la prueba que una máquina de Turing no puede resolver el problema de parada.

De hecho, esta no es una de esas preguntas que cuestionan la prueba o el resultado.

Sin embargo, siento que aún queda algo por explicar... Todavía me queda por saber exactamente por qué el problema de Halting no tiene solución. Por supuesto, en el sentido de que hay una prueba, hay una por qué aquí ... y sin embargo ... Siento que alguna otra parte importante de la por qué no está.

Déjeme explicarle:

En primer lugar, supongamos que sólo tratamos de resolver el "problema de detención con cinta vacía" y supongamos que las máquinas que nos interesan sólo tienen dos símbolos: 1 y 0. Ahora, dada una máquina, ¿se detendrá, cuando se declare en la cinta vacía (es decir: todo 0) o no?

Ahora bien, sabemos que este problema no es solucionable por Turing. Si lo fuera, obtendríamos una contradicción lógica. OK, lo entiendo. No tengo ningún problema con eso, y como dije, puedo seguir la prueba y estoy completamente de acuerdo con ella. Acepto perfectamente que este problema de detención no se puede resolver.

Pero supongamos que lo intento y lo intento: supongamos que intento resolver este problema de detención. Sabemos que el conjunto de todas las máquinas de Turing es enumerable, así que vamos a repasarlas una por una. Ahora bien, es de suponer que esta enumeración es tal que comienza con máquinas relativamente "simples". De hecho, podría enumerar primero todas las que tienen 1 estado interno, luego todas las que tienen 2, etc. ya que para cualquier $n$ y con sólo $2$ símbolos, sólo hay un número finito de máquinas posibles

Ahora, para todas las máquinas con $1$ estado, puedo predecir fácilmente su comportamiento. Algunos se detienen. Otras no. Bien, pasando a las máquinas con $2$ estados. Con algo de esfuerzo, puedo predecir el comportamiento de todos ellos también. Genial. En cuanto a $3$ ... ok, ahora se vuelve más difícil .. pero incluso aquí puedo hacerlo. Lo sé, porque la gente que trabaja en el problema de Busy Beaver ha descubierto esto. Y creo que lo han resuelto por $n=4$ así como ...

Curiosamente, estos investigadores están utilizando ordenadores para ayudarles a averiguar el comportamiento de parada o no de estas máquinas relativamente "simples". Estos programas informáticos intentan, en cierto modo, resolver el problema de la parada, al menos para valores muy pequeños de $n$ . Presumiblemente, estas máquinas "analizan" y "descomponen" el comportamiento de una máquina con $4$ estados en algo que pueda demostrarse que se detiene o no se detiene. Pero por supuesto, sabemos que no pueden resolverlo para todos $n$ ... no pueden ser perfectos. Y de hecho, para $n=5$ el comportamiento de las máquinas de Turing se complica tanto que ni el ser humano ni la máquina son capaces de averiguar (todavía) si la máquina se detiene o no.

Así que... esta es mi pregunta: ¿qué es ¿con qué nos encontramos que nos impide averiguar el comportamiento de parada?

La prueba del problema Halting utiliza la autorreferencia. Es decir, si una máquina podría resolver la detención, entonces podemos demostrar que debe haber una máquina que se detenga en su propia entrada (es decir, cuando se le da su propio programa, o su propio número en alguna enumeración, o..) si y sólo si no .. una contradicción.

De acuerdo, pero esto es cuando tenemos una máquina con ciertas potencias... en cierto modo, una máquina que puede resolver el problema de detención es una máquina con "demasiada" potencia, lo que lleva a una contradicción.

Pero, las máquinas de detección de paradas utilizadas por los investigadores de Busy Beaver no tienen demasiada potencia. Tienen muy poca potencia. Actualmente no pueden resolver $n=5$ . Vale, pues les damos más poder. Tal vez en algún momento puedan resolver $n=5$ ... pero todavía no pueden resolver $n=6$ . Tal vez podamos darles suficiente poder para resolver $n=6$ o $n=7$ o ....

... así que mi pregunta es: ¿hay algún valor "especial" de $n$ , digamos que $n=m$ donde esto tiene que parar. Donde, de alguna manera, la única forma de resolver $n=m$ ¿es por una máquina que tiene "demasiada" potencia? Pero, ¿por qué? ¿Es por algún tipo de autorreferencia? Porque la única manera de resolver $n=m$ es por una máquina que, al tratar de analizar y predecir el comportamiento de alguna máquina con $m$ estados, no puede reducirse a nada "más pequeño" que algo que requiera resolver $n=m$ ¿en sí mismo? ¿Algún tipo de valor "mínimo" no diferente de algún conjunto de requisitos mínimos que deben tener los sistemas formales para poder aplicarles la construcción de Godel?

Un pensamiento que tengo es que esto no puede ser: como dije, para cualquier $n$ Sólo hay un número finito de máquinas que considerar. Como tal, es computable; existe alguna máquina que clasifica correctamente todas las máquinas con $n$ estados como halters de cinta vacía o no halters: toma una máquina en la entrada, recorre su lista finita con respuestas prealmacenadas y emite esa respuesta. Hay una máquina que hace esto para $n=5$ hay uno para $n=6$ etc. Y ninguna de esas máquinas tiene demasiada potencia: no hay contradicciones. Todas tienen muy poca.

Por otra parte, estas máquinas no hacen ningún análisis explícito de las máquinas involucradas ... sólo pasar para dar el valor correcto. Por lo tanto, tal vez todavía hay algún valor de $n$ ¿dónde el enfoque de intentar realmente analizar y predecir el comportamiento de la máquina comienza a romperse por alguna razón fundamental, de nuevo posiblemente autorreferencial?

O bien: ¿es que el enfoque analítico simplemente se vuelve más y más difícil ... pero que hay no punto "especial" en el que se convierte, por alguna razón teórica y fundamental, en algo demasiado difícil? Como tal, la contradicción sólo viene de una máquina que puede hacerlo por todo infinitos valores de $n$ ? Efectivamente, quizás el problema es que para analizar el comportamiento de todas las máquinas con $n$ estados, necesitamos una máquina que tiene que tener más de $n$ estados ... y así mientras para cada $n$ hay una máquina $M$ que puede realizar el análisis, la complejidad de $M$ es mayor que cualquiera de las máquinas con $n$ estados, y por lo tanto necesitarías otra máquina aún más complicada $M'$ para analizar máquinas con el tipo de complejidad que $M$ ha ... estableciendo así una regresión infinita que nunca se puede completar, es decir, no hay una máquina que pueda "hacerlo todo"?

¿Puede alguien ayudarme a pensar en esto?

Answer 1

Creo que la siguiente parte de su pregunta es la más importante:

Pero, las máquinas de detección de paradas utilizadas por los investigadores de Busy Beaver no tienen demasiada potencia. Tienen muy poca potencia. Actualmente no pueden resolver $n=5$ . Vale, pues les damos más poder. Tal vez en algún momento puedan resolver $n=5$ ... pero todavía no pueden resolver $n=6$ . Tal vez podamos darles suficiente poder para resolver $n=6$ o $n=7$

o ....

... así que mi pregunta es: ¿hay algún valor "especial" de $n$ , digamos que $n=m$ donde esto tiene que parar. Donde, de alguna manera, la única forma de resolver $n=m$ ¿es por una máquina que tiene "demasiada" potencia? Pero, ¿por qué sería eso?

La solución para resolver $\Sigma(5)$ no es simplemente dar a las máquinas de Turing "más poder". La razón por la que no sabemos $\Sigma(5)$ ahora mismo es porque hay máquinas de Turing de 5 estados que los matemáticos creen que nunca se detendrán, pero no han podido demostrar que nunca se detendrán. El problema no es tan sencillo como enumerar todas las máquinas de Turing de 5 estados, ya que una vez hecho esto, hay que averiguar si la máquina de Turing se detiene o no, lo cual, como se sabe, no es un problema trivial. Hemos sido capaces de hacer esto para las máquinas de Turing de 4 estados, pero aún no sabemos si podemos hacer esto para las máquinas de Turing de 5 estados porque es muy posible que haya máquinas de Turing de 5 estados que nunca podamos demostrar que se detienen/no se detienen dentro del sistema de la matemática clásica (es decir, ZFC).

Ahora, has preguntado cuál es el número mágico: ¿Cuál es el número mágico $n=m$ de tal manera que nunca podremos resolver para $\Sigma(n)$ ? Como he dicho más arriba, ese número mágico bien podría ser $n=5$ pero aún no se ha demostrado. Sin embargo, los matemáticos han demostrado que $\Sigma(1919)$ es efectivamente incognoscible dentro de ZFC . Antes de explicar esto, creo que podría ser útil citar de nuevo su pregunta:

Por otra parte, estas máquinas no hacen ningún análisis explícito de las máquinas implicadas... simplemente dan el valor correcto. Por lo tanto, tal vez todavía hay algún valor de $n$ ¿dónde el enfoque de intentar realmente analizar y predecir el comportamiento de la máquina comienza a romperse por alguna razón fundamental, de nuevo posiblemente autorreferencial?

Mi respuesta a esta pregunta es que sí, que existe una máquina de Turing de 1919 estados, de manera que intentar predecir si la máquina se detiene sería fundamentalmente irresoluble dentro de nuestro sistema de matemáticas. Verás, la forma en que los matemáticos demostraron $\Sigma(1919)$ es irresoluble es construyendo una máquina de Turing de 1919 estados $M$ que se detiene si hay una contradicción dentro de ZFC y nunca se detiene si ZFC es consistente. Sin embargo, no hay manera de demostrar que ZFC es consistente utilizando los axiomas de ZFC debido a Segundo Teorema de Incompletitud de Godel . Esto significa que nunca podremos utilizar los axiomas ZFC de las matemáticas para demostrar que la máquina $M$ se detiene o no, porque hacerlo constituiría una prueba de que ZFC es consistente. Así, los matemáticos no pueden predecir si la máquina $M$ se detiene o no a causa del Teorema de Incompletitud de Godel, lo que significa que el problema de la mariposa ocupada para las máquinas de Turing de 1919 es irresoluble.

Espero que esto le dé una idea más clara de por qué $\Sigma(n)$ es solucionable para valores pequeños de $n$ pero irresoluble para valores mayores de $n$ . De todos modos, ciertamente no soy un experto en teoría del cálculo, así que si alguien quiere añadir una explicación alternativa/comentarios aclaratorios a mi respuesta, no dude en hacerlo. Gracias.

Answer 2

Dado que, como se observa, cualquier cantidad finita del problema de detención -es decir, cualquier conjunto de la forma $H\upharpoonright s:=\{x<s:\Phi_x(x)\downarrow\}$ - es computable, no hay ningún punto de imposibilidad agudo en particular. Hay algunas "transiciones de fase" interesantes que parecen relevantes, por ejemplo, en un punto determinado llegamos a nuestro primer universal pero no conozco ninguna que tenga la pretensión de ser el punto en el que el problema de parada se convierte en no computable.

Por otro lado, como también se observa el forma en que el $H\upharpoonright s$ s son computables es no uniforme (de lo contrario, todo el problema de detención sería computable). Así que podemos intentar medir esta "complejidad continua". Hay dos enfoques, en mi opinión, naturales:

• Dado $n$ La "jerarquía de las teorías", desde los fragmentos de la AP hasta los fragmentos de la $Z_2$ a fragmentos de ZFC, a ZFC + grandes cardinales - ¿tenemos que ir para conseguir una teoría que pueda decidir si cada uno de los primeros $n$ Las máquinas de Turing se detienen en la entrada $0$ ?

• Dado $n$ ¿Qué tan complicada es la cadena finita que consiste en la primera $n$ bits de la función característica del problema de detención (llame a esta cadena " $\eta_n$ ")?

De estos dos enfoques, el primero tiene cierto atractivo del que carece el segundo, pero también es mucho más vago y limitado. El segundo acaba dando lugar a una teoría muy rica, a saber, la teoría de Complejidad de Kolmogorov (y sus nociones asociadas, como aleatoriedad algorítmica ), y también subsume parcialmente la anterior cuestión. Así que creo que esa es mi respuesta a tu pregunta: en última instancia, no encontrarás un punto de transición claro, pero el estudio de la dinámico comportamiento de la complejidad del problema de detención es bastante gratificante.

Answer 3

Por ejemplo, se puede construir una máquina de Turing (no sé cuántos estados necesita, pero es un número finito) que busque un contraejemplo a la conjetura de Goldbach, es decir, un número par $> 2$ que no es la suma de dos primos, pasando por los números pares uno a uno; para el número par $n > 2$ comprueba cada $k$ de $2$ a $n/2$ ; si $k$ es primo y $n-k$ es primordial pasa a la siguiente $n$ pero si pasa a través de todos los $k$ se detiene. Por tanto, esta máquina de Turing se detendrá si y sólo si la conjetura de Goldbach es falsa. Para decidir si se detendrá, su análisis tendrá que decidir la conjetura de Goldbach.

Y cuando hayas terminado con esa, hay muchas otras conjeturas que podrías comprobar con una máquina de Turing.

Answer 4

Un potencial Castor Ocupado tiene tres posibilidades:

1. Es fácil demostrar que se detiene
2. Es fácil demostrar que nunca se detiene
3. Es difícil demostrar cualquiera de los dos casos

El número 1 o bien se detiene rápidamente, o bien tiene un patrón de repetición con un eventual fallo que hace que se detenga.

El número 2 tiene un patrón que se repite y nunca tiene un fallo, lo que hace que continúe para siempre.

El número 3 es el caso interesante. Su comportamiento es caótico. Puede tener patrones a corto plazo, pero no tiene patrones a largo plazo. Sus estados futuros pueden predecirse a corto plazo sin necesidad de hacer funcionar la máquina. Llega un punto en el que no se puede predecir su comportamiento sin hacerla funcionar. En este punto se necesita una máquina capaz de emular a la máquina de Turning pero más rápida. Sin embargo, también se llegará al mismo problema con esta hipotética nueva máquina, siempre que tenga una potencia finita, que es lo que tienen todas las máquinas del mundo real.

Si se mejora el análisis de Busy Beavers, se puede decidir si ciertos candidatos son realmente el caso 1 o el caso 2. Podemos pensar en ello como un espectro de comportamiento con la parada en 0, la ejecución para siempre en 2 y la indecidibilidad en 1. Para empezar, sabemos que de 0 a 0,5 se detendrá (caso 1) y de 1,5 a 2 se ejecutará para siempre (caso 2), siendo 0,5 a 1,5 indecidible sin ejecutarlo (caso 3). Mejoramos nuestra comprensión de Busy Beavers. Ahora sabemos que de 0 a 0,95 se detendrá y de 1,05 a 2 se ejecutará para siempre, siendo 0,95 a 1,05 indecidible.

En algún momento, no hay forma de predecir sin hacer funcionar la máquina si se detendrá o no. La única manera de determinar su comportamiento es ejecutarla, y si se detiene, normalmente no te da ninguna idea que puedas utilizar para otros posibles Busy Beavers. Si no se detiene después de $10^6$ ciclos, puede probar $10^7$ entonces $10^8$ y así sucesivamente. En algún momento te rindes sin saber si se detendrá si se le da el tiempo suficiente.

El problema es similar a dibujar un conjunto de Mandelbrot. Ciertos puntos "escapan" al infinito rápidamente, otros se asientan en un patrón de repetición rápidamente. Los puntos de la frontera del conjunto de Mandelbrot son difíciles de predecir sin calcularlos. Existen métodos para facilitar la decisión, pero siempre habrá un comportamiento caótico entre los dos resultados fácilmente detectables que no se pueden predecir.

Espero haber respondido al "por qué". Luego, el "cuándo" lo determinará tu comprensión del problema específico que intentas resolver y la potencia de la máquina que utilizas. Con el tiempo podemos comer en el caos y hacerlo decidible, pero crece mucho más rápido de lo que podemos resolver.

Answer 5

Me gustaría ofrecer una forma alternativa de pensar en el problema de halting, que me ayudó a entender mejor por qué el problema de halting es no computable, o mejor, por qué en general hay funciones que son no computables.

En su famoso artículo sobre la Computabilidad, Turing menciona que va a demostrar que hay números reales que no son computables. Los números computables se definen como aquellos cuyos decimales son calculables por medios finitos, o en otras palabras, decimales que pueden ser computados por una máquina.

También menciona que es igualmente fácil definir e investigar funciones computables en lugar de números computables y eso es lo que me gustaría mostrar. Informaré en breve de la conferencia del enlace que ya he publicado ( https://www.youtube.com/watch?v=9JeIG_CsgvI&index=14&list=FLIknGRIW8gX2yutAMeHVEKw ) porque creo que vale la pena: es efectivamente la primera parte de una conferencia que demuestra el primer Teorema de Incompletitud de Goedel. Los créditos van a "UC Davis Academics" por supuesto.

Definamos una función $f$ de enteros no negativos al conjunto $\{0,1\}$ . Dejamos que $Q$ sea el conjunto de todas esas funciones. Es evidente que $Q$ es infinito (demostraremos que, de hecho, es incontablemente infinito).

También una función $f$ en $Q$ se define como computable si existe un programa de ordenador $P$ (en términos generales, una máquina de Turing), que puede tomar cualquier número entero no negativo $x$ y la salida $f(x)$ . Añadimos las restricciones que $P$ debe terminar siempre en un tiempo finito y $P$ debe ser correcto, en otras palabras emitir el valor correcto de $f$ para todos los enteros no negativos.

Dejamos que $A$ sean todas las funciones de $Q$ que son computables. Podemos demostrar que existe una función en $Q$ que no está en $A$ es decir, existen funciones no computables.

Definimos un programa como una serie de sentencias finitas sobre un alfabeto finito $\alpha$ En otras palabras, se puede pensar en una sola cadena finita. Supongamos que el lenguaje $L$ que utilizamos para expresar nuestro programa es Turing completo, es decir, puede utilizarse para simular cualquier máquina de Turing.

Podemos empezar a enumerar por orden de longitud las cadenas expresables en $\alpha$ . Las cadenas de la misma longitud se toman en base a un orden alfabético que puede definirse arbitrariamente en $\alpha$ .

En efecto, se podría escribir un programa $T$ para enumerar todas las cadenas expresables en $\alpha$ por lo que para cualquier cadena $s$ expresable en $\alpha$ , $T$ en un tiempo finito generará $s$ .

Por lo tanto, tiene una lista $Z$ de cadenas en $\alpha$ ordenados por su longitud. Algunas de esas cadenas en $Z$ serán programas legítimos en el lenguaje de programación que hayamos elegido $L$ . De hecho, todos los programas posibles estarán en $Z$ y en particular los programas que computan funciones en $A$ deben estar todos (por definición de función computable) y están ordenados en $Z$ .

Llamemos a $H$ esta lista ordenada de funciones en $A$ , $\{f_{1}, f_{2},...\}$ . Aplicando ahora el método de diagonalización, definiendo $$g(x)=1-f_{i}(i)$$ Es fácil ver que $g$ está en $Q$ Sin embargo $g$ no es computable ya que no está en $A$ Y así hemos terminado.