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