Алгоритмически неразрешимая задача
Материал из Википедии — свободной энциклопедии
В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов.
Содержание |
[править] Проблемы, касающиеся абстрактных машин
- Проблема остановки
- Проблема самоприменимости
- Busy beaver (англ.)
- Любая проблема, сформулированная в теореме Райса
- Определить, достигнет ли когда-нибудь заданная исходная конфигурация в игре «Жизнь» заданной конечной конфигурации[1]
[править] Проблемы, касающиеся матриц
- Проблема умирающей матрицы: для данного конечного множества квадратных матриц n × n определить, существует ли произведение всех или некоторых из этих матриц (возможно, с повторениями) в каком-либо порядке, дающее нулевую матрицу. Проблема неразрешима даже для n=3 (разрешимость для n=2 является открытым вопросом[2])
[править] Другие проблемы
- Проблема разрешения (Entscheidungsproblem)
- Выводимость формулы в арифметике Пеано
- Проблема соответствий Поста (англ.)
- Вычисление колмогоровской сложности произвольной строки
- Идеальный архиватор, создающий для любого входного файла программу наименьшего возможного размера, печатающую этот файл[3]
- Идеальный оптимизирующий по размеру компилятор[4]
- Десятая проблема Гильберта
- Определить, можно ли замостить плоскость данным набором плиток Ванга (англ.)
- Определить, можно ли замостить плоскость данным набором полимино
- Проблема унификации (англ.) второго и высшего порядков
- Проблема вывода типов в модели Хиндли — Милнера с rank-N полиморфизмом
[править] Проблемы, алгоритмическая неразрешимость которых не доказана
Для некоторых задач неизвестен алгоритм, решающий их, и по своей природе они похожи на известные алгоритмически неразрешимые задачи. Вопросы об алгоритмической разрешимости таких задач являются открытыми проблемами. Вот некоторые из таких задач:
- Аналог десятой проблемы Гильберта для уравнений степени 3
- Аналог десятой проблемы Гильберта для уравнений в рациональных числах
- Проблема умирающей матрицы для матриц порядка 2
[править] См. также
- Алгоритмическая разрешимость формальной теории
- Теорема Гёделя о неполноте
[править] Ссылки
- ↑ Life Universal Computer
- ↑ When is a pair of matrices mortal?
- ↑ Наличие такого архиватора позволило бы вычислить колмогоровскую сложность произвольной строки, что является алгоритмически неразрешимой задачей.
- ↑ В частности, он заменял бы любой не останавливающийся алгоритм на тривиальный пустой цикл, а распознавание таких алгоритмов эквивалентно проблеме останова и является алгоритмически неразрешимой задачей.
