La paradoja de Richard es una paradoja semántica descrita por primera vez por el matemático francés Jules Richard en 1905.
Con la ayuda de algunas frases de cualquier idioma , se pueden caracterizar ciertos números reales . Por ejemplo, la frase "la razón de la circunferencia de un círculo a la longitud de su diámetro" caracteriza el número "pi" , y la frase "dos enteros y tres décimas" caracteriza el número 2.3. Todas las frases de este idioma se pueden numerar de cierta manera (por ejemplo, si ordena las frases alfabéticamente, como en un diccionario, cada frase recibirá el número donde se encuentra). Ahora dejemos en esta enumeración de frases solo aquellas frases que caracterizan un número real (y no dos o más). El número, que se caracteriza por tal numeración por la frase número n , lo llamaremos el n -ésimo número de Richard.
Considere la siguiente oración: "Un número real cuyo n-ésimo lugar decimal es 1 si el n-ésimo número de Richard tiene un n-ésimo lugar decimal distinto de 1, y el n-ésimo lugar decimal es 2 si el n-ésimo número de Richard tiene El n-ésimo lugar decimal es 1". Esta frase define algún número de Richard, digamos k -e; sin embargo, por definición, difiere del k - ésimo número de Richard en el k - ésimo lugar decimal. Por lo tanto, hemos llegado a una contradicción.
En la teoría de la computabilidad, los intentos de obtener el resultado del cálculo del "número de Richard" en la formulación indicada son algorítmicamente indecidibles. Las descripciones verbales dadas del número determinan no solo el valor en sí mismo, sino también la condición para la finalización exitosa de algoritmos para calcular este valor en forma de ciertos programas , cuya ejecución, en el caso general, puede requerir una cantidad ilimitada de memoria y tiempo infinito en un intento de seleccionar el número racional resultante que satisfaga la condición formulada del valor exacto. Puede haber muchas formas de implementar el algoritmo , y todos los programas son correctos , cuya ejecución da el resultado correcto que satisface la condición formulada. Pero la satisfacción de algunas condiciones puede ser algorítmicamente indecidible .
Por ejemplo, el valor exacto "dos enteros y tres décimas" es computable , ya que el resultado del cálculo es un número racional que se puede escribir como una razón de números naturales en un tiempo finito usando una cantidad finita de memoria. Y el valor exacto “la relación entre la circunferencia de un círculo y la longitud de su diámetro” es, en principio, incalculable, ya que el resultado deseado es en realidad un número irracional , cuyo valor exacto, incluso teóricamente, no puede representarse mediante ninguna relación. de números naturales, sin importar qué números intentemos seleccionar. En un tiempo finito, es posible calcular solo un valor aproximado del número Pi con cualquier número finito de dígitos después del punto decimal, para cuyo cálculo hay suficiente tiempo y para cuyo almacenamiento hay suficiente memoria (que es decir , sólo es computable un valor aproximado de Pi en forma de número racional ). Pero el valor exacto de pi es incomputable: cualquier programa para calcular el valor exacto de pi se ejecutará indefinidamente y requerirá una cantidad infinita de memoria para almacenar más y más datos acumulados con cada iteración . La condición de escribir "la relación entre la circunferencia de un círculo y la longitud de su diámetro" en números naturales es imposible en principio, si no se especifica el error permisible.
De manera similar, al calcular un determinado “Número de Richard”, será necesario verificar la condición anterior “Un número real cuyo n-ésimo decimal es 1, si el n-ésimo número de Richard tiene el n-ésimo decimal distinto de 1, y el n-ésimo lugar decimal es igual a 2 si el n-ésimo número de Richard tiene el n-ésimo lugar decimal igual a 1. Tal verificación requerirá la ejecución del programa con una llamada recursiva a sí mismo (la descripción contiene operaciones en un cierto "número de Richard", para calcular el valor del cual es necesario comenzar nuevamente la próxima ejecución del algoritmo de este programa con inmersión recursiva sin limitar la profundidad de anidamiento, con la expectativa de usar una cantidad infinitamente grande de memoria y tiempo ilimitado).
El "número de Richard" deseado en la formulación anterior es incomputable y algorítmicamente irresoluble , es decir, no existe ningún algoritmo capaz de calcularlo en un tiempo finito por la sencilla razón de que la condición de un resultado correcto es obviamente imposible.