Prueba de imposibilidad

Una de las primeras pruebas de imposibilidad conocidas: la demostración de que ${\displaystyle {\sqrt {2}}}$ no se puede expresar como el cociente de dos números enteros ${\displaystyle (a/b)}$

Una prueba de imposibilidad, también conocida como prueba negativa, prueba de un teorema de imposibilidad, o resultado negativo, es una demostración mediante la que se concluye que un problema particular no se puede resolver como se describe en su enunciado, o que un conjunto particular de problemas no se puede resolver en general.^[1]​ Algunas de estas pruebas han permanecido a la espera de resolución durante décadas o incluso siglos de trabajo. Comprobar que algo es imposible suele ser mucho más difícil que la tarea opuesta; ya que a menudo es necesario desarrollar una teoría en la que se apoya la demostración.^[2]​ Los teoremas de imposibilidad generalmente se pueden expresar como proposiciones de existencia negativas o proposiciones universales en lógica (véase cuantificador universal).

Visión general

Quizás una de las pruebas de imposibilidad más antiguas es la de la irracionalidad de la raíz cuadrada de 2, que demuestra que es imposible expresar la raíz cuadrada de 2 como un cociente de números enteros. Otra famosa prueba de imposibilidad fue publicada en 1882 por Carl Louis Ferdinand von Lindemann, demostrando que el antiguo problema de la cuadratura del círculo no se puede resolver,^[3]​ porque el número π es transcendente (es decir, no algebraico) y solo un subconjunto de números algebraicos puede construirse con regla y compás. Otros dos problemas clásicos, la trisección del ángulo y la duplicación del cubo mediante construcciones con regla y compás, también se demostró rigurosamente en el siglo XIX que no tienen solución.

Un problema que surgió en el siglo XVI fue el de crear una fórmula general usando radicales que expresen la solución de cualquier ecuación polinomial de grado dado k, donde k≥5. En la década de 1820, el teorema de Abel-Ruffini (también conocido como el teorema de imposibilidad de Abel) demostró que esto era imposible,^[4]​ usando conceptos como el de grupo resoluble de la teoría de Galois, un nuevo subcampo del álgebra abstracta.

Entre las pruebas de imposibilidad más importantes del siglo XX figuran las relacionadas con el problema de indecibilidad, que demostraron que existen problemas que en general no pueden ser resueltos por ningún algoritmo, siendo el más famoso el problema de la parada. Otros hallazgos relacionados de manera similar son los teoremas de incompletitud de Gödel, que evidencian algunas limitaciones fundamentales en la posibilidad de disponer de pruebas independientes en los sistemas formales.^[5]​

En teoría de la complejidad computacional, técnicas como la relativización (véase máquina oráculo) proporcionan pruebas débiles de imposibilidad excluyendo ciertas técnicas de prueba. Otras técnicas, como las pruebas de completitud para una clase de complejidad, proporcionan evidencia de la dificultad de los problemas, al mostrar que son tan difíciles de resolver como otros problemas conocidos que se han demostrado intratables.

Tipos de pruebas de imposibilidad

Véase también: Demostración en matemática

Prueba por contradicción

Un tipo de prueba de imposibilidad ampliamente utilizado es la prueba por contradicción o reducción al absurdo. En este tipo de prueba, se demuestra que si algo, como una solución a una clase particular de ecuaciones, fuera posible, entonces dos cosas mutuamente contradictorias serían verdaderas, como que un número sea tanto par como impar. La contradicción implica que la premisa original es imposible.

Prueba por descenso

Artículo principal: Descenso infinito

Un tipo de prueba por contradicción es la prueba por descenso, que procede primero asumiendo que algo es posible, como una solución entera positiva^[6]​ a una clase de ecuaciones, y que por lo tanto debe haber una solución mínima. A partir de la supuesta solución más pequeña, se muestra que se puede encontrar una solución más pequeña, contradiciendo la premisa de que la primera solución era la más pequeña posible, mostrando así que la premisa original (que existe una solución) debe ser falsa.

Tipos de refutación de conjeturas de imposibilidad

Hay dos métodos alternativos para refutar una conjetura de que algo es imposible: mediante un contraejemplo (prueba constructiva) y por contradicción lógica (prueba no constructiva).

