Conjunto de instrucciones alfanumérico x86 de Turing Completo (Subconjunto)

Question

Estoy buscando crear un subconjunto computacional universal mínimo de códigos de operación x86 alfanuméricos. Eventualmente quiero que el subconjunto contenga la menor cantidad de instrucciones posible, y si hay múltiples subconjuntos mínimos, también quiero saber eso. El subconjunto debe ser capaz de simular cualquier programa que pueda escribirse con todo el conjunto de instrucciones alfanuméricas. Las instrucciones solo deben cubrir las instrucciones que corresponden a los caracteres "A-Z", "a-z" y "0-9".

hasta ahora creo que, inc, sería suficiente push, popdec, cmp, y je, pero estoy seguro de que hay un conjunto más pequeño. ¿Cómo podría probar que un conjunto que genero puede simular cualquier programa usando todas las instrucciones alfanuméricas? ¿Cómo podría demostrar que ese conjunto es mínimo? ¿Alguien sabe si existe un subconjunto de instrucciones?

Answer 1

¡Es solo UNA instrucción! aquí la prueba

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

¿Por qué? Solo porque "instrucción" es un concepto dependiente de la máquina. No se puede definir un pequeño conjunto de instrucciones simplemente porque no hay tales instrucciones universales/absolutas/atómicas: todo depende del hardware subyacente: de hecho, la máquina de turing "real" es un concepto matemático (un conjunto de reglas) no físico máquina

Answer 2

No estoy seguro de que recibo su pregunta, especialmente la parte sobre "alfanumérico", pero me gustaría señalar que es bien sabido que tanto mov como xor están completos.