Ver el código de «Prueba de imposibilidad»

{|class="wikitable floatright" width=200px
|bgcolor="White"|[[Archivo:Quadrat-Wurzel-2.svg|250px]]  [[Archivo:Número raiz de dos.svg|250px]]
|-
|style="font-size:85%; line-height:125%;"|Una de las primeras pruebas de imposibilidad conocidas: la demostración de que <math>\sqrt {2}</math> no se puede expresar como el cociente de dos números enteros <math>(a/b)</math>
|}
Una '''prueba de imposibilidad''', también conocida como '''prueba negativa''', prueba de un '''teorema de imposibilidad''', o '''resultado negativo''', es una [[Demostración en matemática|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.<ref>{{Cite web|url=https://mathvault.ca/math-glossary/#theorem|title=The Definitive Glossary of Higher Mathematical Jargon — Theorem|date=2019-08-01|website=Math Vault|language=en-US|access-date=2019-12-13}}</ref> 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.<ref>Pudlák, pp. 255–256.</ref> 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 [[Raíz cuadrada de dos|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,<ref>{{Cite web|url=http://mathworld.wolfram.com/CircleSquaring.html|title=Circle Squaring|last=Weisstein|first=Eric W.|website=mathworld.wolfram.com|language=en|access-date=2019-12-13}}</ref> porque el número {{math|[[Número π|π]]}} es [[Número trascendente|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||s}} que no tienen solución.

Un problema que surgió en el {{siglo|XVI||s}} 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,<ref>{{Cite web|url=http://mathworld.wolfram.com/AbelsImpossibilityTheorem.html|title=Abel's Impossibility Theorem|last=Weisstein|first=Eric W.|website=mathworld.wolfram.com|language=en|access-date=2019-12-13}}</ref> 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||s}} figuran las relacionadas con el [[Problema indecidible|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.<ref>{{Citation|last=Raatikainen|first=Panu|title=Gödel's Incompleteness Theorems|date=2018|url=https://plato.stanford.edu/archives/fall2018/entries/goedel-incompleteness/|work=The Stanford Encyclopedia of Philosophy|editor-last=Zalta|editor-first=Edward N.|edition=Fall 2018|publisher=Metaphysics Research Lab, Stanford University|access-date=2019-12-13}}</ref>

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 (lógica)|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 [[Teoría de la complejidad computacional|intratables]].

== Tipos de pruebas de imposibilidad ==
{{VT| 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 ====
{{AP|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 [[Número natural|entera positiva]]<ref>De manera más general, la prueba por descenso infinito es aplicable a cualquier [[conjunto bien ordenado]].</ref> 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<sup>5</sup> + 84<sup>5</sup> + 110<sup>5</sup> + 133<sup>5</sup> = 144<sup>5</sup>.
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&nbsp;a.{{esd}}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 [[Georg Cantor|Cantor]] en su [[Argumento de la diagonal de Cantor|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 [[David Hilbert|Hilbert]], es indecidible.

{{cita|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&nbsp;a.C. Demócrito, nacido alrededor del 470&nbsp;a.C., escribió ''sobre líneas irracionales y sólidos''&nbsp;...|source={{citation needed|date=July 2017}}|author=Heath}}

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

{{cita|He aquí un famoso pasaje del diálogo ''[[Teeteto (diálogo)|Teeteto]]'' de [[Platón]], en el que se establece que Teodoro (maestro de Platón) probó la irracionalidad de
:<math>\sqrt{3}, \sqrt{5}, ...,</math> analizando todos los casos separados hasta la raíz de 17...<ref>Hardy and Wright, p.&nbsp;42</ref>}}

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''.<ref>Hardy and Wright, p.&nbsp;40</ref>

Es decir, es imposible expresar la raíz ''m''-ésima de un número entero ''N'' como la razón {{frac|''a''|''b''}} de dos enteros ''a'' y ''b'', que no comparten [[número primo|números primos]] en común excepto en los casos en los que ''b''&nbsp;=&nbsp;1.

== Construcciones imposibles buscadas por los antiguos griegos ==
Tres cuestiones planteadas por los geómetras de la Grecia clásica se hicieron especialmente conocidas:

# La [[trisección del ángulo]] con [[regla y compás]]
# La construcción de un cubo con el [[Duplicación del cubo|doble de volumen]] que uno dado
# La construcción de un cuadrado de [[Cuadratura del círculo|igual área]] que la de un círculo dado

Durante más de 2000&nbsp;años se hicieron intentos infructuosos para resolver estos problemas, hasta que por fin, en el {{siglo|XIX||s}} se comprobó que estas tres construcciones son conceptualmente imposibles.<ref>Nagel and Newman p.&nbsp;8</ref>

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''&nbsp;=&nbsp;3, 4 y 5 que sí se sabían construir.

Todos estos son problemas de [[Número construible|construcción euclídea]], que solo son realizables si involucran únicamente [[Número construible|números construibles]] (Hardy y Wright p.&nbsp;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 del ángulo|trisección de un ángulo arbitrario]] como la [[duplicación del cubo]] requieren obtener [[raíz cúbica|raíces cúbicas]], que no son [[número construible|números construibles]] exclusivamente con regla y compás.

=== Cuadratura del círculo ===
{{cita|<math>\pi</math> 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.<ref>Hardy and Wright p.&nbsp;176</ref>}}

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 <math>\pi</math> 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 <math>\pi</math> a partir de un círculo unitario es imposible,<ref>Hardy and Wright p.&nbsp;159 referenced by E. Hecke. (1923). ''Vorlesungen über die Theorie der algebraischen Zahlen''. Leipzig: Akademische Verlagsgesellschaft</ref> 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 [[Polígono construible|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 ==
{{AP|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.&nbsp;9).

La pregunta es: 

{{cita|¿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||s}} de "... [[Carl Friedrich Gauss|Gauss]], [[János Bolyai|Bolyai]], [[Nikolái Lobachevski|Lobachevski]] y [[Bernhard Riemann|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.&nbsp;10)

== Último teorema de Fermat ==
{{AP|Último teorema de Fermat}}

El [[último teorema de Fermat]] fue conjeturado por [[Pierre de Fermat]] en el {{siglo|XVII||s}}. Establece la imposibilidad de encontrar soluciones en números enteros positivos para la ecuación <math>x^n+y^n=z^n</math> con <math>n>2</math>.

El propio [[Pierre de Fermat|Fermat]] dio una prueba para el caso de ''n''&nbsp;=&nbsp;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 ==
{{AP|Paradoja de Richard}}

Esta profunda paradoja presentada por [[Jules Richard (matemático)|Jules Richard]] en 1905 precedió a los trabajos de [[Kurt Gödel]] (cf. Nagel y Newman p.&nbsp;60ff) y de [[Alan Turing]]. Se encuentra una definición sucinta en los ''[[Principia Mathematica]]'':<ref>[http://quod.lib.umich.edu/u/umhistmath/AAT3201.0001.001/86?rgn=full+text;view=pdf ''Principia Mathematica'', 2nd edition 1927, p.&nbsp;61, 64] in [http://quod.lib.umich.edu/cgi/t/text/text-idx?c=umhistmath;idno=AAT3201.0001.001 ''Principia Mathematica online'', Vol.1] at University of Michigan Historical Math Collection</ref>

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

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''&nbsp;+&nbsp;1 [o 0, si ''p''&nbsp;{{=}}&nbsp;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 <small> [es decir, con la misma definición de ''palabra'' usada anteriormente.]</small> 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.&nbsp;61}}

Kurt Gödel consideró que su prueba era “una analogía” de la [[paradoja de Richard]], a la que llamó “''antinomia de Richard''”<ref>Gödel in ''Undecidable'', p.&nbsp;9</ref> (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:

{{cita|¿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 ==
{{AP|Teoremas de incompletitud de Gödel}}

Citando de nuevo a Nagel y Newman (p.&nbsp;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.&nbsp;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:

{{cita| "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]]):

{{cita|"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 [[epistemología|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 ==
{{AP|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:

# 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.&nbsp;90))
# 1946: [[Problema de correspondencia de Post]] (véase Hopcroft y Ullman<ref name="Hopcroft.Ullman.1979">{{cite book| author=[[John Hopcroft]], [[Jeffrey Ullman]]| title=Introduction to Automata Theory, Languages, and Computation| year=1979| publisher=Addison-Wesley| isbn=0-201-02988-X| url-access=registration| url=https://archive.org/details/introductiontoau00hopc}}</ref> p.&nbsp;193ff, p.&nbsp;407 como referencia)
# Abril de 1947: Prueba de [[Emil Leon Post]] (''Inestabilidad recursiva de un problema de Thue'') (Indecidible p.&nbsp;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.&nbsp;303)).
# [[Teorema de Rice]]: una formulación generalizada del segundo teorema de Turing (cf Hopcroft y Ullman<ref name="Hopcroft.Ullman.1979"/> p.&nbsp;185ff)<ref>"...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.</ref>
# [[Teorema de Greibach]]: indecidibilidad en la teoría del lenguaje (cf Hopcroft y Ullman<ref name="Hopcroft.Ullman.1979"/> p.&nbsp;205ff y referencia en p.&nbsp;401 ibid: [[Sheila Greibach|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.&nbsp;402 ibid: Greibach [1968] "Una nota sobre propiedades indecidibles de los lenguajes formales", Teoría de sistemas matemáticos 2:1, 1-6.)
# Cuestiones sobre la [[teselación de Penrose]]
# Preguntas sobre soluciones de [[ecuación diofántica|ecuaciones diofánticas]] y la respuesta resultante en el teorema MRDP (véase la entrada siguiente).

== ¿Se puede comprimir esta cadena? Prueba de Chaitin ==
{{AP|Complejidad de Kolmogórov}}

Para una exposición adecuada para no especialistas, consúltese Beltrami (p.&nbsp;108ff), y véase también Franzén (Capítulo 8 págs.&nbsp;137-148), y Davis (págs.&nbsp;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:

{{cita| "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 <u>"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"</u>''. 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.&nbsp;108).

== ¿Esta ecuación diofántica tiene una solución entera? Décimo problema de Hilbert ==
{{AP|Teorema de Matiyasevich|Problemas de Hilbert}}

La pregunta "¿Tiene una «ecuación diofántica arbitraria» una solución entera"? es [[Problema indecidible|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.&nbsp;71).

== En ciencias sociales ==
En [[ciencia política|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 (ciencia económica)|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]]{{snd}} 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 ==
{{Reflist}}

== 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.&nbsp;37ff, y cap. 2.VIII. "The contradictions" ("Las contradicciones") p.&nbsp;60ff.
* {{ Citation | last= Turing | first= A.M. | publication-date = 1937 | year = 1936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | issue= 1 | pages = 230–65 | doi= 10.1112/plms/s2-42.1.230 }} (y {{Citation | last = Turing | first = A.M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | issue = 6 | pages = 544–6 | doi = 10.1112/plms/s2-43.6.544 | year = 1938 }}). {{Enlace roto|1=[http://www.turingarchive.org/browse.php/B/12 versión en línea] |2=http://www.turingarchive.org/browse.php/B/12 }} 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 R. Newman|James Newman]], [https://archive.org/details/gdelsproof00nage ''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, ''[https://books.google.com/books?id=obxDAAAAQBAJ&printsec=frontcover#v=onepage&q=impossibility%20proof&f=false 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").

{{Control de autoridades}}
[[Categoría:Lógica matemática]]
[[Categoría:Demostraciones matemáticas]]
[[Categoría:Posibilidad]]