Număr real calculabil

În informatică și algoritmică , un număr real calculabil este un real pentru care există un algoritm sau o mașină Turing care face posibilă enumerarea secvenței cifrelor sale (posibil infinit) sau, mai general, a simbolurilor scrierii sale sub forma a unui sir de caractere . Mai general, și echivalent, un număr real este calculabil dacă putem calcula o aproximare cât de precisă dorim, cu o precizie cunoscută.

Această noțiune a fost pusă în aplicare de Alan Turing în 1936. A fost apoi dezvoltată în diferite ramuri ale matematicii constructive și mai ales în analiza constructivă .

Setul de reali calculabili este un câmp numărabil . Acesta conține, de exemplu, toate numerele algebrice reale sau constante celebre precum π sau γ .

Cei care nu sunt calculabile Reali sunt , prin urmare , mult mai numeroase, deși este în general dificil să le definească, și sunt pentru cea mai mare parte aleatoare numere . Cu toate acestea, reușim să caracterizăm unele dintre ele, cum ar fi constanta Omega a lui Chaitin sau numerele definite din castorul ocupat sau din suitele Specker .

Definiții principale

Orice x real este legat de multe secvențe de numere raționale . În special, există secvențe de perechi de numere întregi ( p n , q n ) , cu q n ≠ 0, astfel încât:

∀nu∈NU|X-pnuqnu|≤12nu.{\ displaystyle \ forall n \ in \ mathbb {N} \ quad \ left | x - {\ frac {p_ {n}} {q_ {n}}} \ right | \ leq {\ frac {1} {2 ^ {nu}}}.}

Se spune că numărul x este calculabil dacă, dintre aceste secvențe ( p n , q n ) , există unele care sunt calculabile . (Nu este suficient pentru aceasta ca x să fie limita unei secvențe raționale calculabile, așa cum arată exemplul secvențelor Specker  : este necesar, de asemenea, că pentru cel puțin o astfel de secvență, modulul de convergență  (en) este, de asemenea, calculabil .)

O definiție echivalentă este:

Un real este calculabil dacă secvența de cifre din orice bază este calculabilă.

Această definiție este adevărată dacă permitem fiecărei „cifre”, pentru orice bază, să fie posibil negativă, iar acest lucru este valabil mai ales pentru baza 10 . În schimb, într- un sistem binar , biții nu trebuie să fie negativi și aceasta este baza utilizată în general pentru a defini și calculabilitatea.

Un număr real poate fi calculabil chiar dacă cifrele sale nu sunt determinate direct. O a treia definiție, întotdeauna dovedită a fi echivalentă, este:

Un x real este calculabil dacă există un program pentru a enumera setul de raționale mai mare decât x și altul pentru a enumera setul de raționale mai mic decât x .

Construirea de numere calculabile

Fie A un set de numere naturale, realul

∑k∈LA2-k{\ displaystyle \ sum _ {k \ în A} 2 ^ {- k}}

este calculabil dacă și numai dacă mulțimea A este recursivă .

Mai concret, știm de exemplu că:

π=4∑k=0∞(-1)k2k+1{\ displaystyle \ pi = 4 \ sum _ {k = 0} ^ {\ infty} {\ frac {(-1) ^ {k}} {2k + 1}}}( Formula lui Leibniz ).

Prin urmare, este posibil să se determine raționalele care se apropie de π cu o precizie arbitrară (teoria alternativă a seriilor face chiar posibil să se știe pentru ce număr întreg m este necesar să se calculeze pentru a avea un număr dat de zecimale exacte). 4∑k=0m(-1)k2k+1{\ displaystyle 4 \ sum _ {k = 0} ^ {m} {\ frac {(-1) ^ {k}} {2k + 1}}}

Mai bine, orice număr dat de o secvență explicită din numere pe care le-am arătat deja că sunt calculabile este, de asemenea, așa. De exemplu, nu numai e este calculabil deoarece

e=∑nu=0+∞1nu!{\ displaystyle \ mathrm {e} = \ sum _ {n = 0} ^ {+ \ infty} {1 \ peste n!}}

dar pentru orice număr calculabil x (de exemplu x = π ), numărul e x este și pentru că

eX=∑nu=0+∞Xnunu!.{\ displaystyle \ mathrm {e} ^ {x} = \ sum _ {n = 0} ^ {+ \ infty} {x ^ {n} \ over n!}.}

Deci, pentru orice funcție calculabilă , imaginea unui număr calculabil este un număr calculabil; de exemplu cosinusul unui rațional dat este calculabil (invers, dacă un x real nu este calculabil atunci e x , de exemplu, nu este nici unul altfel, altfel x = ln (e x ) ar fi).

Starea setului de reali calculabili

