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

Файл №1019126 8_1 (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004) 2 страница8_1 (1019126) страница 22017-07-08СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Р(х12, .... хn) = Q(x1,x2, .... хn), где Р и Q — полиномы, например:

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 (вечный двигатель). После напрасных попыток конструирования вечного двигателя стали, наоборот, исследовать соотношения, которые должны су­ществовать между силами природы в предположении, что perpe­tuum mobile невозможно. И эта постановка обратной задачи при­вела к открытию закона сохранения энергии, из которой и вытекает невозможность perpetuum mobile в первоначальном по­нимании его смысла.

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

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

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

Тип файла
Документ
Размер
163,5 Kb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее