8_1
.docКакая именно команда программы будет выполняться в данный момент, определяется двумя параметрами: читаемым головкой символом и состоянием машины.
Результатами выполнения команды являются: новый символ записанный на ленту в ту ячейку, напротив которой находится в данный момент головка; перемещение головки на одну позицию (ячейку) вправо или влево вдоль ленты; переход машины в новое состояние. В частных случаях новый символ может быть равен старому, перемещение может отсутствовать, состояние может остаться прежним.
Формат команды имеет следующий вид:
a q b r D,
где а — читаемый символ; q — текущее состояние; b — символ записываемый в обозреваемую ячейку ленты вместо символа а; r — новое состояние; D — направление движения головки машины относительно ленты.
Символы выбираются из конечного алфавита А = {а1, . . . , a1}.
В дальнейшем будем использовать трехсимвольный алфавит {е 0, 1}, причем е будет означать «пустой (empty)» символ — отсутствие информации в ячейке, а с помощью нуля и единицы будут кодироваться все данные. Иногда используют двухсимвольный алфавит А = {е, 1}. В этом случае числа кодируются только единицами: нуль кодируется одной единицей, число один кодируется двумя единицами, а число х кодируется х + 1 единицами Это — единичная система счисления. Однако она плоха с точки зрения сложности задач (см. гл. 5).
Множество состояний обозначим Q= { q1, . . . , qk}. Направление движения D выбирается из множества {L, R, S} где L — движение влево, R — движение вправо, S — отсутствие лви жения.
Таким образом, команда 1 q3 0 q6 L означает: если, находясь в состоянии q3, машина Тьюринга обозревает ячейку ленты в которой записана 1, то машина должна записать в эту ячейку 0, произвести сдвиг головки относительно ленты влево на одну ячейку и перейти в состояние q6.
Это описание действия, соответствующего команде говорит о том, что команда может рассматриваться как отображение пар (a, q) в тройки (b, r, D), т. е. отображение
AxQ=> AxQx {L, R, S}.
Данное отображение является частичным, так как не для любой пары-аргумента существует тройка-результат. Но для произвольной пары существует не более одной тройки, т. е. отображение не является многозначным.
Все действия производятся в дискретном времени. Иначе говоря, можно рассматривать целочисленные моменты времени t = = 0, 1, 2, 3, ... Любое изменение происходит мгновенно в момент t = i и ничего не меняется между двумя соседними моментами времени.
Работает машина Тьюринга следующим образом. Стартовая конфигурация: на ленте находятся исходные данные — строка символов в алфавите А, состояние внутренней памяти соответствует некоторому оговоренному (всегда одному и тому же) начальному состоянию, например, q1. При этом головка машины обозревает некоторую ячейку ленты с записанным там символом а. Нормальным считается начальное положение головки напротив самого левого непустого символа, т. е. не совпадающего с е.
Момент старта рассматривается как нулевой момент времени. В момент старта выполняется первая команда, это единственная команда, начинающаяся с пары (a, q1). В результате выполнения команды машина перейдет в новое состояние, и головка машины прочтет новый символ с ленты. Эта пара (новый символ, новое состояние) станет начальной частью следующей команды и т. д. Машина будет продолжать работать в дискретном времени, шаг за шагом переходя из состояния в состояние, и постепенно изменяя содержимое ленты. Наконец, для некоторой пары (a, q) не окажется команды в программе. Такая ситуация считается завершающей. Машина прекращает функционирование. Оставшаяся запись на ленте считается записью результата.
Таким образом, машина Тьюринга реализует вычисление некоторой функции — отображения исходной строки символов в результирующую строку.
Существует несколько способов представления программы машины Тьюринга (множества команд). Два наиболее употребительных:
-
двумерная таблица (рис. 1.2);
-
диаграмма (нагруженный псевдограф).
В двумерной таблице строки помечаются различными символами алфавита, а столбцы — именами различных состояний машины, т. е. таблица имеет размер Ik. Каждой команде программы
Состояние Символ |
q1 |
… |
q |
… |
qk |
a1 |
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
brD |
|
|
… |
|
|
|
|
|
a1 |
|
|
|
|
|
Рис. 1.2. Табличная форма программы машины Тьюринга
соответствует единственная клетка в таблице. Она определяется для команды aqbrD следующим образом: в клетку, находящуюся на пересечении строки, помеченной символом я, и столбца помеченного состоянием q. вписывается тройка b r D.
Для некоторых пар (а, q) в программе нет команд, следовательно, соответствующие клетки таблицы остаются пустыми. При достижении в процессе работы пустой клетки машина Тьюринга останавливается.
В качестве простого примера приведем программу вычисления функции S(x) = x + 1, т. е. увеличение аргумента на единицу (рис. 1.3). Используем алфавит A = {e, 0, 1}, причем x будем кодировать последовательностью нулей и единиц так. как это принято при двоичном кодировании целых неотрицательных чисел.
предположим также, что в момент старта головка машины Тьюринга находится напротив крайней левой ячейки с символом 1.
-
q1
q2
q3
q4
0
0q1R
1q3L
0q3L
1
1q1R
0q2L
1q3L
e
eq2L
1q4S
eq4R
Р и с. 1.3. Программа машины Тьюринга для вычисления функции S(x)=x+1
Первая выполняемая команда —1q11q1R оставляет 1 в ячейке ленты, оставляет неизменным состояние q1 и производит сдвиг головки вправо по ленте. В новой читаемой ячейке может оказаться любой из трех символов алфавита. Если это 0 или 1, то производится дальнейшее движение вправо до окончания кода числа х. Если же встретится символ е, то это будет означать, что код числа закончился и головка находится справа от младшей цифры кода числа. После этого, собственно, и начинается процесс прибавления единицы. Если младшая цифра — 0 то достаточно заменить се на 1 (команда 0 q2 1 q3 L) и начать обратное движение к исходной позиции. Если младшая цифра — 1 то результатом в данной ячейке будет 0 (сложение по mod 2), и единица перейдет в следующий по старшинству разряд (влево). Процесс распространения переноса может закончиться где-то внутри кода числа и тогда необходимо осуществить «прокрутку» ленты так, чтобы машина остановилась на крайней левой единице кода результата (x+1)
Второй пример - программа вычисления функции Z(x) = 0(x) = 0, превращающей запись любого аргумента. x в запись нуля (рис. 1.4). Эта программа стирает с ленты код x, т. е. запол
-
q1
q2
0
eq1R
1
eq1R
е
0q2R
P 11 с. 1.4. Программа машины Тьюринга для вычисления функции 0(x) = 0
няет клетки символом е и перед остановкой записывает в текущую клетку 0.
Более длинная программа получается для вычисления функции Inm (x1,x2, … , xn) выбирающей m-й аргумент из последовательности п аргументов, 1 m n, Inm (х1, х2, ... ,xn)=xm (рис. 1.5).
Представление последовательности п аргументов зададим на ленте в виде записанных один за другим через разделитель — пустую клетку е — двоичных кодов хi. Программа, написанная для конкретного значения т, действует следующим образом. Сначала стирается (заменяется на е ...е) первый аргумент, затем стирается второй, ..., стирается (т - 1)-й; затем подтверждается т-й аргумент; затем стираются оставшиеся аргументы.
|
q1 |
q2 |
… |
qm-1 |
qm |
qm+1 |
… |
qn |
qn+1 |
0 |
eq1R |
eq2R |
… |
eqm-1R |
0qmR |
eqm+1R |
|
eqnR |
|
1 |
eq1R |
eq2R |
… |
eqm-1R |
1qmR |
eqm+1R |
|
eqnR |
|
е |
eq2R |
eq3R |
… |
eqmR |
eqm+1R |
eqm+2R |
|
eqn+1R |
|
Рис. 1.5. Программа машины Тьюринга для вычисления функции
Inm(x1, x2, … , xn)
Другой способ представления программы машины Тьюринга — диаграмма (рис. 1.6).
Диаграмма представляет собой геометрический объект, состоящий из вершин (обозначаемых точками или окружностями) и дуг (рисуемых в виде направленных отрезков прямой со стрелкой на одном из концов или в виде отрезков несамопсресекаю-щихся кривых). Каждой вершине приписывается состояние машины Тьюринга: таким образом вершин в диаграмме ровно столько, сколько имеется состояний. Дуге, соединяющей две вершины qi и qj, приписывается некоторый символ а алфавита А и двойка b D так, что запись a qi b qj D образует команду программы машины Тьюринга.
Дуга (стрелка) символизирует переход из состояния qi в состояние qj при условии, что головка читает символ а. Одновременно с этим символ а заменяется на символ b и совершается движение D. По этой причине диаграмму называют диаграммой (графом) переходов.
Рис. 1.6. Элемент диаграммы. Рис. 1.7. Диаграмма машины
Переход из состояния qi, в состояние qj Тьюринга
Программа вычисления Z(x) = О может быть изображена диаграммой, изображенной на рис. 1.7.
Алан Тьюринг сформулировал тезис, связывающий понятие алгоритма и машины: «Для всякого (неформального) алгоритма может быть построен Тьюрингов алгоритм (программа машины Тьюринга), дающий при одинаковых исходных данных тот же результат».
Это недоказуемое математическими методами утверждение играет важную роль при проектировании программного обеспечения, особенно на начальных этапах проектирования. Первоначальная постановка задачи зачастую является словесной, неформальной. Если ее решение удается описать в виде конечной последовательности шагов, каждый из которых достаточно прост, то в соответствии с Тезисом Тьюринга это означает, что может быть написана программа на каком-либо алгоритмическом языке, решающая поставленную задачу.
Композиции машин Тьюринга
Пусть поставлена вычислительная задача, которую сумели разбить на части. Более того, для решения каждой из частей задачи предоставлены соответствующие машины Тьюринга. Как организовать совместную работу этих машин для решения полной задачи? Ответ на вопрос заключается во введении некоторых операций над машинами Тьюринга, которые называются композициями машин.
Первая композиция — последовательное соединение машин.
Пусть даны две программы машины Тьюринга. Первая получает на ленте исходные данные и начинает работу. После конечного числа шагов попытка выбрать из таблицы (программы) очередную команду заканчивается безрезультатно — соответствующая клетка таблицы пуста. Первая программа должна остановиться, на ленте остается некоторое число — значение вычисленной функции. Но в этот момент начинает работать вторая программа, заданная другой таблицей и использующая результат
работы первой программы в качестве исходных данных. Через конечное число шагов вторая программа завершает свою работу, оставив на ленте результат последовательного выполнения двух программ. .
Для организации такой работы достаточно построить объединенную таблицу машины Тьюринга, приписав к первой таблице вторую (справа) и заполнив пустые клетки первой таблицы командой i p1 S — командой перехода к первому (начальному) состоянию p1, второй программы; здесь i — буква алфавита, соответствующая строке, в которой находится пустая клетка.
Второй вид композиции — итерация (повторение) машины Тьюринга.
В этом случае повторяем выполнение одной и той же программы конечное число раз. По окончании первого выполнения на ленте остается промежуточный результат, который является исходными данными для второго выполнения и т. д Для обеспечения второго и последующих выполнений необходимо в некоторые пустые клетки таблицы вписать команду перехода на начало: i qi S. Во все пустые клетки эту команду вписать нельзя, так как измененная таким образом программа не сможет заканчиваться.
Итерация машины Тьюринга соответствует конструкциям циклов в языках программирования.
8.3 Тезис Черча. Алгоритмически неразрешимые проблемы.
Словосочетание «решить задачу» допускает множество толкований. В математике иногда решают задачи с привлечением интуиции путем озарения: решение возникает вдруг и остается только проверить его правильность. Будем рассматривать решения с позиции алгоритмической: задача может быть решена, если построен алгоритм, приводящий к результату — решению задачи. Если сумеем для некоторой задачи построить алгоритм, ее решающий, то будем говорить, что задача алгоритмически разрешима. Но даже если не построили алгоритм, а только каким-либо математическим методом доказали, что алгоритм может быть построен, то и тогда будем считать задачу алгоритмически разрешимой. Во многих случаях алгоритм без труда или с большим трудом может быть найден. Но что означает ситуация, когда не удалось найти необходимый алгоритм?
Долгое время математики были уверены, что любая задача в конце концов может быть решена, нужно лишь приложить адекватные усилия. Составлялись перечни еще не решенных задач, чтобы обратить внимание коллег на необходимость «выровнять фронт» исследований в той или иной области математики. Наиболее известен в истории математики один из таких призывов, сделанный 8 августа 1900 г. Д. Гильбертом на Международном Конгрессе математиков в Париже.
Это убеждение в разрешимости каждой математической проблемы является для нас большим подспорьем в работе; мы слышим внутри себя постоянный призыв: вот проблема, ищи решение. Ты можешь найти его с помощью чистого мышления; ибо в математике не существует Ignorabimus (мы не будем знать)!»
Затем Гильберт перечисляет и анализирует 23 открытых,проблемы. Для нас наиболее интересна 10-я проблема.
Задача о разрешимости диофантова уравнения
Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах.
Диофантовы уравнения (названы в память греческого математика Диофанта, жившего в III в. н. э.) имеют вид
Р(х1,х2, .... хn) = Q(x1,x2, .... хn), где Р и Q — полиномы, например:
aх2 + bх + с = у2; ахn+ byn = czn; ax3 + bx2y + сху2 + dy3 = 1.
где коэффициенты а, b, с и степень п — целые числа; решения — значения х, у, z — также должны быть целыми числами.
Конечно, решения не всегда существуют: вспомним хотя бы известную теорему Ферма о том, что уравнение хn + уn = zn, п > 2, не имеет целочисленных решений. Теорема была сформулирована Пьером де Ферма в середине XVII в. без доказательства и доказана Э. Уайлсом в 1995 г.
Если вспомнить высказывания Гильберта в начале доклада, то можно предположить, что он считал «способ» существующим, который рано или поздно будет найден. Точного понятия алгоритма в то время еще не существовало, но в современной терминологии десятую проблему можно сформулировать так: «Построить алгоритм, который получает на входе строку символов — запись уравнения с конкретными целочисленными коэффициентами и показателями степени — и выдает ответ «ДА», если решение уравнения существует, или «НЕТ», если уравнение не имеет решения». При этом сам алгоритм — универсален, т. е. его текст не зависит от конкретных входных данных (обычное свойство массовости алгоритма).
Для машин Тьюринга был задан вопрос: Всякий ли неформально описанный алгоритм может быть реализован некоторой машиной Тьюринга? Ответом был тезис Тьюринга. Аналогичный вопрос может быть задан в отношении частично рекурсивной функции. Ответом был тезис Черча, который показал связь рекурсивных функций с машинами Тьюринга. Следует заметить, что исторически тезис Черча был сформулирован раньше тезиса Тьюринга.
Понятие частично-рекурсивной функции оказалось исчерпывающей формализацией понятия вычислимой функции. Это обстоятельство выражено в виде тезиса Черна, являющегося аналогом 1 тезиса Тьюринга для рекурсивных функций: всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивна.
Из сопоставления двух тезисов вытекает утверждение: финкция вычислима машиной Тьюринга тогда и только тогда когда она частично-рекурсивна. Это утверждение об эквивалентности двух алгоритмических моделей является (в отличие от тезисов) вполне точным математическим утверждением и, следовательно, должно быть доказано. Дан доказательства разобьем его на две теоремы.
Теорема 1. Всякая частично-рекурсивная функция вычислима на машине Тьюринга.
План доказательства ясен: сначала доказывается, что простейшие функции вычислимы (это довольно очевидно), а затем это операторы суперпозиции, примитивной рекурсии и -оператор сохраняют вычислимость.
Теорема 2 Всякая функция, вычислимая на машине Тьюринга, частично рекурсивна.
Итак, всякий алгоритм, описанный в терминах частично-рекурсивных функций, можно реализовать машиной Тьюринга, и наоборот. Отсюда следует, что любые утверждения о существовании или несуществовании алгоритмов, сделанные в одной из этих теорий, верны и в другой. В сочетании с тезисом Черча—Тьюринга это означает, что такие, утверждения можно формулировать для алгоритмов вообще, не фиксируя конкретную модель и используя результаты обеих теорий. Таким образом, возможно изложение теории алгоритмов, инвариантное по отношению к способу формализации понятия «алгоритм», — при любой формализации основные свойства алгоритмов остаются теми же самыми. Основные понятия такой инвариантной теории (будем называть ее общей теорией алгоритмов)—это алгоритм (рекурсивное описание функции, система команд машины Тьюринга или описание в какой-либо другой модели; считается, что выбрана какая-то модель, но какая именно — неважно) и вычислимая функция. Функция называется вычислимой, если существует вычисляющий ее алгоритм. При этом несущественно, числовая функция это или нет. Термин «общерекурсивная функция», употребленный в инвариантном смысле, является синонимом термина 0«всюду определенная вычислимая функция».
Эквивалентность утверждений «функция f вычислима» и «существует алгоритм, вычисляющий функцию f» иногда приводит к смешению понятий алгоритма и вычислимой функции; в частности, говоря о рекурсивной функции, часто имеют в виду ее конкретное рекурсивное описание. В действительности же различие между вычислимой функцией и алгоритмом — это различие между функцией и способом ее задания. Без соблюдения этих различий невозможна корректная интерпретация некоторых важных результатов теории алгоритмов. В то же время традиция изложения теории алгоритмов позволяет не различать понятия алгоритма и функции в тех случаях, когда-то не приводит к путанице.
Если нам не удается найти решение математической проблемы, то часто причина этого заключается в том, что мы не овладели еще достаточно общей точкой зрения, с которой рассматриваемая проблема представляется лишь отдельным звеном в цепи родственных проблем. Отыскав эту точку зрения, мы часто не только делаем более доступной для исследования данную проблему, но и овладеваем методом, применимым и к родственным проблемам<... >
Этот удивительный факт наряду с другими философскими основаниями создает у нас уверенность, которую разделяет, несомненно, каждый математик, но которую до сих пор никто не подтвердил доказательствами, — уверенность в том, что каждая определенная математическая проблема непременно должна быть доступна строгому решению или в том смысле, что удается получить ответ на поставленный вопрос, или же в том смысле, что будет установлена невозможность ее решения и вместе с тем доказана неизбежность неудачи всех попыток ее решить<...>
Является ли эта аксиома разрешимости каждой данной проблемы характерной особенностью только математического мышления или, быть может, имеет место общий, относящийся к внутренней сущности нашего разума закон, по которому все вопросы, которые он ставит, способны быть им разрешимы? Встречаются ведь в других областях знания старые проблемы, которые были самым удовлетворительным образом и к величайшей пользе науки разрешены путем доказательства невозможности их решения. Я вспоминаю проблему о perpetuum mobile (вечный двигатель). После напрасных попыток конструирования вечного двигателя стали, наоборот, исследовать соотношения, которые должны существовать между силами природы в предположении, что perpetuum mobile невозможно. И эта постановка обратной задачи привела к открытию закона сохранения энергии, из которой и вытекает невозможность perpetuum mobile в первоначальном понимании его смысла.