Richards paradoks er et semantisk paradoks første gang beskrevet af den franske matematiker Jules Richard i 1905.
Ved hjælp af nogle sætninger af ethvert sprog kan visse reelle tal karakteriseres . For eksempel karakteriserer sætningen "forholdet mellem omkredsen af en cirkel og længden af dens diameter" tallet "pi" , og sætningen "to hele og tre tiendedele" karakteriserer tallet 2,3. Alle sådanne sætninger i dette sprog kan nummereres på en bestemt måde (hvis du f.eks. sorterer sætningerne alfabetisk, som i en ordbog, vil hver sætning modtage nummeret, hvor den er placeret). Lad os nu i denne opremsning af sætninger kun lade de sætninger, der karakteriserer et reelt tal (og ikke to eller flere). Tallet, som er karakteriseret ved en sådan nummerering af sætningen nummer n , vil vi kalde det n - te Richard nummer.
Overvej følgende sætning: "Et reelt tal, hvis n'te decimal er 1, hvis det n'te Richard-tal har en anden decimal end 1, og den n'te decimal er 2, hvis n'te Richard-tal har Den n'te decimal er 1". Denne sætning definerer et eller andet Richard-nummer, lad os sige k -e; dog adskiller det sig per definition fra det k - th Richard-tal i den k - th decimal. Dermed er vi nået frem til en modsigelse.
I teorien om beregnelighed er forsøg på at opnå resultatet af beregningen af "Richard-tallet" i den angivne formulering algoritmisk uafgørlige. De givne verbale beskrivelser af tallet bestemmer ikke kun selve værdien, men betingelsen for en vellykket gennemførelse af algoritmer til beregning af denne værdi i form af visse programmer , hvis udførelse i det generelle tilfælde kan kræve en ubegrænset mængde af hukommelse og uendelig tid i et forsøg på at vælge det resulterende rationelle tal , der opfylder den formulerede betingelse for den nøjagtige værdi. Der kan være mange måder at implementere algoritmen på , og alle programmer er korrekte , hvis udførelse giver det korrekte resultat, der opfylder den formulerede betingelse. Men tilfredsstillelsen af nogle betingelser kan være algoritmisk uafklarelig .
For eksempel kan den nøjagtige værdi "to heltal og tre tiendedele" beregnes , da resultatet af beregningen er et rationelt tal , der kan skrives som et forhold mellem naturlige tal i en endelig tid ved hjælp af en begrænset mængde hukommelse. Og den nøjagtige værdi "forholdet mellem omkredsen af en cirkel og længden af dens diameter" er i princippet uberegnelig, da det ønskede resultat faktisk er et irrationelt tal , hvis nøjagtige værdi, selv teoretisk, ikke kan repræsenteres af noget forhold af naturlige tal, uanset hvilke tal vi forsøger at vælge. I en endelig tid er det muligt kun at beregne en tilnærmet værdi af tallet Pi med ethvert endeligt antal cifre efter decimalkommaet, til hvis beregning der er nok tid, og til lagringen der er nok hukommelse (at er , kun en omtrentlig værdi af Pi i form af et rationelt tal kan beregnes ). Men den nøjagtige værdi af pi er uberegnelig: ethvert program til at beregne den nøjagtige værdi af pi vil køre på ubestemt tid og kræver en uendelig mængde hukommelse for at gemme flere og flere data, der akkumuleres med hver iteration . Betingelsen for at skrive "forholdet mellem omkredsen af en cirkel og længden af dens diameter" i naturlige tal er umuligt i princippet, hvis den tilladte fejl ikke er angivet.
På samme måde, når man beregner et bestemt "Richard-tal", vil det være nødvendigt at kontrollere ovenstående betingelse "Et reelt tal, hvis n-te decimal er 1, hvis det n-te Richard-tal har den n-te decimal, der ikke er lig med 1, og den n'te decimal er lig med 2, hvis det n'te Richard-tal har den n'te decimal lig med 1. En sådan kontrol vil kræve udførelse af programmet med et rekursivt kald til sig selv (beskrivelsen indeholder operationer på et bestemt "Richard-nummer", for at beregne værdien af hvilken det er nødvendigt at starte den næste udførelse af dette programs algoritme igen med rekursiv fordybelse uden at begrænse dybden af rede, med forventning om at bruge en uendelig stor mængde hukommelse og ubegrænset tid).
Det ønskede "Richard-tal" i ovenstående formulering er uberegnelig og algoritmisk uopløselig , det vil sige, at der ikke er nogen algoritme, der er i stand til at beregne det på en begrænset tid af den simple grund, at betingelsen for et korrekt resultat naturligvis er umulig.