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

hardware low-level turing-completeness

— 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

Jaki jest minimalny zestaw instrukcji wymagany do uznania dowolnego języka asemblera za użyteczny?

— phuclv

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:

(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)

— 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 :

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

— 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