8_1

Какая именно команда программы будет выполняться в данный момент, определяется двумя параметрами: читаемым голов­кой символом и состоянием машины.

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

Формат команды имеет следующий вид:

a q b r D,

где а — читаемый символ; q — текущее состояние; b — символ за­писываемый в обозреваемую ячейку ленты вместо символа а; r — новое состояние; D — направление движения головки машины от­носительно ленты.

Символы выбираются из конечного алфавита А = {а₁, . . . , a₁}.

В дальнейшем будем использовать трехсимвольный алфавит {е 0, 1}, причем е будет означать «пустой (empty)» символ — отсут­ствие информации в ячейке, а с помощью нуля и единицы будут кодироваться все данные. Иногда используют двухсимвольный алфавит А = {е, 1}. В этом случае числа кодируются только еди­ницами: нуль кодируется одной единицей, число один кодируется двумя единицами, а число х кодируется х + 1 единицами Это — единичная система счисления. Однако она плоха с точки зрения сложности задач (см. гл. 5).

Множество состояний обозначим Q= { q₁, . . . , q_k}. Направ­ление движения D выбирается из множества {L, R, S} где L — движение влево, R — движение вправо, S — отсутствие лви жения.

Таким образом, команда 1 q₃ 0 q₆ L означает: если, находясь в состоянии q₃, машина Тьюринга обозревает ячейку ленты в ко­торой записана 1, то машина должна записать в эту ячейку 0, произвести сдвиг головки относительно ленты влево на одну ячейку и перейти в состояние q₆.

Это описание действия, соответствующего команде говорит о том, что команда может рассматриваться как отображение пар (a, q) в тройки (b, r, D), т. е. отображение

AxQ=> AxQx {L, R, S}.

Данное отображение является частичным, так как не для любой пары-аргумента существует тройка-результат. Но для произ­вольной пары существует не более одной тройки, т. е. отображе­ние не является многозначным.

Все действия производятся в дискретном времени. Иначе го­воря, можно рассматривать целочисленные моменты времени t = = 0, 1, 2, 3, ... Любое изменение происходит мгновенно в момент t = i и ничего не меняется между двумя соседними моментами времени.

Работает машина Тьюринга следующим образом. Стартовая конфигурация: на ленте находятся исходные данные — строка символов в алфавите А, состояние внутренней памяти соответст­вует некоторому оговоренному (всегда одному и тому же) нача­льному состоянию, например, q₁. При этом головка машины обо­зревает некоторую ячейку ленты с записанным там символом а. Нормальным считается начальное положение головки напротив самого левого непустого символа, т. е. не совпадающего с е.

Момент старта рассматривается как нулевой момент времени. В момент старта выполняется первая команда, это единственная команда, начинающаяся с пары (a, q₁). В результате выполнения команды машина перейдет в новое состояние, и головка машины прочтет новый символ с ленты. Эта пара (новый символ, новое состояние) станет начальной частью следующей команды и т. д. Машина будет продолжать работать в дискретном времени, шаг за шагом переходя из состояния в состояние, и постепенно изме­няя содержимое ленты. Наконец, для некоторой пары (a, q) не окажется команды в программе. Такая ситуация считается завер­шающей. Машина прекращает функционирование. Оставшаяся запись на ленте считается записью результата.

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

Существует несколько способов представления программы машины Тьюринга (множества команд). Два наиболее употреби­тельных:

1. двумерная таблица (рис. 1.2);

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

