Richards paradox är en semantisk paradox som först beskrevs av den franske matematikern Jules Richard 1905.
Med hjälp av några fraser av vilket språk som helst kan vissa reella tal karakteriseras . Till exempel kännetecknar frasen "förhållandet mellan en cirkels omkrets och längden på dess diameter" talet "pi" och frasen "två hela och tre tiondelar" kännetecknar talet 2,3. Alla sådana fraser i detta språk kan numreras på ett visst sätt (om du till exempel sorterar fraserna alfabetiskt, som i en ordbok, kommer varje fras att få numret där den finns). Låt oss nu i denna uppräkning av fraser bara lämna de fraser som kännetecknar ett reellt tal (och inte två eller fler). Numret, som kännetecknas av sådan numrering av frasen numret n , kommer vi att kalla det n - te Richard-numret.
Tänk på följande mening: "Ett reellt tal vars n :te decimal är 1 om det n :te Richard-talet har en annan n :te decimal än 1, och den n :te decimalen är 2 om det n :te Richard-talet har n :te decimalen är 1". Den här frasen definierar något Richard-nummer, låt oss säga k -e; men per definition skiljer det sig från det k - :te Richard-talet i den k - :e decimalen. Därmed har vi kommit fram till en motsägelse.
I teorin om beräkningsbarhet är försök att erhålla resultatet av beräkningen av "Richard-talet" i den angivna formuleringen algoritmiskt obestämbara. De givna verbala beskrivningarna av numret bestämmer inte bara själva värdet, utan villkoret för framgångsrikt slutförande av algoritmer för att beräkna detta värde i form av vissa program , vars exekvering, i det allmänna fallet, kan kräva en obegränsad mängd minne och oändlig tid i ett försök att välja det resulterande rationella talet som uppfyller det formulerade villkoret för det exakta värdet. Det kan finnas många sätt att implementera algoritmen , och alla program är korrekta , vars exekvering ger det korrekta resultatet som uppfyller det formulerade villkoret. Men tillfredsställelsen av vissa villkor kan vara algoritmiskt obestämbar .
Till exempel är det exakta värdet "två heltal och tre tiondelar" beräkningsbart , eftersom resultatet av beräkningen är ett rationellt tal som kan skrivas som ett förhållande mellan naturliga tal i en ändlig tid med hjälp av en ändlig mängd minne. Och det exakta värdet "förhållandet mellan omkretsen av en cirkel och längden på dess diameter" är i princip oberäkningsbart, eftersom det önskade resultatet faktiskt är ett irrationellt tal , vars exakta värde, även teoretiskt, inte kan representeras av något förhållande av naturliga tal, oavsett vilka tal vi försöker välja. I en ändlig tid är det möjligt att bara beräkna ett ungefärligt värde av talet Pi med valfritt ändligt antal siffror efter decimalkomma, för beräkningen av vilken det finns tillräckligt med tid och för vars lagring det finns tillräckligt med minne (det är , endast ett ungefärligt värde av Pi i form av ett rationellt tal kan beräknas ). Men det exakta värdet på pi är oberäkningsbart: vilket program som helst för att beräkna det exakta värdet på pi kommer att köras på obestämd tid och kräver en oändlig mängd minne för att lagra mer och mer data som ackumuleras med varje iteration . Villkoret att skriva "förhållandet mellan omkretsen av en cirkel och längden på dess diameter" i naturliga tal är i princip omöjligt, om det tillåtna felet inte anges.
På liknande sätt, när man beräknar ett visst "Richard-tal", kommer det att vara nödvändigt att kontrollera ovanstående villkor "Ett reellt tal vars n:te decimal är 1, om det n:te Richard-talet har den n:te decimalen som inte är lika med 1, och den n:e decimalen är lika med 2 om det n:te Richard-talet har den n:te decimalen lika med 1. En sådan kontroll kommer att kräva exekvering av programmet med ett rekursivt anrop till sig själv (beskrivningen innehåller operationer på ett visst "Richard-nummer", för att beräkna värdet av vilket det är nödvändigt att starta nästa exekvering av algoritmen för detta program igen med rekursiv nedsänkning utan att begränsa häckningsdjupet, med förväntan att använda en oändligt stor mängd minne och obegränsad tid).
Det önskade "Richard-talet" i ovanstående formulering är oberäkningsbart och algoritmiskt olösligt , det vill säga det finns ingen algoritm som kan beräkna det på en begränsad tid av den enkla anledningen att villkoret för ett korrekt resultat uppenbarligen är omöjligt.