¿Existe una prueba más intuitiva de la indecidibilidad del problema de detención que la diagonalización?

30

Entiendo la prueba de la indecidibilidad del problema de detención (dada, por ejemplo, en el libro de texto de Papadimitriou), basada en la diagonalización.

Si bien la prueba es convincente (entiendo cada paso), no es intuitiva para mí en el sentido de que no veo cómo alguien la derivaría, comenzando solo por el problema.

En el libro, la prueba es así: "supongamos que resuelve el problema de detención en una entrada , es decir, decide si la máquina Turing detiene para la entrada . Construya una máquina Turing que tome una máquina Turing como entrada , ejecuta e invierte la salida ". Luego muestra que no puede producir una salida satisfactoria.MHM x D M M H ( M ; M ) D ( D )M;xMxDMMH(M;M)D(D)

Es la construcción aparentemente arbitraria de , particularmente la idea de alimentar a sí mismo, y luego a sí mismo, por lo que me gustaría tener una intuición. ¿Qué llevó a las personas a definir esas construcciones y pasos en primer lugar?M DDMD

¿Alguien tiene una explicación sobre cómo alguien razonaría su camino hacia el argumento de la diagonalización (o alguna otra prueba), si no conocieran ese tipo de argumento para comenzar?

Anexo dado la primera ronda de respuestas:

Entonces, las primeras respuestas señalan que demostrar la indecidibilidad del problema de detención fue algo basado en el trabajo previo de Cantor y Russell y el desarrollo del problema de diagonalización, y que comenzar "desde cero" simplemente significaría tener que redescubrir ese argumento.

Lo suficientemente justo. Sin embargo, incluso si aceptamos el argumento de la diagonalización como algo bien entendido, todavía encuentro que hay una "brecha de intuición" desde el problema de detención. La prueba de Cantor de la incontabilidad de los números reales me parece bastante intuitiva; La paradoja de Russell aún más.

Lo que todavía no se ve es lo que podría motivar a alguien para definir sobre la base de 'auto-aplicación' 's , y luego aplicar de nuevo a sí mismo. Eso parece estar menos relacionado con la diagonalización (en el sentido de que el argumento de Cantor no tenía algo parecido), aunque obviamente funciona bien con la diagonalización una vez que los define.M M ; M DD(M)MM;MD

PD

@babou resumió lo que me preocupaba mejor que yo: "El problema con muchas versiones de la prueba es que las construcciones parecen sacadas de un sombrero mágico".

usuario118967
fuente
3
Considere la posibilidad de que cualquier prueba de la existencia de conjuntos incontables tenga que ser algo contradictorio, incluso si nos acostumbramos al hecho de que son correctos . Considere también la posibilidad de que esta pregunta (si se reformula correctamente) pertenece a math.stackexchange.com .
André Souza Lemos
44
Cantor encontró el argumento de la diagonalización, y ahora no podemos desaprenderlo: Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können .
Hendrik ene
1
Después de pensarlo más, debo preguntarle por qué cree que esto es tan diferente de la paradoja de Russell. La paradoja de Russell incluso se ve igual si usamos la notación para significar (es decir, pensamos que los conjuntos son funciones cuyos valores son o ). Entonces la paradoja de Russell es definir , y luego considerar . X SS(X)XStruefalseD(M) = not M(M)D(D)
1
La diagonalización es una técnica estándar . Claro que hubo un momento en que no se conocía, pero ha sido estándar durante mucho tiempo ahora, por lo que su argumento se debe simplemente a su ignorancia (no quiero ser grosero, es un hecho: no lo sabía todas las demás pruebas que utilizan dicha técnica y, por lo tanto, la encuentran extraña la primera vez que la ve. Cuando la haya visto 50 veces, probablemente podrá comprender cómo se puede aplicar en una nueva situación).
Bakuriu
1
Tal vez leerías mi intercambio de comentarios con Luke Mathieson (siguiendo su respuesta). Su respuesta explica históricamente por qué Turing usó la auto aplicación (una cosa que usted pide en su pregunta). Parece ser más o menos cómo los matemáticos percibieron los problemas en ese momento. Mi propia respuesta trata de dar una prueba muy simple de que no la usa (o al menos muestra que no es esencial), que es otra cosa que pides, bastante diferente. Posiblemente, podría hacerlo aún más simple que en mi respuesta. ¿Por qué los maestros todavía usan la prueba de Turing es un problema sociológico y pedagógico (?!) cc @HendrikJan
babou

