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

Проблемы, касающиеся абстрактных машин

• Проблема остановки
• Проблема самоприменимости
• Любая проблема, сформулированная в теореме Райса
• Определить, достигнет ли когда-нибудь заданная исходная конфигурация в игре « Жизнь » заданной конечной конфигурации

Проблемы, касающиеся матриц

• : для данного конечного множества квадратных матриц n × n определить, существует ли произведение всех или некоторых из этих матриц (возможно, с повторениями) в каком-либо порядке, дающее нулевую матрицу. Проблема неразрешима даже для n=3 (разрешимость для n=2 является открытым вопросом ).
• : для данного конечного множества квадратных матриц n × n определить, существует ли произведение всех или некоторых из этих матриц (возможно, с повторениями) в каком-либо порядке, дающее единичную матрицу. Проблема неразрешима для целочисленных матриц начиная с n=4 и разрешима для n=2 (разрешимость для n=3 является открытым вопросом). Проблема эквивалентна вопросу, является ли матричная полугруппа группой.
• алгоритмически неразрешима для целочисленных матриц начиная с n=3 и открыта для n=2.

Другие проблемы

• Проблема разрешения ( нем. Entscheidungsproblem ).
• Выводимость формулы в арифметике Пеано .
• .
• Вычисление колмогоровской сложности произвольной строки. Важные практические следствия из этого утверждения для области программирования:
  • невозможность создания идеального архиватора , формирующего для любого входного файла программу наименьшего возможного размера, печатающую этот файл
  • невозможность создания идеального оптимизирующего по размеру компилятора
• Десятая проблема Гильберта
  • в частности, невозможно вычислить такую функцию: f(n) = max{min{max{|x_1|, |x_2|, ..., |x_k|: P(x_1, x_2, ..., x_k) = 0}}}, где k пробегает значения от 1 до n, P пробегает все многочлены от k переменных степени не более чем n, при этом модуль коэффициента каждого слагаемого не превосходит n. Значение этой функции позволяет ограничить перебор решений диофантового уравнения степени не более чем n, с не более чем n переменными, у которого модуль коэффициентов не превосходит n. Например, f(1)=1, f(2)=5 Если бы существовала вычислимая функция, не отстающая от f(n), то десятая проблема Гильберта имела бы противоположное решение.
• Определить, можно ли замостить плоскость данным набором плиток Вана .
• Определить, можно ли замостить плоскость данным набором полимино .
• Проблема второго и высшего порядков.
• Проблема вывода типов в системе типов Хиндли — Милнера с полиморфизмом N -го ранга.

Проблемы, алгоритмическая неразрешимость которых не доказана

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

• Аналог десятой проблемы Гильберта для уравнений степени 3
• Аналог десятой проблемы Гильберта для уравнений в рациональных числах
• Проблема умирающей матрицы для матриц порядка 2

См. также

• Алгоритмическая разрешимость формальной теории
• Теорема Гёделя о неполноте

Примечания