Можно показать, что две вычислительные модели являются полными, если каждая из них может кодировать универсальный симулятор для другой. Можно показать, что две логики будут полными, если будет показано, что кодирование правил логических выводов (и, возможно, аксиом, если они присутствуют) каждого из них является теоремами другого. В вычислимости это привело к естественному представлению о полноте Тьюринга и тезисе Тьюринга Церкви. Тем не менее, я не видел, где логическая сопряженность привела к какой-либо естественной идее полной полноты подобного качества.
Поскольку выполнимость и вычислимость тесно связаны друг с другом, я думаю, что не так уж и много думать о том, что в логике может существовать концепция, которая является естественным двойником полноты по Тьюрингу. Предположительно, что-то вроде: есть «истинная» теорема, которая не доказуема в логике тогда и только тогда, когда есть вычислимая функция, которая не описывается вычислительной моделью. Мой вопрос, кто-нибудь изучал это? Ссылка или некоторые ключевые слова будут полезны.
Под «истинным» и «вычислимым» в предыдущем абзаце я имею в виду интуитивные, но в конечном итоге неопределимые идеи. Например, кто-то может показать, что конечность последовательностей Гудштейна является «истинной», но не доказуемой в арифметике Пеано без полного определения понятия «истинно». Аналогично, с помощью диагонализации можно показать, что существуют вычислимые функции, которые не являются примитивно-рекурсивными без фактического полного определения концепции вычислимости. Мне было интересно, несмотря на то, что в конечном итоге они, как правило, являются эмпирическими понятиями, возможно, эти понятия могли бы быть достаточно хорошо связаны друг с другом, чтобы связать понятия полноты.
Ответы:
Я не уверен, почему вы говорите, что «истина» в конечном итоге неопределима, так как существует точное определение того, что означает, что формула первого порядка является истинной .
Что уникально в случае вычислимости, так это то, что для любого определения (столь дикого, как ваши сны) «вычислительной модели» вы можете, наконец, связать его с набором функций (функций, которые он может вычислять). Таким образом, вы можете естественным образом сравнивать разные модели, и, исправив одну (основываясь на некотором эмпирическом обосновании, таком как «это хорошее представление вычислений в реальном мире»), вы можете назвать любую другую модель завершенной, если она вычисляет точно такой же набор функции.
Однако как вы сравниваете разные логики? Кажется, что нет естественного свойства, которое вы можете прикрепить к произвольной логике и использовать его для сравнения с другими системами. Возможно, вы можете исправить логику, например логику предикатов первого порядка, и спросить о полноте аксиоматической системы. Предположим, вы работаете в ZFC и считаете, что он состоит из естественных аксиом, которые представляют мир. Теперь, когда дана другая аксиоматическая система, вы можете спросить, имеют ли они одну и ту же теорию, и назвать эту систему полной, если ответ положительный. Я думаю, что отличие от случая вычислимости в том, что для вычислимости существует более сильный консенсус относительно того, какой должна быть «базовая модель». Причиной такого консенсуса является то, что многие независимые модели вычислений были позже показаны эквивалентными,
источник