Teza Churcha Turinga

Teza Churcha — Turinga

Maszyna Turinga może zatem wykonywać działania na liczbach, może też prowadzić wyszukiwanie. Zapytajmy, jaki jest kres możliwości M. T. Odpowiedź jest bardzo zaskakująca. Okazuje się, że każdy problem algorytmiczny, dla którego możemy znaleźć algorytm daiacy sie zaprogramować w dowolnym języku na dowolnym komputerze (taki problem nazywamy efektywnie rozwiązywalnym), nawet takim, którego jeszcze nie zbudowano, ale można zbudować, nawet na takim, który wymaga nieograniczonej ilości czasu i pamięci — jest także rozwiązywalny przez maszynę Turinga.

Jest to tzw teza Churcha — Tuiinoo (od Alana Turinga i Alonzo Churcha, którzy tezę tę sformułowali niezależnie w połowie lat 30-tych). Teza ta nosi skiót CT. który oznacza nie tylko nazwiska autorów, ale także angielskie sformułowanie Computability Theory — teoiia obliczalności. bo tego teza dotyczy. Żeby lepiej uzmysłowić sobie o co tu chodzi — Harel poróyynuje MT z maszyną do pisania, która też ma skończoną liczbę "stanów" — trybóyy pracy — duże litery, małe litery, wymienna głowica, czcionek (np. łacińskie, greckie, cyrylica), taśma czerwona lub czarna, ale można na niej zapisać krótki prymitywny anonim, ale także dzieła takie jak "Wojna i pokój" czy "Hamlet". Rzecz w tym, kto ją programuje — tak i do odpowiedniego zaprogramowania MT, by mogła rozwiązywać dowolnie skomplikoyyany algorytm, trzeba odpoyyiednio utalentowanego programisty.

Konsekwencje tezy CT

Własności obliczalności:

Z tezy CT wynika, że najpotężniejszy superkomputer z najwymyślniejszymi językami programowania nie jest w sensie obliczalności lepszy od zwykłego domowego PC. Mając nieograniczoną ilość czasu i pamięci oba mogą rozwiązać te same problemy algorytmiczne. Zaś nieobliczalnych lub nierozstrzygalnych problemów nie rozwiąże ani jeden ani drugi.

W wyniku tezy CT — klasa problemów obliczalnych jest bardzo silna (bardzo silnie wyróżniona). Jest ona niezmiennicza ze względu na zmianę typu komputera lub języka programowania.

Uproszczenia i rozszerzenia MT:

Maszynę MT można upraszczać np. stosować taśmę nieskończoną nie z obu stron, ale tylko z jednej jej strony i przesuwanej tylko w jednym kierunku. Takie uproszczenie nie zmniejszy jednak klasy problemów rozwiązywalnych przez uproszczona maszynę! Podobnie można rozszerzyć maszynę MT dodając wiele taśm z własnymi głowicami i działającą tak, że sposób działania zależy od całego symbolu zbiorów jednocześnie widzianych przez głowice. Można zdefiniować maszyny z taśmami dwuwymiarowymi — o liczbie kierunków przesuwu taśmy zwiększonej do czterech. Wszystko to nie zmieni faktu, że model poszerzony nie rozwiąże problemu nierozwiązywalnego przez model podstawowy!

Próbując rozszerzyć maszynę T moglibyśmy się uciec do niestandardowego pomysłu i zaproponować niedeterministyczna maszynę T. Tzn. maszynę dopuszczającą wiele różnych przejść wyzwalanych przez ten sam wyzwalacz. I to maszyna ma wybierać, które przejście użyć. Rozwiązywanie problemu decyzyjnego przez taka maszynę jest podobne do magicznego rozwiązywania problemów klasy NP. Maszyna ma wybrać przejście, aby doprowadzić do odpowiedzi tak, jeśli to tylko jest możliwe. Niedeterministyczna maszyna T odpowiada tak na pewne dane X, jeśli tylko istnieje sekwencja przejść, która do tego tak prowadzi, nawet jeśli są inne, które prowadzą do stanu nie lub do nieskończonej pętli. Niestety i ten zabieg nie zwiększa mocy maszyny. "Magiczne" obliczenia nie umożliwiają nam rozwiązania problemu, który nie mógłby być rozwiązywalny be tej "magii". (Może natomiast poprawić efektywność obliczeń, zmniejszyć złożoność!)

Można zatem inaczej sformułować tezę CT:

'Wszystkie komputery i wszystkie iezyki programowania sa równoważne pod względem zdolności obliczeniowej, jeśli tylko czas i pomieć sa nieograniczone"._