Проблема алгоритмической разрешимости в математике. 2. Основатели теории алгоритмов – Клини, Черч, Пост, Тьюринг

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

Следует отметить, что невозможность найти для теории общий разрешающий метод не исключает поиска процедуры разрешения для отдельных классов её утверждений. Неразрешимость проблемы означает лишь отсутствие единого метода, хотя в каждом конкретном случае её можно пытаться решать, если решение не претендует на слишком большую общность. В последнее время выявилось общее свойство частных решений неразрешимых проблем: по мере расширения класса решаемых задач сложность методов с некоторого момента быстро растёт, а эффективность столь же быстро убывает. Точно так же результат о достаточно простой разрешимости проблемы может оказаться дезориентирующим, если эта достаточная простота достигается лишь на очень больших объектах, а для малых всё равно приходится практически действовать перебором.

Сведение к неразрешимым проблемам стало столь же мощным методом установления некорректности задач либо решений, каким является в физике сведение к возможности построить вечный двигатель. Неразрешимость проблемы разложения числа на простые множители достаточно простым алгоритмом стала основой современной теории надёжных индивидуальных шифров. Одним из методов решения неразрешимых проблем является переход к вероятностным алгоритмам разрешения и к квантовым вычислениям. Показано, что для многих переборных задач есть быстрые алгоритмы, решающие их со сколь угодно близкой к единице заранее заданной вероятностью.

В последние десятилетия в связи с приложениями к проблемам, имеющим практическое значение, к проблеме разрешения относят и вопросы оптимизации найденных алгоритмов, то есть требуется не только предоставить разрешающий алгоритм, но и обосновать, что этот алгоритм имеет наименьшую возможную сложность вычисления в том или ином смысле (по затратам времени, памяти, и так далее). С точки зрения этой подпроблемы проблема разрешения многие теории (или множества конструктивных объектов), для которых проблемы разрешения были положительно решены, оказались практически неразрешимыми или, по крайней мере, найденные алгоритмы не годятся для практического применения.

Литература

Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. — М.: Наука, 1980.

Катленд Н. Вычислимость.

Введение

в теорию рекурсивных функций. — М.: Наука, 1983.

Мальцев А. И.. Алгоритмы и рекурсивные функции. — М.: Наука, 1986.

Справочная книга по математической логике. Ч. III. Теория рекурсии. — М.: Наука. 1982.

Чёрч А. Введение в математическую логику. — М.: Наука, 1960.

Н. Н. Непейвода. А. А. Ивин. А. С. Карпенко. Проблема разрешимости. Гуманитарная энциклопедия [Электронный ресурс] // Центр гуманитарных технологий. — 21.

08.2014 (последняя редакция: 10.

06.2015). URL:

http://gtmarket.ru/concepts/6927.