Respuestas:

18

En tu edición, escribes:

Lo que todavía no se ve es lo que podría motivar a alguien para definir sobre la base de 'auto-aplicación' 's , y luego aplicar de nuevo a sí mismo. Eso parece estar menos relacionado con la diagonalización (en el sentido de que el argumento de Cantor no tenía algo parecido), aunque obviamente funciona bien con la diagonalización una vez que los define.M M ; M DD(M)MM;MD

Un resumen "popular" común de la prueba de Turing es algo así:

"Si tuviéramos una máquina que pudiera decidir si otra máquina de Turing se detiene o no, podríamos usar esto para construir otra máquina que, dada una máquina de Turing , se detendría si y solo si no se detuviera. Pero entonces podríamos pasar como entrada para sí mismo, y así obtener una paradoja: ¡esta máquina se detendría si y solo si no se detuviera! " D M M DMHDMMD

Ahora, es fácil ver que el resumen anterior pasa por alto un detalle importante: ¡la detención de la máquina Turing también depende de su entrada, que no hemos especificado! Pero este problema se puede solucionar fácilmente: solo necesitamos que elija alguna entrada adecuada para cada máquina de entrada , antes de pasar ambas a .D x M M M HMDxMMMH

¿Cuál es una opción adecuada para , dado que finalmente queremos derivar una contradicción? Bueno, una opción natural es sugerida directamente por la prueba "manual" anterior, donde finalmente obtenemos la contradicción al ejecutar la máquina sobre sí misma. DxMD

Por lo tanto, para que el comportamiento de sea ​​realmente paradójico en este caso, es decir, cuando se invoca como , lo que queremos es que la detención de D ( M ) dependa del comportamiento de M cuando se invoca como M ( M ) . De esta manera, vamos a obtener la contradicción que queremos estableciendo M = D .D ( D )DD(D)D(M)M M(M)M=D

Eso sí, esta no es la única opción; también podríamos haber derivado la misma contradicción, por ejemplo, construyendo una máquina tal manera que D ' ( M ) se detenga si y solo si M ( D ' ) (en lugar de M ( M ) ) no se detiene. Pero, aunque está claro que la máquina D puede duplicar fácilmente su entrada antes de pasarla a M H , no es tan obvio cómo construir una máquina D ' que invoque a M H con su propio código como entrada. Por lo tanto, usando estoDD(M)M(D)M(M)DMHDMH lugar de D complicaría innecesariamente la prueba y la haría menos intuitiva.DD

Ilmari Karonen
fuente
1
¡Guau, realmente has asimilado mi pregunta! ¡Ese es exactamente el tipo de historia que estaba buscando! Todavía estoy leyendo todo, pero parece que sería la respuesta aceptada. ¡Gracias!
user118967
18

Puede ser simplemente que es un error pensar que alguien razonaría su camino hacia este argumento sin hacer un argumento similar en algún momento anterior, en un contexto "más simple".

Recuerde que Turing conocía la prueba de diagonalización de Cantor de la incontabilidad de los reales. Además, su trabajo es parte de una historia de las matemáticas que incluye la paradoja de Russell (que usa un argumento de diagonalización) y el primer teorema de incompletitud de Gödel (que usa un argumento de diagonalización). De hecho, el resultado de Gödel está profundamente relacionado con la prueba de indecidibilidad del problema de detención (y, por lo tanto, la respuesta negativa al problema Entscheidungsproblem de Hilbert).

Entonces, mi argumento es que su pregunta está, en cierto sentido, mal fundada y que no puede alcanzar el Problema de detención sin pasar primero el resto (o algo notablemente similar). Si bien les mostramos estas cosas a los estudiantes sin pasar por la historia, si usted fuera un matemático que trabajara, parece poco probable que pase de la nada a las Máquinas de Turing sin nada en el medio; el objetivo de ellas era formalizar la computación, un problema que mucha gente tenía estado trabajando durante décadas en ese momento.

Cantor ni siquiera usó la diagonalización en su primera prueba de la incontabilidad de los reales, si tomamos las fechas de publicación como una aproximación de cuándo pensó en la idea (no siempre es algo confiable), le llevó unos 17 años saberlo que los reales eran incontables, para resolver el argumento de la diagonalización.

