What is the absolute minimum set of instructions required to build a Turing complete processor

Question

I have a general idea of how the processor handles instructions but spend my time working in mostly high level languages. Maybe somebody who works closer to the iron can provide some valuable insight.

Assuming that programming languages are basically very high level abstractions of a processor's instruction set, what is the most basic set of instructions necessary to create a turing complete machine?

Note: I don't know anything about the diversity of hardware architectures but -- for the sake of simplicity -- lets assume it's a typical processor with an ALU (if necessary) and instruction stack.*

Answer 1

It turns out you only need one instruction to build a machine capable of Turing-computation. This class of machines that have only one instruction and are Turing-complete is called One Instruction Set Computers or also somewhat jokingly Ultimate RISC.

Answer 2

There are many ways to implement something that one can implement a turing machine in.

As you are looking at processors, the one that is most applicable is probably the register machine model. The simplest of these (in terms of symbols) is the mulit-tape two symbol (mark and blank). If you go for something not quite as esoteric, the inc(r), dec(r) and jz(r,z) (jump if register r is zero to instruction z) or the clr(r) (clear r), inc, je(i,j,z) (jump if register i and j are equal to instruction z).

I have seen mention of a register machine that is:

• inc(i, m) - increment register i and go to line m
• jzdec(i, m1, m2) - if register i is 0 go to line m, else decrement i, and go to line m2

which is turing complete too - its a Minsky register machine though it has other constraints on the data in the tape (it has to be a Gödel number storing the state rather than individual registers)

Thats it. Nothing more.

---

So, why aren't these ultra risc processors used instead? Its a real pain to write a compiler for them and you give up a lot of other things that the processor can do. Its really nice to have a bitwise and, and an add rather than trying to do everything with incrementing registers and looping. Thats the basis of a favorite programming language titled Brainfuck which has 8 instructions.

• > increment the data pointer
• < decrement the data pointer
• + increment the data at the data pointer
• - decrement the data at the data pointer
• . output the data at the data pointer
• , read input, storing the data at the data pointer
• [ if the data at the pointer is zero, instead of moving the instruction pointer forward one, jump it forward to the command after the matching ] command
• ] if the data at the pointer is nonzero, instead of moving the instruction pointer forward, jump it back to the command after the matching ] command

One can find compilers to Brainfuck, though its really not fun to do even simple things in it. Unless you enjoy the frustration, which is the purpose of the language.

Related reading:

• (esolangs) Turing tarpit
• What makes a language Turing-complete? (for a programming language)
• Why is FRACTRAN turing complete? (on Gödel number based register machines)

Answer 3

I suspect that Post machine is about the simplest form of a Turing-complete device. You need a supply of bit-addressable memory, an address register that points to the current data location, and five instructions:

• Set the bit at the current location;
• Reset the bit at the current location;
• Move to the next address (increment data address register);
• Move to the previous address (decrement data address register);
• Check the bit at the current data location.

I don't think it's easy to invent something much simpler hardware-wise, though something even more reduced probably exists.

Answer 4

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.
• http://mazonka.com/subleq/sqasm.cpp | http://mazonka.com/subleq/sqrun.cpp C++ assembler and emulator.

See also

https://stackoverflow.com/questions/3711443/minimal-instruction-set-to-solve-any-problem-with-a-computer-program/38523869#38523869

Answer 5

What is the absolute minimum set of instructions required to build a Turing complete processor?

Jörg W Mittag said, "one," but how about zero?

Why do you assume that a "processor" has to have "instructions"?

A Turing machine is a Turing-complete processor, and it does not operate on "instructions" as such. It has rules, but the rules are not instructions that are fetched from a random-access memory.

When Alan Turing thought up his eponymous machine, he was searching for the simplest possible model of "computation" so that he could use mathematical techniques to answer the question, "What is computable?"

You'd be hard pressed to design a Turing-equivalent machine that is simpler than an actual Turing machine.

FWIW, the type of processor that you are thinking of---one that fetches instructions from memory, decodes them, and executes them, and which operates on data stored in the same memory system---is known as a Von Neumann Architecture

https://en.wikipedia.org/wiki/Von_Neumann_architecture