Jaki jest absolutny minimalny zestaw instrukcji wymaganych do zbudowania kompletnego procesora Turinga

19

Mam ogólne pojęcie o tym, jak procesor obsługuje instrukcje, ale spędzam czas na pracy w językach wysokiego poziomu. Może ktoś, kto pracuje bliżej żelaza, może zapewnić cenny wgląd.

Zakładając, że języki programowania są w zasadzie bardzo wysokopoziomowymi abstrakcjami zestawu instrukcji procesora, jaki jest najbardziej podstawowy zestaw instrukcji konieczny do stworzenia kompletnej maszyny?

Uwaga: Nic nie wiem na temat różnorodności architektur sprzętowych, ale - dla uproszczenia - załóżmy, że jest to typowy procesor z ALU (jeśli to konieczne) i stosem instrukcji. *

Evan Plaice
źródło
Informatyka SE może być lepszym miejscem do zadawania podobnych pytań. (Nie ma sensu kierować cię tam w tym momencie.) Jednak interesujące pytanie.
Oskar Skog
Wraz ze spadkiem liczby instrukcji ISA spada również znaczenie LICZBY instrukcji. ISA stają się dziwniejsze, gdy mają mniej instrukcji niż „optymalny” RISC. ISA z tylko jedną instrukcją będzie dziwne. // Staje się coraz dziwniejszy, gdy liczba rośnie, a ISA staje się CISC. // „dziwne” jest oczywiście mniej lub bardziej subiektywne.
Oskar Skog

Odpowiedzi:

35

Okazuje się, że potrzebujesz tylko jednej instrukcji, aby zbudować maszynę zdolną do obliczeń Turinga. Ta klasa maszyn, które mają tylko jedną instrukcję i są kompletne Turinga, nazywa się Komputery z zestawem instrukcji lub nieco żartobliwie Ultimate RISC .

Jörg W Mittag
źródło
4
+1 za trafienie w najlepszą możliwą odpowiedź, chyba że zostanie znalezione rozwiązanie zerowej instrukcji (w rzeczywistości jeden komputer instrukcji jest czasami nazywany komputerem instrukcji zerowej, ponieważ w samej instrukcji nie znaleziono informacji)
Cort Ammon - Przywróć Monikę
4
Tak, ale ta jedna instrukcja nie jest tym, co sprawia, że ​​maszyna Turinga jest kompletna: magia znajduje się we wszystkich różnych specjalistycznych rejestrach, które instrukcja może rozwiązać. Myślę, że twoja odpowiedź wskazuje, że OP utożsamia „komputer” z „architekturą von Neumanna”, podczas gdy w rzeczywistości kategoria „komputery” jest znacznie szersza.
Solomon Slow
2
@jameslarge Magia niekoniecznie znajduje się w specjalistycznych rejestrach. BitBitJump, SBNZ, SUBLEQ i SUBNEG wcale nie potrzebują rejestrów, tylko jedna instrukcja i głupia pamięć.
8bittree
2
@ 8bittree, Hunh! Wydaje mi się, że zapomniałem, że projektowanie dziwnych, ale kompletnych architektur Turinga jest sportem wyczynowym. Kiedy przeczytałem odpowiedź Jörga, przypomniałem sobie przyjaciela z czasów studenckich (około 1980 roku), który planował zbudować „komputer z jedną instrukcją” z układów serii 74LS, a następnie zaprogramować go tak, aby emulował DecSystem 10. Właśnie spojrzałem na stronie Wikipedii, a teraz wiem, że jego projekt zostałby dziś nazwany „Architektura wyzwalana transportem”. Nie wiem, czy kiedykolwiek to zrobił.
Solomon Slow
2
@jameslarge: Intel MMU jest również Turing-complete (w szczególności mechanizm pułapki). To jest naprawdę bardzo dziwne, jednak jest odwrotne do bycia zaprojektowanym, to czysty wypadek.
Jörg W Mittag,
15

Istnieje wiele sposobów implementacji czegoś, w czym można wdrożyć maszynę Turinga.

Patrząc na procesory, najbardziej odpowiedni jest prawdopodobnie model maszyny rejestrującej . Najprostszym z nich (pod względem symboli) jest symbol mulit-tape dwa ( marki blank). Jeśli pójdziesz za coś nie tak ezoteryczne, inc(r), dec(r)i jz(r,z)(Przełącz jeżeli rejestr rjest zero z instrukcją z) lub clr(r)(clear r) inc, je(i,j,z)(skok jeśli zarejestrować i oraz j są równe instrukcji z).

