Hilbert, Gödel, Turing: co da się (i czego nie) obliczyć

🎯 Po co Ci to?

Po wstrząsie paradoksem Russella matematycy zapytali: czy da się w ogóle mieć absolutną pewność, że matematyka jest wolna od sprzeczności? Niemiecki matematyk postawił sobie za cel odpowiedzieć na to pytanie raz na zawsze. Jego program badawczy wydawał się niemal na wyciągnięcie ręki — dopóki dwudziestopięcioletni austriacki logik nie pokazał, że cel ten jest w zasadzie nieosiągalny. A kilka lat później młody Brytyjczyk, próbując zrozumieć konsekwencje tego odkrycia, wynalazł — niejako przy okazji — matematyczny model tego, czym dziś jest każdy komputer na świecie.

✅ Czego się nauczysz

Po tej lekcji potrafisz (na poziomie intuicyjnym, bez formalnych dowodów):

opisać cel programu formalistycznego Hilberta;
wyjaśnić — intuicyjnie — sens twierdzeń Gödla o niezupełności;
opisać ideę maszyny Turinga i problem stopu, oraz wyjaśnić, dlaczego maszyna Turinga jest fundamentem informatyki.

🔁 Przypomnij sobie

Z Jednostki 5.1: paradoks Russella pokazał, że nawet pozornie oczywiste założenia logiczne mogą kryć sprzeczności. Hilbert zapyta: czy da się to wykluczyć raz na zawsze, dla całej matematyki?

📘 Wyjaśnienie

David Hilbert (1862–1943) był niekwestionowanym królem matematyki przełomu stuleci — to on na kongresie w Paryżu w 1900 r. ogłosił słynną listę dwudziestu trzech problemów, które miały zająć matematyków na cały nadchodzący wiek. I to on zaproponował ambitny program badawczy zwany formalizmem (lub programem Hilberta). Jego cel: zapisać całą matematykę jako system formalny — zbiór jasno określonych aksjomatów i reguł wnioskowania — a następnie udowodnić, w sposób absolutnie pewny i przy użyciu wyłącznie skończonych, „bezpiecznych" metod, że system ten nigdy nie doprowadzi do sprzeczności.

💭 Pomyśl: Dlaczego Hilbert chciał, żeby dowód niesprzeczności matematyki używał wyłącznie „skończonych, bezpiecznych" metod — a nie po prostu dowolnych metod matematycznych?

Sprawdź odpowiedź

Gdyby dowód niesprzeczności matematyki sam korzystał z metod matematycznych, których niesprzeczności nie jesteśmy pewni, popadlibyśmy w błędne koło — używalibyśmy potencjalnie niepewnego narzędzia, by udowodnić pewność. Hilbert chciał więc oprzeć dowód na metodach tak podstawowych, prostych i „oczywistych" (dotyczących skończonych operacji na symbolach, bez odwoływania się do nieskończoności), że nikt rozsądny nie mógłby ich kwestionować — coś w rodzaju absolutnie pewnego, niepodważalnego fundamentu.

📐 DEFINICJA — program Hilberta (formalizm): program badawczy zaproponowany przez Davida Hilberta, dążący do zapisania całej matematyki jako systemu formalnego (aksjomaty + reguły wnioskowania) oraz udowodnienia, przy użyciu wyłącznie elementarnych, skończonych metod, że system ten jest: (1) niesprzeczny (nie da się w nim wyprowadzić zarazem zdania i jego zaprzeczenia) oraz (2) zupełny (każde prawdziwe zdanie matematyczne da się w nim udowodnić).

Po ludzku: Hilbert chciał raz na zawsze „zamknąć sprawę" — pokazać, że matematyka stoi na absolutnie solidnym, dającym się sprawdzić fundamencie, bez ukrytych paradoksów czekających na odkrycie. Czym to NIE jest: to nie było twierdzenie o konkretnym twierdzeniu matematycznym — to był program dotyczący całej matematyki jako systemu.

