Википедия

Алгоритмическая разрешимость: различия между версиями

Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
→‎Связь разрешимости и полноты: формально — нет источника, неформально — неаккуратная формулировка
Строка 29:
 
== Связь разрешимости и полноты ==
В [[Математическая логика|математической логике]], традиционно используется два понятия полноты: собственно полнота и полнота относительно некоторого класса интерпретаций (или структур). В первом случае, теория полна, если любое предложение в ней является либо истинным, либо ложным. Во втором — если любое предложение, истинное при всех интерпретациях из данного класса, выводимо. Например, [[арифметика Пеано|натуральная арифметика]] неполна, согласно [[теорема Гёделя о неполноте|теоремам Гёделя о неполноте]], но она полна относительно своей стандартной интерпретации — это следует из [[теорема Гёделя о полноте|теоремы Гёделя о полноте]]{{Нет АИ|17|10|2014}}.
 
Оба понятия тесно связаны с разрешимостью. Например, если множество аксиом полной теории первого порядка рекурсивно перечислимо, то она разрешима. Это следует из известной [[Теорема Поста|теоремы Поста]], утверждающей, что если множество и его дополнение оба рекурсивно перечислимы, то они также [[Разрешимое множество|разрешимы]]. Интуитивно, аргумент, показывающий истинность приведённого утверждения, следующий: если теория полна, и множество её аксиом рекурсивно перечислимо, то существуют полуразрешающие процедуры для проверки истинности любого утверждения, равно как и его отрицания. Если запустить обе эти процедуры [[Параллельные вычисления|параллельно]], то учитывая полноту теории, одна из них должна когда-нибудь остановиться и выдать позитивный ответ.
Источник — https://ru.wikipedia.org/wiki/Алгоритмическая_разрешимость