Widziałem wzmiankę o maszynie rejestrującej, która jest:

  • inc (i, m) - rejestr przyrostowy i idź do linii m
  • jzdec (i, m1, m2) - jeśli rejestr i wynosi 0, przejdź do linii m, w innym przypadku zmniejsz i i przejdź do linii m2

który również jest kompletny - to maszyna rejestru Minsky'ego, choć ma inne ograniczenia danych na taśmie (musi to być numer Gödela przechowujący stan, a nie poszczególne rejestry)

Otóż ​​to. Nic więcej.


Dlaczego więc nie używa się tych ultra ryzykownych procesorów? Pisanie dla nich kompilatora to prawdziwy problem, a ty rezygnujesz z wielu innych rzeczy, które może zrobić procesor. Naprawdę miło jest mieć odrobinę bitów andi addzamiast próbować robić wszystko z przyrostowymi rejestrami i zapętlaniem. To podstawa ulubionego języka programowania zatytułowanego Brainfuck, który ma 8 instrukcji.

  • > zwiększ wskaźnik danych
  • < zmniejsz wskaźnik danych
  • + zwiększyć dane przy wskaźniku danych
  • - zmniejszać dane przy wskaźniku danych
  • . wyprowadzać dane przy wskaźniku danych
  • , odczytać dane wejściowe, przechowując dane we wskaźniku danych
  • [jeśli dane na wskaźniku wynoszą zero, zamiast przesuwać wskaźnik instrukcji o jeden do przodu, przeskocz go do polecenia po dopasowanym ]poleceniu
  • ]jeśli dane na wskaźniku są niezerowe, zamiast przesuwać wskaźnik instrukcji do przodu, przeskocz z powrotem do polecenia po dopasowanym ]poleceniu

Można znaleźć kompilatory dla Brainfuck, choć naprawdę nie jest fajnie robić w nim nawet proste rzeczy. Chyba że lubisz frustrację, która jest celem języka.

Powiązana lektura:

Społeczność
źródło
5

Podejrzewam, że maszyna pocztowa dotyczy najprostszej formy urządzenia pełnego Turinga. Potrzebny jest zapas pamięci adresowalnej bitowo, rejestr adresów wskazujący bieżącą lokalizację danych oraz pięć instrukcji:

  • Ustaw bit w bieżącej lokalizacji;
  • Zresetuj bit w bieżącej lokalizacji;
  • Przejdź do następnego adresu (rejestr adresu przyrostowego);
  • Przejdź do poprzedniego adresu (rejestr adresów danych dekrementacji);
  • Sprawdź bit w bieżącej lokalizacji danych.

Nie sądzę, że łatwo jest wymyślić coś znacznie prostszego sprzętowo, chociaż prawdopodobnie istnieje coś jeszcze bardziej zredukowanego.

9000
źródło
5

Realizacje

Ta odpowiedź skupi się na interesujących implementacjach procesorów, kompilatorów i asemblerów z pojedynczymi instrukcjami.

movfuscator

https://github.com/xoreaxeaxeax/movfuscator

Kompiluje kod C przy użyciu tylko movinstrukcji x86, pokazując w bardzo konkretny sposób, że wystarczy jedna instrukcja.

Wydaje się, że kompletność Turinga została udowodniona w dokumencie: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

subleq

https://esolangs.org/wiki/Subleq :

Zobacz też

/programming/3711443/minimal-instruction-set-to-solve-any-problem-with-a-computer-program/38523869#38523869

Ciro Santilli
źródło
3

Jaki jest absolutny minimalny zestaw instrukcji wymaganych do zbudowania kompletnego procesora Turing?

Jörg W Mittag powiedział „jeden”, ale co powiesz na zero?

Dlaczego zakładasz, że „procesor” musi mieć „instrukcje”?

Maszyna Turinga jest kompletnym procesorem Turinga i nie działa jako taka na „instrukcjach”. Ma reguły , ale nie są to instrukcje pobierane z pamięci o swobodnym dostępie.

Kiedy Alan Turing wymyślił swoją tytułową maszynę, szukał najprostszego możliwego modelu „obliczeń”, aby móc skorzystać z technik matematycznych, aby odpowiedzieć na pytanie „Co można obliczyć?”.

Trudno byłoby zaprojektować maszynę równoważną Turinga, która jest prostsza niż rzeczywista maszyna Turinga.

FWIW, rodzaj procesora, o którym myślisz --- taki, który pobiera instrukcje z pamięci, dekoduje je i wykonuje je i który działa na danych przechowywanych w tym samym systemie pamięci --- jest znany jako Architektura von Neumanna

https://en.wikipedia.org/wiki/Von_Neumann_architecture

Solomon Slow
źródło