Richardův paradox je sémantický paradox , který poprvé popsal francouzský matematik Jules Richard v roce 1905.
S pomocí některých frází libovolného jazyka lze charakterizovat určitá reálná čísla . Například výraz „poměr obvodu kruhu k délce jeho průměru“ charakterizuje číslo „pí“ a výraz „dvě celé a tři desetiny“ charakterizuje číslo 2,3. Všechny takové fráze tohoto jazyka lze určitým způsobem očíslovat (pokud například fráze seřadíte abecedně jako ve slovníku, pak každá fráze obdrží číslo, kde se nachází). Nyní ponechme v tomto výčtu frází pouze ty fráze, které charakterizují jedno reálné číslo (a ne dvě nebo více). Číslo, které je charakterizováno takovým číslováním frázovým číslem n , budeme nazývat n -té Richardovo číslo.
Zvažte následující větu: „Reálné číslo, jehož n-té desetinné místo je 1, pokud n-té Richardovo číslo má n-té desetinné místo jiné než 1, a n-té desetinné místo je 2, pokud má n -té Richardovo číslo N-té desetinné místo je 1“. Tato fráze definuje nějaké Richardovo číslo, řekněme k -e; nicméně z definice se liší od k -tého Richardova čísla na k -tém desetinném místě. Tím jsme se dostali k rozporu.
V teorii vyčíslitelnosti jsou pokusy získat výsledek výpočtu "Richardova čísla" v uvedené formulaci algoritmicky nerozhodnutelné. Uvedené slovní popisy čísla určují nejen hodnotu samotnou, ale i podmínku úspěšného dokončení algoritmů pro výpočet této hodnoty ve formě určitých programů , jejichž provedení může v obecném případě vyžadovat neomezené množství paměť a nekonečný čas ve snaze vybrat výsledné racionální číslo , které splňuje formulovanou podmínku přesné hodnoty. Algoritmus může být implementován mnoha způsoby a všechny programy jsou správné , jejichž provedení dává správný výsledek, který splňuje formulovanou podmínku. Ale splnění některých podmínek může být algoritmicky nerozhodnutelné .
Například přesná hodnota "dvě celá čísla a tři desetiny" je vypočitatelná , protože výsledkem výpočtu je racionální číslo , které lze zapsat jako poměr přirozených čísel v konečném čase za použití konečného množství paměti. A přesná hodnota „poměr obvodu kruhu k délce jeho průměru“ je v zásadě nevyčíslitelná, protože požadovaný výsledek je ve skutečnosti iracionální číslo , jehož přesnou hodnotu ani teoreticky nelze vyjádřit žádným poměrem. přirozených čísel, bez ohledu na to, jaká čísla se snažíme vybrat. V konečném čase je možné vypočítat pouze přibližnou hodnotu čísla Pi s libovolným konečným počtem číslic za desetinnou čárkou, na jejíž výpočet je dostatek času a na jejíž uložení je dostatek paměti (že je , je vyčíslitelná pouze přibližná hodnota Pi ve tvaru racionálního čísla ). Přesná hodnota pí je však nevypočitatelná: jakýkoli program pro výpočet přesné hodnoty pí poběží neomezeně dlouho a vyžaduje nekonečné množství paměti pro uložení stále více dat nashromážděných při každé iteraci . Podmínka zápisu "poměru obvodu kruhu k délce jeho průměru" přirozenými čísly je v zásadě nemožná, není-li uvedena dovolená chyba.
Obdobně při výpočtu určitého „Richardova čísla“ bude nutné zkontrolovat výše uvedenou podmínku „Reálné číslo, jehož n-té desetinné místo je 1, pokud n-té Richardovo číslo nemá n-té desetinné místo rovné 1 a n-té desetinné místo je rovno 2, pokud má n-té Richardovo číslo n-té desetinné místo rovné 1. Taková kontrola bude vyžadovat spuštění programu s rekurzivním voláním na sebe (popis obsahuje operace s určitým „Richardovým číslem“, pro výpočet hodnoty, jehož hodnotu je nutné spustit znovu s dalším spuštěním algoritmu tohoto programu s rekurzivním ponořením bez omezení hloubky vnoření, s očekáváním využití nekonečně velkého množství paměti a neomezeného času).
Požadované "Richardovo číslo" ve výše uvedené formulaci je nevypočitatelné a algoritmicky neřešitelné , to znamená, že neexistuje žádný algoritmus, který by jej mohl vypočítat v konečném čase z prostého důvodu, že podmínka správného výsledku je zjevně nemožná.