Hipoteza Churcha-Turinga
Z Wikipedii
Hipoteza Churcha-Turinga (zwana również Tezą Churcha-Turinga) jest hipotezą określającą 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 jest niemożliwa do sprawdzenia matematycznie, ponieważ łączy w sobie zarówno ścisłe, jak i nieprecyzyjne sformułowania, których interpretacja może zależeć od konkretnej osoby. Dlatego traktowana jest bardziej jako aksjomat lub swoiste prawo.
Mniej formalnie, 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.
Hipoteza została zaproponowana po raz pierwszy przez Stephena Kleene'ego w 1943 roku, lecz została nazwana od Alonzo Churcha i Alana Turinga.
Spis treści |
[edytuj] Formalna definicja
Formalna definicja hipotezy:
- Każdy problem, który może być intuicyjnie uznany za obliczalny, jest rozwiązywalny przez maszynę Turinga.
Sformułowanie "intuicyjnie uznany za obliczalny" uniemożliwia przeprowadzenie matematycznego dowodu tej hipotezy.
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, będzie to oznaczać unieważnienie silnej hipotezy Churcha-Turinga, ponieważ klasa problemów rozwiązywalnych w kwantowym czasie wielomianowym jest większa od probabilistycznego. Istnieją efektywne algorytmy kwantowe rozwiązujące problemy, dla których nie istnieją efektywne algorytmy probabilistyczne, np. rozkład liczby na czynniki pierwsze.
[edytuj] 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:
- 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.
- 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).
- 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.
[edytuj] 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.
