Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question

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.

share|improve this answer
2  
+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.

Related reading:

share|improve this answer

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.

share|improve this answer

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

See also: http://stackoverflow.com/questions/3711443/minimal-instruction-set-to-solve-any-problem-with-a-computer-program

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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