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

Основные понятия

Универсальные алгоритмы

Можно выделить три основных типа универсальных алгоритмических моделей:

1- й тип связывает понятие алгоритма с наиболее традиционными понятями математики – вычислениями и числовыми функциями;

2- й тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент времени лишь весьма примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Кроме того эвристика этих моделей близка к ЭВМ. Основной теоретической моделью этого типа является машина Тьюринга.

3- й тип – это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены куска слова другим словом. Преимущества этого типа – в его максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной природы.

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

До сих пор все вычислительные машины в некотором смысле базируются на идее Тьюринга: их память физически состоит из битов, каждый из которых содержит либо 0 либо 1. Более того, т.н. микропрограммное управление унаследовало от этих абстрактных машин и программу, помещенную в "постоянную память", и в значительной мере структуру команды.

Машина Тьюринга представляет собой автомат, с конечным числом состояний, соединенный с внешней памятью – лентой, разбитой на ячейки, в каждой из которых записан один из символов конечного алфавита А= { a1, ... am}.

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

Данные в машине Т – это слова в алфавите ленты; на ленте записываются и исходные данные и окончательные результаты. Элементарные шаги – это считывание и запись символов, сдвиг головки на ячейку влево или вправо, а также переход управляющего устройства в следующее состояние.

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

а) следующее состояние qi`

б) символ aj`, который надо записать в ту же ячейку вместо aj(стирание – это запись пустого символа )

в) направление сдвига головки dk(L – влево, R – вправо, E – на месте).

Это задание может описываться либо системой правил

qiaj qi`aj`dk

либо таблицей, строкам которой соответствуют состояния, столбцам – входные символы, а на пересечении записана тройка символов qi`aj`dk.

либо блок-схемой (диаграммой переходов), в которой состояниям соотвествуют вершины, а правилу вида (qiaj qi`aj`dk) – ребро, ведущее из qi в qi`.

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

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

qiaj qi`aj`dk,

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

Для того чтобы говорить о том, что могут делать машины Т, уточним как будет интерпретироваться их поведение и как будут представляться данные.

Исходными данными машины Т будем считать записанные на ленте слова в алфавите исходных данных и векторы из таких слов. Для любого набора V над Аисхмашина Т либо работает бесконечно, либо перерабатывает его в совокупность слов в алфавите результатов ( Аисхи Арез могут пересекаться и даже совпадать).

Пусть f – функция, отображающая множество векторов над Аисхв множество векторов над Арез. Машина Т правильно вычисляет функцию f , если

1) для любых V и W таких, что f(V)=W q1V* q1zW* , где V* и W*– правильные записи V, W.

2) для любого V такого, что f(V) не определена, машина Т, запущенная в стандартной начальной конфигурации q1V*, работает бесконечно долго.

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

Пусть f() задана описанием: "если P() истинно, то f()=g1(), иначе f()=g2()". Функция называется разветвлением или условным переходом к g1() и g2() по условию P().

Благодаря вычислимости композиции и разветвления словесные описания и язык блок-схем можно сделать вполне точным языком для описания работы машин Тьюринга.

Cистему команд машин Тьюринга можно интерпретировать и как описание работы конкретного механизма и как программу. Естественно поставить задачу построения машины Тьюринга, реализующей алгоритм воспроизведения работы машины Тьюринга – такая машина называется универсальной. Существование универсальной машины Тьюринга означает, что систему команд любой машины Тьюринга можно представить двояко: либо как описание работы конкретного устройства машины Т, либо как программу для универсальной машины U. Это естетственно: для инженера, проектирующего систему управления, любой алгоритм управления может быть реализован либо аппаратурно – построением соответствующей схемы, либо программно – написанием программы для универсальной управляющей ЭВМ.

Такая интерпретация на абстрактном уровне сохраняет основные плюсы и минусы инженерной реализации: конкретная машина Т работает гораздо быстрее; управляющее устройство U довольно громоздко, однако его величина постоянна и, будучи раз построено, оно годится для реализации сколь угодно больших алгоритмов. Кроме того при смене алгоритма не понадобится строить новых устройств, нужно будет лишь написать новую программу.

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

В числе общих требований, предъявляемых к алгоритмам упоминалось требование результативности. В наиболее радикальном виде: по любому алгоритму А и данным определить, приведет ли работа А при исходных данных к результату или нет. Иначе говоря, нужно построить алгоритм В такой, что В(А,)=И, если А() дает результат, и В(А,)=Л, если нет.

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

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

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