Формализация понятия алгоритма

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: бесплатный решебник, методы дипломной работы
| Добавил(а) на сайт: Камилла.

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

Теперь, когда мы немного освоились с работой Машины Тьюринга и ее устройством, сделаем одно замечание по поводу записи последовательности команд, которую мы будем называть программой Машины Тьюринга. Один способ записи показан на рисунке 1. Другой способ основан на том, что пара - (текущий символ, текущее состояние каретки) однозначно определяет правую часть любой команды.

Действительно, возьмем таблицу размером p×(m-1), где p=|D| - число символов алфавита, m=|Q| - число состояний каретки. В размерности указано (m-1) потому, что состояние ! не может встретиться в левых частях команд. Столбцы этой таблицы поименуем символами из D, а строки - символами из Q. Тогда в соответствующих полях таблицы надо будет записать лишь тройку из правых частей команд.

На рис. 2 показана табличная запись программы с рисунка 1.