Poznawalność i niepoznawalność

19 listopada 2009
Blog szalonych naukowców

Poznanie samochodu jest trudne, a komputera niemożliwe

Co dzień rano kupuję świeże pieczywo w sklepie pani Marzeny i pana Bogdana. Zaopatrzenie do swego sklepu dostarczają starszym już wiekiem Fordem Transitem, który niedawno miał kłopoty z instalacją elektryczną. Przez dłuższy czas pan Bogdan szukał elektryka, który by odkrył, co należy naprawić. Po kilku nieudanych próbach znalazł się  prawdziwy fachowiec, który w godzinę ustalił, co trzeba zrobić i dziś samochód znowu jeździ.

Pod moim poprzednim wpisem Bobola skomentował, że „Każdy kto prowadzi samochód czy używa komputera nie jest świadom całego szeregu operacji, które prowadzą do oczekiwanego rezultatu. Niemniej funkcjonowanie takich urządzeń nie oznacza fundamentalnej niepoznawalności ich działania.” (polskie literki dorobiłem sam).

Faktycznie, w wypadku samochodu udało się, choć wcale nie było łatwo i Ford stał nieczynny  kilka tygodni. Czemu to był taki problem, skoro wszystkich urządzeń elektrycznych i kabli jest w nim tylko kilkadziesiąt? Bo nie wystarczy znać je wszystkie, tylko trzeba znać objawy awarii w różnych konfiguracjach systemu, określonych przez to, które elementy nie funkcjonują należycie. Tych konfiguracji jest bez porównania więcej niż kilkadziesiąt.

A co z komputerem? Na pewno będzie trudniej, bo ma więcej elementów.

Porachujmy zatem, o ile trudniej. Komputer z 1 MB RAM ma około 1000000000 bajtów pamięci operacyjnej. Każdy z bajtów może zapisać 256 różnych wartości, ale powiedzmy, że w każdym bajcie zapisujemy tylko jedną cyfrę dziesiętną. Możemy w ten sposób zapisać każdą liczbę o co najwyżej 1000000000 cyfrach: od 0 (same zera wszędzie) do liczby złożonej z 1000000000 dziewiątek. To bardzo skromne oszacowanie wskazuje, że liczba różnych konfiguracji, w których może się teoretycznie znajdować komputer ma ponad 1000000000 cyfr.  Tymczasem liczba wszystkich cząstek w obserwowalnym wszechświecie nie ma więcej niż 100 cyfr. Do rozpatrywanej w filozofii matematyki nieskończoności potencjalnej i aktualnej dodałbym też nieskończoność praktyczną i uważam, że liczba konfiguracji, w których komputer może się znajdować jest praktycznie nieskończona.

Ta skala oznacza, że komputer jest fundamentalnie niepoznawalny, bo, jak wszyscy się domyślają, zmiana jednego bajtu w pamięci zmienia dalsze działanie programu. Oczywiście liczba stanów, w których każdy konkretny komputer znajdzie się w trakcie całego swego istnienia, jest drobnym pyłkiem przy tej praktycznej nieskończoności, ale żadnego stanu z niej nie można wyłączyć jako niemożliwego do uzyskania.

Wszystko co informatycy z tym robią, to próby wyodrębnienia i kontrolowania systematycznie zbudowanych konfiguracji, które są efektem działania dobrze napisanych i przetestowanych programów. Tylko tyle i aż tyle.

Ale nawet dla bardzo prostych programów pytanie, co się z nimi dzieje i jak działają, bywa dramatycznie trudne.  Nie mogę się powstrzymać od opisania problemu Collatza: startujemy od dowolnej dodatniej liczby całkowitej, którą zapisujemy w pamięci komputera. Jeśli jest ona podzielna przez 2, to ją dzielimy, a jeśli nie jest podzielna, to mnożymy ją przez 3 i do iloczynu dodajemy 1. W każdym wypadku wynik zapisujemy w miejsce starej liczby i powtarzamy operację z nową liczbą jeszcze raz, i jeszcze raz, i jeszcze raz, tak długo, aż w końcu dostaniemy 1 – albo w nieskończoność, jeśli nigdy 1 nie dostaniemy. Oczywiście tę procedurę można zapisać jako prościutki program komputerowy (można go dostrzec, choć pewnie nie odczytać, na ilustracji przedstawiającej jedną z tablic na fasadzie Biblioteki UW). Hipoteza  Collatza mówi, że niezależnie od początkowej liczby, zawsze kiedyś dostaniemy 1 i program zakończy działanie. Dowodu albo kontrprzykładu dotąd nie ma i wielu wybitnych badaczy uważa, że trudniej go będzie znaleźć niż dowód ostatniego twierdzenia Fermata, na który czekano 300 lat.  I tak wygląda sprawa z tą poznawalnością komputera.

Jerzy Tyszkiewicz

Fot. Jerzy Tyszkiewicz (CC SA)