Possible Duplicate: Are there minimum criteria for a programming language being
ID: 649096 • Letter: P
Question
Possible Duplicate:
Are there minimum criteria for a programming language being Turing complete?
I overheard a conversation on the topic and the conclusion that one gent came to was that in order to be Turing complete, given one has infinite storage, all one needs is a conditional control structure and a jump instruction.
Is this true?
If it is true, and Turing completeness requires that the language that is Turing complete be able to simulate every instruction available in another Turing complete language, how do those two simple elements achieve that?
Explanation / Answer
The machine you describe would be turing complete with the addition of an assignment operator (you need this to take advantage of memory), and at least one comparison operator (which could be folded into the jump, like a jump-if-(not)-zero). (Note that an increment operator is necessary - either as a primitive, or appropriate representations need to be available such that one can roll ones own).
However, there are many turing-complete models of computation with completely different primitive operations, such as lambda calculus, or petri nets.