Minimal instruction set to solve any problem with a computer program

Years ago, I have heard that someone was about to demonstrate that every computer program could be solved w开发者_如何学运维ith just three instructions:

• Assignment
• Conditional
• Loop

Please I would like to hear your opinion. I mean representing any algorithm as a computer program. Do you agree with this?

No need. The minimal theoretical computer needs just one instruction. They are called One Instruction Set Computers (OISC for short, kinda like the ultimate RISC).

There are two types. The first is a theoretically "pure" one instruction machine in which the instruction really works like a regular instruction in normal CPUs. The instruction is usually:

subtract and branch if less than zero

or variations thereof. The wikipedia article have examples of how this single instruction can be used to write code that emulates other instructions.

The second type is not theoretically pure. It is the transfer triggered architecture (wikipedia again, sorry). This family of architectures are also known as move machines and I have designed and built some myself.

Some consider move machines cheating since the machine actually have all the regular instructions only that they are memory mapped instead of being part of the opcode. But move machines are not merely theoretical, they are practical (like I said, I've built some myself). There is even a commercially available family of CPUs built by Maxim: the MAXQ. If you look at the MAXQ instruction set (they call it transfer set since there is really only one instruction, I usually call it register set) you will see that MAXQ assembly looks rather like a standard accumulator based architecture.

This is a consequence of Turing Completeness, which is something that was established many decades ago.

Alan Turing, the famous computer scientist, proved that any computable function could be computed using a Turing Machine. A Turing machine is a very simple theoretical device which can do only a few things. It can read and write to a tape (i.e. memory), maintain an internal state which is altered by the contents read from memory, and use the internal state and the last read memory cell to determine which direction to move the tape before reading the next memory cell.

The operations of assignment, conditional, and loop are sufficient to simulate a Turing Machine. Reading and writing memory and maintaining state requires assignment. Changing the direction of the tape based on state and memory contents require conditionals and loops. "Loops" in fact are a bit more high-level than what is actually required. All that is really required is that program flow can jump backwards somehow. This implies that you can create loops if you want to, but the language does not need to have an explicit loop construct.

Since these three operations allow simulation of a Turing Machine, and a Turing Machine has been proven to be able to compute any computable function, it follows that any language which provides these operations is also able to compute any computable function.

Edit: And, as other answerers pointed out, these operations do not need to be discrete. You can craft a single instruction which does all three of these things (assign, compare, and branch) in such a way that it can simulate a Turing machine all by itself.

The minimal set is a single command, but you have to choose a fitting one, for example - One instruction set computer

When I studied, we used such a "computer" to calculate factorial, using just a single instruction:

SBN - Subtract and Branch if Negative:
SBN A, B, C

Meaning:

if((Memory[A] -= Memory[B]) < 0) goto C  
// (Wikipedia has a slightly different definition)

Notable one instruction set computer (OSIC) implementations

This answer will focus on interesting implementations of single instruction set CPUs, compilers and assemblers.

movfuscator

https://github.com/xoreaxeaxeax/movfuscator

Compiles C code using only mov x86 instructions, showing in a very concrete way that a single instruction suffices.

The Turing completeness seems to have been proven in a paper: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

subleq

https://esolangs.org/wiki/Subleq:

• https://github.com/hasithvm/subleq-verilog Verilog, Xilinx ISE.
• https://github.com/purisc-group/purisc Verilog and VHDL, Altera. Maybe that project has a clang backend, but I can't use it: https://github.com/purisc-group/purisc/issues/5
• http://mazonka.com/subleq/sqasm.cpp | http://mazonka.com/subleq/sqrun.cpp C++-based assembler and emulator.

See also

• What is the minimum instruction set required for any Assembly language to be considered useful?
• https://softwareengineering.stackexchange.com/questions/230538/what-is-the-absolute-minimum-set-of-instructions-required-to-build-a-turing-comp/325501

In 1964, Bohm and Jacopini published a paper in which they demonstrated that all programs could be written in terms of only three control structures: the sequence structure, the selection structure and the repetition structure.

Programmers using Haskell might argue that you only need the Contional and Loop because assignments, and mutable state, don't exist in Haskell.