La forma obvia de refutar una conjetura de imposibilidad es proporcionando un único contraejemplo. Por ejemplo, la conjetura de la suma de potencias de Euler planteaba que en el campo de los números naturales, son necesarias al menos n potencias enésimas diferentes para sumar cualquier otra potencia n-ésima. La conjetura fue refutada en 1966, con un contraejemplo que involucra un total de solo cuatro quintas potencias diferentes sumadas para obtener otra quinta potencia:

27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵.

Una demostración por contraejemplo es un prueba constructiva, en la que se presenta un caso que refuta la afirmación. Por el contrario, una prueba no constructiva de una afirmación de imposibilidad procedería mostrando que es lógicamente contradictorio que "todos" los posibles contraejemplos sean inválidos: al menos "uno" de los elementos de una lista de posibles contraejemplos debe en realidad ser un contraejemplo válido de la conjetura de imposibilidad. Por ejemplo, una conjetura de que es imposible que una potencia irracional elevada a una potencia irracional sea racional, se puede refutar mostrando que uno de los dos posibles contraejemplos debe ser un contraejemplo válido, sin mostrar cuál es.

La existencia de números irracionales: la prueba de los pitagóricos

La prueba de Pitágoras (o más probablemente, de uno de sus alumnos) descubierta sobre el año 500 a. C. ha tenido un efecto profundo en las matemáticas. Demuestra que la raíz cuadrada de dos no se puede expresar como la proporción de dos números enteros (numerables). La prueba bifurcó "los números" en dos colecciones que no se superponen: los números racionales y los números irracionales. Esta bifurcación fue utilizada por Cantor en su método de la diagonal, que a su vez fue utilizado por Turing en su prueba de que el Entscheidungsproblem, el problema de decisión de Hilbert, es indecidible.

Se desconoce cuándo o quién descubrió el "teorema de Pitágoras". Difícilmente pudo haber hecho el descubrimiento el propio Pitágoras, pero ciertamente se hizo en su escuela. Pitágoras vivió alrededor del 570–490 a.C. Demócrito, nacido alrededor del 470 a.C., escribió sobre líneas irracionales y sólidos ...

La prueba de irracionalidad para las raíces cuadradas de los números primos hasta 17 figura en un texto clásico:

He aquí un famoso pasaje del diálogo Teeteto de Platón, en el que se establece que Teodoro (maestro de Platón) probó la irracionalidad de

${\displaystyle {\sqrt {3}},{\sqrt {5}},...,}$ analizando todos los casos separados hasta la raíz de 17...^[7]​

Ahora existe una prueba más general de que:

La raíz m-ésima de un número entero N es irracional, a menos que N sea la m-ésima potencia de un número entero n.^[8]​

Es decir, es imposible expresar la raíz m-ésima de un número entero N como la razón ^a⁄_b de dos enteros a y b, que no comparten números primos en común excepto en los casos en los que b = 1.

Construcciones imposibles buscadas por los antiguos griegos

Tres cuestiones planteadas por los geómetras de la Grecia clásica se hicieron especialmente conocidas:

1. La trisección del ángulo con regla y compás
2. La construcción de un cubo con el doble de volumen que uno dado
3. La construcción de un cuadrado de igual área que la de un círculo dado

Durante más de 2000 años se hicieron intentos infructuosos para resolver estos problemas, hasta que por fin, en el siglo XIX se comprobó que estas tres construcciones son conceptualmente imposibles.^[9]​

Un cuarto problema de los antiguos griegos era construir un polígono equilátero con un número específico de n lados, más allá de los casos básicos de n = 3, 4 y 5 que sí se sabían construir.

Todos estos son problemas de construcción euclídea, que solo son realizables si involucran únicamente números construibles (Hardy y Wright p. 159). Curiosamente, hay números irracionales que pueden ser euclidianos. Un buen ejemplo es el número irracional raíz cuadrada de 2 (la longitud de la hipotenusa de un triángulo rectángulo con catetos de una unidad de longitud), que se puede construir fácilmente con regla y compás. Siglos después de Euclides, se demostró que los números euclidianos no pueden involucrar ninguna operación más que la suma, la resta, la multiplicación, la división y la extracción de raíces cuadradas.

