Математическая логика и теория алгоритмов

2.3 Вычисление функций на машине Тьюринга

назад | оглавление | вперёд

 

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

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

Пример 1. Вычислим функцию O(x)=0.
       Очевидно, что действия МТ сводятся к замене всех последовательно идущих на ленте единиц нулями.
       Программа вычислений :
       
       Пошаговое исполнение программы для начальной конфигурации='1111110' вы можете увидеть, перейдя по ссылке "Иллюстрация примера №1".
       Иллюстрация примера №1

Пример 2. Вычислим функцию S(x)=x+1
       Для вычисления этой функции достаточно приписать слева одну единицу к последовательности единиц на ленте.
       Программа вычислений:
       
       Пошаговое исполнение программы для начальной конфигурации='0111' вы можете увидеть, перейдя по ссылке "Иллюстрация примера №2".
       Иллюстрация примера №2

Пример 3. Построить машину Тьюринга для вычисления функции C(x)=S(O(x)).
       Для этого будем использовать принцип суперпозииции для МТ. Суть его поясним на следующем примере. Искомую машину будем строить как суперпозицию машин, вычисляющих функции O(x)=0 и S(x)=x+1. Возьмем МТ, вычисляющие эти функции. Объединим состояния и программы этих машин. Пусть имеются две машины T1 и T2, которые вычисляют функции f1(x) и f2(x) соответственно в одном и том же алфавите. Построим новую машину Тьюринга Т следующим образом. Состояния машины T2 переобозначим так, чтобы они отличались от состояний T1. Начальное состояние q11 машины Т1 объявляем начальным состоянием q1 машины Т. Заключительное состояние q02 машины Т2 объявляем заключительным состоянием q0 машины Т. Заключительное состояние q01 машины Т1 и начальное состояние q12 машины Т2 отождествляем. Полученные команды для обеих машин объединяем в одну программу новой машины. Построенная машина Т вычисляет суперпозицию функций и называется суперпозицией машин Т1 и Т2.
       В результате из двух таблиц:
       
       получим одну:
       

Пример 4.Построить МТ для вычисления функции
       Ранее были построены МТ для вычисления функций O(x)=0 и S(x)=x+1. Легко видеть, что исходная функция – это функция O(x), если x > 1 и функция S(x) в противном случае. Таким образом, перед вычислением нужно определить, сколько единиц находится на ленте, и в зависимости от этого переходить к вычислению функций. Для определения количества единиц на ленте будем сдвигаться по ленте вправо и на каждом сдвиге менять состояние МТ. Если обнаружили больше двух единиц, необходимо вернуться назад на начало последовательности единиц и применить МТ для вычисления функции O(x). Если обнаружили две или одну единицу, то устанавливаем головку на начале последовательности единиц и применяем МТ для вычисления функции S(x). Внутренние состояния машин для вычисления функций O(x) и S(x) пометим буквами O и S соответственно. Заключительные состояния этих машин отождествим.
       Программа MT:

       

       Пошаговое исполнение программы для двух разных начальных конфигураций вы можете увидеть, перейдя по ссылке "Иллюстрация примера №4".



Пример 5. Построить МТ для вычисления функции .
       Чтобы правильно вычислить данную функцию, необходимо построить МТ, которая переводит конфигурацию в конфигурацию . Порядок действий для МТ можно выбрать такой. Сначала происходит движение головки вправо до появления на ленте нуля. Этот нуль разделяет аргументы на ленте. Поставим в эту ячейку вместо нуля единицу и вернемся к началу последовательности единиц. Заменим первые две единицы нулями. Тогда на ленте останется x+y+1 единиц.
       Набор команд для такой MT:

       
       Программу МТ можно изобразить в виде ориентированного графа, вершинами которого являются внутренние состояния МТ, а дуги помечены тройками из символов внешнего алфавита и символов из множества {L,R,H}.
       

       Пошаговое исполнение программы при х=2, у=1 (начальная конфигурация='01110110') вы можете увидеть, перейдя по ссылке "Иллюстрация примера №5".
       Иллюстрация примера №5

       Если Вы хотите создать свои примеры МТ, либо проверить работу МТ на примерах, приведенных выше (разделы 2.2 и 2.3) на других начальных конфигурациях, то перейдите по ссылке "Создайте свою Машину Тьюринга". Эта программа также поможет Вам при выполнении контрольной работы. Сохраните архив на свой жесткий диск и запустите файл MT.exe
       Создайте свою Машину Тьюринга


назад | оглавление | вперёд