Richard paradoxona egy szemantikai paradoxon , amelyet először Jules Richard francia matematikus írt le 1905-ben.
Bármely nyelv egyes kifejezéseinek segítségével jellemezhetők bizonyos valós számok . Például a "kör kerületének és átmérőjének hosszához viszonyított aránya" kifejezés a "pi" számot , a "két egész és három tized" kifejezés pedig a 2.3 számot jellemzi. Ennek a nyelvnek az összes ilyen kifejezése bizonyos módon számozható (például ha a kifejezéseket ábécé szerint rendezi, mint egy szótárban, akkor minden kifejezés megkapja a számot, ahol található). Hagyjuk most a kifejezések felsorolásában csak azokat a kifejezéseket, amelyek egy valós számot (és nem kettőt vagy többet) jellemeznek. Azt a számot, amelyet az ilyen számozás az n számmal jellemez, n - edik Richard számnak nevezzük .
Tekintsük a következő mondatot: „Valós szám, amelynek n- edik tizedesjele 1, ha az n- edik Richard-szám n- edik tizedesjele 1-től eltérő, és az n- edik tizedesjegy 2, ha az n- edik Richard-szám n- edik tizedesjegye 1. Ez a kifejezés valamilyen Richard-számot határoz meg, mondjuk k -e; azonban definíció szerint a k - edik tizedesjegyben eltér a k - edik Richard-számtól . Ezzel ellentmondáshoz érkeztünk.
A kiszámíthatóság elméletében a „Richard-szám” kiszámításának eredményére tett kísérletek a jelzett megfogalmazásban algoritmikusan eldönthetetlenek. A szám adott szóbeli leírása nemcsak magát az értéket határozza meg, hanem annak a feltételét is, hogy bizonyos programok formájában az ezen érték kiszámítására szolgáló algoritmusok sikeresen lezajlanak , amelyek végrehajtása általános esetben korlátlan mennyiségű számítást igényelhet. memória és végtelen idő, hogy megpróbálja kiválasztani a kapott racionális számot , amely kielégíti a pontos érték megfogalmazott feltételét. Az algoritmus megvalósításának sokféle módja lehet , és minden program helyes , amelyek végrehajtása a megfogalmazott feltételnek megfelelő helyes eredményt ad. Néhány feltétel teljesítése azonban algoritmikusan eldönthetetlen lehet .
Például a "két egész és három tized" pontos érték kiszámítható , mivel a számítás eredménye egy racionális szám , amely véges időn belül természetes számok arányaként írható fel véges mennyiségű memória felhasználásával. A „kör kerületének és átmérőjének hosszához viszonyított aránya” pontos érték pedig elvileg kiszámíthatatlan, mivel a kívánt eredmény valójában egy irracionális szám , amelynek pontos értéke még elméletileg sem ábrázolható semmilyen arányszámmal. természetes számokból, függetlenül attól, hogy milyen számokat próbálunk kiválasztani. Véges idő alatt a tizedesvessző után tetszőleges számú véges számjegyű Pi számnak csak közelítő értékét lehet kiszámítani, amelynek kiszámításához elegendő idő és tárolására elegendő memória (az , csak egy közelítő Pi értéke racionális szám formájában számítható ki ). A pi pontos értéke azonban kiszámíthatatlan: a pi pontos értékét kiszámító program korlátlan ideig fog futni, és végtelen mennyiségű memóriát igényel az egyes iterációk során felhalmozott adatok tárolására . A "kör kerületének és átmérőjének hosszához viszonyított arány" természetes számokkal való írásának feltétele elvileg lehetetlen, ha nincs megadva a megengedett hiba.
Hasonlóképpen, egy bizonyos „Richard-szám” kiszámításakor ellenőrizni kell a fenti feltételt: „Valós szám, amelynek n-edik tizedesjele 1, ha az n-edik Richard-szám n-edik tizedeshelye nem egyenlő 1, és az n-edik tizedesjegy egyenlő 2-vel, ha az n-edik Richard-szám n-edik tizedesjegye 1-gyel egyenlő. Egy ilyen ellenőrzés megköveteli a program végrehajtását egy rekurzív hívással (a leírás egy bizonyos „Richard-számon” tartalmaz műveleteket, amelyek értékének kiszámításához újra kell indítani a program algoritmusának következő végrehajtását rekurzív merítéssel a beágyazás mélységének korlátozása nélkül, végtelenül nagy mennyiségű memória és korlátlan idő használatának elvárásával).
A kívánt "Richard-szám" a fenti megfogalmazásban kiszámíthatatlan és algoritmikusan megoldhatatlan , vagyis nincs véges idő alatt kiszámítható algoritmus azon egyszerű oknál fogva, hogy a helyes eredmény feltétele nyilvánvalóan lehetetlen.