Maszyna Turinga

Nieobliczalność

Odpowiedź na pytanie, co komputery potrafią obliczyć, a czego nie potrafią, stanowiła z kolei obsesję angielskiego matematyka Alana Turinga.

        W czasie drugiej wojny światowej, Turing pracował w supertajnym ośrodku wywiadowczym Bletchley Park, gdzie między innymi złamano szyfry Enigma oraz Fish, którymi hitlerowcy szyfrowali swoje komunikaty radiowe.

        Informacje, które pozyskiwano dzięki złamaniu tych szyfrów, pozwoliły zmniejszyć straty i skrócić wojnę, według niektórych historyków, nawet o dwa lata.

      
               Colossus

Sukces Turinga i jego kolegów polegał w znacznym stopniu na zastosowaniu urządzenia pod nazwą Colossus, które było pierwszym programowalnym elektronicznym komputerem.

        Pod koniec wojny, w Bletchley Park działało co najmniej dziesięć takich maszyn.

Nazwisko Turing kojarzy się jednak głównie z pojęciem maszyna Turinga, oraz pracami, które wykonywał jeszcze przed wojną, a które dotyczyły możliwości i ograniczeń komputerów.

         

W latach trzydziestych było to urządzenie nie z tej ziemi, dziś maszyną Turinga jest każdy komputer.

Można powiedzieć, że Alan Turing był wynalazcą komputera ogólnego zastosowania, które swą niezrównaną wszechstronność zawdzięcza nieskończonej elastyczności oprogramowania.

       Genialne odkrycie Turinga polegało na spostrzeżeniu, że w ostatecznym rozrachunku wszystko co robi komputer to żonglowanie symbolami.

Komputer jest karmiony jedną sekwencją symboli, po czym wypluwa inną sekwencję symboli, która zależy od aktualnie działającego programu.

I to wszystko.

Turinga interesowało, czego komputer policzyć nie może. Niemal natychmiast natknął się na takie zadanie, które na dodatek okazało się niezwykle proste.

        Problem stopu

Niemożliwe zadanie polegało na tym, aby sprawdzić, kiedy jakikolwiek program komputerowy się zatrzyma.

Dzisiejsi programiści wiedzą, że komputer czasami się zapętla, wykonuje w kółko ten sam zestaw instrukcji.

       Najprostszy sposób sprawdzenia polega na uruchomieniu komputera i obserwacji, kiedy się zatrzyma.

Jest to proste zadanie, jeżeli komputer zatrzyma się po minucie, godzinie, albo nawet po roku.

Ale co będzie, jeśli program zatrzyma się dopiero po tysiącu, albo milionie lat?

Nikt nie będzie czekał tak długo.

A więc proste zadanie, ale żaden komputer nie jest w stanie go obliczyć.