Turing Kompletny alfanumeryczny zestaw instrukcji x86 (podzbiór)

Question

Szukam utworzyć minimalny, uniwersalny pod względem obliczeniowym podzbiór alfanumerycznych kodów opcyjnych x86. W końcu chcę podzbiór zawierać jak najmniej instrukcji, jak to możliwe, a jeśli istnieje wiele minimalnych podzbiorów, chcę to również wiedzieć. Podzbiór powinien być w stanie symulować dowolny program, który można zapisać za pomocą całego zestawu instrukcji alfanumerycznych. Instrukcje powinny obejmować tylko instrukcje, które odpowiadają znakom "A-Z", "a-z" i "0-9".

tej pory myślę, że push, pop, inc, dec, cmp, a je wystarczyłoby, ale jestem pewien, że jest mniejszy zestaw. W jaki sposób mógłbym udowodnić, że wygenerowany przeze mnie zestaw jest w stanie symulować dowolny program przy użyciu wszystkich instrukcji alfanumerycznych? Jak udowodnić, że taki zestaw jest minimalny? Czy ktoś wie, czy taki podzbiór instrukcji istnieje?

Answer 1

To tylko JEDNA instrukcja! tutaj dowód

http://en.wikipedia.org/wiki/One_instruction_set_computer

Dlaczego? Tylko dlatego, że "instrukcja" jest pojęciem zależnym od maszyny. Nie możesz zdefiniować małego zestawu instrukcji tylko dlatego, że nie ma takich instrukcji uniwersalnych/absolutnych/atomowych: wszystko zależy od podstawowego sprzętu: W rzeczywistości "prawdziwa" maszyna jest metaforyczną koncepcją (zbiorem zasad) nie fizyczną. maszyna

Answer 2

Nie jestem pewien, czy dostaję twoje pytanie, szczególnie część o "alfanumerycznym", ale chciałbym zaznaczyć, że dobrze wiadomo, że zarówno Turinga są kompletne, jak i mov i xor.