Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Проблемы в логике [ править ]

Проблемы с абстрактными машинами [ править ]

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

Проблемы с матрицами [ править ]

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

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

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

Проблемы в топологии [ править ]

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

Проблемы в анализе [ править ]

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

Проблемы с формальными языками и грамматиками [ править ]

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

Другие проблемы [ править ]

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

См. Также [ править ]

  • Списки проблем
  • Список нерешенных проблем
  • Редукция (сложность)

Заметки [ править ]

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

Библиография [ править ]

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

Дальнейшее чтение [ править ]

  • Пунен, Бьорн (2 апреля 2012 г.), Неразрешимые проблемы: семплер , arXiv : 1204.0299 , Bibcode : 2012arXiv1204.0299P

Внешние ссылки [ править ]

  • Обсуждение на MathOverflow