What are the six basic primitives in Turing Complete

turing-machines turing-complete
YourTeddy picture YourTeddy · Jan 26, 2015 · Viewed 18.4k times · Source

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?

Answer

staticdev picture staticdev · Jan 26, 2015

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.

Related questions

What is Turing Complete?

What does the expression "Turing Complete" mean? Can you give a simple explanation, without going into too many theoretical details?

Read More
What's a Turing machine?

What is a Turing machine and why do people keep mentioning it? My IBM PC is all I need to do my computation! Why does anyone care about these machines?

Read More
Turing machine vs Von Neuman machine

Background The Von-Neumann architecture describes the stored-program computer where instructions and data are stored in memory and the machine works by changing its internal state, i.e an instruction operates on some data and modifies the data. So inherently, there …

Read More