8_1 (1019126), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Переход из состояния 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 в первоначальном по­нимании его смысла.

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

Утверждение это весьма сильное. Оно означает не только то, что мы не знаем сейчас соот­ветствующего алгоритма, оно говорит о том, что такого алгоритма мы никогда най­ти не сможем. Долгое время математики считали, что для любой четко сформули­рованной проблемы алгоритм найти можно. Например, Д. Гильберт считал, что в математике не может быть неразрешимых проблем: «In mathematics there is nothing which cannot be known». Его целью в начале XX века было представить математи­ку в виде такой формальной системы, что в ней все проблемы могли бы быть сфор­мулированы в виде утверждений, которые либо истинны, либо ложны, а также най­ти алгоритм, который по заданному утверждению в этой системе мог бы опреде­лить его истинность. Гильберт рассматривал эту проблему как фундаментальную открытую проблему математики.

Характеристики

Список файлов книги