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 Noche Jan 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.

  • $\begingroup$ You may be interested in cstheory.stackexchange.com/questions/10207/…. $\endgroup$ – Noah Schweber Jan 13 '18 at 8:59
  • $\begingroup$ When you ask about the minimal design. What linear ordering are you referring to? $\endgroup$ – D.F.F Jan 13 '18 at 9:00
  • 2
    $\begingroup$ Is it really related to mathematics ? $\endgroup$ – Boris E. Jan 13 '18 at 9:38
  • $\begingroup$ 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. $\endgroup$ – user361949 Jan 13 '18 at 14:42
  • $\begingroup$ @BorisEng Very much so. Simple computing formalisms are very closely related to logic and foundations of mathematics. $\endgroup$ – user361949 Jan 13 '18 at 14:42

This is a quite deep question, and has some problems:

  • What is "any" software? I.e. what do you define as a "program"?
  • With respect to what exactly should this machine be minimal?

It seems like you want to minimize the bits of your CPU registers. Unfortunately, the number of bits is logarithmically proportional to how much memory you have access to. Since a program might need any amount of memory, in fact, no number of bits would be enough to run any program, even if you had an infinite amount of memory.

So you see, even asking the question correctly might be difficult and the answer can vary depending on how you do that. Automata Theory, and theoretical computer science in general, deal with many of these kinds of questions. I am afraid unless you are more specific with what you want to optimize under which conditions, it is hard to give a formal answer.

  • $\begingroup$ I'm no trying to do any optimization, but find the theoretically minimal set of required logical operations provided by the hardware to execute any software than modern PC may also execute. Specifically, what is the absolutely minimum functions of ALU to be able to emulate modern PC on the software running on this minimal hardware, when performance isn't considered? $\endgroup$ – Tuomas Toivonen Jan 13 '18 at 14:24
  • 1
    $\begingroup$ In that case, NOR is a functionally complete gate. Is that what you are looking for? $\endgroup$ – Jesko Hüttenhain Jan 13 '18 at 15:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.