Примеры построения машин Тьюринга

Пример 1. Построить машину Тьюринга, которая правильно вычисляет функцию f(x) = x+1 по правилам двоичного сложения.

Решение. Исходя из формулировки задачи, требующей вычислить функцию по правилам сложения в двоичной системе сложения, выберем входной алфавит:

А ={0, 1, ε}.

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

Таблица соответствия:

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

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

1) q₀1 → q₀1R ε111ε 6) q₁1 → q₁0L ε110ε

2) q₀1 → q₀1R ε111ε 7) q₁1 → q₁0L ε100ε

3) q₀1 → q₀1R ε111ε 8) q₁ε → q₂1L ε000ε

4) q₀ε → q₁εL ε111ε 9) q₂ ε → q_z εR ε1000ε

5) q₁1 → q₁0L ε111ε

Из примера видно, что машина Тьюринга из стандартной начальной конфигурации, имея на ленте аргумент 111, выполнив совокупность команд 1-9, перешла в стандартное заключительное состояние, имея на ленте результат 1000. Действительно:

111₂ + 1₂ = 1000₂.

Пример 2. Построить машину Тьюринга, выполняющую операцию (x div 2) и имеющую входной алфавит А = {0, 1, ε}.

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

Операция (x div 2) реализована сдвигом цепочки вправо на 1 разряд.

Пример 3. Построить машину Тьюринга, которая выполняет копирование заданного аргумента. Выберем входной алфавит А={0,1,ε}. Представим данную машину таблицей соответствия:

Запишем программу построенной машины для заданной входной цепочки на ленте, равной двоичному числу 111. Слева от каждой команды приведем представление входной цепочки на ленте до выполнения данной команды. Символ, который находится под головкой, будем помечать подчеркиванием.

Из примера видно, что машина Тьюринга из стандартной начальной конфигурации, имея на ленте аргумент 111 и выполнив совокупность команд 1-32, перешла в стандартное заключительное состояние, имея на ленте результат ε111*111ε.

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

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