27

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?

Marcin
  • 48,559
  • 18
  • 128
  • 201
YourTeddy
  • 413
  • 2
  • 5
  • 8

3 Answers3

30

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.

mtl
  • 7,529
  • 2
  • 20
  • 22
staticdev
  • 2,950
  • 8
  • 42
  • 66
  • 2
    Is this about programming languages, or Turing Machines? They're not the same thing. – Marcin Jan 26 '15 at 10:54
  • @Marcin This is about Turing O-Machines that are implemented as programming languages. – staticdev Jan 26 '15 at 10:55
  • @Marcin I'm sorry, it is not. I have studied programming languages for a while now. I wouldn't answer if I didn't study that. – staticdev Jan 26 '15 at 11:02
  • 1
    But, these are not programming language operations. These are turing machine operations. – Marcin Jan 26 '15 at 13:53
  • 3
    for those that want to try writing something using the above primitives this esoteric language has been created: https://en.wikipedia.org/wiki/Brainfuck – X10D Nov 06 '16 at 21:23
1

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.

Wald
  • 1,063
  • 7
  • 13
  • This is the same as the answer I posted before. – staticdev Jan 26 '15 at 10:52
  • @StaticX Yes, but your answer is misleadingly - arguably incorrectly - worded. – Marcin Jan 26 '15 at 10:57
  • 2
    @StaticX When I started typing there wasn't anything + this question is basically "Let me google it for you" he could have found the answer within the first 3-4 results without any previous knowledge in machine learning – Wald Jan 26 '15 at 12:41
  • 1
    @Wald I agree. I usually research much more before posting a question here. Sadly, many people don't. – staticdev Jan 27 '15 at 10:18
0

Right move ,Left move ,Read ,Write ,erase and donothing

kareem atef
  • 1
  • This answer has nothing to add compared to the accepted one that has been posted years ago. It should be removed. – buddemat Sep 06 '21 at 11:01
  • Please add further details to expand on your answer, such as working code or documentation citations. – Community Sep 06 '21 at 11:01