Каковы шесть основных примитивов в Turing Complete

Я слушаю урок edX, и профессор подчеркивает, что каждая машина, способная выполнять эти шесть основных примитивов, может называться Turing Complete. Но каковы шесть основных примитивов?

Ответы

Ответ 1

Шесть основных операций/примитивов, которые дают полноту языка Тьюринга:

  • Вправо: переместите столбец Машины справа от текущего квадрата.
  • Слева: переместите столбец Машины слева от текущего квадрата.
  • Печать: печать символа на текущем квадрате
  • Сканирование: определение любых символов на текущем квадрате
  • Стереть: стереть любые символы, представленные на текущем квадрате.
  • Ничего/остановить: ничего не делать

Вы можете узнать больше на справочном веб-сайте Алана Тьюринга и/или смотрите небольшое видео об этом.

Ответ 2

Они являются основными для машины Тьюринга и состоят из

Вправо: Переместите столбец Машины справа от текущего квадрата

Слева: Переместите столбец Машины слева от текущего квадрата

Печать: Печать символа на текущем квадрате

Сканирование: Определите любые символы на текущем квадрате

Стереть: Удалить все символы, представленные в текущем квадрате

Ничего /HALT: Ничего не делать

Идея состоит в том, что с этими шестью примитивами вы можете программировать что угодно.