Beräknat antal

I matematik är ett beräkningsbart (eller rekursivt ) tal ett tal som kan beräknas med vilken precision som helst med en algoritm (för komplexa tal måste både reella och imaginära delar vara beräkningsbara).

Ett tal som inte är beräkningsbart sägs vara icke beräkningsbart (ett exempel på ett icke beräkningsbart tal är Chaitins konstant i stoppproblemet ).

Alla algebraiska tal (och därmed alla rationella och ännu mer alla heltal ) är beräkningsbara. Alla element i periodringen (som inkluderar talet π och många andra transcendentala tal ) är beräkningsbara. Alla beräkningsbara tal är aritmetiska .

Uppsättningen av alla beräkningsbara siffror kan räknas och mängden av alla icke beräkningsbara siffror är oräkneliga . Uppsättningen av alla beräkningsbara tal (liksom mängden av alla icke-beräknbara tal) är tät i och i $\mathbb {R}$ $\mathbb {C} .$

Ordningen på mängden beräkningsbara reella tal är isomorf med ordningen på mängden rationella tal.

Definition

Ett reellt tal kallas beräkningsbart [1] om det finns en algoritm som tillåter var och en att i ett ändligt antal steg beräkna en binär bråkdel så att . $x$ $n\in P$ $a={\frac {k}{2^{r))},\ k\in \mathbb {Z} ,\ r\in \mathbb {N}$ ${\displaystyle |xa|<2^{-n))$

Egenskaper

Summan , skillnaden och produkten av beräkningsbara tal är beräkningsbara.
Gränsen för en beräkningsbar sekvens av rationella tal är inte nödvändigtvis ett beräkningsbart tal (men är alltid 0′-beräknarbar )
Det finns en en-till-en-överensstämmelse mellan beräkningsbara delmängder och beräkningsbara reella tal [1] . $S\delmängd P$ $x\in [0,1]$

Se även

Algoritmisk avgörbarhet
Grad av olöslighet

Anteckningar

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

Numeriska system
Räknebara set	Naturliga tal ( ) $\scriptstyle \mathbb {N}$ Heltal ( ) $\scriptstyle \mathbb {Z}$ Rationell ( ) $\scriptstyle \mathbb {Q}$ Algebraisk ( ) $\scriptstyle {\overline {\mathbb {Q} }}$ Perioder Beräknarbar Aritmetisk
Reella tal och deras anknytningar	Riktig ( ) $\scriptstyle \mathbb {R}$ Komplex ( ) $\scriptstyle \mathbb {C}$ Kvaternioner ( ) $\scriptstyle \mathbb {H}$ Cayley-tal (oktaver, oktonjoner) ( ) $\scriptstyle \mathbb {O}$ Sedenioner ( ) $\scriptstyle \mathbb {S}$ Ändringar Dubbel Hyperkomplex Superrealistiskt Hypermaterial surrealistiskt
Numeriska förlängningsverktyg	Cayley-Dixon procedur Frobenius teorem Hurwitz teorem
Andra nummersystem	grundtal Ordningstal (transfinita, ordningstal) p-adic Övernaturliga siffror intervallnummer
se även	dubbla siffror Irrationella siffror transcendentala tal nummerstråle Biquaternion