Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

3 Answers 3

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

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
    
+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 at 2:43

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

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.