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 (
blank). If you go for something not quite as esoteric, the
jz(r,z) (jump if register
r is zero to instruction
z) or the
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
] if the data at the pointer is nonzero, instead of moving the instruction pointer forward, jump it back to the command after the matching
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.