Список неразрешимых проблем

В теории вычислимости неразрешимая проблема — это тип вычислительной задачи , которая требует ответа «да» или «нет», но при которой не может быть какой-либо компьютерной программы, которая всегда дает правильный ответ; то есть любая возможная программа иногда давала неправильный ответ или работала вечно, не давая никакого ответа. Более формально, неразрешимая проблема — это проблема, язык которой не является рекурсивным множеством ; см. статью Разрешимый язык . Существует бесчисленное множество неразрешимых проблем, поэтому приведенный ниже список обязательно неполный. Хотя неразрешимые языки не являются рекурсивными языками, они могут быть подмножествами распознаваемых по Тьюрингу языков: т. е. такие неразрешимые языки могут быть рекурсивно перечислимыми.

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

О неразрешимости в аксиоматической математике см. Список утверждений, неразрешимых в ZFC .

Проблемы с логикой

• Гильберта Проблема решения .
• Вывод типа и проверка типов для лямбда-исчисления второго порядка (или его эквивалента).
• Определение того, может ли предложение первого порядка в логике графов быть реализовано конечным неориентированным графом.
• Теорема Трахтенброта - Конечная выполнимость неразрешима.
• Выполнимость предложений Хорна первого порядка .

Проблемы с абстрактными машинами

• Проблема остановки (определение того, останавливается ли машина Тьюринга на заданных входных данных) и проблема смертности (определение того, останавливается ли она для каждой начальной конфигурации).
• Определение того, является ли машина Тьюринга « чемпионом занятого бобра» (т. е. является ли машина Тьюринга самой продолжительной среди останавливающихся машин Тьюринга с таким же количеством состояний и символов).
• Теорема Райса утверждает, что для всех нетривиальных свойств частичных функций неразрешимо, вычисляет ли данная машина частичную функцию с этим свойством.
• Проблема остановки регистровой машины : конечный автомат без входов и с двумя счетчиками, которые можно увеличивать, уменьшать и проверять на ноль.
• Универсальность недетерминированного автомата Pushdown : определение того, все ли слова приняты.
• Проблема в том, останавливается ли система тегов .

Проблемы с матрицами

• Проблема смертной матрицы .
• Определение того, порождает ли конечное множество верхнетреугольных матриц 3 × 3 с неотрицательными целыми элементами свободную полугруппу .
• Определение того, имеют ли две конечно порожденные подполугруппы целочисленных матриц общий элемент.

Проблемы комбинаторной теории групп

• Словесная задача для групп .
• Проблема сопряжения .
• Проблема группового изоморфизма .

Проблемы топологии

Основная статья: Проблема упрощенного комплексного распознавания

• двух конечных комплексов Определение гомеоморфности . симплициальных
• Определение того, является ли конечный симплициальный комплекс (гомеоморфным) многообразием .
• Определение того, является ли фундаментальная группа конечного симплициального комплекса тривиальной.
• Определение того, гомеоморфны ли два неодносвязных 5 -многообразия или 5-многообразие гомеоморфно S ⁵ .

Проблемы анализа

• Для функций определенных классов возникает проблема определения: равны ли две функции, известная как проблема нулевой эквивалентности (см. теорему Ричардсона ); нули функции; находится ли неопределенный интеграл функции также в классе. Конечно, некоторые подклассы этих задач разрешимы. Например, существует эффективная процедура решения элементарного интегрирования любой функции, принадлежащей области трансцендентных элементарных функций, — алгоритм Риша .
• «Проблема определения того, равен ли нулю определенный контурный кратный интеграл элементарной мероморфной функции на всюду вещественном аналитическом многообразии, на котором он является аналитическим», следствие теоремы MRDP, разрешающей десятую проблему Гильберта .
• Определение области определения решения обыкновенного дифференциального уравнения вида

${\frac {dx}{dt}}=p(t,x),~x(t_{0})=x_{0},$

где x — вектор из R ^н , p ( t , x ) — вектор многочленов от t и x , а (t ₀ , x ₀ ) принадлежит R ^п+1 .

Проблемы формальных языков и грамматик

• Проблема почтовой переписки .
• Определение того, генерирует ли контекстно-свободная грамматика все возможные строки или она неоднозначна .
• Даны две контекстно-свободные грамматики, определяющие, генерируют ли они один и тот же набор строк, или одна генерирует подмножество строк, сгенерированных другой, или существует ли вообще какая-либо строка, которую генерируют обе.

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

• Проблема определения того, может ли заданный набор плиток Ванга замостить плоскость.
• Задача определения колмогоровской сложности строки.
• Десятая проблема Гильберта : проблема определения того, имеет ли диофантово уравнение (полиномиальное уравнение со многими переменными) решение в целых числах.
• Определение того, является ли данная начальная точка с рациональными координатами периодической, или она лежит в бассейне притяжения данного открытого множества, в кусочно-линейном итерированном отображении в двух измерениях или в кусочно-линейном потоке в трех измерениях.
• Определение того, имеет ли формула λ-исчисления нормальную форму.
• «Игра жизни» Конвея о том, может ли последний образец когда-либо возникнуть из исходного, если при наличии исходного шаблона и другого шаблона.
• Правило 110 — большинство вопросов, касающихся «может ли свойство X появиться позже», неразрешимы.
• Проблема определения наличия в квантовомеханической системе спектральной щели .
• Нахождение пропускной способности информационно-устойчивого канала конечного автомата.
• В сетевом кодировании — определение разрешимости сети.
• Определение наличия у игрока выигрышной стратегии в игре Magic: The Gathering .
• Планирование в частично наблюдаемом марковском процессе принятия решений .
• Проблема планирования авиаперелета из одного пункта назначения в другой с тарифов . учетом
• В задаче трассировки лучей для трехмерной системы отражающих или преломляющих объектов определение того, достигает ли луч, начинающийся в заданном положении и направлении, в конечном итоге определенной точки.
• Определение того, достигает ли траектория частицы идеальной жидкости в трехмерной области определенной области пространства.

См. также

• Списки проблем
• Список нерешенных проблем
• Сокращение (сложность)
• Непознаваемость

Библиография

• Брукшир, Дж. Гленн (1989). Теория вычислений: формальные языки, автоматы и сложность . Редвуд-Сити, Калифорния: Benjamin/Cummings Publishing Company, Inc. Приложение C включает в себя невозможность определения алгоритмами наличия двусмысленностей в грамматике, а также невозможность проверки правильности программы с помощью алгоритма в качестве примера проблемы остановки.
• Халава, Веса (1997). Разрешимые и неразрешимые проблемы теории матриц (технический отчет TUCS). Том. 127. Центр компьютерных наук Турку. CiteSeerX   10.1.1.31.5792 .
• Море, BME; HD Шапиро (1991). Алгоритмы от P до NP, том 1 — Проектирование и эффективность . Редвуд-Сити, Калифорния: Benjamin/Cummings Publishing Company, Inc. В главе 2 «Математические методы анализа алгоритмов» обсуждаются трудноразрешимые проблемы с алгоритмами, имеющими экспоненциальную производительность.
• Вайнбергер, Шмуэль (2005). Компьютеры, жесткость и модули . Принстон, Нью-Джерси: Издательство Принстонского университета. Обсуждает неразрешимость проблемы слов для групп и различных проблем топологии.

Дальнейшее чтение

• Пунен, Бьорн (2 апреля 2012 г.). «Неразрешимые проблемы: сэмплер». arXiv : 1204.0299 [ math.LO ].