Trisección de un ángulo y duplicación del cubo

Tanto la trisección de un ángulo arbitrario como la duplicación del cubo requieren obtener raíces cúbicas, que no son números construibles exclusivamente con regla y compás.

Cuadratura del círculo

${\displaystyle \pi }$ no es un número construible ... y por lo tanto es imposible construir, por métodos euclidianos, una longitud igual a la de la circunferencia de un círculo de diámetro unidad.^[10]​

Existe una prueba para demostrar que cualquier número euclidiano es un número algebraico, un número que es la solución de alguna ecuación algebraica. Por lo tanto, debido a que en 1882 se demostró que ${\displaystyle \pi }$ es un número trascendente (y que por lo tanto, por definición, no es un número algebraico), queda demostrado que no es un número euclidiano. En consecuencia, la construcción de una longitud ${\displaystyle \pi }$ a partir de un círculo unitario es imposible,^[11]​ y no se puede lograr la cuadratura del área del círculo exclusivamente por métodos euclídeos.

Construcción de un polígono regular de n lados

En 1837 se publicó el teorema de Gauss-Wantzel, mediante el que se demostró que la construcción euclídea de un polígono regular de n lados es imposible para la mayoría de los valores de n.

Axioma de las paralelas de Euclides

Artículo principal: Geometría no euclídea

Nagel y Newman consideran que la cuestión implícitamente planteada en el quinto postulado de Euclides es "... quizás el desarrollo más significativo en sus efectos a largo plazo sobre la historia de la matemática posterior" (p. 9).

La pregunta es:

¿Puede el axioma de que dos líneas paralelas "... no se encontrarán ni siquiera 'en el infinito'" (nota al pie, ibid) derivarse de los otros axiomas de la geometría de Euclides?

No fue hasta el trabajo en el siglo XIX de "... Gauss, Bolyai, Lobachevski y Riemann, que se demostró la imposibilidad de deducir el axioma de las paralelas de los demás. Este resultado fue de la mayor importancia intelectual ... Se puede dar "prueba" de la "imposibilidad de probar" ciertas proposiciones [en este caso, el postulado de las paralelas] dentro de un sistema dado [en este caso, los primeros cuatro postulados de Euclides]". (pág. 10)

Último teorema de Fermat

Artículo principal: Último teorema de Fermat

El último teorema de Fermat fue conjeturado por Pierre de Fermat en el siglo XVII. Establece la imposibilidad de encontrar soluciones en números enteros positivos para la ecuación ${\displaystyle x^{n}+y^{n}=z^{n}}$ con ${\displaystyle n>2}$.

El propio Fermat dio una prueba para el caso de n = 4 usando su técnica de descenso infinito, y otros casos especiales fueron probados posteriormente, pero el caso general no fue probado hasta 1994 por Andrew Wiles.

La paradoja de Richard

Artículo principal: Paradoja de Richard

Esta profunda paradoja presentada por Jules Richard en 1905 precedió a los trabajos de Kurt Gödel (cf. Nagel y Newman p. 60ff) y de Alan Turing. Se encuentra una definición sucinta en los Principia Mathematica:^[12]​

La paradoja de Richard ... es la siguiente. Considérense todos los decimales que se pueden definir mediante un número finito de palabras [las “palabras” son símbolos; la fuente negrita se agrega para enfatizar el enunciado]; sea E la clase de dichos decimales. Entonces E tiene ${\displaystyle \aleph _{0}}$ (un número infinito de) miembros; que pueden ordenarse como el 1º, 2º, 3º, ... Sea X un número definido de la siguiente manera [Whitehead y Russell ahora emplean el método diagonal de Cantor].

Si la n-ésima cifra en el n-ésimo número decimal del conjunto E es p, entonces la n-ésima cifra en X pasa a ser p + 1 [o 0, si p = 9]. Entonces X es diferente de todos los miembros de E, ya que, sea cual sea el valor finito que n pueda tener, la n-ésima cifra en X es diferente de la n-ésima cifra en la n-ésima posición de los decimales que componen E, y por lo tanto, X es diferente en el n-ésimo decimal. Sin embargo, se ha definido X mediante un número finito de palabras [es decir, con la misma definición de palabra usada anteriormente.] y por lo tanto X debería ser un miembro de E. En consecuencia, X es y no es miembro de E.

