Set completo di istruzioni alfanumeriche x86 di Turing (sottoinsieme)

Question

Sto cercando di creare un sottoinsieme minimo universale di opcode alfanumerici x86. Alla fine voglio che il sottoinsieme contenga il minor numero possibile di istruzioni, e se ci sono più sottoinsiemi minimi, voglio saperlo anche io. Il sottoinsieme dovrebbe essere in grado di simulare qualsiasi programma che possa essere scritto con l'intera serie di istruzioni alfanumeriche. Le istruzioni devono riguardare solo le istruzioni che corrispondono ai caratteri "A-Z", "a-z" e "0-9".

Finora penso che un push, pop, inc, dec, cmp, e je sarebbe sufficiente, ma sono sicuro che ci sia un insieme ridotto. Come potrei provare a dimostrare che un set che ho generato è in grado di simulare qualsiasi programma utilizzando tutte le istruzioni alfanumeriche? Come potrei dimostrare che un tale insieme è minimo? Qualcuno sa se esiste un sottoinsieme di istruzioni di questo tipo?

Answer 1

È solo UN'istruzione! qui la prova

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

Perché? Solo perché "istruzione" è un concetto dipendente dalla macchina. Non è possibile definire un piccolo insieme di istruzioni solo perché non ci sono istruzioni universali/assolute/atomiche: tutto dipende dall'hardware sottostante: infatti la "vera" macchina è un concetto matematico (un insieme di regole) non fisico macchina

Answer 2

Non sono sicuro di ottenere la tua domanda, in particolare la parte relativa a "alfanumerico", ma vorrei far notare che è noto che sia mov sia xor sono completati da Turing.