En referencia a la "autoaplicación" en la prueba que mencionas, esto también es una parte integral de la paradoja de Russell (que depende completamente de la auto-referencia), y el primer teorema de incompletitud de Gödel es como la versión de alto poder de la paradoja de Russell . La prueba de la indecidibilidad del problema de detención está tan fuertemente informada por el trabajo de Gödel que es difícil imaginar llegar allí sin ella, por lo tanto, la idea de "autoaplicación" ya es parte del conocimiento básico que necesita para llegar al problema de detención. . Del mismo modo, el trabajo de Gödel es una reelaboración de la paradoja de Russell, por lo que no se llega sin la otra (tenga en cuenta que Russell no fue el primero en observar una paradoja como esta, por lo que los prototipos del argumento de la diagonalización han existido en la lógica formal desde aproximadamente 600 AEC). Tanto el trabajo de Turing como el de Gödel (las partes de las que estamos hablando aquí) pueden verse como demostraciones cada vez más poderosas de los problemas con la autorreferencia, y cómo se está incrustando en las matemáticas. Entonces, una vez más, es muy difícil sugerir que estas ideas en el nivel que Turing estaba tratando con ellas surgierona priori , fueron la culminación del trabajo de milenios en partes de filosofía, matemáticas y lógica.

Esta autorreferencia también es parte del argumento de Cantor, simplemente no se presenta en un lenguaje tan poco natural como el trabajo más fundamentalmente lógico de Turing. La diagonalización de Cantor se puede reformular como una selección de elementos del conjunto de potencia de un conjunto (esencialmente parte del Teorema de Cantor). Si consideramos el conjunto de reales (positivos) como subconjuntos de los naturales (tenga en cuenta que realmente no necesitamos que se ordenen los dígitos para que esto funcione, simplemente hace una presentación más simple) y afirmamos que hay un surjection de los naturales para los reales, entonces podemos producir un elemento del conjunto de poder (es decir, un real) que no está en la imagen de la sorpresa (y, por lo tanto, derivar una contradicción) al tomar este elemento como el conjunto de naturales que no están en su propio imagen debajo del surjection. Una vez que lo expresamos de esta manera, '

Luke Mathieson
fuente
2
Sí, parece que el objetivo de Turing era recrear la circularidad (de la que proviene la diagonalización) utilizando máquinas, en aras de introducir alguna idea abstracta del tiempo , con la que hablar sobre la finitud de una nueva manera.
André Souza Lemos
Tal vez puedas iluminarme, ya que no estoy familiarizado con algunas de estas pruebas. Puedo entender que estas pruebas se pueden crear utilizando autorreferenciación. Incluso puedo creer (aunque podría necesitar una prueba) que siempre hay alguna auto referencia en cualquier estructura construida para ese propósito. Pero no veo la necesidad de usarlo explícitamente para llevar a cabo la prueba hasta su conclusión. Puede reformular el argumento de Cantor de esa manera, pero no tiene que hacerlo. Y no veo por qué tienes que hacerlo por el problema de detención. Puede que haya perdido un paso, pero ¿cuál?
babou
Para aclarar mi comentario anterior, la pregunta original es : " ¿Existe una prueba más intuitiva de la indecidibilidad del problema de detención ... ". Estoy omitiendo el final, ya que siento que el OP se queja principalmente de la falta de intuición. Creo que, de hecho, hay una prueba más intuitiva, que no utiliza autorreferencia. Puede pensar que usar esa prueba es pedagógicamente imprudente (ya que no está relacionado con el trabajo de Russell y Gödel), pero si responde a la pregunta, ¿cuál es el punto de rechazarla? Parece que estás negando la pregunta en lugar de responderla.
babou
@babou Creo que el problema aquí es que estamos respondiendo diferentes preguntas. El OP no estaba bien redactado en ese sentido, supongo. La pregunta repetida en el cuerpo del OP me parece ser "¿cómo pensó alguien alguna vez el argumento de la diagonalización para probar ..." (parafraseado, por supuesto), y que "las construcciones parecen sacadas de un sombrero mágico"? .
Luke Mathieson
@babou, también para elaborar un poco, con un teclado adecuado, no creo que de una forma u otra sea necesariamente pedagógicamente útil (dependería en gran medida del contexto). De hecho, para la mayoría de los cursos de CS modernos, probablemente sea mejor hacerlo sin el argumento de la diagonalización, la mayoría de los estudiantes de CS simplemente ya no tienen la inclinación matemática suficiente para conocer los antecedentes que facilitarían la comprensión, pero definitivamente respondía pregunta que terminó el texto original del cuerpo: ...
Luke Mathieson
9

