Список неразрешимых проблем - List of undecidable problems

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

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

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

Проблемы в логика

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

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

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

  • В проблема матрицы смертных: определение, учитывая конечный набор п × п матрицы с целочисленными элементами, можно ли их перемножить в каком-либо порядке, возможно, с повторением, чтобы получить нулевая матрица. Это, как известно, неразрешимо для набора из шести или более матриц 3 × 3 или набора из двух матриц 15 × 15.[3]
  • Определение того, генерирует ли конечный набор верхнетреугольных матриц 3 × 3 с неотрицательными целочисленными элементами свободный полугруппа.
  • Определение того, есть ли две конечно порожденные подполугруппы Mп(Z) имеют общий элемент.

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

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

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

  • Для функций в определенных классах проблема определения: равны ли две функции, известная как проблема нулевой эквивалентности (см. Теорема Ричардсона );[4] нули функции; находится ли неопределенный интеграл функции также в классе.[5] Конечно, некоторые подклассы этих проблем разрешимы. Например, существует эффективная процедура принятия решения для элементарного интегрирования любой функции, которая принадлежит к области трансцендентных элементарных функций, т.е. Алгоритм риша.)
  • «Проблема определения того, является ли определенный контурный кратный интеграл элементарной мероморфной функции нулем над всюду вещественным аналитическим многообразием, на котором он является аналитическим», - следствие Теорема MRDP разрешение Десятая проблема Гильберта.[5]
  • Определение области решения обыкновенное дифференциальное уравнение формы
куда Икс это вектор в рп, п(т, Икс) - вектор многочлены в т и Икс, и (т0, Икс0) принадлежит рп + 1.[6]

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

  • В Проблема с почтовой корреспонденцией.
  • Проблема определения того, является ли данный набор Ванская плитка можно выложить плоскость плиткой.
  • Проблема в том, система тегов остановки.
  • Проблема определения Колмогоровская сложность строки.
  • Десятая проблема Гильберта: проблема определения того, имеет ли диофантово уравнение (многочленное полиномиальное уравнение) решение в целых числах.
  • Определение наличия контекстно-свободная грамматика генерирует все возможные строки, или если это неоднозначно.
  • Учитывая две контекстно-свободные грамматики, определение того, генерируют ли они один и тот же набор строк, или одна генерирует подмножество строк, генерируемых другой, или существует ли вообще какая-либо строка, которую генерируют обе.
  • Определение того, является ли заданная начальная точка с рациональными координатами периодической или находится ли она в области притяжения данного открытого множества, на кусочно-линейной повторяющейся карте в двух измерениях или в кусочно-линейном потоке в трех измерениях.[7]
  • Определение того, есть ли λ-исчисление формула имеет нормальный вид.
  • Игра жизни Конвея от того, дан ли начальный образец и другой образец, может ли последний образец когда-либо появиться из начального.
  • Правило 110 - большинство вопросов, касающихся того, может ли свойство "X" появиться позже, неразрешимы.
  • Проблема определения того, имеет ли квантово-механическая система спектральный промежуток.[8]
  • Определение, есть ли у игрока выигрышная стратегия в игре Магия: Сбор.[9]
  • Планирование в Частично наблюдаемый марковский процесс принятия решений.
  • Планирование путешествия.

Смотрите также

Примечания

  1. ^ Уэллс, Дж. Б. (1993). «Типизация и проверка типов в лямбда-исчислении второго порядка эквивалентны и неразрешимы». Tech. Реп. 93-011. Comput. Sci. Отделение Бостонского университета: 176–185. CiteSeerX  10.1.1.31.3590.
  2. ^ Трахтенброт, Б.А. (1950). «Невозможность алгоритма решения задачи для конечных областей». Доклады Академии Наук СССР (Н.С.). 70: 569–572. МИСТЕР  0033784.
  3. ^ Кассень, Жюльен; Халава, Веса; Харью, Теро; Николя, Франсуа (2014). «Более жесткие границы неразрешимости для матричной смертности, проблемы с нулевым углом и многое другое». arXiv:1404.0644 [cs.DM ].
  4. ^ Кейт О. Геддес, Стивен Р. Чапор, Джордж Лабан, Алгоритмы компьютерной алгебры, ISBN  0585332479, 2007, стр. 81ff
  5. ^ а б Столлворт, Дэниел Т. и Фред В. Роуш Неразрешимое свойство определенных интегралов Труды Американского математического общества Том 125, номер 7, июль 1997 г., страницы 2147-2148
  6. ^ Graça, Daniel S .; Буеску, Хорхе; Кампаньоло, Мануэль Л. (21 марта 2008 г.). «Ограниченность области определения неразрешима для полиномиальных ОДУ». Электронные заметки по теоретической информатике. 202: 49–57. Дои:10.1016 / j.entcs.2008.03.007.
  7. ^ Мур, Кристофер (1990), «Непредсказуемость и неразрешимость в динамических системах» (PDF), Письма с физическими проверками, 64 (20): 2354–2357, Bibcode:1990ПхРвЛ..64.2354М, Дои:10.1103 / PhysRevLett.64.2354, PMID  10041691.
  8. ^ Cubitt, Toby S .; Перес-Гарсия, Дэвид; Вольф, Майкл М. (2015). «Неразрешимость спектральной щели». Природа. 528 (7581): 207–211. arXiv:1502.04135. Bibcode:2015Натура. 528..207C. Дои:10.1038 / природа16059. PMID  26659181.
  9. ^ Херрик, Остин; Бидерман, Стелла; Черчилль, Алекс (2019-03-24). "Magic: The Gathering завершена по Тьюрингу". arXiv:1904.09828v2. Bibcode:2019arXiv190409828C. Цитировать журнал требует | журнал = (помощь)

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

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

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

внешняя ссылка