Zastanawiam się teraz, jak przekonać się, że maszyny Turinga są ogólnym modelem obliczeń. Zgadzam się, że standardowe podejście do tezy Church-Turinga w niektórych standardowych podręcznikach, np. Sipser, nie jest bardzo kompletne. Oto szkic, w jaki sposób mogę przejść od maszyn Turinga do bardziej rozpoznawalnego języka programowania.
Rozważmy język blokowy strukturze programowania z ifi whilesprawozdań, z nierekursywnych określonych funkcji i podprogramów, z nazwanych logicznych zmiennych losowych i ogólnych wyrażeń logicznych, a także z jednym bezgranicznej logicznej tablicy tape[n]z wskaźnik tablicy liczb całkowitych n, który może być zwiększana lub zmniejszana, n++lub n--. Wskaźnik njest początkowo zerowy, a tablica tapepoczątkowo wynosi zero. Tak więc ten język komputera może być podobny do C lub Python, ale jego typy danych są bardzo ograniczone. W rzeczywistości są one tak ograniczone, że nie mamy nawet możliwości użycia wskaźnika nw wyrażeniu boolowskim. Przy założeniu, żetapejest nieskończony tylko w prawo, możemy zadeklarować niedopełnienie wskaźnika „błędem systemowym”, jeśli nkiedykolwiek jest ujemne. Ponadto nasz język ma exitinstrukcję z jednym argumentem, która wyświetla odpowiedź logiczną.
Pierwszą kwestią jest to, że ten język programowania jest dobrym językiem specyfikacji dla maszyny Turinga. Można łatwo zobaczyć, że oprócz tablicy taśm kod ma tylko wiele możliwych stanów: Stan wszystkich zadeklarowanych zmiennych oraz bieżący wiersz wykonania i stos podprogramów. Ten ostatni ma tylko skończoną liczbę stanów, ponieważ funkcje rekurencyjne nie są dozwolone. Można sobie wyobrazić „kompilator”, który tworzy „rzeczywistą” maszynę Turinga z kodu tego typu, ale szczegóły tego nie są ważne. Chodzi o to, że mamy język programowania z całkiem dobrą składnią, ale bardzo prymitywnymi typami danych.
Reszta konstrukcji polega na przekształceniu go w bardziej znośny język programowania ze skończoną listą funkcji bibliotecznych i etapów wstępnej kompilacji. Możemy postępować w następujący sposób:
Za pomocą prekompilatora możemy rozwinąć typ danych boolowskich do większego, ale skończonego alfabetu symboli, takiego jak ASCII. Możemy założyć, że tapeprzyjmuje wartości w tym większym alfabecie. Możemy zostawić znacznik na początku taśmy, aby zapobiec niedopełnieniu wskaźnika, oraz ruchomy znacznik na końcu taśmy, aby zapobiec przypadkowemu zjechaniu TM do nieskończoności na taśmie. Możemy zaimplementować dowolne operacje binarne między symbolami oraz konwersje do wartości logicznych ifi whileinstrukcji. (Właściwie ifmożna go również zaimplementować while, jeśli nie był dostępny.)
Chcemy nieograniczonego typu danych liczb całkowitych w celu zaimplementowania zarówno losowego dostępu do taśmy, jak i (dodatniej) arytmetyki liczb całkowitych. W tym celu symulujemy taśm TM dla niektórych stałych za pomocą jednej taśmy, którą mamy. Ta konstrukcja jest podana jako twierdzenie Sipsera. Chodzi o to, aby przeplatać emulowane taśmy na taśmie niskiego poziomu, którą mamy, z symbolami znaczników reprezentującymi pozycje głowy. Jeśli wskaźnik taśmy niskiego poziomu ma wartość zero, obsługuje tą podtapę, przesuwając do pozycji a następnie przeskakując kroków jednocześnie; po każdym odczycie lub zapisie wskaźnik niskiego poziomu zmniejsza się ponownie do zera. Podobnie jak w poprzednim etapie, łatwiej jest zaimplementować to jako prekompilator.k i i kkkjajak
Jedną taśmę określamy jako „pamięć” o wartościach symboli, a pozostałe jako „rejestry” lub „zmienne” bez znaku, o wartościach całkowitych. Przechowujemy liczby całkowite w formacie binarnym little-endian ze znacznikami zakończenia. Najpierw wdrażamy kopię rejestru i binarną dekrementację rejestru. Łącząc to z przyrostem i spadkiem wskaźnika pamięci, możemy zaimplementować wyszukiwanie losowego dostępu do pamięci symboli. Możemy również pisać funkcje do obliczania sumy binarnej i mnożenia liczb całkowitych. Nie jest trudno napisać binarną funkcję dodawania z operacjami bitowymi i funkcję pomnożenia przez 2 z przesunięciem w lewo. (Lub naprawdę prawe przesunięcie, ponieważ jest to little-endian.) Za pomocą tych prymitywów możemy napisać funkcję mnożenia dwóch rejestrów za pomocą algorytmu długiego mnożenia.
Możemy zreorganizować taśmę pamięci z jednowymiarowej tablicy symboli symbol[n]na dwuwymiarową tablicę symboli, symbol[x,y]korzystając ze wzoru n = (x+y)*(x+y) + y. Teraz możemy użyć każdego wiersza pamięci do wyrażenia binarnej liczby całkowitej bez znaku za pomocą symbolu zakończenia, aby uzyskać jednowymiarową pamięć o wartości całkowitej o losowym dostępie memory[x]. Możemy zaimplementować odczyt z pamięci do rejestru liczb całkowitych i zapis z rejestru do pamięci. Wiele funkcji można teraz zaimplementować za pomocą funkcji: arytmetyka znaków zmiennoprzecinkowych, ciągi symboli itp.
Tylko jedna podstawowa funkcja ściśle wymaga prekompilatora, a mianowicie funkcji rekurencyjnych. Można tego dokonać za pomocą techniki powszechnie stosowanej do implementacji języków interpretowanych. Każdej funkcji rekurencyjnej wysokiego poziomu przypisujemy ciąg nazwy i organizujemy kod niskiego poziomu w jedną dużą whilepętlę, która utrzymuje stos wywołań ze zwykłymi parametrami: punkt wywoływania, wywoływana funkcja i lista argumentów.
W tym momencie konstrukcja ma wystarczająco dużo cech języka programowania wysokiego poziomu, że dalsza funkcjonalność jest bardziej tematem języków programowania i kompilatorów niż teorii CS. Już teraz łatwo jest napisać symulator maszyny Turinga w tym rozwiniętym języku. Napisanie kompilatora dla tego języka nie jest łatwe, ale z pewnością standardowe. Oczywiście potrzebujesz zewnętrznego kompilatora, aby utworzyć zewnętrzną bazę TM z kodu w tym języku podobnym do C lub Pythona, ale można to zrobić w dowolnym języku komputerowym.
Zauważ, że ta naszkicowana implementacja obsługuje nie tylko tezę Church-Turinga logików dla rekurencyjnej klasy funkcji, ale także rozszerzoną (tj. Wielomianową) tezę Churcha-Turinga w odniesieniu do obliczeń deterministycznych. Innymi słowy, ma narzut wielomianowy. W rzeczywistości, jeśli otrzymamy maszynę RAM lub (moją ulubioną) taśmę drzewną TM, można to zredukować do narzutu polilogarytmicznego do obliczeń szeregowych z pamięcią RAM.
Wystarczy mówić, jeśli ktoś jest zainteresowany, oto informacja publiczna do skontaktowania się ze mną: