Informatyka i programowanieGranice obliczeń — problemy łatwe, trudne i niemożliwe

Prawie wszystkie liczby rzeczywiste są nieobliczalne

Liczba rzeczywista jest obliczalna, jeśli istnieje skończony algorytm potrafiący przybliżać ją z dowolnie zadaną dokładnością. π, e czy √2 spełniają ten warunek. Zaskoczenie pojawia się przy policzeniu „ile” takich liczb istnieje. Programy są skończonymi napisami nad skończonym alfabetem, więc jest ich tylko przeliczalnie wiele. Każdy program może definiować najwyżej określoną liczbę rzeczywistą w danym schemacie obliczania, więc liczb obliczalnych jest co najwyżej przeliczalnie wiele. Zbiór wszystkich liczb rzeczywistych jest nieprzeliczalny. Co więcej, każdy zbiór przeliczalny ma miarę Lebesgue’a zero — zatem w standardowym sensie miary „prawie każda” liczba rzeczywista jest nieobliczalna.

Co znaczy obliczyć liczbę

Nie trzeba wypisywać nieskończonego rozwinięcia dziesiętnego naraz. W standardowej definicji algorytm otrzymuje żądaną dokładność n i zwraca przybliżenie wymierne, którego błąd jest odpowiednio mały, np. mniejszy niż 2^−n. Dzięki temu liczby o nieskończonym i nieregularnym rozwinięciu mogą być obliczalne, jeśli istnieje skuteczna procedura generowania coraz dokładniejszych przybliżeń.

Programów jest tylko przeliczalnie wiele

Każdy program ma skończony tekst. Wszystkie skończone ciągi bitów można uporządkować według długości, a potem leksykograficznie, tworząc listę przeliczalną. Nie każdy ciąg jest poprawnym programem i nie każdy program oblicza liczbę rzeczywistą, ale to tylko zmniejsza zbiór. Zatem liczb, dla których istnieje odpowiedni program, nie może być więcej niż programów: są co najwyżej przeliczalne.

Reali jest nieprzeliczalnie wiele

Cantor pokazał metodą diagonalną, że liczb rzeczywistych nie da się umieścić na kompletnej liście ponumerowanej liczbami naturalnymi. Kardynalność continuum jest większa niż zbioru przeliczalnego. Stąd większość liczb rzeczywistych w sensie liczności nie ma algorytmu generującego ich przybliżenia. To prawda nawet though wszystkie liczby, których zwykle używamy w nauce i technice, należą do maleńkiej, specjalnej części continuum.

„Prawie wszystkie” także w sensie miary

Zbiór obliczalnych liczb rzeczywistych jest przeliczalny, a każdy przeliczalny podzbiór prostej ma miarę Lebesgue’a zero. Oznacza to, że na dowolnym skończonym przedziale udział miary przypadający na liczby obliczalne wynosi zero. „Prawie wszystkie” jest więc tutaj precyzyjnym terminem teorii miary, nie tylko publicystycznym skrótem.

Paradoks codziennej matematyki

W praktyce spotykamy głównie liczby definiowalne i obliczalne, bo aby konkretną liczbę podać w książce, programie czy pomiarze, potrzebujemy skończonego opisu. Ogromna większość continuum nie ma takiego algorytmicznego uchwytu. To pokazuje, że matematyczny zbiór liczb rzeczywistych jest znacznie większy niż świat liczb, które komputer może generować z dowolną dokładnością.

„Prawie wszystkie” ma tu precyzyjne znaczenie

Stwierdzenie nie jest tylko retoryką opartą na tym, że liczb nieobliczalnych jest „więcej”. Zbiór liczb obliczalnych jest przeliczalny, ponieważ każdy program ma skończony opis i skończonych napisów jest przeliczalnie wiele. Każdy przeliczalny podzbiór prostej ma miarę Lebesgue’a zero. W tym standardowym sensie miary zbiór liczb obliczalnych zajmuje zerową część continuum, a liczby nieobliczalne mają pełną miarę. Paradoks poznawczy polega na tym, że liczby, którymi faktycznie umiemy się posługiwać — wymienić je, opisać algorytmem i obliczać ich cyfry — pochodzą właśnie z tej wyjątkowej, bardzo małej klasy.

Dlaczego nie potrafimy wskazać „losowej typowej” liczby

Choć prawie wszystkie liczby rzeczywiste są nieobliczalne, każda konkretna liczba, którą wygodnie definiujemy algorytmem — π, e, √2 czy liczby algebraiczne — trafia do wyjątkowej klasy obliczalnej. Sam fakt nazwania liczby skończonym przepisem już silnie ją wyróżnia. Dlatego twierdzenie o „prawie wszystkich” jest łatwe kardynalnie i miarowo, ale trudno zamienić je w katalog zwyczajnych przykładów: nasz sposób specyfikowania liczb faworyzuje właśnie obiekty o skończonych opisach.

#Cantor#liczby obliczalne#liczby rzeczywiste#miara zero#obliczalność
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki