Richardin paradoksi on semanttinen paradoksi , jonka ranskalainen matemaatikko Jules Richard kuvasi ensimmäisen kerran vuonna 1905.
Joidenkin minkä tahansa kielen lauseiden avulla voidaan luonnehtia tiettyjä reaalilukuja . Esimerkiksi lause "ympyrän kehän suhde sen halkaisijan pituuteen" kuvaa lukua "pi" ja lause "kaksi kokonaista ja kolme kymmenesosaa" kuvaa lukua 2.3. Kaikki tällaiset tämän kielen lauseet voidaan numeroida tietyllä tavalla (esimerkiksi jos lajittelet lauseet aakkosjärjestyksessä, kuten sanakirjassa, jokainen lause saa numeron, jossa se sijaitsee). Jätetään nyt tähän lauseluetteloon vain ne lauseet, jotka kuvaavat yhtä reaalilukua (eikä kahta tai useampaa). Numeroa, jolle tällainen numerointi on tunnusomaista lausenumerolla n , kutsutaan n : nneksi Richardin numeroksi.
Tarkastellaan seuraavaa lausetta: "Reaaliluku, jonka n:s desimaali on 1, jos n :nnellä Richardin numerolla on n:s desimaalipaikka kuin 1, ja n :nnen desimaalin piste on 2, jos n:nnellä Richard -luvulla on n:s desimaalipaikka on 1". Tämä lause määrittelee jonkin Richard-luvun, sanotaanpa k -e; kuitenkin määritelmän mukaan se eroaa k -. Richard-luvusta k - :nnen desimaalin kohdalla. Siten olemme päätyneet ristiriitaan.
Lasketettavuuden teoriassa yritykset saada "Richardin luvun" laskentatulos esitetyssä formulaatiossa ovat algoritmisesti ratkaisemattomia. Numeron annetut sanalliset kuvaukset määräävät paitsi itse arvon, myös ehdon tämän arvon laskemiseen tarvittavien algoritmien onnistuneelle suorittamiselle tiettyjen ohjelmien muodossa , joiden suorittaminen voi yleensä vaatia rajoittamattoman määrän muistia ja ääretöntä aikaa yritettäessä valita tuloksena oleva rationaalinen luku , joka täyttää täsmällisen arvon muotoillun ehdon. Algoritmia voi toteuttaa monella tapaa , ja kaikki ohjelmat ovat oikeita , joiden suorittaminen antaa oikean tuloksen, joka täyttää muotoillun ehdon. Mutta joidenkin ehtojen täyttyminen voi olla algoritmisesti ratkaisematon .
Esimerkiksi tarkka arvo "kaksi kokonaislukua ja kolme kymmenesosaa" on laskettavissa , koska laskennan tulos on rationaalinen luku , joka voidaan kirjoittaa luonnollisten lukujen suhteeksi rajallisessa ajassa käyttämällä äärellistä muistimäärää. Ja tarkka arvo "ympyrän kehän suhde sen halkaisijan pituuteen" on periaatteessa mahdoton laskea, koska haluttu tulos on itse asiassa irrationaalinen luku , jonka tarkkaa arvoa ei edes teoreettisesti voida esittää millään suhteella luonnollisista luvuista riippumatta siitä, mitä lukuja yritämme valita. Äärillisessä ajassa on mahdollista laskea vain likimääräinen arvo luvusta Pi millä tahansa äärellisellä määrällä desimaalipilkun jälkeen olevia numeroita, jonka laskemiseen on riittävästi aikaa ja jonka tallentamiseen on riittävästi muistia (että on , vain likimääräinen Pi :n arvo rationaaliluvun muodossa on laskettavissa ). Mutta pi:n tarkkaa arvoa ei voi laskea: mikä tahansa ohjelma , joka laskee pi:n tarkan arvon, toimii loputtomasti ja vaatii äärettömän määrän muistia tallentaakseen yhä enemmän jokaisella iteraatiolla kertynyttä dataa . Ehto kirjoittaa "ympyrän kehän suhde sen halkaisijan pituuteen" luonnollisilla luvuilla on periaatteessa mahdotonta, jos sallittua virhettä ei ole määritelty.
Vastaavasti tiettyä "Richard-lukua" laskettaessa on tarkistettava yllä oleva ehto "Reaaliluku, jonka n. desimaali on 1, jos n:nnen Richardin luvun n:s desimaali ei ole yhtä suuri kuin 1, ja n:s desimaali on yhtä kuin 2, jos n:nnen Richard-luvun n:s desimaali on yhtä kuin 1. Tällainen tarkistus vaatii ohjelman suorittamisen rekursiivisella kutsulla itselleen (kuvaus sisältää operaatioita tietylle "Richardin numerolle", jonka arvon laskemiseksi on tarpeen aloittaa tämän ohjelman algoritmin seuraava suoritus uudelleen rekursiivisella upotuksella ilman sisäkkäisyyden syvyyttä rajoittamatta, odottaen äärettömän suuren muistimäärän ja rajattoman ajan käyttämistä).
Haluttu "Richard-luku" yllä olevassa formulaatiossa on laskematon ja algoritmisesti ratkaisematon , eli ei ole olemassa algoritmia, joka pystyisi laskemaan sen rajallisessa ajassa siitä yksinkertaisesta syystä, että oikean tuloksen ehto on ilmeisen mahdoton.