Каковы шесть основных примитивов в Тьюринге?
Я слушаю урок edX, и профессор подчеркивает, что каждую машину, способную выполнить эти шесть основных примитивов, можно назвать Turing Complete. Но каковы шесть основных примитивов?
3 ответа
Шесть основных операций / примитивов, обеспечивающих полноту языка Тьюринга:
- Справа: переместите голову машины справа от текущего квадрата
- Слева: переместите голову машины слева от текущего квадрата
- Печать: печать символа на текущем квадрате
- Сканирование: определить любые символы на текущем квадрате
- Стереть: Стереть любые символы, представленные на текущем квадрате
- Ничего / остановка: ничего не делать
Вы можете узнать больше на справочном веб-сайте Alan Turing и / или посмотреть небольшое видео об этом.
Они являются основой машины Тьюринга и состоят из
Справа: переместите голову машины справа от текущего квадрата
Слева: переместите голову машины слева от текущего квадрата
Печать: печать символа на текущем квадрате
Сканирование: определить любые символы на текущем квадрате
Стереть: Стереть любые символы, представленные на текущем квадрате
Nothing/HALT: ничего не делать
Идея состоит в том, что с этими шестью примитивами вы можете программировать что угодно.
Правый ход, левый ход, чтение, запись, стирание и ничего не делать