Тема 6. Способы представления машины Тьюринга

План лекции:

1. Способы представления машины Тьюринга

2. Операции над машинами Тьюринга

1. Способы представления машины Тьюринга

Существует три способа представления машины Тьюринга: совокупностью команд, в виде графа, в виде таблицы соответствия.

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

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

Чтобы записать совокупность команд, нужно воспользоваться следующими правилами:

1) начальному шагу алгоритма ставится в соответствие q₀ - начальное состояние;

2) циклы реализуются так, что последнее действие цикла должно соответствовать переходу в то состояние, которое соответствует началу цикла;

3) соседним шагам алгоритма соответствует переход в смежные состояния, которые соответствуют этим пунктам;

4) последний шаг алгоритма вызывает переход в заключительное состояние.

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

Пусть алфавит машины Тьюринга задан множеством A={0, 1, ε}, где символ ε соответствует пустой ячейке, а число состояний устройства управления задано в виде множества Q = {q₀, q₁, q_z}.

Если, например, начальная конфигурация имеет вид q₀110011, то конечная конфигурация после завершения операции инвертирования должна иметь вид q_z001100. Для решения задачи машиной будет порождена следующая последовательность команд:

q₀1 → q₀0R, q₁0 → q₁0L,

q₀0 → q₀1R, q₁1 → q₁1L,

q₀ ε → q₁εL, q₁ε → q_zεR.

В стандартной начальной конфигурации головка стоит над первым символом слева, и устройство управления находится в начальном состоянии. На следующем такте машина Тьюринга, не меняя своего состояния, заменяет символ 0 на 1 или 1 на 0 и сдвигается вправо на один символ. После просмотра всей цепочки под головкой оказывается символ, указывающий на пустую ячейку. В этом случае машина Тьюринга переходит в новое состояние и сдвигается влево на один символ. На последующих тактах управляющее устройство не меняет своего состояния, оставляет без изменения символ под головкой и перемещается влево до тех пор, пока не встретит пустую ячейку. Встретив пустую ячейку, машина Тьюринга переходит в заключительное состояние и перемещается вправо на один символ, переходя в стандартную заключительную конфигурацию.

3.4.2. Представление машины Тьюринга графом

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

Машина Тьюринга из рассмотренного примера инвертирования цепочки, состоящей из символов 0 и 1, будет представлена в виде графа следующим образом:

Начальная и конечная вершины графа обычно выделяются; на рисунке они отмечены черным кружком. Если на очередном такте работы машины Тьюринга символ на ленте не изменяется, то в правой части команды его можно не писать (ε на ребре в состояние q_z ).

Представление машины Тьюринга таблицей соответствия

При представлении машины Тьюринга данным способом составляется таблица, в которой каждому состоянию соответствует строка, а каждому символу из входного алфавита - столбец. В клетках таблицы на пересечении строки и столбца будет находиться действие (или правая часть команды).

Таблица соответствия для задания машины Тьюринга из рассмотренного примера будет выглядеть следующим образом:

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

Дата добавления: 2015-07-26; просмотров: 253; Нарушение авторских прав

Мы поможем в написании ваших работ!