V živote stretneme všelijaké čísla. Malé, veľké, kladné, záporné, celé, zlomky, odmocniny, imaginárne čísla, ale i takých špekulantov ako pí alebo Eulerovo číslo. Väčšina z nich má jednu spoločnú vlastnosť – vieme ich napísať. Keďže však veľa z týchto čísel má nekonečný rozvoj, je lepšie povedať, že vieme napísať počítačový program, ktorý nám dané číslo vypíše na ľubovoľný požadovaný počet desatinných miest. Čísla s takouto vlastnosťou sa nazývajú vypočítateľné (computable). [1]
Napríklad pre číslo pí poznáme mnoho jednoduchých vzorčekov, ktoré môžeme použiť na napísanie takého programu, ako
π = 4 × (1 – 1/3 + 1/5 – 1/7 + 1/9 – 1/11 + …)
Existujú však aj čísla, ktoré vypočítateľné nie sú. Čo je však ešte čudnejšie, väčšina reálnych čísel nie je vypočítateľná! Inak povedané, ak by ste hodili šípku na reálnu os, prakticky nikdy by sa vám nepodarilo trafiť číslo, ktoré sa dá vypísať nejakým počítačovým programom!
Ako je niečo také možné? Jednoducho. Vieme totiž zistiť, koľko existuje dokopy všetkých možných programov, ktoré môžeme napísať. Pri programovaní používame konečne veľa rôznych symbolov, v konečnom dôsledku sú to jednotky a nuly. Programy sú tiež vždy konečne dlhé, vieme preto ukázať, že počítačových programov je rovnako veľa ako prirodzených čísel. [2] Lenže my už vieme, že všetkých (reálnych) čísel je omnoho viac ako čísel prirodzených. Z toho prirodzene plynie, že vypočítateľné čísla tvoria len malú časť spomedzi všetkých čísel. Dobré, nie?
[Frico]Zdroj: wiki (Computable number)
[1] Ešte trochu presnejšie: vypočítateľné číslo Č je také, pre ktoré vieme napísať program, ktorému najprv zadáme prirodzené číslo P, a on nám následne po konečnom čase vypíše číslo Č s presnosťou na P desatinných miest. Predpokladáme pritom, že máme k dispozícii počítač s dostatočne veľkou pamäťou.[2] Inak povedané, keby sme chceli, môžeme si programy postupne očíslovať.
