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

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

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

править

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

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

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

править
  • Проблема разрешения (нем. Entscheidungsproblem).
  • Выводимость формулы в арифметике Пеано.
  • Post correspondence problem.
  • Вычисление колмогоровской сложности произвольной строки. Важные практические следствия из этого утверждения для области программирования:
    • невозможность создания идеального архиватора, формирующего для любого входного файла программу наименьшего возможного размера, печатающую этот файл
    • невозможность создания идеального оптимизирующего по размеру компилятора
  • Десятая проблема Гильберта
    • в частности, невозможно вычислить такую функцию: 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

См. также

править

Примечания

править
  1. Life Universal Computer. Дата обращения: 13 мая 2010. Архивировано 31 октября 2014 года.
  2. When is a pair of matrices mortal? Дата обращения: 6 мая 2010. Архивировано 8 декабря 2015 года.
  3. Cassaigne, Julien; Halava, Vesa; Harju, Tero; Nicolas, Francois (2014). "Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More". arXiv:1404.0644 [cs.DM].
  4. Paul C. Bell; Igor Potapov. On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups (англ.) // International Journal of Foundations of Computer Science[англ.] : journal. — World Scientific, 2010. — Vol. 21.6. — P. 963—978. — doi:10.1142/S0129054110007660.
  5. Christian Choffrut; Juhani Karhumäki. Some decision problems on integer matrices. (неопр.) // ITA. — 2005. — Т. 39(1). — С. 125—131. — doi:10.1051/ita:2005007.
  6. Успенский В. А., Семёнов А. Л. Решимые и нерешимые алгоритмические проблемы. // Квант, 1985, № 7, с. 9 — 15