9.Неразрешимость проблемы остановки.

В теории вычислимости проблема остановки — это проблема разрешимости, которая может неформально быть поставлена в виде:

Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки.

Рассмотрим множество S алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество S лексикографически (в словарном порядке), при этом каждый алгоритм получит свой порядковый номер. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел (N,X), и:

• останавливается и возвращает 1, если алгоритм с номером N не останавливается, получив на вход X

• не останавливается в противном случае (если алгоритм с номером N останавливается, получив на вход X).

Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?

Теорема. Анализатор не существует.

Докажем это от противного. Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число N, передает пару аргументов (N,N) Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не остановливается алгоритм с номером N, получив на вход число N. Пусть K - это порядковый номер Диагонализатора в множестве S. Запустим Диагонализатор, передав ему это число K. Диагонализатор остановится в том и только том случае, если алгоритм с номером K (то есть, он сам) не останавливается, получив на вход число K (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатор не существует, что и требовалось доказать.

10.Другие примеры неразрешимых алгоритмически задач.

В математике проблемой разрешения (Entscheidungsproblem) называется задача, сформулированная Давидом Гильбертом в 1928 году: найти алгоритм, который бы принимал в качестве входных данных описание любой проблемы разрешимости (формального языка и математического утверждения S на этом языке), и после конечного числа шагов останавливался бы и выдавал один из двух ответов: «Истина» или «Ложь», в зависимости от того, истинно или ложно утверждение S. Не требуется, чтобы алгоритм давал какое-либо обоснование своего ответа, однако ответ всегда должен быть верным. Такой алгоритм мог бы, к примеру, определить, истинны ли такие утверждения, как гипотеза Гольдбаха или гипотеза Римана, несмотря на то, что никакого доказательства (или опровержения) этих утверждений пока не известно.

В 1936 — Алонзо Чёрч, а в 1937 — Алан Тьюринг опубликовали работы, в которых показали, что не существует алгоритма для определения истинности утверждений арифметики, а поэтому и более общая проблема разрешения также не имеет решения. Этот результат получил название теорема Чёрча — Тьюринга.

Деся́тая пробле́ма Ги́льберта — одна из 23 задач, которые Давид Гильберт предложил 8 августа 1900 года на II Международном конгрессе математиков. Она состоит в нахождении универсального метода целочисленного решения произвольного алгебраического диофантова уравнения. Доказательство алгоритмической неразрешимости этой задачи заняло около двадцати лет и было завершено Юрием Матиясевичем в 1970 году.

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

Нам потребуется следующий простой результат.

УТВЕРЖДЕНИЕ. Ели функция f(x) вычислима, то вычислима и обратная ей функция.

Доказательство. Пусть M_y - правила машины Тьюринга, которая вычисляет f_y(x).

Возьмем какое-нибудь одно из ее правил, например,

Qi   Qj  L

Читаем: если машина находится в состоянии Qi и читает символ , то она переходит в состояние Qj, записывает вместо  символ  и сдвигает ленту влево.

Перепишем это правило 'в обратную сторону"

Qj   Qi  R

Это правило показывает, как работает машина Тьюринга, вычисляющая обратную функцию для данной вычислимой функции. Таким же образом прямо показывается, что любое правило машины Тьюринга можно заменить "обратным", что доказывает УТВЕРЖДЕНИЕ.

Рассмотрим уравнение f_y(x) = с, где c – положительное целое число, например

2*x=4. Здесь f_y(x) =2*x. Обратная функция есть x=0.5*y. Найти корень уравнения 2*x=4 это то же самое, что ответить на вопрос: останавливается ли на входе y=4 машина, вычисляющая обратную функцию. Таким образом, проблема отыскания корня произвольной вычислимой функции на произвольном входе равносильна проблеме останова, а последняя алгоритмически не разрешима.

В заключение обратимся к знаменитому результату К.Геделя.

Теорема К. Геделя о неполноте формальных систем, содержащих арифметику целых чисел. Существуют истинные недоказуемые формулы.

Общая идея доказательства. Пусть формула (x,y) истинна, если y есть доказательство формулы с номером x. Недоказуемость формулы (x,y) равносильна формуле y((x,y)). По правилам логики последняя формула эквивалентна некоторой формуле (x), в которой y уже не присутствует. Формула (x) утверждает недоказуемость формулы с номером x. Пусть  - номер формулы (x). Тогда () утверждает собственную недоказуемость. Формула () не может быть ложной, поскольку ложные формулы недоказуемы в непротиворечивых системах. Следовательно, она истинна и не доказуема.