Hilbert wierzył w swój program bezgranicznie. 8 września 1930 r. w rodzinnym Królewcu wygłosił mowę, którą zakończył słowami wyrytymi później na jego nagrobku: Wir müssen wissen — wir werden wissen („Musimy wiedzieć — będziemy wiedzieć"). Historia bywa złośliwa: dzień wcześniej, na konferencji w tym samym mieście, nieśmiały dwudziestoczteroletni doktorant z Wiednia zasygnalizował w dyskusji wynik, który miał ten program pogrzebać. Nazywał się Kurt Gödel. Podobno jedynym, który natychmiast pojął wagę tej krótkiej uwagi, był obecny na sali John von Neumann — po obradach wziął Gödla na bok i wypytał o szczegóły.

David Hilbert (ok. 1912) · źródło: Wikimedia Commons, domena publiczna

Reszcie świata program Hilberta wciąż wydawał się realistycznym, choć ambitnym celem — aż do 1931 roku, gdy ten sam Kurt Gödel (1906–1978), mający zaledwie 25 lat, opublikował pracę, która wstrząsnęła całą matematyką niemal tak samo mocno, jak paradoks Russella wstrząsnął logicyzmem Fregego. Gödel udowodnił swoje słynne twierdzenia o niezupełności.

📐 DEFINICJA — twierdzenia Gödla o niezupełności (ujęcie intuicyjne): Gödel pokazał, że w każdym wystarczająco bogatym systemie formalnym (na tyle bogatym, by opisać podstawową arytmetykę liczb naturalnych): (1) istnieją prawdziwe zdania, których NIE da się w tym systemie udowodnić (system jest niezupełny), oraz (2) system NIE MOŻE udowodnić własnej niesprzeczności, korzystając wyłącznie ze środków dostępnych wewnątrz siebie.

Po ludzku: w każdym dostatecznie bogatym systemie matematycznym zawsze będą prawdziwe zdania, których nie da się w tym systemie udowodnić — a sam system nigdy nie może „zaświadczyć" o własnej niesprzeczności od wewnątrz. Czym to NIE jest: to nie znaczy, że matematyka jest „zepsuta" albo że nie da się niczego udowodnić — większość codziennej matematyki (i cała ta, której uczysz się w szkole) jest zupełnie bezpieczna. Chodzi o fundamentalną, teoretyczną granicę, jaką napotyka KAŻDY dostatecznie bogaty system formalny — granicę wewnętrzną, nie praktyczny problem na co dzień.

💭 Pomyśl: Gödel skonstruował swój dowód, tworząc (w bardzo dużym uproszczeniu) zdanie, które w efekcie mówi o sobie samym: „Tego zdania nie da się udowodnić w tym systemie". Zastanów się: co się dzieje, jeśli spróbujesz ustalić, czy takie zdanie jest prawdziwe, czy fałszywe?

Sprawdź odpowiedź

To bardzo subtelna konstrukcja (podobna w duchu do klasycznego paradoksu kłamcy: „to zdanie jest fałszywe"), więc potraktuj to jako intuicję, nie ścisły dowód. Jeśli zdanie „tego zdania nie da się udowodnić" JEST prawdziwe — to rzeczywiście nie da się go udowodnić w systemie (czyli mamy prawdziwe zdanie, którego system nie potrafi dowieść — niezupełność). Jeśli natomiast zdanie to jest FAŁSZYWE — oznaczałoby to, że zdanie DA SIĘ udowodnić, co jednak prowadziłoby do udowodnienia fałszywego zdania w systemie, czyli do sprzeczności. Gödel bardzo precyzyjnie, za pomocą specjalnej techniki „kodowania" zdań jako liczb (tzw. numeracja Gödla), przekształcił tę intuicję w rygorystyczny dowód matematyczny — jedno z największych osiągnięć logiki XX wieku.

Gödel pokazał więc, że program Hilberta w swojej pierwotnej, pełnej formie jest niewykonalny: żaden wystarczająco bogaty system formalny nie może być jednocześnie zupełny i sam siebie udowadniać jako niesprzeczny. To był ogromny szok dla środowiska matematycznego — marzenie o absolutnej, ostatecznej pewności matematyki okazało się w zasadzie nieosiągalne.

O samym Gödlu krążą legendy. W Princeton, dokąd uciekł przed wojną, jego najbliższym przyjacielem został Albert Einstein — mawiał pod koniec życia, że przychodzi do instytutu głównie po to, „by mieć przywilej wracania do domu pieszo z Gödlem". A gdy w 1947 r. Gödel zdawał egzamin na obywatelstwo amerykańskie, oznajmił sędziemu, że znalazł w konstytucji USA lukę logiczną, przez którą legalnie dałoby się zaprowadzić dyktaturę. Od katastrofy uratowali go świadkowie — Einstein i ekonomista Oskar Morgenstern — czym prędzej sprowadzając rozmowę na bezpieczne tory.

Kurt Gödel jako student (1925) · źródło: IAS / Wikimedia Commons, domena publiczna

Kilka lat później, w 1936 roku, młody brytyjski matematyk Alan Turing (1912–1954) zmierzył się z pokrewnym, ale osobnym pytaniem, sformułowanym przez Hilberta jako część jego programu: Entscheidungsproblem („problem rozstrzygalności") — czy istnieje ogólna metoda (algorytm), która dla DOWOLNEGO zdania matematycznego potrafiłaby w skończonym czasie rozstrzygnąć, czy jest ono prawdziwe, czy fałszywe?

Żeby w ogóle precyzyjnie odpowiedzieć na to pytanie, Turing musiał najpierw zdefiniować, czym w ogóle jest „metoda obliczeniowa" — i w tym celu wynalazł abstrakcyjny model matematyczny, dziś znany jako maszyna Turinga.

📐 DEFINICJA — maszyna Turinga: abstrakcyjny (matematyczny, nie fizyczny) model obliczeń wymyślony przez Alana Turinga, składający się z nieskończenie długiej taśmy podzielonej na komórki, głowicy odczytująco-zapisującej przesuwającej się po taśmie oraz skończonego zbioru stanów wewnętrznych i reguł określających, co maszyna robi (zapisuje symbol, przesuwa się, zmienia stan) w zależności od bieżącego stanu i odczytanego symbolu.

Po ludzku: najprostszy możliwy matematyczny opis tego, czym w ogóle jest „obliczanie krok po kroku" — na tyle prosty, że da się go precyzyjnie zdefiniować matematycznie, a jednocześnie na tyle uniwersalny, że potrafi wykonać (jak się okazało) każde obliczenie, jakie da się zdefiniować jako algorytm. Czym to NIE jest: to nie była propozycja fizycznego urządzenia do zbudowania — to czysto teoretyczny, matematyczny konstrukt, narzędzie do definiowania pojęcia obliczalności, nie do budowania komputerów (choć, jak zobaczysz w Jednostce 5.3, okazała się zdumiewająco bliska strukturze realnych komputerów).

Fizyczna maszyna Turinga zbudowana przez Mike'a Daveya — taśma, głowica, stany

Za pomocą tego modelu Turing pokazał coś niezwykle ważnego: istnieją problemy, których żadna maszyna Turinga (czyli żaden algorytm) nie jest w stanie rozwiązać — nawet dysponując nieograniczonym czasem i pamięcią. Najsłynniejszym przykładem jest problem stopu.

📐 DEFINICJA — problem stopu (nierozstrzygalność): pytanie, czy istnieje ogólny algorytm, który — dla dowolnego programu i dowolnych danych wejściowych — potrafiłby zawsze poprawnie stwierdzić, czy ten program w końcu się zatrzyma, czy będzie działał w nieskończoność. Turing dowiódł, że taki ogólny algorytm nie istnieje — problem stopu jest nierozstrzygalny.

Po ludzku: nie ma uniwersalnego „wykrywacza nieskończonych pętli", który działałby bezbłędnie dla KAŻDEGO możliwego programu — to fundamentalna, matematycznie dowiedziona granica tego, co da się w ogóle obliczyć. Czym to NIE jest: to nie znaczy, że nie da się sprawdzić, czy KONKRETNY, prosty program się zatrzyma — często to łatwe. Chodzi o to, że nie istnieje JEDEN uniwersalny algorytm, który rozstrzygałby to poprawnie dla wszystkich możliwych programów bez wyjątku.

Odpowiedź Turinga na Entscheidungsproblem Hilberta brzmiała więc: NIE, taka ogólna metoda nie istnieje — co jest bezpośrednią konsekwencją nierozstrzygalności problemu stopu. (Niezależnie i niemal równocześnie do tego samego wniosku doszedł amerykański logik Alonzo Church, inną metodą matematyczną — dlatego to odkrycie nazywa się czasem tezą Churcha-Turinga.)

💭 Pomyśl: Dlaczego odkrycie, że NIE da się zbudować uniwersalnej maszyny obliczającej WSZYSTKO, jest zarazem odkryciem, które doprowadziło do powstania informatyki — dziedziny budującej maszyny obliczające bardzo, bardzo wiele rzeczy?

Sprawdź odpowiedź

To pozornie paradoksalne, ale ma sens: żeby udowodnić, czego NIE da się obliczyć, Turing musiał najpierw precyzyjnie zdefiniować, czym W OGÓLE jest „obliczanie" — i to właśnie ta definicja (maszyna Turinga) okazała się być matematycznym opisem uniwersalnego komputera, zdolnego (w granicach nierozstrzygalności) wykonać każde możliwe do sformułowania obliczenie. Innymi słowy: negatywny wynik (są granice obliczalności) i pozytywny wynik (mamy teraz precyzyjny, uniwersalny model tego, co JEST obliczalne) to dwie strony tego samego odkrycia. Maszyna Turinga stała się teoretycznym fundamentem wszystkich późniejszych komputerów — poznasz to bliżej w Jednostce 5.3.

⚠️ Uwaga, pułapka

Bardzo częste nieporozumienie: ludzie mylą niezupełność Gödla z nierozstrzygalnością Turinga, traktując je jako to samo odkrycie. To błąd! Są to dwa osobne, choć głęboko powiązane wyniki, dotyczące różnych pytań: Gödel pytał, czy każde PRAWDZIWE zdanie da się UDOWODNIĆ w danym systemie formalnym (niezupełność). Turing pytał, czy istnieje ALGORYTM, który dla dowolnego programu rozstrzygnie, czy się zatrzyma (nierozstrzygalność problemu stopu — szczególny przypadek szerszej odpowiedzi na Entscheidungsproblem). Oba wyniki mają podobnego „ducha" (obie odkrywają fundamentalne granice systemów formalnych/obliczeniowych) i obie wykorzystują pokrewną technikę dowodową (samoodniesienie — zdanie lub program „mówiące" coś o sobie samym), ale to różne twierdzenia, o różnych obiektach matematycznych, opublikowane w różnych latach (1931 i 1936) przez różnych autorów.

🏛️ Stanowiska — jak zareagować na odkrycia Gödla i Turinga?

Stanowisko rezygnacji: skoro nie da się osiągnąć absolutnej pewności matematyki (Gödel) ani zbudować uniwersalnego algorytmu rozstrzygającego wszystko (Turing), program Hilberta należy uznać za porażkę, a marzenie o „mechanizacji" całej matematyki — za naiwne.
Stanowisko pragmatyczne (przeważające dziś): odkrycia Gödla i Turinga NIE oznaczają porażki matematyki czy informatyki w praktyce — codzienna matematyka i informatyka funkcjonują świetnie mimo tych teoretycznych granic (podobnie jak fizyka funkcjonuje świetnie mimo tego, że nie zna „teorii wszystkiego"). Co więcej, odkrycia te — paradoksalnie — DAŁY narzędzia (precyzyjną definicję obliczalności) niezbędne do zbudowania współczesnej informatyki i komputerów.

📐 Definicje tej lekcji

Program Hilberta (formalizm) — dążenie do zapisania matematyki jako niesprzecznego i zupełnego systemu formalnego.
Twierdzenia Gödla o niezupełności — dowód, że żaden dostatecznie bogaty system formalny nie może być zarazem zupełny i dowodzić własnej niesprzeczności.
Maszyna Turinga — abstrakcyjny matematyczny model obliczeń, fundament pojęcia algorytmu i informatyki.
Problem stopu — dowód nierozstrzygalności: nie istnieje uniwersalny algorytm rozstrzygający, czy dowolny program się zatrzyma.

📌 Najważniejsze w pigułce

David Hilbert chciał udowodnić, że matematyka jest niesprzeczna i zupełna, używając wyłącznie elementarnych metod (program Hilberta).
Kurt Gödel (1931) pokazał, że to niemożliwe: każdy dostatecznie bogaty system formalny jest niezupełny i nie może dowieść własnej niesprzeczności od wewnątrz.
Alan Turing (1936), definiując abstrakcyjną maszynę Turinga, dowiódł nierozstrzygalności problemu stopu — nie istnieje uniwersalny algorytm rozwiązujący wszystkie problemy.
Paradoksalnie, te „negatywne" odkrycia dały ludzkości precyzyjną definicję tego, czym JEST obliczanie — fundament całej informatyki.

🎒 Zadania

Zadanie 5.2.1. Wyjaśnij różnicę między pytaniem, które zadawał Gödel, a pytaniem, które zadawał Turing — mimo że oba prowadzą do „negatywnych", ograniczających wyników.

Sprawdź odpowiedź

Gödel pytał, czy KAŻDE prawdziwe zdanie matematyczne da się udowodnić wewnątrz danego systemu formalnego — i pokazał, że nie (niezupełność). Turing pytał, czy istnieje UNIWERSALNY ALGORYTM, który rozstrzygnie dla dowolnego programu, czy się on zatrzyma — i pokazał, że nie (nierozstrzygalność problemu stopu). Pierwsze pytanie dotyczy dowodliwości zdań w systemie logicznym; drugie — istnienia ogólnej procedury obliczeniowej. To różne obiekty badania (zdania logiczne vs. programy/algorytmy), choć wykorzystujące podobną technikę dowodową (samoodniesienie).

Zadanie 5.2.2. Wyjaśnij, dlaczego maszyna Turinga — mimo że jest czysto abstrakcyjnym, matematycznym konstruktem, a nie fizycznym urządzeniem — jest uznawana za fundament informatyki.

Pokaż rozwiązanie

Maszyna Turinga dostarczyła pierwszej precyzyjnej, matematycznej definicji tego, czym w ogóle jest „obliczanie krok po kroku" (algorytm). Dzięki tej definicji można było formalnie badać granice obliczalności (co da się, a czego nie da się obliczyć) — i, co równie ważne, okazało się, że KAŻDY późniejszy model obliczeń (w tym każdy realny komputer elektroniczny) jest w stanie wykonać dokładnie te same obliczenia, co maszyna Turinga — ani więcej, ani mniej (to zjawisko nazywa się „równoważnością obliczeniową" i wiąże się z tezą Churcha-Turinga). Innymi słowy: maszyna Turinga wyznacza teoretyczny „sufit" możliwości każdego komputera, jaki kiedykolwiek zbudujemy.

Zadanie 5.2.3. „Skoro istnieją problemy matematyczne nierozstrzygalne (Gödel) i nieobliczalne (Turing), to matematyka i informatyka są w gruncie rzeczy zawodne i nie można im ufać." Oceń to twierdzenie, odwołując się do stanowiska pragmatycznego z tekstu.

Sprawdź odpowiedź

Twierdzenie jest przesadzone. Odkrycia Gödla i Turinga dotyczą fundamentalnych, TEORETYCZNYCH granic systemów formalnych i obliczeniowych jako całości — nie oznaczają, że konkretne, praktyczne obliczenia czy dowody, z jakimi mamy do czynienia na co dzień (w szkole, w inżynierii, w nauce), są niepewne czy zawodne. Zdecydowana większość praktycznych problemów matematycznych i informatycznych jest w pełni rozstrzygalna i obliczalna — granice odkryte przez Gödla i Turinga dotyczą specyficznych, często sztucznie skonstruowanych przypadków „na granicy" systemu (jak zdania samoodnoszące się czy programy sprawdzające same siebie), a nie codziennej praktyki matematycznej i informatycznej.

🔍 Sprawdź, czy umiesz

[ ] Opisać cel programu Hilberta.
[ ] Wyjaśnić intuicyjnie sens twierdzeń Gödla o niezupełności.
[ ] Opisać ideę maszyny Turinga i problem stopu.
[ ] Wyjaśnić różnicę między niezupełnością Gödla a nierozstrzygalnością Turinga.

Ucz się tej jednostki z asystentem