Paradoxul lui Richard este un paradox semantic descris pentru prima dată de matematicianul francez Jules Richard în 1905.
Cu ajutorul unor fraze din orice limbă se pot caracteriza anumite numere reale . De exemplu, expresia „raportul dintre circumferința unui cerc și lungimea diametrului său” caracterizează numărul „pi” , iar expresia „două întregi și trei zecimi” caracterizează numărul 2,3. Toate astfel de fraze din această limbă pot fi numerotate într-un anumit mod (de exemplu, dacă sortați frazele alfabetic, ca într-un dicționar, atunci fiecare frază va primi numărul în care se află). Acum să lăsăm în această enumerare de fraze doar acele fraze care caracterizează un număr real (și nu două sau mai multe). Numărul, care este caracterizat printr-o astfel de numerotare prin fraza numărul n , îl vom numi numărul n --lea Richard.
Luați în considerare următoarea propoziție: „Un număr real a cărui a n- a zecimală este 1 dacă al n- a număr Richard are a n- a zecimală, alta decât 1, iar a n- a zecimală este 2 dacă al n- a număr Richard are A n- a zecimală este 1". Această frază definește un număr Richard, să spunem k -e; cu toate acestea, prin definiție, diferă de numărul k - al- lea Richard în k - a zecimală. Astfel, am ajuns la o contradicție.
În teoria computabilității, încercările de a obține rezultatul calculării „numărului Richard” în formularea indicată sunt algoritmic indecidabile. Descrierile verbale date ale numărului determină nu doar valoarea în sine, ci și condiția pentru finalizarea cu succes a algoritmilor pentru calcularea acestei valori sub forma anumitor programe , a căror execuție, în cazul general, poate necesita o cantitate nelimitată de memorie şi timp infinit în încercarea de a selecta numărul raţional rezultat care satisface condiţia formulată a valorii exacte . Pot exista multe moduri de implementare a algoritmului și toate programele sunt corecte , a căror execuție dă rezultatul corect care satisface condiția formulată. Dar satisfacerea unor condiții poate fi indecidabilă din punct de vedere algoritmic .
De exemplu, valoarea exactă „două numere întregi și trei zecimi” este calculabilă , deoarece rezultatul calculului este un număr rațional care poate fi scris ca raport al numerelor naturale într-un timp finit folosind o cantitate finită de memorie. Și valoarea exactă „raportul dintre circumferința unui cerc și lungimea diametrului său” este, în principiu, necalculabilă, deoarece rezultatul dorit este de fapt un număr irațional , a cărui valoare exactă, chiar și teoretic, nu poate fi reprezentată de niciun raport. de numere naturale, indiferent de numerele pe care încercăm să le selectăm. Într-un timp finit, este posibil să se calculeze doar o valoare aproximativă a numărului Pi cu orice număr finit de cifre după virgulă zecimală, pentru al cărui calcul este suficient timp și pentru a cărui stocare există suficientă memorie (aceasta este , doar o valoare aproximativă a lui Pi sub forma unui număr rațional este calculată ). Dar valoarea exactă a lui pi este necalculabilă: orice program pentru a calcula valoarea exactă a lui pi va rula pe termen nelimitat și va necesita o cantitate infinită de memorie pentru a stoca din ce în ce mai multe date acumulate cu fiecare iterație . Condiția de a scrie „raportul dintre circumferința unui cerc și lungimea diametrului său” în numere naturale este imposibilă în principiu, dacă eroarea admisă nu este specificată.
În mod similar, atunci când se calculează un anumit „număr Richard”, va fi necesar să se verifice condiția de mai sus „Un număr real a cărui a n-a zecimală este 1, dacă al n-a număr Richard are a n-a zecimală nu este egală cu 1, iar a n-a zecimală este egală cu 2 dacă al n-a număr Richard are a n-a zecimală egală cu 1. O astfel de verificare va necesita executarea programului cu un apel recursiv către el însuși (descrierea conține operații pe un anumit „număr Richard”, pentru a calcula valoarea căreia este necesar să începeți din nou următoarea execuție a algoritmului acestui program cu imersiune recursivă fără a limita adâncimea cuibării, cu așteptarea utilizării unei cantități infinit de memorie și timp nelimitat).
„Numărul Richard” dorit în formularea de mai sus este necalculabil și nerezolvabil din punct de vedere algoritmic , adică nu există un algoritm capabil să-l calculeze într-un timp finit din simplul motiv că condiția unui rezultat corect este evident imposibilă.