Principia Mathematica, 2ª edición 1927, p. 61

Kurt Gödel consideró que su prueba era “una analogía” de la paradoja de Richard, a la que llamó “antinomia de Richard”^[13]​ (la demostración de Gödel es analizada más adelante).

Alan Turing construyó esta paradoja valiéndose de una máquina virtual, y demostró que esta máquina no podría responder a una pregunta simple:

¿Esta máquina podrá determinar si alguna máquina (incluyéndose a sí misma) quedará atrapada en un 'bucle infinito' improductivo?

Dicho de otra manera, Turing demostró que la máquina teórica no podría continuar con el cálculo mediante un método de numeración diagonal.

¿Puede demostrarse este teorema a partir de estos axiomas? Prueba de Gödel

Artículo principal: Teoremas de incompletitud de Gödel

Citando de nuevo a Nagel y Newman (p. 68), "El artículo de Gödel es difícil. Se deben dominar cuarenta y seis definiciones preliminares, junto con varios teoremas previos importantes, antes de alcanzar los resultados principales" (p. 68). De hecho, Nagel y Newman incorporaron una introducción de 67 páginas a su exposición de la prueba, lo que da una correcta imagen de su complejidad, aunque para Martin Davis "Este notable artículo no es solo un hito intelectual, sino que está escrito con una claridad y vigor que hace que sea un placer leerlo" (Davis, en Undecidable, pág. 4).

Entonces, ¿Qué demostró Gödel? En sus propias palabras:

"Es razonable ... hacer la conjetura de que ... [los] axiomas [de los Principia Mathematica y de Giuseppe Peano] son ... suficientes para decidir todas las cuestiones matemáticas que pueden expresarse formalmente en los sistemas dados. En lo que sigue se demostrará que no es así, sino que ... existen problemas relativamente simples de la teoría de los números enteros ordinarios que no pueden decidirse sobre la base de los axiomas.

(Gödel, en Undecidable, pág. 4)

Gödel comparó su prueba con la "antinomia de Richard" (un "antinomia" es una contradicción o una paradoja; para más información, consúltese la paradoja de Richard):

"La analogía de este resultado con la antinomia de Richard es inmediatamente evidente; también hay una estrecha relación [14] con la paradoja del mentiroso (nota al pie 14 de Gödel: Cada antinomia epistemológica puede usarse para una prueba similar de indecidibilidad) ... una proposición que tenemos ante nosotros que afirma su propia imposibilidad de ser probada [15]. (Su nota al pie de página 15: Contrariamente a las apariencias, tal proposición no es circular, ya que, para empezar, afirma la imposibilidad de probar una fórmula suficientemente definida)"

(Gödel, en Undecidable, pág. 9)

¿Esta máquina de computación se bloqueará en un "bucle"? La primera prueba de Turing

Artículo principal: Prueba de Turing

• El Entscheidungsproblem, el problema de decisión, fue respondido por primera vez por Church en abril de 1935 y se adelantó a Turing por más de un año, ya que el artículo de Turing se recibió para su publicación en mayo de 1936 (también se recibió para su publicación en 1936, en octubre, más tarde que el de Turing, un artículo breve de Emil Post que discutía la reducción de un algoritmo a un "método" simple similar a una máquina, muy parecido al modelo de máquina de computación de Turing; véase máquina posterior a Turing para más detalles).
• La demostración de Turing presenta la dificultad de la cantidad de definiciones requiere y de su naturaleza sutil (véase máquina de Turing y prueba de Turing).
• La primera prueba de Turing (de las tres que planteó) sigue el esquema de la paradoja de Richard: la máquina de computación de Turing es un algoritmo representado por una cadena de siete letras en una "máquina de computación". Su "cálculo" es probar "todas" las máquinas informáticas (incluidas ella misma) en busca de "bucles" (o círculos) y formar un número diagonal a partir de los cálculos de las máquinas informáticas no circulares o "exitosas". Lo hace, comenzando en secuencia desde 1, convirtiendo los números (de base 8) en cadenas de siete letras para probarlo. Cuando llega a su propio número, crea "su propia" cadena de letras. Decide que es la cadena de letras de una máquina exitosa, pero cuando intenta hacer el cálculo de esta máquina ("el suyo propio"), se bloquea en un círculo y no puede continuar. Así se llega a la paradoja de Richard.

