Liczby obliczalne

Liczby obliczalne (ang. computable numbers) to pojęcie z dziedziny teorii computacji, opisujące rzeczywiste liczby, które można wyznaczyć z dowolną dokładnością przy pomocy algorytmu skończonego działania. Idea ta została sformułowana po raz pierwszy w pracy Alonzo Churcha i Alana Turinga pod koniec lat 30. XX wieku i odgrywa kluczową rolę w rozumieniu granic obliczalności oraz w dowodach o nieobliczalności niektórych zbiorów liczb.

Definicja formalna

Liczbę rzeczywistą x nazywamy obliczalną, jeśli istnieje maszyna Turinga M (lub równoważny model, np. program w języku λ‑kalkul), który dla każdego dodatniego całkowitego n po zakończeniu działania wypisuje liczbę całkowitą qₙ spełniającą nierówność

| x − qₙ / 10ⁿ | < 10⁻ⁿ .

Innymi słowy, maszyna jest w stanie wygenerować kolejne przybliżenia dziesiętne liczby x w dowolnie wybranej precyzji.

Historia

W 1936 roku Alan Turing wprowadził pojęcie maszyny Turinga w pracy „On Computable Numbers, with an Application to the Entscheidungsproblem”. W tej samej publikacji zdefiniował liczby obliczalne jako te, które można uzyskać przy pomocy takiej maszyny. Równocześnie Alonzo Church opracowywał teorię λ‑kalkulu, prowadząc do analogicznej definicji obliczalności.

Przykłady liczb obliczalnych

• Wszystkie liczby wymierne – można je wypisać dokładnie przy pomocy skończonego algorytmu.
• Liczby algebraiczne, czyli pierwiastki wielomianów o współczynnikach całkowitych, np. √2, ∛5.
• Liczby transcendentne o znanej konstrukcji, np. π i e. Choć ich własności są skomplikowane, istnieją algorytmy (np. szereg Taylora), które pozwalają obliczyć ich przybliżenia dowolnej dokładności.
• Liczby definiowane jako granice zbieżnych ciągów skutecznie obliczalnych, np. liczba Chaitina‑Ω, będąca prawdopodobieństwem, że losowy program zakończy się w trybie przystankowym (choć Ω jest nieobliczalna, jej kolejno‑rosnące przybliżenia można generować).

Nieobliczalne liczby

Zbiór liczb rzeczywistych jest nieprzeliczny, podczas gdy zbiór liczb obliczalnych jest przeliczny. Oznacza to, że “większość” liczb rzeczywistych jest nieobliczalna. Przykładem najbardziej znanym nieobliczalnym jest liczba Chaitina‑Ω, a także niektóre liczby definiowane przy pomocy problemów nierozstrzygalnych, np. liczba definiująca odpowiedź na problem rozdzielania.

Powiązania z innymi pojęciami

• Teoria computacji – ramy teoretyczne, w których badane są klasy funkcji i problemów pod względem ich obliczalności.
• Maszyna Turinga – model formalny, którego działanie definiuje, które liczby są obliczalne.
• Algorytm – skończony zestaw instrukcji, którego istnienie dla danej liczby jest równoważne jej obliczalności.
• Hipoteza Churcha‑Turinga – twierdzenie, że wszystkie „intuicyjnie wykonalne” obliczenia mogą zostać zrealizowane przez maszynę Turinga.
• Liczby nieobliczalne – przeciwieństwo liczb obliczalnych, które wykazują granice możliwości algorytmicznego przetwarzania.

Zastosowania

W praktyce pojęcie liczb obliczalnych znajduje zastosowanie w dziedzinach takich jak:

• Analiza numeryczna – zapewnia podstawowe uzasadnienie dla metod przybliżania funkcji i rozwiązywania równań.
• Kryptografia – w tworzeniu generatorów liczb pseudolosowych, które muszą wykazywać właściwości trudne do odtworzenia przy ograniczonych zasobach.
• Logika matematyczna – w dowodach niezupełności i badaniach granic formalnych systemów.

Podsumowanie

Liczby obliczalne stanowią most pomiędzy matematyką a informatyką, określając, które elementy kontinuum rzeczywistego można skutecznie przybliżać przy pomocy skończonych procedur algorytmicznych. Ich badanie pozwala nie tylko lepiej zrozumieć naturę obliczeń, ale także wyznaczyć granice tego, co jest możliwe do wyliczenia w ramach przyjętego modelu maszynowego.