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

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

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 .

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:

• (esolangi) Turing Tarpit
• Co sprawia, że ​​język Turinga jest kompletny? (dla języka programowania)
• Dlaczego FRACTRAN Turing jest gotowy? (na urządzeniach rejestrujących opartych na liczbie Gödela)

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.

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 :

• https://github.com/hasithvm/subleq-verilog Verilog, Xilinx ISE.
• https://github.com/purisc-group/purisc Verilog i VHDL, Altera.
• http://mazonka.com/subleq/sqasm.cpp | http://mazonka.com/subleq/sqrun.cpp Asembler i emulator C ++.

Zobacz też

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

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