What are the six basic primitives in Turing Complete

Asked 26/1, 2015 at 10:41 Answered 6/9, 2021 at 10:47

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?

Consistory answered 26/1, 2015 at 10:41 Comment(0)

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.

Leund answered 26/1, 2015 at 10:46 Comment(5)

Is this about programming languages, or Turing Machines? They're not the same thing. – Kurbash 26/1, 2015 at 10:54

@Kurbash This is about Turing O-Machines that are implemented as programming languages. – Leund 26/1, 2015 at 10:55

@Kurbash 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. – Leund 26/1, 2015 at 11:2

But, these are not programming language operations. These are turing machine operations. – Kurbash 26/1, 2015 at 13:53

for those that want to try writing something using the above primitives this esoteric language has been created: en.wikipedia.org/wiki/Brainfuck – Zia 6/11, 2016 at 21:23

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.

Drolet answered 26/1, 2015 at 10:51 Comment(4)

This is the same as the answer I posted before. – Leund 26/1, 2015 at 10:52

@StaticX Yes, but your answer is misleadingly - arguably incorrectly - worded. – Kurbash 26/1, 2015 at 10:57

@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 – Drolet 26/1, 2015 at 12:41

@Drolet I agree. I usually research much more before posting a question here. Sadly, many people don't. – Leund 27/1, 2015 at 10:18

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

Ladida answered 6/9, 2021 at 10:47 Comment(2)

This answer has nothing to add compared to the accepted one that has been posted years ago. It should be removed. – Stomy 6/9, 2021 at 11:1

Please add further details to expand on your answer, such as working code or documentation citations. – Affinity 6/9, 2021 at 11:1

Recommended topics

Hot tags