• Setul de reali calculabili este un subcâmp al lui ℝ.
• Conține algebra perioadelor (deci toate numerele algebrice reale și anumite numere transcendente precum π ), dar și constanta Euler-Mascheroni γ (pe care nu știm dacă este rațională).
• Este un adevărat corp închis .
• Este un set numărabil (un algoritm fiind o serie finită de litere ale unui alfabet finit, setul de algoritmi și, prin urmare, a fortiori al numerelor calculabile, este numărabil). Prin urmare, aproape toate numerele reale nu pot fi calculate (complementare unui set numărabil). Acestea sunt în mare parte numere aleatorii . Deși sunt foarte numeroase , este dificil să le expui „explicit”. Cu toate acestea, se poate cita constanta Omega a lui Chaitin sau numerele definite de castorul ocupat .
• Deoarece setul de reali calculabili este numărabil, s-ar putea fi tentați să spunem că aplicarea metodei diagonale a lui Cantor la acest set ar oferi un algoritm pentru a calcula un număr nou, ceea ce ar duce la o contradicție. Răspunsul lui Turing este că nu știm cum să atribuim un număr fiecărui număr calculabil (mai precis, putem demonstra cu ușurință, cu precizie, că o astfel de atribuire nu este calculabilă), dar acest lucru trebuie făcut înainte de diagonalizare.
• Egalitatea dintre realele calculabile nu este decisă .

Extensii

Număr complex calculabil

Prin extensie, un număr complex ale cărui părți reale și imaginare sunt simultan calculabile se numește număr complex calculabil.

Succesiune calculabilă a numerelor reale

Se spune că o serie de reali ( x m ) este calculabilă dacă există o serie calculabilă (dublă indexată) de perechi de numere întregi ( p m, n , q m, n ) , cu q m, n ≠ 0, astfel încât:

∀m,nu∈NU|Xm-pm,nuqm,nu|≤12nu.{\ displaystyle \ forall m, n \ in \ mathbb {N} \ quad \ left | x_ {m} - {\ frac {p_ {m, n}} {q_ {m, n}}} \ right | \ leq {\ frac {1} {2 ^ {n}}}.}

Fiecare dintre realii x m este apoi clar calculabil.

Dacă secvența (dublă indexată) a zecimalelor lui x m este calculabilă, atunci ( x m ) este o serie calculabilă de reali, dar inversul este fals și, de asemenea, înlocuind 10 cu orice bază > 1.

Note și referințe

Note

1. Turing 1937
2. Di Gianantonio 1996 , p.  1
3. Vezi § „Construirea prin secvențe Cauchy” a articolului „Construcția numerelor reale”
4. Pentru definiții și referințe echivalente, cf. de exemplu Mostowski 1979 , p.  96, Rice 1954 și Pour-El și Richards 1989 .
5. Există o întreagă ierarhie a claselor de reali definite în mod similar. De exemplu, prin înlocuirea funcțiilor calculabile cu funcțiile recursive primare (în numărător, numitor și modulul de convergență al secvenței raționale), definim noțiunea (mai restrictivă) de număr real elementar  : cf. Bibliografie (în) Katrin Tent și Martin Ziegler, Funcții scăzute ale realelor. „  0903.1384  ” , text accesibil gratuit, pe arXiv .
6. Di Gianantonio 1996 , def. d), p.  4
7. Rice 1954 , def. B, p.  784
8. Mostowski 1957
9. Numere JP Delayahe Omega în aleatoriu și complexitate. De la Leibniz la Chaitin World Scientific, 2007, p. 355
10. Weihrauch 2000 , p.  5, Exemplul 1.3.2 sau Weihrauch 1995 , p.  21 exemplu 1 (4)
11. Mostowski 1979 , p.  96
12. Turing 1937 , § 8
13. Cf. Mostowski 1979 , p.  96 și câteva explicații în (en) Secvență calculabilă , pe Planetmath .
14. Mostowski 1957 stabilește incluziuni stricte între diferite variante, care totuși corespund definițiilor echivalente ale unui real calculabil și subliniază analogia inexplicabilă cu neechivalența, deja observată de Specker , a acestor aceleași variante în definiția „a„ semi -calculabil ”real.

Bibliografie

• (ro) Pietro Di Gianantonio , „  Computabilitatea numărului real și teoria domeniului  ” , Informații și calcul , vol.  127, nr .  1,1996, p.  12-25 ( citește online )
• (ro) Andrzej Mostowski , Studii fundamentale: lucrări selectate , vol.  1, Amsterdam / New York, Elsevier ,1979( ISBN  978-0-444-85102-4 , citit online )
• (ro) A. Mostowski , „  Despre secvențe computabile  ” , Fund. Matematica. , vol.  44,1957, p.  37-51 ( citiți online )
• (ro) Marian B. Pour-El și J. Ian Richards , Computability in Analysis and Physics , Springer ,1989( citește online )
• (ro) HG Rice , „  Numere reale recursive  ” , Proc. Amar. Matematica. Soc. , vol.  5,1954, p.  784-791 ( citește online )
• (ro) Alan Turing, On Computable Numbers, with a Application to the Entscheidungsproblem: Proceedings of the London Mathematical Society , London Mathematical Society,1937( DOI  10.1112 / PLMS / S2-42.1.230 , citiți online )și „  [ idem ]: A Correction  ”, Proc. London Math. Soc. , 2 nd serii, voi.  43,1938, p.  544-546 ( DOI  10.1112 / plms / s2-43.6.544 , citiți online )
• (ro) Klaus Weihrauch , O introducere simplă la analiza calculabilă , FernUniversität Hagen , col.  „Informatik Berichte” ( nr .  171),Iulie 1995, A 2 -a  ed. , 79  p. ( citește online )
• (ro) Klaus Weihrauch , Computable Analysis: An Introduction , Springer, col.  "Texte în informatică teoretică",2000, 285  p. ( ISBN  978-3-540-66817-6 , citit online )