Najważniejsza maszyna, której nigdy nie zbudowano

Obliczenia to znana koncepcja, którą większość z nas rozumie intuicyjnie. Weź funkcję f(x) = x + 3. Kiedy x jest trzy, f(3) = 3 + 3. Sześć. Łatwy. Wydaje się oczywiste, że ta funkcja jest obliczalna. Ale niektóre funkcje nie są takie proste i nie jest łatwo określić, czy można je obliczyć, co oznacza, że ​​mogą nigdy nie dać nam ostatecznej odpowiedzi.

W 1928 roku niemieccy matematycy David Hilbert i Wilhelm Ackermann zaproponowali pytanie zwane Entscheidungs ​​problem („problem decyzyjny”). Z czasem ich pytanie doprowadziłoby do formalnej definicji obliczalności, która pozwoliła matematykom odpowiedzieć na wiele nowych problemów i położyła podwaliny pod teoretyczną informatykę.

Definicja pochodzi od 23-letniego studenta, Alana Turinga, który w 1936 r. przełomowy artykuł które nie tylko sformalizowały koncepcję obliczeń, ale także udowodniły fundamentalną kwestię w matematyce i stworzyły intelektualną podstawę wynalezienia komputera elektronicznego. Wielkim spostrzeżeniem Turinga było dostarczenie konkretnej odpowiedzi na pytanie obliczeniowe w postaci abstrakcyjnej maszyny, nazwanej później maszyną Turinga przez jego doradcę doktora, Alonzo Churcha. Jest abstrakcyjny, ponieważ nie istnieje (i nie może) fizycznie jako namacalne urządzenie. Zamiast tego jest to koncepcyjny model obliczeń: jeśli maszyna może obliczyć funkcję, to funkcja jest obliczalna.

Oto jak to działa. Maszyna Turinga może odczytywać i zmieniać symbole na nieskończenie długiej taśmie, zgodnie z tabelą reguł. Taśma składa się z „komórek”, z których każda może przechowywać dokładnie jeden symbol, a maszyna odczytuje i przepisuje zawartość komórek za pomocą głowicy taśmy. Każda reguła w tabeli określa, co maszyna powinna zrobić na podstawie zarówno jej bieżącego stanu, jak i symbolu, który odczytuje. Maszyna może wejść w stan końcowy („stan akceptacji” lub „stan odrzucenia”), w którym zatrzymuje się, akceptując lub odrzucając dane wejściowe. Lub wpada w nieskończoną pętlę i kontynuuje czytanie taśmy w nieskończoność.

