Los ordenadores están formados por hardware, literalmente instrucciones de lenguaje de máquina (operaciones) y operandos de cableado duro para obtener resultados predeterminados. En el nivel más bajo de interés, este cableado es la implementación física del álgebra booleana o de algún otro sistema matemático discreto, implementado con puertas lógicas electrónicas.
En el nivel más básico, una puerta lógica toma una o dos entradas binarias (señales) y devuelve una salida binaria con respecto a una de estas operaciones lógicas: AND, OR y NOT. Cualquier tabla de verdad de entradas y salidas binarias arbitrarias puede reducirse a una expresión booleana canónica compuesta por estos operadores lógicos. Es decir, cualquier chip que realice alguna operación lógica sobre datos binarios arbitrarios puede estar compuesto por estas puertas lógicas. Las instrucciones de máquina son bits de control binario para parametrizar el comportamiento del chip.
A partir de estas puertas lógicas elementales, se deriva un nivel de abstracción superior: Sumadores, ALU, multiplexores, registros, CPU, memoria, etc. En este nivel, el ordenador realiza operaciones aritméticas en el hardware de forma secuencial, moviendo los resultados binarios de un lado a otro entre la ALU, los registros y la memoria, sincronizados por la señal de reloj. Estas transformaciones físicas (aritmética) de los datos binarios obedecen lógicamente a los axiomas matemáticos en los que se basan las puertas lógicas.
El software es la abstracción definitiva sobre el hardware. Con él, se puede ordenar a un ordenador que haga cualquier cosa. El software puede definirse utilizando cualquier sintaxis, y está completamente desacoplado del hardware, hasta que se compila. Incluso entonces, sólo depende del código binario, que es la interfaz abstracta del hardware. Nunca se encuentra con el hardware. Ninguno conoce la existencia del otro. Pero, en última instancia, cualquier software se reduce (y se limita) a la secuencia de operaciones aritméticas o lógicas realizadas por el hardware.
Mi pregunta es: ¿cuál es el diseño mínimo de los circuitos y la arquitectura del ordenador (ancho de bits, operaciones de la ALU, registros, conjunto de instrucciones, etc.) para poder compilar y ejecutar teóricamente cualquier software que pueda ejecutar un PC moderno (SO y aplicaciones) en el ordenador, sin tener en cuenta el rendimiento? ¿Y cómo se demuestra esto matemáticamente?
He aquí la cuestión en pocas palabras: ¿Cuál es el conjunto de instrucciones mínimo necesario para que el hardware pueda emular un PC moderno?