La auto aplicación no es un ingrediente necesario de la prueba

En una palabra

Si hay una máquina de Turing que resuelve el problema de detención, entonces desde esa máquina podemos construir otra máquina de Turing L con un comportamiento de detención (función característica de detención) que no puede ser el comportamiento de detención de ninguna máquina de Turing.HL

La paradoja construida sobre la función autoaplicada (llamada L en esta respuesta, perdón por las inconsistencias de notación) no es un ingrediente necesario de la prueba, sino un dispositivo utilizable con la construcción de una contradicción específica, ocultando lo que parece ser el "verdadero propósito "de la construcción. Probablemente por eso no es intuitivo.DL

Parece más directo mostrar que solo hay un número innumerable de comportamientos de detención (no más que las máquinas de Turing), que se pueden definir como funciones de detención características asociadas con cada máquina de Turing. Se puede definir constructivamente una función de detención característica que no está en la lista, y construir a partir de ella, y desde una máquina que resuelve el problema de detención, una máquina L que tiene esa nueva función de detención característica. Pero dado que, por construcción, no es la función de detención característica de una máquina de Turing, L no puede ser una. Como L está construido a partir de H utilizando técnicas de construcción de máquinas de Turing, H no puede ser una máquina de Turing.HLLLHH

La autoaplicación de a sí misma, utilizada en muchas pruebas, es una forma de mostrar la contradicción. Pero solo funciona cuando la función de detención característica imposible se construye a partir de la diagonal de la lista de funciones de detención características permitidas por Turing, volteando esta diagonal (intercambiando 0 y 1 ). Pero hay infinitas maneras de construir una nueva función de detención característica. Entonces la no-Turing-ness ya no se puede evidenciar con una paradoja mentirosa (al menos no simplemente). La construcción de la aplicación automática no es intuitiva porque no es esencial, pero se ve resbaladiza cuando se saca del sombrero mágico.L01

Básicamente, no es una máquina de Turing porque está diseñada desde el principio para tener un comportamiento de detención que no es el de una máquina de Turing, y que se puede mostrar más directamente, por lo tanto, de manera más intuitiva.L

Nota : Puede ser que, para cualquier elección constructiva de la función de detención característica imposible, haya una reordenación computable de la enumeración de la máquina de Turing de modo que se convierta en diagonal (no lo sé). Pero, en mi opinión, esto no cambia el hecho de que la autoaplicación es una técnica de prueba indirecta que oculta un hecho más intuitivo e interesante.

Análisis detallado de las pruebas.

No voy a ser histórico (pero gracias a quienes lo son, lo disfruto), pero solo estoy tratando de trabajar el lado intuitivo.

Creo que la presentación dada a @vzn , que encontré hace mucho tiempo (lo había olvidado), en realidad es bastante intuitiva e incluso explica la diagonalización del nombre. Lo repito en detalles solo porque siento que @vzn no enfatizó lo suficiente su simplicidad.

Mi propósito es tener una forma intuitiva de recuperar la prueba, sabiendo eso de Cantor. El problema con muchas versiones de la prueba es que las construcciones parecen sacadas de un sombrero mágico.

La prueba que doy no es exactamente la misma que en la pregunta, pero es correcta, por lo que puedo ver. Si no cometí un error, es lo suficientemente intuitivo ya que podría recuperarlo después de más años de los que me gustaría contar, trabajando en problemas muy diferentes.

El caso de los subconjuntos de (Cantor)N

La prueba de Cantor supone (es solo una hipótesis) que hay una enumeración de los subconjuntos de los enteros, de modo que todo el subconjunto puede describirse por su función característica C j ( i ), que es 1 si i S j y es 0 de lo contrario.SjCj(i)1iSj0

Esto puede verse como una tabla , tal que T [ i , j ] = C j ( i )TT[i,j]=Cj(i)

Luego, considerando la diagonal, construimos una función característica tal que D ( i ) = ¯ T [ i , i ] , es decir, es idéntica a la diagonal de la tabla con cada bit invertido al otro valor.DD(i)=T[i,i]¯

La diagonal no tiene nada de especial, excepto que es una manera fácil de obtener una función característica que sea diferente de todas las demás, y eso es todo lo que necesitamos.D

