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

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.*

• Computer Science SE might be a better place to ask similar questions in. (No point in directing you there at this time.) Interesting question though. Commented May 8, 2017 at 14:46
• As the number of instructions an ISA has goes down, so does the meaningfullness of the NUMBER of instructions. ISAs get weirder when they have fewer instructions than an "optimal" RISC. An ISA with only one instruction is going to be weird. // They also get weirder as the number increases and the ISA becomes a CISC. // "weird" is of course more or less subjective. Commented May 8, 2017 at 14:51
• We can have a debate about the definition of processor and instruction but note that all you need is a NAND gate. From there it is building ever more complex processors, first in hardware, then in software. The physical chip with the external hardware interface (what you probably see as the processor) is just one intermediate step to the machine we call Turing complete. Commented Feb 10, 2021 at 9:09

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.

• +1 for hitting the best possible answer, unless a zero instruction solution is found (actually, one instruction computers are sometimes called zero instruction computers, because there's no information found in the instruction itself) Commented Feb 27, 2014 at 2:43
• Yes, but that one instruction is not what makes the machine Turing complete: The magic is in all of the different specialized registers that the instruction can address. I think your answer points out that the OP equates "computer" with "Von Neumann architecture", when actually, the "computers" category is much broader than that. Commented Jul 22, 2016 at 15:44
• @jameslarge The magic is not necessarily in specialized registers. BitBitJump, SBNZ, SUBLEQ, and SUBNEG don't need registers at all, just a single instruction each, and dumb memory. Commented Apr 6, 2017 at 19:08
• @8bittree, Hunh! I guess I forgot that designing weird-but-Turing-complete architectures is a competitive sport. When I read Jörg's answer, I recalled a friend from back in my undergrad days (circa 1980-something) who planned to build a "one instruction computer" from 74LS series chips, and then program it to emulate a DecSystem 10. I just looked at the Wikipedia page, and I now know that his design would be called a "Transport Triggered Architecture" today. I don't know whether he ever followed through. Commented Apr 6, 2017 at 21:14
• @jameslarge: the Intel MMU is also Turing-complete (in particular, the trap mechanism). It is indeed very weird, however, it is the opposite of being designed, it is a pure accident. Commented Apr 7, 2017 at 0:32

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.

single instruction CPU 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

FlipJump

https://esolangs.org/wiki/FlipJump

Flip a bit, then Jump.

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

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;
• 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.

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