Varias pruebas de indecidibilidad similares aparecieron poco antes y después de la prueba de Turing:

1. Abril de 1935: Prueba de Alonzo Church ("Un problema irresoluble de la teoría de números elemental"). Su prueba fue "... proponer una definición de calculabilidad efectiva ... y mostrar, por medio de un ejemplo, que no todos los problemas de esta clase tienen solución" (Indecidible p. 90))
2. 1946: Problema de correspondencia de Post (véase Hopcroft y Ullman^[14]​ p. 193ff, p. 407 como referencia)
3. Abril de 1947: Prueba de Emil Leon Post (Inestabilidad recursiva de un problema de Thue) (Indecidible p. 293). Desde entonces, esto se conoce como "El problema de la palabra de Thue" (Axel Thue propuso este problema en un artículo de 1914 (cf. Referencias al artículo de Post en Undecidable, p. 303)).
4. Teorema de Rice: una formulación generalizada del segundo teorema de Turing (cf Hopcroft y Ullman^[14]​ p. 185ff)^[15]​
5. Teorema de Greibach: indecidibilidad en la teoría del lenguaje (cf Hopcroft y Ullman^[14]​ p. 205ff y referencia en p. 401 ibid: Greibach [1963] "La indecidibilidad del problema de ambigüedad para gramáticas lineales mínimas", Información y control 6:2, 117-125, también referencia en la p. 402 ibid: Greibach [1968] "Una nota sobre propiedades indecidibles de los lenguajes formales", Teoría de sistemas matemáticos 2:1, 1-6.)
6. Cuestiones sobre la teselación de Penrose
7. Preguntas sobre soluciones de ecuaciones diofánticas y la respuesta resultante en el teorema MRDP (véase la entrada siguiente).

¿Se puede comprimir esta cadena? Prueba de Chaitin

Artículo principal: Complejidad de Kolmogórov

Para una exposición adecuada para no especialistas, consúltese Beltrami (p. 108ff), y véase también Franzén (Capítulo 8 págs. 137-148), y Davis (págs. 263-266). La discusión de Franzén es significativamente más complicada que la de Beltrami y profundiza en Ω, la llamada "probabilidad de detención" de Gregory Chaitin. El tratamiento anterior de Davis aborda la cuestión desde un punto de vista de una máquina de Turing. Chaitin ha escrito varios libros sobre sus esfuerzos y las consecuencias filosóficas y matemáticas que se deducen de ellos.

Una cadena es denominada (algorítmicamente) aleatoria de acuerdo con el concepto de complejidad de Kolmogórov, si no se puede producir a partir de un programa informático más corto. Mientras que la mayoría de las cadenas son aleatorias, ninguna en particular puede probarse así, excepto para un número finito de casos cortos:

"Una paráfrasis del resultado de Chaitin es que no puede haber una prueba formal de que una cadena suficientemente larga sea aleatoria ..."

(Beltrami p. 109)

Beltrami observa que "la prueba de Chaitin está relacionada con una paradoja planteada por el bibliotecario de Oxford G. Berry a principios del siglo XX, en la que se solicita "el número entero positivo más pequeño que no pueda ser definido por una oración en inglés con menos de 1000 caracteres". Evidentemente, la definición más corta de este número debe tener al menos 1000 caracteres. Sin embargo, la propia oración subrayada, que en sí misma es una definición del supuesto número, ¡tiene menos de 1000 caracteres!" (Beltrami, pág. 108).

¿Esta ecuación diofántica tiene una solución entera? Décimo problema de Hilbert

Artículos principales: Teorema de Matiyasevich y Problemas de Hilbert.

La pregunta "¿Tiene una «ecuación diofántica arbitraria» una solución entera"? es indecidible. Es decir, es imposible responder a la pregunta en todos los casos.