Najlepszym sposobem zrozumienia maszyny Turinga jest rozważenie prostego przykładu. Wyobraźmy sobie taki, który ma nam powiedzieć, czy dane wejście jest liczbą zero. Użyjemy numeru wejściowego 0001 wraz z pustymi symbolami (#), więc „#0001#” jest odpowiednią częścią naszej taśmy.

Maszyna startuje w stanie początkowym, który nazwiemy q0. Odczytuje skrajną lewą komórkę na naszej taśmie i znajduje puste miejsce. Reguły mówią: „Kiedy w stanie q0 symbolem jest #, pozostaw go bez zmian, przesuń jedną komórkę w prawo i zmień stan maszyny na q1”. Po tym kroku maszyna jest w stanie q1, a jej głowica odczytuje drugi symbol, 0.

Teraz szukamy reguły, która ma zastosowanie do tych warunków. Znajdujemy taki, który mówi: „Pozostań w stanie q1 i przesuń głowę o jedną komórkę w prawo”. To pozostawia nas w tej samej pozycji (w stanie q1, odczyt „0”), więc przesuwamy się w prawo, aż w końcu głowa odczyta inną liczbę, 1.

Kiedy ponownie sprawdzamy tabelę, znajdujemy nową regułę: „Jeśli napotkamy 1, przejdź do q2, co jest stanem„ odrzucenia ”. Maszyna zatrzymuje się, odpowiadając „Nie” na pierwotne pytanie „Czy „0001” to zero?”

Jeśli zamiast tego wprowadzone zostanie „#0000#”, maszyna napotka znak # po wszystkich tych zerach. Kiedy zajrzymy do tabeli, znajdziemy regułę mówiącą, że oznacza to, że maszyna wchodzi w stan q3, stan „akceptacji”. Teraz maszyna odpowiada „Tak” na pytanie „Czy '0000' to zero?”

Za pomocą swojej abstrakcyjnej maszyny Turing stworzył model obliczeniowy, aby odpowiedzieć na problem Entscheidungs, który formalnie pyta: Czy przy danym zbiorze matematycznych aksjomatów istnieje proces mechaniczny — zbiór instrukcji, który dziś nazwalibyśmy algorytmem — który zawsze może określić, czy dane zdanie jest prawdziwe?

Powiedzmy, że chcemy znaleźć algorytm, który powie nam, czy dana pozycja szachowa jest możliwa. Tutaj aksjomaty są regułami szachowymi, które rządzą legalnymi ruchami. Czy możemy wykonać skończoną sekwencję procedur krok po kroku, aby dojść do tej pozycji? Chociaż analiza niektórych pozycji może zająć więcej czasu niż nasze życie — algorytm może wygenerować wszystkie możliwe pozycje i porównać każdą z nich z danymi wejściowymi — takie algorytmy istnieją w grze w szachy. W rezultacie mówimy, że szachy są „rozstrzygalne”.

Jednak w 1936 roku Church i Turing — różnymi metodami — niezależnie udowodnili, że nie ma ogólnego sposobu rozwiązania każdego przypadku problemu Entscheidungs. Na przykład niektóre gry, takie jak Game of Life Johna Conwaya, są nierozstrzygalne: żaden algorytm nie może określić, czy określony wzór pojawi się na podstawie początkowego wzoru.

Turing wykazał, że funkcja jest obliczalna, jeśli istnieje algorytm, który może wykonać żądane zadanie. Jednocześnie pokazał, że algorytm to proces, który można zdefiniować za pomocą maszyny Turinga. Stąd funkcja obliczalna to funkcja, która ma maszynę Turinga do jej obliczenia. Może się to wydawać okrężnym sposobem zdefiniowania obliczalności, ale to najlepsze, co mamy. „To nie jest tak, że masz wybór, aby zdefiniować to w inny sposób” – powiedział Michał Sipser, informatyk teoretyczny w Massachusetts Institute of Technology. „Myślę, że powszechnie przyjmuje się, że teza Churcha-Turinga mówi, że nieformalne pojęcie algorytmu odpowiada temu, co może zrobić każdy„ rozsądny ”model obliczeniowy”. Inni matematycy wymyślili różne modele obliczeń, które z pozoru wyglądają zupełnie inaczej, ale w rzeczywistości są równoważne: mogą wykonać dowolne obliczenia, które mogą wykonać maszyny Turinga, i odwrotnie.

Zaledwie kilka lat po tym, jak Kurt Gödel udowodnił, że matematyka istnieje niekompletny, Church i Turing wykazali w tej pracy, że niektóre problemy w matematyce są nierozstrzygalne — żaden algorytm, jakkolwiek wyrafinowany, nie powie nam, czy odpowiedź brzmi tak, czy nie. Oba były druzgocącymi ciosami dla Hilberta, który miał nadzieję, że matematyka będzie miała uporządkowane, wyidealizowane odpowiedzi. Ale może to i dobrze: gdyby istniało ogólne rozwiązanie problemu Entscheidungs, oznaczałoby to, że wszystkie problemy w matematyce można by sprowadzić do prostych obliczeń mechanicznych.

Oprócz odpowiedzi na te fundamentalne pytania, maszyna Turinga doprowadziła również bezpośrednio do rozwoju nowoczesnych komputerów, poprzez wariant znany jako uniwersalna maszyna Turinga. Jest to specjalny rodzaj maszyny Turinga, który może symulować dowolną inną maszynę Turinga na dowolnym wejściu. Może czytać opis innych maszyn Turinga (ich zasady i taśmy wejściowe) i symulować ich zachowanie na własnej taśmie wejściowej, wytwarzając takie same dane wyjściowe, jakie generowałaby symulowana maszyna, tak jak dzisiejsze komputery mogą czytać dowolny program i go wykonywać. W 1945 roku John von Neumann zaproponował architekturę komputera — zwaną architekturą von Neumanna — która umożliwiła uniwersalną koncepcję maszyny Turinga w rzeczywistej maszynie.

Kiedy Sanjeev Arora, informatyk teoretyczny z Princeton University, naucza tej koncepcji, podkreśla szerszy obraz filozoficzny. „Istnieją dwa pojęcia „uniwersalności”” — powiedział. „Jedną z koncepcji uniwersalizmu jest to, że może on obsługiwać dowolną inną maszynę Turinga. Ale innym, większym pojęciem „uniwersalności” jest to, że może wykonać dowolne obliczenia we wszechświecie, które wymyślisz. W świecie fizyki klasycznej każdy proces fizyczny można modelować lub symulować za pomocą algorytmów, które z kolei mogą być symulowane przez maszynę Turinga.

Innym godnym uwagi i coraz bardziej użytecznym wariantem jest probabilistyczna maszyna Turinga. W przeciwieństwie do zwykłej maszyny Turinga — która ma dobrze zdefiniowaną reakcję na każde wejście — probabilistyczna maszyna Turinga może mieć wiele reakcji opartych na prawdopodobieństwach. Oznacza to, że może dawać różne wyniki dla tych samych danych wejściowych w różnym czasie. Dziwne, że tego rodzaju strategia probabilistyczna może być bardziej efektywne niż czysto deterministyczne podejście do pewnych problemów. Wykazano, że pomysły z probabilistycznych maszyn Turinga są praktycznie przydatne w takich dziedzinach, jak kryptografia, optymalizacja i uczenie maszynowe.

Te abstrakcyjne maszyny są prawdopodobnie najlepszym dowodem na to, że zadawanie podstawowych pytań może być jedną z najbardziej użytecznych rzeczy, jakie może zrobić naukowiec.