Por lo tanto, el subconjunto caracterizado por no puede estar en la enumeración. Ya que sería cierto para cualquier enumeración, no puede haber una enumeración que enumera todos los subconjuntos de N .DN

Esto es ciertamente, de acuerdo con la pregunta inicial, bastante intuitivo. ¿Podemos hacer que la prueba del problema de detención sea intuitiva?

El caso del problema de detención (Turing)

Asumimos que tenemos una enumeración de máquinas de Turing (que sabemos que es posible). El comportamiento de detención de una máquina de Turing se puede describir por su función de detención característica H j ( i ) que es 1 si M j se detiene en la entrada i y es 0 en caso contrario.MjHj(i)1Mji0

Esto puede verse como una tabla , tal que T [ i , j ] = H j ( i )TT[i,j]=Hj(i)

DD(i)=T[i,i]¯

D

D

THj

HH(i,j)Hj(i)

HLDLHL(i)H(i,i)H(i,i)1L(i)

LHDLH

Deliberadamente imité la primera prueba y entré en pequeños detalles

Mi sensación es que los pasos vienen naturalmente de esta manera, especialmente cuando uno considera que la prueba de Cantor es razonablemente intuitiva.

Primero se enumeran los constructos litigiosos. Luego, uno toma y modifica la diagonal como una forma conveniente de tocarlos a todos para obtener un comportamiento no contabilizado, luego obtiene una contradicción al exhibir un objeto que tiene el comportamiento no explicado ... si alguna hipótesis fuera cierta: existencia de la enumeración para Cantor y la existencia de un oráculo de detención computable para Turing.

DTTLDL(i)HH(i,i)

Comparación con la "otra" prueba

LD

Solo lo construimos de tal manera que tenga una función de detención característica que no corresponde a ninguna máquina de Turing, y obtenemos directamente una contradicción de eso. Esto nos da la libertad de no usar la diagonal (por lo que vale).

LjLL=MjLL(jL)T[jL,jL]=H(jL,jL)=1L(jL)L(jL)T[jL,jL]=H(jL,jL)=0L(jL)LL no puede ser una máquina de Turing porque está construida para tener una función de detención característica que no es la de una máquina de Turing.

Un punto secundario es que esta prueba habitual sería mucho más dolorosa si no eligiéramos la diagonal, mientras que el enfoque directo utilizado anteriormente no tiene ningún problema. Si eso puede ser útil, no lo sé.

babou
fuente
¡Muy bonito, gracias! Parece que de alguna manera lograste sortear las construcciones autoaplicadas que encontré problemáticas. Ahora me pregunto por qué la gente los consideró necesarios en primer lugar.
user118967
@ user118967 Traté de subrayar que usar la diagonal no es realmente importante. Todo lo que desea es definir una función de detención característica que sea diferente de todas las enumeradas en la tabla, y que sea computable de las enumeradas, siempre que tengamos un oráculo de detención. Hay infinitas funciones de detención tan características. Ahora, eso no parece tan visible en la prueba habitual, y puede ser que algunas construcciones de esa prueba parezcan arbitrarias simplemente porque lo son, como elegir la diagonal en la prueba anterior. Es simple, no esencial.
babou
@ user118967 Agregué una introducción que resume el análisis de varias pruebas. Complementa la comparación entre pruebas (con y sin aplicación propia) que se da al final. No sé si eliminé la diagonalización como se me pidió :) (creo que sería injusto decirlo), pero sí insinúo cómo eliminar la diagonal obvia. Y la prueba no utiliza la autoaplicación, lo que parece un truco innecesario, pero de aspecto ingenioso, que oculta lo que puede parecer un problema más importante, el comportamiento de detención.
babou
@ user118967 Para responder a su primer comentario, y después de leer la respuesta más votada, parece que la motivación principal es el vínculo con el trabajo de Russell y Gödel. Ahora no tengo idea de si es realmente esencial para ese propósito, y la variante de construcciones autoaplicadas ciertamente puede estudiarse para ese propósito, pero no veo el punto de imponerla a todos. Además, la prueba más directa parece más intuitiva y ofrece la herramienta para analizar más a fondo la versión de aplicación automática. ¿Porqué entonces?
babou
Sí, tiendo a estar de acuerdo contigo en eso.
user118967
8

También hay una prueba de este hecho que utiliza una paradoja diferente, la paradoja de Berry, que escuché de Ran Raz.

B(n)nS(n)nB(n)S(n)

