Алгоритмически неразрешимая задача

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

• Проблема умирающей матрицы: для данного конечного множества квадратных матриц n × n определить, существует ли произведение всех или некоторых из этих матриц (возможно, с повторениями) в каком-либо порядке, дающее нулевую матрицу. Проблема неразрешима даже для n=3 (разрешимость для n=2 является открытым вопросом[2]).[3]
• Проблема единичной матрицы: для данного конечного множества квадратных матриц n × n определить, существует ли произведение всех или некоторых из этих матриц (возможно, с повторениями) в каком-либо порядке, дающее единичную матрицу. Проблема неразрешима для целочисленных матриц начиная с n=4[4] и разрешима для n=2[5] (разрешимость для 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
• Аналог десятой проблемы Гильберта для уравнений в рациональных числах[6]
• Проблема умирающей матрицы для матриц порядка 2

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