Hipoteza Churcha-Turinga

Hipoteza Churcha-Turinga (zwana również Tezą Churcha-Turinga) – hipoteza określająca możliwości komputerów i innych maszyn obliczeniowych. Mówi ona, że każdy problem, dla którego przy nieograniczonej pamięci oraz zasobach istnieje efektywny algorytm jego rozwiązywania, da się rozwiązać na maszynie Turinga.

Hipoteza pozwala dokładniej sformułować pojęcie samego algorytmu, mówiąc jednocześnie, że komputery są w stanie go wykonać. Co więcej, wszystkie komputery mają jednakowe możliwości, jeśli chodzi o zdolność do ich wykonywania, a nie dostępne zasoby oraz że nie jest możliwe zbudowanie komputera o zdolności do rozwiązywania większej liczby problemów niż najprostsza maszyna Turinga.

Hipotezę zaproponował po raz pierwszy Stephen Cole Kleene w 1943 roku, lecz została ona potwierdzona niezależnie przez Alonzo Churcha i Alana Turinga w 1936 roku. Najważniejszą konsekwencją tej tezy jest to, że ogólne rozwiązanie problemu rozstrzygalności (Entscheidungsproblem), postawionego przez Davida Hilberta w 1928 roku, jest niemożliwe.

Sformułowanie

Sformułowanie hipotezy Churcha-Turinga jest następujące:

Każdy problem, który może być intuicyjnie uznany za obliczalny, jest rozwiązywalny przez maszynę Turinga.

Fraza „intuicyjnie uznany za obliczalny” uniemożliwia przeprowadzenie matematycznego dowodu tej hipotezy.

Każda funkcja obliczalna jest rekurencyjnie obliczalna

Łatwo zauważyć, że teza odwrotna jest dobrze określonym twierdzeniem matematycznym: każda funkcja rekurencyjnie obliczalna jest równoważna pewnemu programowi dla maszyny Turinga, jest algorytmem o skończonej liczbie kroków złożonym z operacji elementarnie rekurencyjnie obliczalnych. Tak więc Teza Churcha jest próbą odwrócenia tego twierdzenia. Status tezy Churcha jest niejasny, gdyż w zależności od jej interpretacji można ją uważać, za definicję obliczalności, model obliczalności, hipotezę empiryczna itp. W każdym z tych przypadków konieczna jest jednak analiza odpowiednio: adekwatności definicji, sensowności modelu, braku kontrprzykładu. Można Tezę Churcha traktować jako przykład naukowo-filozoficznego zastosowania indukcji – z braku kontrprzykładów wyciągamy wniosek o prawdziwości Tezy Churcha.

Każdy nieinteraktywny program może być zredukowany do rozwiązującej go maszyny Turinga, a ta może być wyrażona w każdym zupełnym w sensie Turinga języku programowania. Dlatego równoważne sformułowanie tej hipotezy mówi, że każdy istniejący algorytm można wyrazić w każdym zupełnym języku programowania.

Istnieją jeszcze inne wersje definiujące hipotezę. Przykładowa, fizyczna hipoteza Churcha-Turinga (ang. Physical Church-Turing Thesis, PCTT):

Każdy problem, który jest fizycznie obliczalny, może być rozwiązany na maszynie Turinga.

Kolejną odmianą jest silna hipoteza Churcha-Turinga. Została ona wypracowana dużo później, w wyniku prac nad teorią złożoności.

Każdy „rozsądny” model obliczeń może być efektywnie zasymulowany na probabilistycznej Maszynie Turinga.

Słowo „efektywny” oznacza tutaj istnienie redukcji problemów wykonywanych w czasie wielomianowym, stąd ta wersja definicji mówi, że wszystkie „rozsądne” modele obliczeń generują tę samą klasę problemów możliwych do policzenia w czasie wielomianowym. Zakładając, że przypuszczalna równość między probabilistycznym czasem wielomianowym równa jest deterministycznemu czasowi wielomianowemu, słowo „probabilistyczny” można w tej definicji pominąć.

