Algoritmicheski-nerazreshimye-zadachi

1.

Алгоритмически
неразрешимые задачи
Границы возможного: что вычисления не могут решить в
принципе — и почему это важно знать

2.

Что такое «неразрешимая
задача»?
Интуитивно — это задача, для
которой не существует ни
одного алгоритма,
способного дать ответ для всех
возможных входных данных за
конечное время.
Это не значит, что
задача очень сложная.
Это значит, что её
решение в принципе
невозможно с
помощью алгоритмов
— при любой
вычислительной
мощности.
Сложная задача
Требует много времени
или ресурсов, но
алгоритм существует
Неразрешимая
задача
Алгоритм не существует в
принципе — ни быстрый,
ни медленный

3.

Проблема остановки: фундаментальный пример
Существует ли алгоритм, который для любой программы и
любых входных данных может определить — остановится ли
программа когда-нибудь, или будет работать вечно?
Алан Тьюринг в 1936 году доказал: такого алгоритма не
существует. Доказательство строится на методе самоприменения
и приводит к неустранимому противоречию — парадоксу,
похожему на «парадокс лжеца».

4.

Машина Тьюринга и
бесконечный цикл
Запуск
программы
Анализатор
предсказыва
ет
Противоречи
е
Ключевая идея доказательства Тьюринга: если бы такой
«анализатор» существовал, его можно было бы применить к
самому себе — и получить логическое противоречие. Значит,
он не может существовать.

5.

Почему проблема остановки так важна?
Если бы она была разрешима, мы могли бы автоматически проверять многие нерешённые математические гипот
Великая теорема
Ферма
Гипотеза Гольдбаха
Автоматически доказать
каждое чётное число > 2
Всегда ли
или опровергнуть
есть сумма двух простых
последовательность
Проверить, верно ли, что
Гипотеза Коллатца
(3n+1)
утверждение о целых
приходит к единице?
степенях
Ответ до сих пор
неизвестен
Неразрешимость проблемы остановки означает: не все математические вопросы поддаются
алгоритмическому исследованию.

6.

Другие примеры неразрешимых задач
1
2
3
Эквивалентность
машин Тьюринга
Проблема соответствия
Поста
Десятая проблема
Гильберта
Невозможно определить,
Нельзя алгоритмически
Доказано неразрешимой в
дают ли две произвольные
решить, существует ли
1970 г. Матиясевичем: нет
машины Тьюринга
совпадение в заданной
алгоритма для нахождения
одинаковый результат для
системе пар строк
целых корней
всех входных данных
произвольного диофантова
уравнения

7.

Границы
вычислений
Существуют вопросы, которые никакой компьютер не
решит — не потому что мал, а потому что математика
запрещает это в принципе.

8.

Значение неразрешимости для науки и технологий