1.6.2 Вычислимость. Эквивалентность алгоритмических моделей

Видеоурок: Введение в алгоритмы. Машина Тьюринга

Лекция: Вычислимость. Эквивалентность алгоритмических моделей

Машина Тьюринга

Для работы машины Тьюринга написан алгоритм, который направлен на работу управляющего устройства. Данный алгоритм позволяет задавать значение той ячейки, в которой находится управляющее устройство. Так же можно задать некоторое действие устройства в данной ячейке.

Для задания значений ячейкам в машине Тьюринга используют ограниченный алфавит. А для перехода от одного значения к другому используют следующую команду:

q₁a₁ ->q₂a₂D.

Слева от команды написано состояние или значение данной ячейки в рассматриваемый момент времени, а справа значение, которое будет иметь данная ячейка после изменения свойств. D – это передвижение управляющего устройства. Если на месте данной буквы стоит L, то необходимо управляющее устройство необходимо передвинуть влево, если R – то вправо, а если N, то остаться на месте.

Машина Поста

Машина Поста очень похожа на машину Тьюринга, поскольку имеет те же возможности, однако она намного проще. Данная машина имеет бесконечный ряд ячеек, которые могут принимать значения только 1 или 0. Алгоритм данной машины прост, состоит всего из нескольких строк и имеет небольшое количество команд:

• L – каретка машины переходит влево,

• R – каретка машины переходит вправо,

• 1 – в ячейке, где находится каретка, ставится значение 1,

• 0 – в ячейке, где находится каретка, ставится значение 0,

• S – машина Поста завершает свою работу,

• ? p₁, p₂ – если ячейка, в которой находится каретка содержит символ 0, то необходимо выполнить строку p₁, если же там стоит 1, то выполняем p₂.

Нормальные алгоритмы Маркова

Алгоритм Маркова позволяет изменять слова заменой их частей. Данный алгоритм имеет множество значений, а замена производится подстановкой.

С помощью специального правила над строкой выполняется ряд действий, которые приводят её к необходимому состоянию. Это возможно при ненулевой строке. Каждая новая подстановка начинается с первой возможной. Если подстановка прошла успешно, то специальное правило завершает алгоритм. Формулы для завершения алгоритма помечаются звездочкой *. Обратите внимание на то, что в данном случае звездочка не должна быть включена в алфавит. Если же необходимо использовать её для замены строк, то в качестве завершающего знака следует использовать другой символ, не входящий в алгоритм.