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

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

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

Содержание

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

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

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

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

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

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

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

См. также

Ссылки

  1. Life Universal Computer
  2. When is a pair of matrices mortal?
  3. Paul C. Bell; Igor Potapov (2010). «On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups». International Journal of Foundations of Computer Science (World Scientific) 21.6: 963-978. DOI:10.1142/S0129054110007660.
  4. Christian Choffrut; Juhani Karhumäki (2005). «Some decision problems on integer matrices.». ITA 39(1): 125-131. DOI:10.1051/ita:2005007.
  5. Наличие такого архиватора позволило бы вычислить колмогоровскую сложность произвольной строки, что является алгоритмически неразрешимой задачей.
  6. В частности, он заменял бы любой не останавливающийся алгоритм на тривиальный пустой цикл, а распознавание таких алгоритмов эквивалентно проблеме останова и является алгоритмически неразрешимой задачей.

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "Алгоритмически неразрешимая задача" в других словарях:

  • Алгоритмическая разрешимость — В математической логике и теории алгоритмов под разрешимостью подразумевают свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если …   Википедия

  • Список статей по математической логике —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не ус …   Википедия

  • Неоднозначная грамматика — В информатике неоднозначной грамматикой называется формальная грамматика, которая может породить некоторую строку более чем одним способом (то есть для строки есть более одного дерева разбора). Язык называется существенно неоднозначным, если он… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»