ПОНЯТИЕ АЛГОРИТМА. МАШИНЫ ТЬЮРИНГА


Баранов Виктор Павлович. Дискретная математика. Раздел 7. Элементы теории алгоритмов.

Лекция 34. Понятие алгоритма. Машины Тьюринга

Лекция 33. ПОНЯТИЕ АЛГОРИТМА. МАШИНЫ ТЬЮРИНГА

План лекции:

  1. Понятие алгоритма.
  2. Машины Тьюринга.
  3. Композиции машин Тьюринга. Тезис Тьюринга.
  4. Определение вычислимой функции.

  1. Понятие алгоритма

Рассмотрим основные требования к алгоритмам.

1. Дискретность. Любой алгоритм состоит из отдельных шагов, на каждом из которых происходят определенные преобразования некоторой системы величин. В начале алгоритма эту систему образуют исходные данные, в конце – результаты работы алгоритма.

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

3. Элементарность шагов. Преобразования системы величин на каждом шаге алгоритма должны быть простыми и число шагов должно быть конечным.

4. Результативность. Заключается в остановке алгоритма после конечного числа шагов с указанием того, что считать результатом.

5. Массовость. Заключается в выборе для работы алгоритма исходных данных из потенциально бесконечного множества.

Со временем в математике накопился ряд проблем, для которых не удалось найти алгоритма их решения, и имелись серьезные основания предполагать, что такого алгоритма нет. В связи с этим возникла необходимость формального определения алгоритма как некоторого математического объекта таким образом, чтобы для одних задач такой объект можно было построить, а для других доказать, что такого объекта не существует.

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

На основе анализа алгоритмов из самых различных областей человеческой деятельности можно постулировать следующее утверждение:

любой алгоритм представляет собой преобразование слов в некотором алфавите в слова в том же алфавите, то есть словарный оператор.

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

1. Рекурсивные функции.

2. Машины Тьюринга.

3. Нормальные алгорифмы А.А. Маркова.

  1. Машины Тьюринга

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

Каждая машина Тьюринга имеет ленту, управляющую головку (читающую и записывающую) и работает с некоторым конечным алфавитом . Лента бесконечна в обе стороны и разбита на клетки. Машина работает в дискретные моменты времени. Среди букв алфавита имеется «пустой» символ . В каждый момент времени в каждой клетке записана одна из букв алфавита .

Управляющая головка представляет собой конечный автомат с множеством внутренних состояний . В каждый момент времени она находится в одном из этих состояний и обозревает одну из клеток ленты. В зависимости от своего состояния и буквы на ленте головка записывает новую букву (в частности, ту же самую букву), переходит к следующему моменту времени в новое состояние(в частности, то же самое) и сдвигается по ленте – либо на одну клетку влево (), либо на одну клетку вправо (), либо остается на месте (). Среди внутренних состояний выделено одно, скажем , которое называется заключительным. Если после некоторого очередного сдвига головка попадает в заключительное состояние, то машина прекращает свою работу (останавливается).

Чтобы полностью определить работу машины, достаточно указать для начального момента времени ее конфигурацию, в которую входят:

  1. распределение букв по клеткам ленты;
  2. клетка, обозреваемая головкой;
  3. состояние головки.

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

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

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

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

,

где – состояние головки; – буква в обозреваемой головкой клетке; – состояние головки в следующий момент; – буква, записываемая вместо в обозреваемую клетку; – сдвиг к следующему моменту (, или ).

Пример 1. Машина “+1” имеет следующую систему команд:

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

Пример 2. Машина задается системой команд

Эта машина, не изменяя написанного на ленте слова, устанавливает головку против крайнего правого символа слова.

Меняя и , получим машину , выходящую на крайний левый символ слова.

Пример 3. Машина “–1” задается системой команд

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

  1. Композиции машин Тьюринга. Тезис Тьюринга

1. Машина последовательной обработки. Пусть и – машины Тьюринга в одном алфавите. Построим третью машину Тьюринга, работа которой будет равносильна последовательной работе машин и .

Пусть машина имеет множество состояний , а – . Назначим заключительное состояние машины начальным состоянием машины . Определим машину более точно. Пусть она имеет множество состояний , а ее команды получаются из команд машин и следующим образом:

– в командах машины всюду заменим на ;

– в командах машины всюду заменим на.

Такую композицию машин и называют машиной последовательной обработки и обозначают , а также изображают блок-схемой СЛЕДОВАНИЕ (рис. 1).

Рис. 1. Структура СЛЕДОВАНИЕ

Пример 4. Композиция машин “+1” и дает машину, которая после прибавления 1 возвращает головку на правый символ результата. Программа новой машины:

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

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

Для построения такой машины надо выполнить действия:

  1. переобозначить состояния машин и :

, …, ;

, …, ;

  1. заменить в программе машины на , на и добавить к измененному таким образом тексту программы машины программы машин и с переобозначенными состояниями.

Построенная композиция машин , и называется машиной условного перехода и обозначатся блок-схемой РАЗВЕТВЛЕНИЕ (рис. 2).

Если в качестве одной из машин или взять машину , то получим структуру ЦИКЛ (рис. 3).

Рис. 2. Структура РАЗВЕТВЛЕНИЕ Рис. 3. Структура ЦИКЛ

  1. Определение вычислимой функции

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

Функция называется вычислимой, если существует машина Тьюринга такая, что:

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

Обозначим через класс всех вычислимых функций. Очевидно, .

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

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

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

1

ПОНЯТИЕ АЛГОРИТМА. МАШИНЫ ТЬЮРИНГА