Mały język podobny do C, który mogą symulować maszyny Turinga

Szukam małego języka, który pomoże „przekonać” studentów, że maszyny Turinga są wystarczająco ogólnym modelem obliczeniowym. To znaczy język, który wygląda jak języki, do których są przyzwyczajeni, ale można go również łatwo symulować na maszynie Turinga.

Papadimitriou używa do tego zadania maszyn RAM, ale obawiam się, że porównanie czegoś dziwnego (jako maszyny Turinga) z inną dziwną rzeczą (w zasadzie językiem asemblera) byłoby zbyt nieprzekonujące dla wielu studentów.

Wszelkie sugestie byłyby bardzo mile widziane (szczególnie jeśli zostałyby opatrzone zalecaną literaturą)

• Jeśli twoi uczniowie wykonali jakieś programowanie funkcjonalne, najmilszym podejściem, jakie znam, jest rozpoczęcie od niepoprawnego rachunku lambda, a następnie użycie twierdzenia o nawiasie abstrakcyjnym, aby przełożyć go na kombinatory SKI. Następnie można użyć i twierdzenia, aby pokazać, że maszyny Turinga tworzą częściową combinatory algebry , i tak można zinterpretować kombinatorów narciarskich.$smn$$utm$

  Wątpię, aby było to najprostsze możliwe podejście, ale podoba mi się to, jak opiera się on na niektórych z najbardziej podstawowych twierdzeń w zakresie obliczalności (które możesz chcieć przedstawić z innych powodów).

  Wygląda na to, że kilka miesięcy temu Andrej Bauer odpowiedział na podobne pytanie dotyczące Mathoverflow .

• Jeśli jesteś ustawiony na język podobny do C, twoja ścieżka będzie znacznie trudniejsza, ponieważ mają one dość skomplikowaną semantykę - musisz

  1. Pokaż, że maszyny Turinga mogą jednocześnie symulować stos i stertę, oraz
  2. Pokaż, jak zmienne można zaimplementować za pomocą stosu, oraz
  3. Pokaż, że wywołania procedur można realizować za pomocą stosu.

  Szczerze mówiąc, to duża część klasy kompilatorów.

Moja teoria profesora Comp w undergrad rozpoczęła się od udowodnienia, że ​​maszyna Turinga z jedną taśmą może implementować maszynę Turinga z wieloma taśmami. Obsługuje to deklarację zmiennych: jeśli program ma sześć deklaracji zmiennych, można go łatwo zaimplementować na siedmiopasmowej maszynie Turinga (taśma dla każdej zmiennej i taśma „rejestrowa”, aby pomóc w wykonywaniu zadań takich jak arytmetyka i sprawdzanie równości między taśmy). Następnie pokazał, jak zaimplementować podstawowe pętle FOR i WHILE, i wtedy mieliśmy podstawowy język T-kompletny. W każdym razie uznałem to za satysfakcjonujące.

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:

1. 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.)

2. 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 $k$$k$$i$$i$$k$

3. 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.

4. 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.

5. 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.

Kompilator LLVM pozwala dość prosto „podłączyć” nową architekturę. Nazywają to pisaniem nowego zaplecza i podają szczegółowe instrukcje i przykłady, jak to zrobić. Podejrzewam, że będziesz musiał przeskoczyć niektóre obręcze w odniesieniu do pamięci o swobodnym dostępie, jeśli nie chcesz atakować maszyny RAM Turing, ale jest to zdecydowanie wykonalne, ponieważ widziałem wiele projektów, które powodują generowanie LLVM VHDL lub inne bardzo różne języki maszynowe.

Miałoby to interesujący efekt posiadania najnowocześniejszego kompilatora optymalizującego (pod wieloma względami LLVM jest bardziej zaawansowany niż GCC) generującego kod dla maszyny Turinga.

Nie jestem w teorii cs, ale mam coś, co może być przydatne. Wziąłem kolejny approch. Zaprojektowałem prosty procesor programowalny bezpośrednio z małym podzbiorem C. Nie ma kodu asemblera, tylko kod podobny do C. Możesz użyć tego samego narzędzia, którego użyłem i zmodyfikować ten procesor, aby zaprojektować symulator maszyny Turinga. Zaprojektowanie, symulacja i przetestowanie tego procesora zajęło mi 4 dni, a także kilka instrukcji! Narzędzia, których użyłem, pozwoliły mi nawet wygenerować prawdziwy kod syntezowalny VHDL. To prawdziwy działający procesor.

Oto jak wygląda program:

Oto zdjęcie procesora wykorzystującego te Narzędzia:

Narzędzia „Novakod Studio” używają języka opisu sprzętu wysokiego poziomu. Jako przykład podajemy kod licznika programu: Wystarczy mówić, jeśli ktoś jest zainteresowany, oto informacja publiczna do skontaktowania się ze mną: https://repertoire.uqac.ca/Fiche.aspx?id=JjstNzsH0&link=1

Luc

A może weźmiesz tutaj pomysł reprezentowany przez użytkownika GMB (maszyna Turinga z jedną taśmą może symulować maszynę Turinga z taśmami N przez przeplatanie N taśm na jednej taśmie i odczytywanie dowolnej z tych taśm przez przeskakiwanie N miejsc na raz, Turinga maszyna z taśmami N może zaimplementować ...) i napisać program maszyny Turinga, który implementuje uproszczoną pamięć RAM. Maszyna RAM może być w rzeczywistości jakimś uproszczonym, prawdziwym procesorem z dostępnym zapleczem LLVM lub GCC. Następnie GCC / LLVM może zostać użyty do kompilacji krzyżowej programu C dla tego procesora, a program maszyny Turinga, który symuluje maszynę RAM, uruchamia symulację maszyny RAM, zlecając symulację maszyny RAM wykonanie wyjścia GCC / LLVM. Implementacją maszyny Turinga może być bardzo prosty kod C, który pasuje do małego pliku C.

Jeśli chodzi o maszynę RAM, to istnieje projekt demonstracyjny, w którym 32-bitowy procesor jest symulowany przez 8-bitowy mikrokontroler, a symulowany 32-bitowy procesor uruchamia Linuksa. Powoli jak diabli, ale według autora , Dmitry'ego Grinberga, zadziałało. Być może procesor Zylin (zylin użytkownika GitHub) może być dobrym wyborem dla symulowanej maszyny RAM. Kolejnym kandydatem na maszynę RAМ może być dot com ProjectOberon autorstwa Niklausa Wirtha .

(„Kropka” i „com” w moim tekście wynikają z faktu, że właśnie, 2015_10_21, zarejestrowałem swoje konto na cstheory.stackexchange, a aplikacja internetowa nie pozwala na więcej niż 2 linki dla początkujących użytkowników, pomimo faktu, że że mogą automatycznie zobaczyć z moich innych kont wymiany stosów, że mogę być głupi, ale nie jestem trollem).