Considere el siguiente programa:

  1. n

  2. L

  3. L

B(n)nO(logn)nO(logn)ClognNClogNNNB(N)B(N)

La misma idea se puede utilizar para probar los teoremas de incompletitud de Gödel, como lo muestran Kritchman y Raz .

Yuval Filmus
fuente
Tal vez sea en el artículo que cito, o en la monografía clásica Kolmogorov Complexity de Li y Vitányi.
Yuval Filmus
Por cierto, ¿crees que este método proporciona un ataque al problema NP vs CoNP?
Mohammad Al-Turkistany
No. Tales problemas están más allá de nosotros en este momento.
Yuval Filmus
n
nnn
6

Hay una idea más general involucrada aquí llamada "teorema de recursión" que puede ser más intuitiva: las máquinas de Turing pueden usar su propia descripción (y así ejecutarse). Más precisamente, hay un teorema:

Para cualquier máquina de Turing T, hay una máquina de Turing Rque calcula R(x) = T(R;x).

Si tuviéramos una máquina de Turing que pudiera resolver el problema de detención, entonces, usando la idea descrita anteriormente, podemos construir fácilmente una variedad de máquinas de mentiroso "mentiroso": por ejemplo, en notación similar a la pitón,

def liar():
    if halts(liar):
        return not liar()
        # or we could do an infinite loop
    else:
        return True

El argumento más complicado es esencialmente tratar de hacer esto directamente sin apelar al teorema de recursión. Es decir, está repitiendo una receta para construir funciones "autorreferenciales". Por ejemplo, dada una máquina de Turing T, aquí hay una de esas recetas para construir una máquina Rsatisfactoria

R(x) = T(R; x)

Primero, defina

S(M; x) = T(M(M; -); x)

donde M(M; -), lo que realmente quiero decir es que calculamos (usando la descripción de M) y conectamos una descripción de una máquina de Turing que, en la entrada y, evalúa M(M; y).

Ahora, se observa que si nos conectamos Sen sí mismo

S(S; x) = T(S(S; -); x)

obtenemos la duplicación que queremos. Entonces si establecemos

R = S(S; -)

entonces tenemos

R(x) = T(R; x)

como se desee.


