- •1.1. Вычислимые функции, разрешимые и перечислимые множества.
- •1.2. Основные свойства разрешимых и перечислимых множеств (с доказательством).
- •1.3. Теоремы, связывающие понятия вычислимость, разрешимость и перечислимость.
- •Разрешимые множества.
- •Перечислимые множества.
- •1.4. Теорему Поста и теорему о графике вычислимой функции (с доказательством).
- •1.5. Интуитивное понятие алгоритма, исполнитель алгоритма. Основные свойства алгоритма.
- •Свойства алгоритмов:
- •Машина Тьюринга как алгоритмическая модель. Модель Тьюринга (Тьюринга-Поста).
- •Та.2.Алгоритмически неразрешимые проблемы.
- •2.3. Нумерация, натуральная нумерация, однозначная нумерация.
- •2.4. Девятая проблему Гильберта о диофантовых уравнениях.
- •Та.3.Основные меры сложности вычисления
- •3.1.Временная и емкостная сложность.
- •3.2. Нижние и верхние оценки временной сложности.
- •3.3. Эффективность вычислений
- •3.4. Классы сложности (p, exp, np, npc).
Та.2.Алгоритмически неразрешимые проблемы.
2.1. Алгоритмическая неразрешимость
Множество называется неразрешимым, если не существует алгоритма, который по любому определяет, принадлежит ли оно множеству X (обратный к разрешимому).
2.2. Проблема останова (с доказательством).
В теории вычислимости проблема остановки — это проблема разрешимости, которая может неформально быть поставлена в виде: Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки.
Алан Тьюринг доказал в 1936 году, что общий алгоритм для решения проблемы зависания для любых возможных входных данных не может существовать. Мы можем сказать, что проблема зависания неразрешима на машине Тьюринга.
Док-во: Рассмотрим множество S алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество S лексикографически (в словарном порядке), при этом каждый алгоритм получит свой порядковый номер. Назовем Анализатором гипотетический ал-горитм, который получает на вход пару натуральных чисел (N,X), и: останавливается и возвращает 1, если алгоритм с номером N не останавливается, получив на вход X
не останавливается в противном случае (если алгоритм с номером N останавливается, получив на вход X).
Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?
Теорема. Анализатор не существует.
Докажем это от противного. Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число N, передает пару аргументов (N,N) Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не остановливается алгоритм с номером N, получив на вход число N. Пусть K - это порядковый номер Диагонализатора в множестве S. Запустим Диагонализатор, передав ему это число K. Диагонализатор остановится в том и только том случае, если алгоритм с номером K (то есть, он сам) не останавливается, получив на вход число K (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатор не существует, что и требовалось доказать.
2.3. Нумерация, натуральная нумерация, однозначная нумерация.
Напомним, что впервые идея нумерации конструктивных объектов (нечисловой природы) натуральными числами была высказана и реализована К.Гёделем.
Определение.
(1) нумерацией объектов множества E назовём отображение g:Ng®E некоторого множества натуральных чисел NgÍ N на множество конструктивных объектов E.
(2) Однозначной гёделевой нумерацией объектов множества E назовём нумерацию объектов множества E, являющуюся биекцией.
(3) Простой гёделевой нумерацией объектов множества E назовём нумерацию объектов множества E в случае, когда Ng=N.