Первая выполняемая команда —1q₁1q₁R оставляет 1 в ячей­ке ленты, оставляет неизменным состояние q₁ и производит сдвиг головки вправо по ленте. В новой читаемой ячейке может оказа­ться любой из трех символов алфавита. Если это 0 или 1, то про­изводится дальнейшее движение вправо до окончания кода числа х. Если же встретится символ е, то это будет означать, что код числа закончился и головка находится справа от младшей цифры кода числа. После этого, собственно, и начинается процесс при­бавления единицы. Если младшая цифра — 0 то достаточно за­менить се на 1 (команда 0 q₂ 1 q₃ 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.

Более длинная программа получается для вычисления функции Iⁿ_m (x₁,x₂, … , x_n) выбирающей m-й аргумент из последовательно­сти п аргументов, 1  m  n, Iⁿ_m (х₁, х₂, ... ,x_n)=x_m (рис. 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. Программа машины Тьюринга для вычисления функции

Iⁿ_m(x₁, x₂, … , x_n)

Другой способ представления программы машины Тьюрин­га — диаграмма (рис. 1.6).

Диаграмма представляет собой геометрический объект, со­стоящий из вершин (обозначаемых точками или окружностями) и дуг (рисуемых в виде направленных отрезков прямой со стрел­кой на одном из концов или в виде отрезков несамопсресекаю-щихся кривых). Каждой вершине приписывается состояние ма­шины Тьюринга: таким образом вершин в диаграмме ровно столько, сколько имеется состояний. Дуге, соединяющей две вер­шины q_i и q_j, приписывается некоторый символ а алфавита А и двойка b D так, что запись a q_i b q_j D образует команду програм­мы машины Тьюринга.

Дуга (стрелка) символизирует переход из состояния q_i в состо­яние q_j при условии, что головка читает символ а. Одновременно с этим символ а заменяется на символ b и совершается движение D. По этой причине диаграмму называют диаграммой (графом) переходов.

Рис. 1.6. Элемент диаграммы. Рис. 1.7. Диаграмма машины

Переход из состояния q_i, в состояние q_j Тьюринга

Программа вычисления Z(x) = О может быть изображена диа­граммой, изображенной на рис. 1.7.

Алан Тьюринг сформулировал тезис, связывающий понятие алгоритма и машины: «Для всякого (неформального) алгоритма может быть построен Тьюрингов алгоритм (программа машины Тьюринга), дающий при одинаковых исходных данных тот же ре­зультат».

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

Композиции машин Тьюринга

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

Первая композиция — последовательное соединение машин.

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

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

Для организации такой работы достаточно построить объе­диненную таблицу машины Тьюринга, приписав к первой табли­це вторую (справа) и заполнив пустые клетки первой таблицы командой i p₁ S — командой перехода к первому (начальному) состоянию p₁, второй программы; здесь i — буква алфавита, соот­ветствующая строке, в которой находится пустая клетка.

Второй вид композиции — итерация (повторение) машины Тьюринга.

В этом случае повторяем выполнение одной и той же программы конечное число раз. По окончании первого вы­полнения на ленте остается промежуточный результат, который является исходными данными для второго выполнения и т. д Для обеспечения второго и последующих выполнений необходи­мо в некоторые пустые клетки таблицы вписать команду пе­рехода на начало: i q_i S. Во все пустые клетки эту команду впи­сать нельзя, так как измененная таким образом программа не сможет заканчиваться.

Итерация машины Тьюринга соответствует конструкциям циклов в языках программирования.

8.3 Тезис Черча. Алгоритмически неразрешимые проблемы.

Словосочетание «решить задачу» допускает множество толкований. В математике иногда решают задачи с привлече­нием интуиции путем озарения: решение возникает вдруг и остается только проверить его правильность. Будем рассмат­ривать решения с позиции алгоритмической: задача может быть решена, если построен алгоритм, приводящий к результа­ту — решению задачи. Если сумеем для некоторой задачи по­строить алгоритм, ее решающий, то будем говорить, что зада­ча алгоритмически разрешима. Но даже если не построили алгоритм, а только каким-либо математическим методом дока­зали, что алгоритм может быть построен, то и тогда будем счи­тать задачу алгоритмически разрешимой. Во многих случаях алгоритм без труда или с большим трудом может быть найден. Но что означает ситуация, когда не удалось найти необходи­мый алгоритм?

Долгое время математики были уверены, что любая задача в конце концов может быть решена, нужно лишь приложить адек­ватные усилия. Составлялись перечни еще не решенных задач, чтобы обратить внимание коллег на необходимость «выровнять фронт» исследований в той или иной области математики. Наи­более известен в истории математики один из таких призывов, сделанный 8 августа 1900 г. Д. Гильбертом на Международном Конгрессе математиков в Париже.

Это убеждение в разрешимости каждой математической проблемы является для нас большим подспорьем в работе; мы слышим внутри себя постоянный призыв: вот проблема, ищи ре­шение. Ты можешь найти его с помощью чистого мышления; ибо в математике не существует Ignorabimus (мы не будем знать)!»

Затем Гильберт перечисляет и анализирует 23 открытых,проблемы. Для нас наиболее интересна 10-я проблема.

Задача о разрешимости диофантова уравнения

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

Диофантовы уравнения (названы в память греческого мате­матика Диофанта, жившего в III в. н. э.) имеют вид

Р(х₁,х₂, .... х_n) = Q(x₁,x₂, .... х_n), где Р и Q — полиномы, например:

aх² + bх + с = у²; ахⁿ+ byⁿ = czⁿ; ax³ + bx²y + сху² + dy³ = 1.

где коэффициенты а, b, с и степень п — целые числа; решения — значения х, у, z — также должны быть целыми числами.

Конечно, решения не всегда существуют: вспомним хотя бы известную теорему Ферма о том, что уравнение хⁿ + уⁿ = zⁿ, п > 2, не имеет целочисленных решений. Теорема была сформулирова­на Пьером де Ферма в середине XVII в. без доказательства и до­казана Э. Уайлсом в 1995 г.

Если вспомнить высказывания Гильберта в начале доклада, то можно предположить, что он считал «способ» существующим, который рано или поздно будет найден. Точного понятия алго­ритма в то время еще не существовало, но в современной терми­нологии десятую проблему можно сформулировать так: «По­строить алгоритм, который получает на входе строку символов — запись уравнения с конкретными целочисленными коэф­фициентами и показателями степени — и выдает ответ «ДА», если решение уравнения существует, или «НЕТ», если уравнение не имеет решения». При этом сам алгоритм — универсален, т. е. его текст не зависит от конкретных входных данных (обычное свой­ство массовости алгоритма).

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

Понятие частично-рекурсивной функции оказа­лось исчерпывающей формализацией понятия вычислимой функции. Это обстоятельство выражено в виде тезиса Черна, являющегося аналогом ¹ тезиса Тьюринга для рекурсивных функций: всякая функция, вычислимая неко­торым алгоритмом, частично-рекурсивна.

Из сопоставления двух тезисов вытекает утверждение: финкция вычислима машиной Тьюринга тогда и только тог­да когда она частично-рекурсивна. Это утверждение об эк­вивалентности двух алгоритмических моделей является (в отличие от тезисов) вполне точным математическим утверждением и, следовательно, должно быть доказано. Дан доказательства разобьем его на две теоремы.

Теорема 1. Всякая частично-рекурсивная функция вы­числима на машине Тьюринга.

План доказательства ясен: сначала доказывается, что простейшие функции вычислимы (это довольно очевидно), а затем это операторы суперпозиции, примитивной рекур­сии и -оператор сохраняют вычислимость.

Теорема 2 Всякая функция, вычислимая на машине Тьюринга, частично рекурсивна.

Итак, всякий алгоритм, описанный в терминах частич­но-рекурсивных функций, можно реализовать машиной Тьюринга, и наоборот. Отсюда следует, что любые утверж­дения о существовании или несуществовании алгоритмов, сделанные в одной из этих теорий, верны и в другой. В со­четании с тезисом Черча—Тьюринга это означает, что та­кие, утверждения можно формулировать для алгоритмов во­обще, не фиксируя конкретную модель и используя резуль­таты обеих теорий. Таким образом, возможно изложение теории алгоритмов, инвариантное по отношению к способу формализации понятия «алгоритм», — при любой форма­лизации основные свойства алгоритмов остаются теми же самыми. Основные понятия такой инвариантной теории (будем называть ее общей теорией алгоритмов)—это алго­ритм (рекурсивное описание функции, система команд ма­шины Тьюринга или описание в какой-либо другой модели; считается, что выбрана какая-то модель, но какая имен­но — неважно) и вычислимая функция. Функция называ­ется вычислимой, если существует вычисляющий ее алго­ритм. При этом несущественно, числовая функция это или нет. Термин «общерекурсивная функция», употребленный в инвариантном смысле, является синонимом термина ₀«всюду определенная вычислимая функция».

Эквивалентность утверждений «функция f вычислима» и «существует алгоритм, вычисляющий функцию f» иногда приводит к смешению понятий алгоритма и вычислимой функции; в частности, говоря о рекурсивной функции, часто имеют в виду ее конкретное рекурсивное описание. В дей­ствительности же различие между вычислимой функцией и алгоритмом — это различие между функцией и способом ее задания. Без соблюдения этих различий невозможна корректная интерпретация некоторых важных результатов теории алгоритмов. В то же время традиция изложения тео­рии алгоритмов позволяет не различать понятия алгоритма и функции в тех случаях, когда-то не приводит к путанице.

Если нам не удается найти решение математической пробле­мы, то часто причина этого заключается в том, что мы не овладе­ли еще достаточно общей точкой зрения, с которой рассматрива­емая проблема представляется лишь отдельным звеном в цепи родственных проблем. Отыскав эту точку зрения, мы часто не то­лько делаем более доступной для исследования данную пробле­му, но и овладеваем методом, применимым и к родственным проблемам<... >

Этот удивительный факт наряду с другими философскими основаниями создает у нас уверенность, которую разделяет, несо­мненно, каждый математик, но которую до сих пор никто не под­твердил доказательствами, — уверенность в том, что каждая определенная математическая проблема непременно должна быть доступна строгому решению или в том смысле, что удается полу­чить ответ на поставленный вопрос, или же в том смысле, что будет установлена невозможность ее решения и вместе с тем до­казана неизбежность неудачи всех попыток ее решить<...>

Является ли эта аксиома разрешимости каждой данной проб­лемы характерной особенностью только математического мыш­ления или, быть может, имеет место общий, относящийся к внут­ренней сущности нашего разума закон, по которому все вопросы, которые он ставит, способны быть им разрешимы? Встречаются ведь в других областях знания старые проблемы, которые были самым удовлетворительным образом и к величайшей пользе нау­ки разрешены путем доказательства невозможности их решения. Я вспоминаю проблему о perpetuum mobile (вечный двигатель). После напрасных попыток конструирования вечного двигателя стали, наоборот, исследовать соотношения, которые должны су­ществовать между силами природы в предположении, что perpe­tuum mobile невозможно. И эта постановка обратной задачи при­вела к открытию закона сохранения энергии, из которой и вытекает невозможность perpetuum mobile в первоначальном по­нимании его смысла.