Liczb, które potrafi obliczać algorytm, jest tylko przeliczalnie wiele
Alan Turing zdefiniował liczby obliczalne jako takie, których cyfry można w zasadzie wyznaczać mechanicznie z dowolną żądaną dokładnością. Każdy konkretny algorytm ma skończony opis, a skończonych napisów nad skończonym alfabetem jest tylko przeliczalnie wiele. Zatem liczb obliczalnych również jest co najwyżej przeliczalnie wiele. Tymczasem liczb rzeczywistych jest nieprzeliczalnie wiele. Wniosek jest zdumiewający: niemal cała nieskończona większość liczb rzeczywistych nie może być wynikiem żadnego programu obliczającego ich kolejne cyfry.
Co znaczy, że liczba jest obliczalna
W intuicyjnym ujęciu liczba rzeczywista jest obliczalna, jeśli istnieje algorytm, który pozwala wyznaczyć jej przybliżenie z dowolnie dużą zadaną dokładnością. Turing w 1936 roku sformalizował podobną ideę przy pomocy swoich maszyn. Znane stałe, takie jak π czy e, są obliczalne: istnieją procedury pozwalające generować ich cyfry lub coraz dokładniejsze przybliżenia. Obliczalność nie wymaga prostego wzoru zamkniętego — wymaga skutecznej, skończenie opisanej procedury.
Dlaczego algorytmów jest tylko przeliczalnie wiele
Każdy program jest skończonym ciągiem symboli zapisanych w pewnym skończonym alfabecie. Wszystkie napisy długości 1 można wypisać, potem długości 2, 3 i tak dalej. Unia tych skończonych warstw daje zbiór przeliczalny. Możemy zatem ponumerować wszystkie możliwe programy: P1, P2, P3, …. Nie każdy program oblicza liczbę rzeczywistą i różne programy mogą obliczać tę samą liczbę, ale to tylko zmniejsza liczbę możliwych wyników. Zbiór liczb obliczalnych pozostaje przeliczalny.
Zderzenie z nieprzeliczalnością R
Cantor pokazał, że zbiór liczb rzeczywistych jest nieprzeliczalny. Nie może więc istnieć program dla każdej liczby rzeczywistej, ponieważ programów jest tylko przeliczalnie wiele. Po usunięciu wszystkich liczb obliczalnych z R nadal pozostaje nieprzeliczalnie wiele liczb. To argument czysto licznościowy: nie musimy umieć wskazać większości tych liczb ani znać ich cyfr. Wiemy, że muszą istnieć, bo po prostu nie starcza algorytmów, aby je wszystkie pokryć.
Dlaczego prawie wszystkie są dla nas anonimowe
W praktyce liczby, o których mówimy w matematyce, mają skończone definicje: π, √2, stałe określone równaniem, granicą, szeregiem czy algorytmem. Takich skończonych opisów jest tylko przeliczalnie wiele. Tymczasem continuum jest nieprzeliczalne. Powstaje więc ogromna przepaść między wszystkimi liczbami istniejącymi w standardowym modelu R a liczbami, które możemy indywidualnie opisać lub obliczać za pomocą skończonych procedur. To jeden z najbardziej kontrintuicyjnych skutków teorii mnogości i obliczeń.
Nieobliczalna nie znaczy losowa ani tajemnicza z definicji
Słowo „nieobliczalna” ma precyzyjny techniczny sens. Nie oznacza po prostu „bardzo trudna do policzenia” ani „wymagająca zbyt dużego komputera”. Chodzi o brak algorytmu, który w określonym modelu obliczeń dawałby przybliżenia z dowolną dokładnością. Problem nie znika po zwiększeniu pamięci czy szybkości sprzętu, ponieważ dotyczy istnienia procedury w ogóle, a nie jej kosztu.
Turing poszedł dalej niż argument licznościowy
Sam rachunek kardynalności dowodzi, że nieobliczalne obiekty istnieją, lecz nie wskazuje konkretnego przykładu. Turing badał również problemy, które pozwalają konstruować jawnie zdefiniowane nieobliczalne zachowania i pokazał granice procedur mechanicznych. To ważne rozróżnienie: „istnieje, bo jest za dużo liczb” to jeden poziom argumentu, a konkretny dowód nierozstrzygalności dla zdefiniowanego problemu — znacznie silniejszy i bardziej informacyjny krok.
W sensie miary obliczalne liczby są znikome
Ponieważ liczb obliczalnych jest przeliczalnie wiele, tworzą one zbiór miary zero na osi rzeczywistej. W tym precyzyjnym, miarowym sensie „prawie każda” liczba rzeczywista jest nieobliczalna. Sformułowanie to nie znaczy jednak, że potrafimy łatwo wskazywać konkretne przykłady takich liczb. Jest wręcz odwrotnie: aby nazwać konkretną liczbę, zwykle podajemy skończony opis lub regułę, a takie opisy są właśnie domeną obiektów, które dają się formalnie uchwycić. Argument licznościowy gwarantuje ogrom nieobliczalnych liczb, ale większość z nich nie przychodzi z wygodną nazwą czy krótkim wzorem. Co ważne, przeliczalność programów nie zależy od konkretnego języka programowania. Każdy program jest skończonym napisem złożonym ze skończonego lub co najwyżej przeliczalnego alfabetu, a takie napisy można uporządkować według długości i następnie leksykograficznie. Nawet gdyby każdy poprawny program wyznaczał inną liczbę rzeczywistą, nadal otrzymalibyśmy tylko zbiór przeliczalny. W rzeczywistości wiele programów oblicza tę samą liczbę, a część w ogóle nie definiuje poprawnego procesu przybliżania liczby. Argument o większości liczb nieobliczalnych jest więc bardzo odporny: wynika z samej różnicy kardynalności między opisami algorytmicznymi a continuum.