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.
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.
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.
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.
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).
Tres cuestiones planteadas por los geómetras de la Grecia clásica se hicieron especialmente conocidas: 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.
Curiosamente, hay números irracionales que pueden ser euclidianos.
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.
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.
Establece la imposibilidad de encontrar soluciones en números enteros positivos para la ecuación
Esta profunda paradoja presentada por Jules Richard en 1905 precedió a los trabajos de Kurt Gödel (cf.
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: 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.
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.
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!"
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.
Este teorema se demuestra comprobando que cuatro de los axiomas juntos implican el opuesto del quinto.