fuente
El primer párrafo no coincide con el teorema que cita, que conozco por el nombre del teorema smn.
Raphael
@Raphael: Se llama teorema de recursión en mi libro de texto. :( Mi breve intento en google no pudo
Sin preocupaciones; tal vez te entiendo mal, o hay diferentes nombres para la misma cosa. Dicho esto, su oración "Las máquinas de Turing pueden usar su propia descripción" no es compatible con el teorema que cita. De hecho, creo que está mal: si la función que calcula una TM dependiera de su índice, ¿cómo serían todas las infinitas TM que calculan la misma función?
Raphael
TliarTruenot liar()False
TRR(x)=T(R;x)TRR(x)=T(R;x)
5

la prueba de Turing es bastante similar a la prueba de Cantors de que la cardinalidad de los reales ("incontable") es mayor que la cardinalidad de los racionales ("contables") porque no se pueden poner en correspondencia 1-1 pero esto no se nota / enfatiza en muchas referencias (¿alguien sabe alguna?) (iirc) un profesor de CS mostró una vez esto hace años en clase (no estoy seguro de dónde lo consiguió él mismo). en la prueba Cantors uno se puede imaginar una cuadrícula con dimensión horizontal del n º dígito del número y la dimensión vertical del n º número del conjunto.

la construcción a prueba de detención Turing es bastante similar, excepto que el contenido de la tabla son Halt / Nonhalt para 1/0 en su lugar, y el eje horizontal es n º de entrada, y el eje vertical es n º programa de ordenador. en otras palabras, la combinación de programas de computadora y entradas son contables, pero la tabla / matriz infinita es incontable en base a una construcción de simulador de máquina universal que puede "voltear" un caso de detención a un caso no mortal suponiendo que exista una máquina detectora de detención (por lo tanto, reductio ad absurdam ) .

Alguna evidencia de que Turing tenía en mente la construcción de Cantors es que su mismo documento con la prueba de detención habla de números computables como (a lo largo de las líneas de) números reales con dígitos computables.

vzn
fuente
Además, existe una forma muy "intuitiva" de ver la indecidibilidad, pero requiere mucha matemática superior para comprender (es decir, la intuición de un neófito es muy diferente a la intuición de un experto). los matemáticos sí consideran el problema de detención y las pruebas idénticas a través de un teorema de punto fijo de Lawvere, pero este es un hecho avanzado que no es muy accesible para los estudiantes "todavía". ¿Ves un problema de detención, conjuntos no calificables, un problema matemático común? Informática teórica y publicación vinculada también para los árbitros
vzn
3

En este punto, vale la pena señalar el trabajo de Emil Post, a quien (justamente) se le atribuye ser un co-descubridor de los resultados básicos de la computabilidad, aunque lamentablemente se publicó demasiado tarde para ser considerado un co-descubridor de la solución al problema Entscheidungsproblem . Ciertamente participó en la elaboración de la llamada tesis de Church-Turing .

Post fue motivado por consideraciones muy filosóficas, a saber, las limitaciones teóricas de la capacidad humana para calcular, o incluso obtener respuestas precisas de manera consistente . Él ideó un sistema, ahora llamado sistemas post-canónicos , cuyos detalles no son importantes, y afirmó que podría usarse para resolver cualquier problema que pueda resolverse de manera adversa mediante la manipulación de símbolos . Curiosamente, él consideró explícitamente que los estados mentales eran parte de la "memoria" explícitamente, por lo que es probable que al menos considerara su modelo de computación como un modelo del pensamiento humano en su totalidad.

El problema Entscheidungs ​​considera la posibilidad de utilizar dicho medio de cálculo para decir, determinar la teoría de cualquier proposición expresable en el sistema de los Principia Mathematica . ¡Pero el PM era un sistema diseñado explícitamente para poder representar todo el razonamiento matemático y, por extensión (al menos en ese momento, cuando el Logicismo todavía estaba en boga) todo el razonamiento humano!

Por lo tanto, es muy sorprendente, entonces, dirigir la atención de tal sistema a los propios sistemas canónicos del Post, al igual que la mente humana, a través de los trabajos de Frege, Russel y los lógicos del cambio de siglo, habían centrado su atención en la facultad de razonamiento. de la mente humana misma.

Entonces, está claro en este punto, que la autorreferencia, o la capacidad de los sistemas para describirse a sí mismos, era un tema bastante natural a principios de la década de 1930. De hecho, David Hilbert esperaba "arrancar" el razonamiento matemático en sí mismo, al proporcionar una descripción formal de todas las matemáticas humanas, que luego podrían demostrarse matemáticamente que son consistentes.

Una vez que se obtiene el paso de usar un sistema formal para razonar sobre sí mismo, es un salto y un salto lejos de las paradojas habituales autorreferenciales (que tienen una historia bastante antigua ).

Dado que se supone que todas las declaraciones en Principia son "verdaderas" en algún sentido metafísico, y los Principia pueden expresar

programa pdevuelve resultado trueen entradan

Si existe un programa para decidir todos los teoremas en ese sistema, es bastante simple expresar directamente la paradoja del mentiroso:

Este programa siempre miente.

puede ser expresado por

El programa psiempre devuelve lo contrario de lo que dice el principio matemático p.

La dificultad es construir el programa p. Pero en este punto, es bastante natural considerar la oración más general

El programa psiempre devuelve lo contrario de lo que dice el PM q.

por alguna arbitraria q. ¡Pero es fácil de construir p(q)para cualquiera q! Simplemente calcule lo que PM predice que generará y devuelva la respuesta opuesta. Sin embargo, no podemos reemplazar qpor pen este punto, ya que ptoma qcomo entrada y qno (no toma entrada). Vamos a cambiar nuestra oración para que p hace de entrada para llevar:

El programa pdevuelve lo contrario de lo que PM dice q(r)que regresará.

Arg! Pero ahora ptoma 2 entradas: qy r, mientras que qsolo toma 1. Pero espere: queremos pen ambos lugares de todos modos, por rlo que no es una nueva información, ¡sino la misma información nuevamente, es decir q! Esta es la observación crítica.

Entonces finalmente tenemos

El programa pdevuelve lo contrario de lo que PM dice q(q)que regresará.

Olvidémonos de este tonto negocio de "PM dice", y tenemos

El programa p(q)devuelve lo contrario de lo q(q)que volverá.

Este es un programa legítimo siempre que tengamos un programa que siempre nos diga qué q(q)retorna . Pero ahora que tenemos nuestro programa p(q), podemos sustituir qpor py obtener la paradoja de nuestra mentiroso.

cody
fuente