# What is (mathematically) minimal computer architecture to run any software [closed]

Computer consist of hardware, literally hard wiring machine language instructions (operations) and operands to predetermined results. At the lowest level of interest, this hard wiring is physical implementation of boolean algebra or some other discrete mathematical system, implemented with electronic logic gates.

At the most basic level, a logic gate takes one or two binary inputs (signals), and return a binary output in respect to one of these logical operations: AND, OR and NOT. Any truth table of arbitrary binary inputs and outputs can be reduced to canonical boolean expression composed of these logical operators. I.e any chip performing some logical operation on arbitrary binary data can be composed of these logic gates. Machine instruction are binary control bits to parameterize the chip behavior.

From these elementary logic gates, higher level of abstraction is derived: Adders, ALU, multiplexers, registers, CPU, memory etc. At this level, computer performs arithmetic operations on hardware sequentially, moving the binary results back and forth between ALU, registers and memory, synchronized by the clock signal. These physical transformations (arithmetics) of binary data logically obeys the mathematical axioms on which the logic gates are based.

Software is the ultimate abstraction over hardware. With it, computer can be instructed to perform anything. Software can be defined using any syntax, and it is completely decoupled from the hardware, until compiled. Even then, it only depends on the binary code, which is abstract interface to hardware. It never meets the hardware. Neither knows the existence of the other. But ultimately, any software is reduced (and limited) to the sequence of arithmetic or logical operations performed by the hardware.

My question is, what is the minimal design of computer circuitry and architecture (bit width, ALU operations, registers, instruction set etc.) to be able to theoretically compile and run any software which modern PC can run (OS and applications) on the computer, when performance isn't considered? And how do you mathematically proof this?

Here is the question in the nutshell: What is the minimal required instruction set for hardware to be able to emulate a modern PC?

## closed as off-topic by achille hui, G Cab, Namaste, Claude Leibovici, Joel Reyes NocheJan 14 '18 at 8:55

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is not about mathematics, within the scope defined in the help center." – achille hui, G Cab, Namaste, Claude Leibovici, Joel Reyes Noche
If this question can be reworded to fit the rules in the help center, please edit the question.

• You may be interested in cstheory.stackexchange.com/questions/10207/…. – Noah Schweber Jan 13 '18 at 8:59
• When you ask about the minimal design. What linear ordering are you referring to? – D.F.F Jan 13 '18 at 9:00
• Is it really related to mathematics ? – Boris E. Jan 13 '18 at 9:38
• It is hard to define a ordering of simplicity, but I would guess register machines are as simple as they can get. en.wikipedia.org/wiki/Register_machine The keyword here is Turing completeness. – user361949 Jan 13 '18 at 14:42
• @BorisEng Very much so. Simple computing formalisms are very closely related to logic and foundations of mathematics. – user361949 Jan 13 '18 at 14:42