Невыполнимая задача в вычислительной технике
В математике и информатике проблема Entscheidungsproblem ( по -немецки «проблема принятия решения»; произносится [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm] ) — это задача, поставленная Дэвидом Гильбертом и Вильгельмом Акерманном в 1928 году. [1] Задача требует разработки алгоритма , который рассматривает в качестве входных данных утверждение и отвечает «да» или «нет» в зависимости от того, является ли утверждение универсальным , то есть действительным в каждой структуре .
Теорема о полноте
Согласно теореме о полноте логики первого порядка , утверждение является универсально действительным тогда и только тогда, когда оно может быть выведено с использованием логических правил и аксиом, поэтому проблему Entscheidungsproblem можно также рассматривать как требование алгоритма решить, доказуемо ли данное утверждение, используя правила логики .
В 1936 году Алонзо Чёрч и Алан Тьюринг опубликовали независимые статьи [2], показывающие, что общее решение проблемы Entscheidungs те, которые выражаются в лямбда-исчислении ). Это предположение теперь известно как тезис Чёрча-Тьюринга .
История проблемы
Истоки проблемы Entscheidungsproblem восходят к Готфриду Лейбницу , который в семнадцатом веке, после создания успешной механической вычислительной машины , мечтал построить машину, которая могла бы манипулировать символами, чтобы определять истинностные значения математических утверждений. [3] Он понял, что первым шагом должен быть чистый формальный язык , и большая часть его последующей работы была направлена на эту цель. В 1928 году Давид Гильберт и Вильгельм Акерман поставили вопрос в форме, изложенной выше.
В продолжение своей «программы» Гильберт поставил на международной конференции в 1928 году три вопроса, третий из которых стал известен как «проблема Гильберта Entscheidungs ». [4] В 1929 году Мозес Шенфинкель опубликовал статью об особых случаях проблемы принятия решений, подготовленную Полем Бернейсом . [5]
Еще в 1930 году Гильберт считал, что неразрешимой проблемы не существует. [6]
Отрицательный ответ
Прежде чем можно было ответить на этот вопрос, необходимо было формально определить понятие «алгоритм». Это было сделано Алонсо Чёрчем в 1935 году с концепцией «эффективной вычислимости», основанной на его λ-исчислении , и Аланом Тьюрингом в следующем году с его концепцией машин Тьюринга . Тьюринг сразу понял, что это эквивалентные модели вычислений .
Отрицательный ответ на проблему Entscheidungsproblem был затем дан Алонзо Чёрчем в 1935–36 годах ( теорема Чёрча ) и независимо вскоре после этого Аланом Тьюрингом в 1936 году ( доказательство Тьюринга ). Чёрч доказал, что не существует вычислимой функции , которая бы решала для двух заданных выражений λ-исчисления, эквивалентны они или нет. Он во многом полагался на более ранние работы Стивена Клини . Тьюринг свел вопрос о существовании «алгоритма» или «общего метода», способного решить проблему Entscheidungs, к вопросу о существовании «общего метода», который решает, остановится или нет какая-либо данная машина Тьюринга ( проблема остановки ). Если под «алгоритмом» понимать метод, который можно представить в виде машины Тьюринга, и при отрицательном (вообще) ответе на последний вопрос, то вопрос о существовании алгоритма для задачи Entscheidungs также должен быть отрицательным (в общий). В своей статье 1936 года Тьюринг говорит: «Соответствуя каждой вычислительной машине «оно», мы конструируем формулу «Un(it)» и показываем, что, если существует общий метод определения того, доказуемо ли «Un(it)», тогда существует общий метод определения того, печатает ли «он» когда-либо 0».
На работу Чёрча и Тьюринга сильно повлияла более ранняя работа Курта Гёделя над его теоремой о неполноте , особенно методом присвоения чисел ( нумерация Гёделя ) логическим формулам с целью свести логику к арифметике.
Проблема Entscheidungsproblem связана с десятой проблемой Гильберта , которая требует алгоритма , позволяющего определить, имеют ли диофантовые уравнения решение. Отсутствие такого алгоритма, установленного работой Юрия Матиясевича , Джулии Робинсон , Мартина Дэвиса и Хилари Патнэм с последней частью доказательства в 1970 году, также подразумевает отрицательный ответ на Entscheidungsproblem .
Обобщения
Используя теорему о дедукции , проблема Entscheidungs охватывает более общую проблему определения того, влечет ли данное предложение первого порядка заданный конечный набор предложений, но достоверность в теориях первого порядка с бесконечным количеством аксиом не может быть напрямую сведена к проблеме Entscheidungs. Однако такие более общие проблемы принятия решений представляют практический интерес. Некоторые теории первого порядка алгоритмически разрешимы ; примеры этого включают арифметику Пресбургера , реальные закрытые поля и системы статических типов многих языков программирования . С другой стороны, теория натуральных чисел первого порядка со сложением и умножением, выраженная аксиомами Пеано, не может быть решена с помощью алгоритма.
Фрагменты
По умолчанию в разделе используются цитаты из Pratt-Hartmann (2023). [7]
Классическая Entscheidungsproblem спрашивает, верна ли данная формула первого порядка во всех моделях. Финитарная проблема спрашивает, верно ли это для всех конечных моделей. Теорема Трахтенброта показывает, что это тоже неразрешимо. [8] [7]
Некоторые обозначения: означает задачу определения того, существует ли модель набора логических формул . та же проблема, но для конечных моделей. Задача для логического фрагмента называется разрешимой, если существует программа, которая для каждого конечного набора логических формул во фрагменте может решить, существует она или нет.![{\displaystyle {\rm {{Сб}(\Фи)}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \Фи}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {{FinSat}(\Phi)}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {Сб}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \Фи}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {{Сб}(\Фи)}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Существует иерархия разрешимостей. Наверху — неразрешимые проблемы. Ниже приведены решаемые проблемы. Кроме того, решаемые проблемы можно разделить по иерархии сложности.
Аристотелевский и реляционный
Аристотелева логика рассматривает 4 вида предложений: «Все p суть q», «Все p не являются q», «Некоторые p есть q», «Некоторые p не являются q». Мы можем формализовать такие предложения как фрагмент логики первого порядка:
![{\displaystyle \forall x,p(x)\to \pm q(x),\quad \exists x,p(x)\wedge \pm q(x)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
NLOGSPACE![{\displaystyle p,q}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle +q:=q,\;-q:=\neg q}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {Сб}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {Сб}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \forall x,\pm p(x)\to \pm q(x),\quad \exists x,\pm p(x)\wedge \pm q(x)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Реляционная логика![{\textstyle \forall x, {\rm {{body}(x),\exists y, {\rm {{body}(y)\wedge {\rm {{love}(x,y)}}}} }}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\begin{aligned}\forall x,p(x)\to (\forall y,q(x)\to \pm r(x,y)),&\quad \forall x,p(x) )\to (\exists y,q(x)\wedge \pm r(x,y))\\\exists x,p(x)\wedge (\forall y,q(x)\to \pm r( x,y)),&\quad \exists x,p(x)\wedge (\exists y,q(x)\wedge \pm r(x,y))\end{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
NLOGSPACEEXPTIME![{\displaystyle {\rm {Сб}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \pm p, \pm q}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Арити
Логический фрагмент первого порядка, в котором есть только имена переменных, является NEXPTIME -полным (теорема 3.18). При , оно RE -полно для решения своего , и ко-RE-полно для решения (теорема 3.15), поэтому неразрешимо.![{\displaystyle x,y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x,y,z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {Сб}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {FinSat}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Монадическое исчисление предикатов представляет собой фрагмент, в котором каждая формула содержит только одномерные предикаты и не содержит функциональных символов. Оно NEXPTIME-полно (теорема 3.22).![{\displaystyle {\rm {Сб}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Префикс квантификатора
Любая формула первого порядка имеет пренексную нормальную форму. Для каждого возможного префикса квантора пренексной нормальной формы у нас есть фрагмент логики первого порядка. Например, класс Бернейса-Шенфинкеля , представляет собой класс формул первого порядка с префиксом квантора , символами равенства и отсутствием функциональных символов .![{\displaystyle [\exists ^{*}\forall ^{*}]_{=}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \exists \cdots \exists \forall \cdots \forall }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Например, в статье Тьюринга 1936 года (стр. 263) отмечалось, что, поскольку проблема остановки для каждой машины Тьюринга эквивалентна логической формуле первого порядка вида , проблема неразрешима.![{\displaystyle \forall \exists \forall \exists ^{6}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {{Сб}(\forall \exists \forall \exists ^{6})}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Точные границы известны, резко:
и ко-RE-полны, а задачи RE-полны (теорема 5.2).![{\displaystyle {\rm {{Сб}([\forall \exists \forall ]_{=})}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {FinSat}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- То же и с (теоремой 5.3).
![{\displaystyle \forall ^{3}\exists }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
разрешима, что независимо доказали Гёдель, Шютте и Кальмар.
является неразрешимым.- Для любого , оба и являются NEXPTIME-полными (теорема 5.1).
![{\displaystyle n\geq 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {{Сб}(\exists ^{n}\forall ^{*})}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {{Сб}([\exists ^{n}\forall ^{*}]_{=})}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Это означает, что это разрешимо, результат, впервые опубликованный Бернейсом и Шенфинкелем. [9]
![{\displaystyle {\rm {{Сб}([\exists ^{*}\forall ^{*}]_{=})}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Для любого , является EXPTIME полным (раздел 5.4.1).
![{\ displaystyle n \ geq 0, m \ geq 2}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {{Сб}(\exists ^{n}\forall \exists ^{m})}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Для любого , является NEXPTIME-полным (раздел 5.4.2).
![{\displaystyle n\geq 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {{Сб}([\exists ^{n}\forall \exists ^{*}]_{=})}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Это означает, что это разрешимо, и этот результат впервые был опубликован Аккерманом. [10]
![{\displaystyle {\rm {{Сб}(\exists ^{*}\forall ^{*}\exists ^{*})}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Для любого и являются PSPACE-полными (раздел 5.4.3).
![{\displaystyle n\geq 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {{Сб}(\exists ^{n}\forall \exists)}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\rm {{Сб}([\exists ^{n}\forall \exists ]_{=})}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Бёргер и др. (2001) [11] описывает уровень вычислительной сложности для каждого возможного фрагмента со всеми возможными комбинациями префикса квантора, функциональной арности, арности предиката и равенства/отсутствия равенства.
Практические процедуры принятия решений
Наличие практических процедур принятия решений для классов логических формул представляет значительный интерес для проверки программ и схем. Чисто логические формулы обычно решаются с использованием методов решения SAT, основанных на алгоритме DPLL .
Для более общих задач решения теорий первого порядка конъюнктивные формулы над линейной вещественной или рациональной арифметикой могут быть решены с использованием симплекс-алгоритма , формулы в линейной целочисленной арифметике ( арифметика Пресбургера ) могут быть решены с использованием алгоритма Купера или Омега-теста Уильяма Пью . Формулы с отрицаниями, конъюнктами и дизъюнкциями сочетают в себе трудности проверки выполнимости с трудностью решения конъюнкций; в настоящее время они обычно решаются с использованием методов SMT-решения , которые сочетают в себе решение SAT с процедурами принятия решений для соединений и методов распространения. Действительная полиномиальная арифметика, также известная как теория действительных замкнутых полей , разрешима; это теорема Тарского-Зейденберга , которая была реализована в компьютерах с помощью цилиндрического алгебраического разложения .
Смотрите также
Примечания
- ^ Дэвид Гильберт и Вильгельм Акерманн. Основы теоретической логики. Шпрингер, Берлин, Германия, 1928 год. Английский перевод: Дэвид Гильберт и Вильгельм Акерманн. Принципы математической логики. Издательство AMS Chelsea Publishing, Провиденс, Род-Айленд, США, 1950 г.
- ↑ Статья Чёрча была представлена Американскому математическому обществу 19 апреля 1935 года и опубликована 15 апреля 1936 года. Тьюринг, добившийся значительного прогресса в описании своих собственных результатов, был разочарован, узнав о доказательстве Чёрча после его публикации (см. переписку между Максом Ньюман и Чёрч в документах Алонзо Чёрча). Тьюринг быстро завершил свою статью и поспешил ее опубликовать; он был получен в Трудах Лондонского математического общества 28 мая 1936 г., прочитан 12 ноября 1936 г. и опубликован в серии 2, том 42 (1936–7); он появился в двух разделах: в Части 3 (страницы 230–240), выпущенной 30 ноября 1936 года, и в Части 4 (страницы 241–265), выпущенной 23 декабря 1936 года; Тьюринг добавил исправления в том 43 (1937), стр. 544–546. См. сноску в конце Soare: 1996.
- ^ Дэвис 2001, стр. 3–20.
- ^ Ходжес 1983, с. 91
- ^ Клайн, Г.Л.; Ановская, С.А. (1951), «Обзор основ математики и математической логики С.А. Яновской», Журнал символической логики , 16 (1): 46–48, doi : 10.2307/2268665, JSTOR 2268665, S2CID 119004002
- ^ Ходжес 1983, с. 92, цитата из Гильберта
- ^ аб Пратт-Хартманн, Ян (30 марта 2023 г.). Фрагменты логики первого порядка. Издательство Оксфордского университета. ISBN 978-0-19-196006-2.
- ^ Б. Трахтенброт. Невозможность алгоритма решения проблемы для конечных моделей . Доклады Академии Наук, 70:572–596, 1950. Английский перевод: AMS Translations Series 2, vol. 33 (1963), стр. 1–6.
- ^ Бернейс, Пол; Шенфинкель, Моисей (декабрь 1928 г.). «Zum Entscheidungsproblem der Mathematischen Logik». Mathematische Annalen (на немецком языке). 99 (1): 342–372. дои : 10.1007/BF01459101. ISSN 0025-5831. S2CID 122312654.
- ↑ Акерманн, Вильгельм (1 декабря 1928 г.). «Über die Erfüllbarkeit gewisser Zählausdrücke». Mathematische Annalen (на немецком языке). 100 (1): 638–649. дои : 10.1007/BF01448869. ISSN 1432-1807. S2CID 119646624.
- ^ Бёргер, Эгон; Гредель, Эрих; Гуревич, Юрий; Гуревич, Юрий (2001). Классическая проблема решения . Университеттекст (2-е издание 1-го изд.). Берлин: Шпрингер. ISBN 978-3-540-42324-9.
Рекомендации
- Гильберт, Дэвид ; Акерманн, Вильгельм (1928). Grundzüge der theoretischen Logik [ Принципы математической логики ] (на немецком языке). Спрингер-Верлаг . ISBN 0821820249.
- Алонзо Чёрч , «Неразрешимая проблема элементарной теории чисел », American Journal of Mathematics, 58 (1936), стр. 345–363.
- Алонзо Чёрч , «Заметка о проблеме Entscheidungs», Journal of Символическая логика, 1 (1936), стр. 40–41.
- Дэвис, Мартин (2001). Логические машины: математики и происхождение компьютера . Norton в мягкой обложке (1. Опубликовано под ред. Norton в мягкой обложке). Нью-Йорк, Нью-Йорк Лондон: Нортон. ISBN 978-0-393-32229-3.
- Алан Тьюринг , « О вычислимых числах с применением к проблеме Entscheidungs », Труды Лондонского математического общества , серия 2, 42 (1936–7), стр. 230–265. Онлайн-версии: с сайта журнала, из цифрового архива Тьюринга, с сайта abelard.org. Опечатки появились в серии 2, 43 (1937), стр. 544–546.
- Дэвис, Мартин , «Неразрешимые, основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях», Raven Press, Нью-Йорк, 1965. Статья Тьюринга занимает третье место в этом томе. В число статей входят работы Гёделя, Чёрча, Россера, Клини и Поста.
- Ходжес, Эндрю (1983). Алан Тьюринг: загадка . Нью-Йорк: Саймон и Шустер. ISBN 978-0-671-49207-6.Биография Алана М. Тьюринга. См. главу «Дух истины», где представлена история, ведущая к его доказательству, и его обсуждение.
- Соаре, Роберт И. , «Вычислимость и рекурсия», Bull. Символическая логика 2 (1996), вып. 3, 284–321.
- Тулмин, Стивен , «Падение гения», рецензия на книгу « Алан Тьюринг: Загадка Эндрю Ходжеса», в The New York Review of Books, 19 января 1984 г., стр. 3 и далее.
- Уайтхед, Альфред Норт ; Рассел, Бертран , Principia Mathematica to *56, Cambridge at University Press, 1962. В отношении проблемы парадоксов авторы обсуждают проблему, заключающуюся в том, что множество не должно быть объектом ни в одной из своих «определяющих функций», в частности « Введение, гл. 1 стр. 24 «...трудности, возникающие в формальной логике», и гл. 2.I. «Принцип порочного круга» стр. 37 и далее, и гл. 2.VIII. .60 и далее.
Внешние ссылки
Словарное определение проблемы entscheidungsproblem в Викисловаре