I am listening the edX lesson, and the professor stresses that every machine able to perform those six basic primitives can be called Turing Complete. But what are the six basic primitives?
25
votes
3 Answers
28
votes
The six basic operations/primitives that gives a language Turing completeness are:
- Right: Move the Machine’s head to the right of the current square
- Left: Move the Machine’s head to the left of the current square
- Print: Print a symbol on the current square
- Scan: Identify any symbols on the current square
- Erase: Erase any symbols presented on the current square
- Nothing/halt: Do nothing
You can learn more at Alan Turing reference web site and/or watch a small video about it.
1
votes
They are the basic of Turing Machine and are composed of
Right: Move the Machine’s head to the right of the current square
Left: Move the Machine’s head to the left of the current square
Print: Print a symbol on the current square
Scan: Identify any symbols on the current square
Erase: Erase any symbols presented o the current square
Nothing/HALT: Do nothing
The idea is that with those six primitives you can program anything.
