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

-

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) – Cort Ammon Feb 27 '14 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. – james large 21 hours ago

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.

-

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.

-

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

-

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

-