Vypočitatelné číslo
V matematice a teoretický informatika, reálné číslo je řekl, aby byl vypočitatelné číslo jestliže to může být zaokrouhlené nějakým algoritmem, v následujícím smyslu: daný nějaké přirozené číslo n, algoritmus produkuje číslo m takový to:Nebo, equivalently, tam existuje algoritmus který, daný nějaká rozumná chyba vázala, produkuje přiblížení m takový to:
komplexní číslo je voláno vypočitatelný jestliže jeho skutečné a fiktivní části jsou vypočitatelné.
Vypočitatelná čísla se tvoří algebraicky uzavřený pole, a pravděpodobně toto pole obsahuje všechna čísla my někdy potřebujeme v praxi. To obsahuje všechna algebraická čísla také tolik známý transcendentní matematické konstanty. Tam je nicméně mnoho reálných čísel, která nejsou vypočitatelná: soubor všech vypočitatelných čísel je počitatelný (protože soubor algoritmů je) zatímco soubor reálných čísel není (viz Cantorův úhlopříčný argument).
Zatímco soubor vypočitatelných čísel je počitatelný, to nemůže být vypočítáno nějakým algoritmem, programem nebo Turing strojem. Formálně: to je ne možný poskytovat kompletní seznam x1, x2, x3,... všech vypočitatelných reálných čísel a Turing stroj který na vstupu (m, n) produkuje n- th číslice xm. Toto je dokázané s nepatrnou modifikací Cantorova úhlopříčného argumentu.
Každé vypočitatelné číslo je definovatelné, ale ne versa zlozvyku. Příklad definovatelný, non-vypočitatelné reálné číslo je Chaitin je konstanta a omega;.
- Alan Turing, Na vypočitatelných číslech, s použitím na Entscheidungsproblem, soudní řízení Londýna matematická společnost, série 2, 42 (1936), 230 pp-265. online verze. Vypočitatelná čísla (a Turing stroje) byl představen v tomto papíru.