Franzén introduce en su análisis el décimo problema de Hilbert y el teorema de Matiyasevich (también conocido como MRDP, teorema de Matiyasevich-Robinson-Davis-Putnam) que establece que "no existe ningún algoritmo que pueda decidir si una ecuación diofántica tiene o no "alguna" solución en absoluto. El teorema MRDP utiliza la prueba de indecidibilidad de Turing: "... el conjunto de ecuaciones diofánticas solubles es un ejemplo de un conjunto computablemente enumerable pero no decidible, y el conjunto de ecuaciones diofánticas insolubles no es computablemente enumerable" (p. 71).

En ciencias sociales

En ciencias políticas, la paradoja de Arrow establece que es imposible diseñar un sistema electoral que satisfaga un conjunto de cinco axiomas específicos. Este teorema se demuestra comprobando que cuatro de los axiomas juntos implican el opuesto del quinto.

En economía, el teorema de Holmström (un teorema de imposibilidad) demuestra que ningún sistema de incentivos para un equipo de agentes puede satisfacer los tres criterios deseables.

En ciencias naturales

En ciencias naturales, las afirmaciones de imposibilidad (como otras afirmaciones) llegan a ser ampliamente aceptadas como abrumadoramente probables en lugar de considerarse probadas hasta el punto de ser indiscutibles. La base para esta fuerte aceptación es una combinación de evidencia extensa de algo que no está ocurriendo, combinada con una teoría subyacente, muy exitosa en hacer predicciones, cuyas suposiciones llevan lógicamente a la conclusión de que algo es imposible.

Dos ejemplos de imposibilidades ampliamente aceptadas en física son el móvil perpetuo, que viola la ley de conservación de la energía, y la posibilidad de sobrepasar la velocidad de la luz, que viola las implicaciones de teoría de la relatividad especial. Otro es la relación de indeterminación de Heisenberg en la mecánica cuántica, que afirma la imposibilidad de conocer simultáneamente tanto la posición como el momento de una partícula; así como el teorema de Bell: ninguna teoría física de las variables ocultas locales puede reproducir todas las predicciones de la mecánica cuántica.

Si bien una afirmación de imposibilidad en las ciencias naturales nunca puede probarse de manera absoluta, podría refutarse mediante la observación de un solo contraejemplo. Tal contraejemplo requeriría que se reexaminaran los supuestos subyacentes a la teoría que implicaban la imposibilidad.

Véase también

• Anexo:Problemas no resueltos de la Matemática – Se siguen buscando soluciones a estos problemas. Por el contrario, se "sabe" que los problemas anteriores no tienen solución.
• Teorema de imposibilidad, la noción física correspondiente.

Notas y referencias

1. «The Definitive Glossary of Higher Mathematical Jargon — Theorem». Math Vault (en inglés estadounidense). 1 de agosto de 2019. Consultado el 13 de diciembre de 2019. 
2. Pudlák, pp. 255–256.
3. Weisstein, Eric W. «Circle Squaring». mathworld.wolfram.com (en inglés). Consultado el 13 de diciembre de 2019. 
4. Weisstein, Eric W. «Abel's Impossibility Theorem». mathworld.wolfram.com (en inglés). Consultado el 13 de diciembre de 2019. 
5. Raatikainen, Panu (2018), «Gödel's Incompleteness Theorems», en Zalta, Edward N., ed., The Stanford Encyclopedia of Philosophy (Fall 2018 edición) (Metaphysics Research Lab, Stanford University), consultado el 13 de diciembre de 2019 .
6. De manera más general, la prueba por descenso infinito es aplicable a cualquier conjunto bien ordenado.
7. Hardy and Wright, p. 42
8. Hardy and Wright, p. 40
9. Nagel and Newman p. 8
10. Hardy and Wright p. 176
11. Hardy and Wright p. 159 referenced by E. Hecke. (1923). Vorlesungen über die Theorie der algebraischen Zahlen. Leipzig: Akademische Verlagsgesellschaft
12. Principia Mathematica, 2nd edition 1927, p. 61, 64 in Principia Mathematica online, Vol.1 at University of Michigan Historical Math Collection
13. Gödel in Undecidable, p. 9
14. John Hopcroft, Jeffrey Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. (requiere registro). 
15. "...no puede haber una máquina E que ... determine si M [una máquina arbitraria] alguna vez imprime un símbolo dado (0 digamos)" (Indecidible p. 134). Turing hace una afirmación extraña al final de esta demostración, que recuerda notablemente al teorema de Rice: "... cada uno de estos problemas de "proceso general" se puede expresar como un problema relativo a un proceso general para determinar si un entero n dado tiene una propiedad G(n) ... y esto equivale a calcular un número cuyo n-ésima cifra es 1 si G(n) es verdadero y 0 si es falso" (Indecidible p 134). Desafortunadamente, no aclara más este punto.