Jeśli komputer kwantowy rzeczywiście jest możliwy do zbudowania, może to oznaczać obalenie silnej hipotezy Churcha-Turinga, ponieważ klasa problemów rozwiązywalnych w kwantowym czasie wielomianowym jest przypuszczalnie większa od probabilistycznego. Istnieją bowiem efektywne algorytmy kwantowe rozwiązujące problemy, dla których nie znamy efektywnych algorytmów probabilistycznych, np. rozkład liczby na czynniki pierwsze.

Filozoficzne implikacje

Istnieją istotne powiązania między hipotezą Churcha-Turinga a filozofią umysłu, podobnie jak kilka ważnych oraz otwartych wciąż pytań dotyczących relacji między tą hipotezą a fizyką oraz hiperobliczalnością. Stosując ją do fizyki, można otrzymać kilka wniosków:

1. Wszechświat jest zupełny w sensie Turinga lub jest nawet słabszy – wtedy obliczanie nierozwiązywalnych problemów i funkcji nierekurencyjnych jest niemożliwe.
2. Wszechświat nie jest zupełny, tzn. istnieją takie prawa fizyki, których nie da się obliczyć za pomocą maszyny Turinga. Nie są one jednak wykorzystywane do konstrukcji hiperkomputera. Przykładowo, fizyka dopuszczająca liczby rzeczywiste pasuje do tej kategorii (ze względu na ograniczone zasoby komputer nie jest w stanie odwzorować części tych liczb).
3. Wszechświat jest hiperkomputerem i możliwe jest wykorzystanie jego właściwości do obliczeń wykraczających poza możliwości maszyn Turinga. Wciąż pozostaje otwarte pytanie, czy wszystkie zdarzenia mechaniki kwantowej są zupełne, pomimo iż wiadomo, że rygorystyczne modele, jak kwantowa maszyna Turinga są równoważne klasycznej (choć czynią niektóre problemy łatwo rozwiązywalnymi, nie powiększają liczby problemów, które da się rozwiązać). John Lucas oraz Roger Penrose twierdzą, że ludzki umysł jest przykładem kwantowego hiperkomputera, lecz nie ma na to żadnych naukowych dowodów.

Nierozwiązywalne problemy

Istnieją funkcje oraz problemy, które są niemożliwe do obliczenia za pomocą maszyny Turinga. Dla takich problemów, zawsze istnieje zestaw danych, dla których dowolny zaproponowany algorytm nie zatrzyma się lub da błędną odpowiedź. W przypadku funkcji, operując na liczbach naturalnych, mogą one produkować niezwykle duże wyniki. Jedną z najsłynniejszych takich funkcji jest Busy Beaver. Określa ona maksymalną ilość pracy, jaką może wykonać maszyna Turinga o zadanej z góry liczbie stanów n (argument funkcji), przy czym nie uwzględniamy tutaj maszyn działających w nieskończoność. Naukowcy potrafią podać jedynie prawidłowy wynik dla pierwszych czterech liczb naturalnych, natomiast dla kolejnych znane jest tylko dolne oszacowanie. Funkcja ta ma wiele powiązań z problemem stopu, który także jest nierozwiązywalny.

Zobacz też

• kompletność Turinga
• teoria obliczeń
• złożoność obliczeniowa

Bibliografia

• Agnijo Banerjee, David Darling: Dziwna matematyka. Helion S.A., 2020. ISBN 83-283-5687-2.

Linki zewnętrzne

• Church thesis (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-10-05].
• B. JackB.J. Copeland B. JackB.J., The Church-Turing Thesis, [w:] Stanford Encyclopedia of Philosophy, CSLI, Stanford University, 10 listopada 2017, ISSN 1095-5054 [dostęp 2018-01-17]  (ang.).
• Church’s thesis (ang.), Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].