Număr calculat

În matematică , un număr computabil (sau recursiv ) este un număr care poate fi calculat cu orice precizie dată de un algoritm (pentru numere complexe, atât părțile reale, cât și cele imaginare trebuie să fie calculabile).

Se spune că un număr care nu este calculabil este necalculabil (un exemplu de număr necalculabil este constanta lui Chaitin în problema opririi ).

Orice număr algebric (și, prin urmare, orice număr rațional și cu atât mai mult orice număr întreg ) este calculabil. Orice element al inelului perioadei (care include numărul π și multe alte numere transcendentale ) este calculabil. Orice număr calculat este aritmetic .

Setul tuturor numerelor calculabile este numărabil , iar setul tuturor numerelor necalculabile este nenumărabil . Setul tuturor numerelor calculabile (precum și setul tuturor numerelor necalculabile) este dens în și în $\mathbb {R}$ $\mathbb {C} .$

Ordinea în mulțimea numerelor reale calculabile este izomorfă cu ordinea în mulțimea numerelor raționale.

Definiție

Un număr real se numește computabil [1] dacă există un algoritm care permite fiecăruia să calculeze într-un număr finit de pași o fracție binară astfel încât . $X$ $n\în P$ $a={\frac {k}{2^{r)}},\k\in \mathbb {Z} ,\r\in \mathbb {N}$ ${\displaystyle |xa|<2^{-n))$

Proprietăți

Suma , diferența și produsul numerelor calculabile sunt calculabile.
Limita unei secvențe calculabile de numere raționale nu este neapărat un număr computabil (dar este întotdeauna 0′-calculabil )
Există o corespondență unu-la-unu între submulțimile calculabile și numerele reale calculabile [1] . $S\subset P$ $x\in [0,1]$

Vezi și

Decidabilitatea algoritmică
Gradul de insolubilitate

Note

↑ 1 2 Birkhoff G. , Barty T. Modern Applied Algebra. - M., Mir, 1976. - p. 375, 376.

Sisteme numerice
Seturi numărabile	numere naturale ( ) $\scriptstyle \mathbb {N}$ numere întregi ( ) $\scriptstyle \mathbb {Z}$ Rațional ( ) $\scriptstyle \mathbb {Q}$ algebric ( ) $\scriptstyle {\overline {\mathbb {Q} }}$ Perioadele Calculabil Aritmetic
Numerele reale și extensiile lor	Real ( ) $\scriptstyle \mathbb {R}$ Complex ( ) $\scriptstyle \mathbb {C}$ Cuaternioni ( ) $\scriptstyle \mathbb {H}$ Numerele Cayley (octave, octooni) ( ) $\scriptstyle \mathbb {O}$ Sedenions ( ) $\scriptstyle \mathbb {S}$ Alterniuni Dual Hipercomplex Superreale Hipermaterial ireal
Instrumente de extensie numerică	Procedura Cayley-Dixon Teorema Frobenius Teorema Hurwitz
Alte sisteme numerice	numere cardinale Numere ordinale (transfinite, ordinale) p-adic Numere supranaturale numere de interval
Vezi si	numere duble Numere irationale numerele transcendentale fascicul numeric Biquaternion