Bibliografía

• Godfrey Harold Hardy y E. M. Wright, An Introduction to the Theory of Numbers ("Una introducción a la teoría de números"), Quinta edición, Clarendon Press, Oxford (Inglaterra), 1979, reimpreso en 2000 con Índice General (primera edición: 1938). Las pruebas de que los números e y pi son trascendentes no son triviales, pero un lector experto en matemáticas podrá abrirse paso a través de ellas.
• Alfred North Whitehead y Bertrand Russell, Principia Mathematica a *56, Cambridge University Press, 1962, reimpresión de la 2ª edición de 1927, primera edición de 1913. Cap. 2.I. "The Vicious-Circle Principle" ("El principio del círculo vicioso") pág. 37ff, y cap. 2.VIII. "The contradictions" ("Las contradicciones") p. 60ff.
• Turing, A.M. (1936), «On Computable Numbers, with an Application to the Entscheidungsproblem», Proceedings of the London Mathematical Society, 2 (1937) 42 (1): 230-65, doi:10.1112/plms/s2-42.1.230 . (y Turing, A.M. (1938), «On Computable Numbers, with an Application to the Entscheidungsproblem: A correction», Proceedings of the London Mathematical Society, 2 (1937) 43 (6): 544-6, doi:10.1112/plms/s2-43.6.544 .). versión en línea (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). Este es el artículo de época en el que Turing define la máquina de Turing y de muestra que (así como el Entscheidungsproblem) no tiene solución.
• Martin Davis, "The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions", Raven Press, Nueva York, 1965. El artículo de Turing ocupa el tercer lugar en este volumen. Los artículos incluyen los de Gödel, Church, Rosser, Kleene y Post.
• El capítulo de Martin Davis "What is a Computation?" ("¿Qué es una computación?") en "Mathematics Today" de Lynn Arthur Steen, 1978, Vintage Books Edition, Nueva York, 1980. Su capítulo describe las máquinas de Turing en los términos de una máquina posterior a Turing más simple, luego continúa con descripciones de la primera prueba de Turing y las contribuciones de Chaitin.
• Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, Nueva York. Véase el capítulo "The Spirit of Truth" ("El espíritu de la verdad") para una historia que conduzca a su prueba y una discusión sobre ella.
• Hans Reichenbach, Elements of Symbolic Logic, Dover Publications Inc., Nueva York, 1947. Una referencia a menudo citada por otros autores.
• Ernest Nagel y James Newman, Gödel's Proof, New York University Press, 1958.
• Edward Beltrami, "What is Random? Chance and Order in Mathematics and Life" ("¿Qué es aleatorio? Azar y orden en las matemáticas y la vida"), Springer-Verlag New York, Inc., 1999.
• Torkel Franzén, "Godel's Theorem, An Incomplete Guide to Its Use and Abuse" ("Teorema de Godel, una guía incompleta para su uso y abuso"), A.K. Peters, Wellesley Mass, 2005. Una versión reciente de los teoremas de Gödel y sus abusos. No es una lectura tan simple como pretende el autor. La discusión (borrosa) de Franzén de la tercera prueba de Turing es útil debido a sus intentos de aclarar la terminología. Ofrece discusiones sobre los argumentos de Freeman Dyson, Stephen Hawking, Roger Penrose y Gregory Chaitin (entre otros) que utilizan los teoremas de Gödel, y una crítica útil de alguna palabrería filosófica y metafísica inspirada en Gödel que ha encontrado en la web.
• Pavel Pudlák, Logical Foundations of Mathematics and Computational Complexity. A Gentle Introduction ("Fundamentos lógicos de las matemáticas y complejidad computacional. Una introducción amable"), Springer 2013. (Consúltese el Capítulo 4 "Pruebas de imposibilidad").