Креативные и продуктивные наборы

В вычислимости теории продуктивные множества и творческие множества представляют собой типы множеств натуральных чисел , которые имеют важные приложения в математической логике . Они являются стандартной темой в учебниках математической логики, таких как Соаре (1987) и Роджерс (1987) .

Определение и пример

В оставшейся части этой статьи предположим, что $\varphi _{i}$ — допустимая нумерация , вычислимых функций W i _— соответствующая нумерация рекурсивно перечислимых множеств.

Множество A натуральных чисел называется продуктивным , если существует тотально рекурсивная (вычислимая) функция $f$ так что для всех $i\in \mathbb {N}$, если $W_{i}\subseteq A$ затем $f(i)\in A\setminus W_{i}.$ Функция $f$ называется продуктивной функцией для $A.$

Множество натуральных чисел А называется творческим , если А рекурсивно перечислимо и его дополнение $\mathbb {N} \setminus A$ является продуктивным. Однако не каждое продуктивное множество имеет рекурсивно перечислимое дополнение, как показано ниже.

Архетипический творческий набор – это $K=\{i\mid i\in W_{i}\}$, набор, представляющий проблему остановки . Его дополнение ${\bar {K}}=\{i\mid i\not \in W_{i}\}$ является продуктивным с производственной функцией f ( i ) = i (функция тождества).

Чтобы убедиться в этом, мы применим определение продуктивной функции и покажем отдельно, что $i\in {\bar {K}}$ и $i\not \in W_{i}$:

• $i\in {\bar {K}}$: предполагать $i\in K$, затем $i\in W_{i}$, теперь учитывая, что $W_{i}\subseteq {\bar {K}}$ у нас есть $i\in {\bar {K}}$, это приводит к противоречию. Так $i\in {\bar {K}}$.
• $i\not \in W_{i}$: на самом деле, если $i\in W_{i}$, то было бы верно, что $i\in K$, но в предыдущем пункте мы продемонстрировали обратное. Так $i\not \in W_{i}$.

Характеристики

Никакой продуктивный набор A не может быть рекурсивно перечислимым, потому что всякий раз, когда A содержит каждое число в наборе сброса Wi _, он содержит другие числа, и, более того, существует эффективная процедура для получения примера такого числа из индекса i . Точно так же ни один творческий набор не может быть разрешимым , поскольку это означало бы, что его дополнение, продуктивное множество, является рекурсивно перечислимым.

Любая производительная совокупность имеет продуктивную функцию, которая является инъективной и тотальной .

Следующие теоремы Майхилла (1955) показывают, что в некотором смысле все творческие множества подобны $K$ и все продуктивные наборы похожи ${\bar {K}}$.

Теорема. Пусть P — набор натуральных чисел. Следующие действия эквивалентны:

• П продуктивен.
• ${\bar {K}}$ сводима 1- к P .
• ${\bar {K}}$ сводима m- к P .

Теорема. Пусть C — множество натуральных чисел. Следующие действия эквивалентны:

• C – творческий.
• C 1 -полный
• C K рекурсивно изоморфен , то есть существует полная вычислимая биекция f на натуральных числах такая, что ( C ) = K. f

Приложения в математической логике

Множество всех доказуемых предложений в эффективной аксиоматической системе всегда является рекурсивно перечислимым множеством . Если система достаточно сложна, как арифметика первого порядка , то набор T гёделевых чисел истинных является рекурсивно предложений в системе будет продуктивным набором, а это означает, что всякий раз, когда W перечислимым набором истинных предложений, существует по крайней мере которого нет в W. одно верное предложение , Это можно использовать для строгого доказательства первой теоремы Гёделя о неполноте , поскольку ни одно рекурсивно перечислимое множество не является продуктивным. Дополнение множества T не будет рекурсивно перечислимым, и, таким образом, T является примером продуктивного набора, дополнение которого не является творческим.

История

В основополагающей статье Поста (1944) была определена концепция, которую он назвал «Творческий набор». Повторюсь, набор $K$ упомянутый выше и определенный как область определения функции $d(x)=[[x]](x)+1$ который берет диагональ всех перечислимых 1-местных вычислимых частичных функций и добавляет к ним 1, является примером творческого набора. Пост предложил версию теоремы Гёделя о неполноте, используя свои творческие наборы, где первоначально Гёдель в некотором смысле построил предложение, которое можно было свободно перевести как «Я недоказуем в этой аксиоматической теории». Однако доказательство Гёделя не основывалось на концепции истинных предложений, а скорее использовало концепцию непротиворечивой теории, что привело ко второй теореме о неполноте . После того, как Пост завершил свою версию неполноты, он добавил следующее:

«Неизбежен вывод, что даже для такого фиксированного, четко определенного корпуса математических положений математическое мышление является и должно оставаться по существу творческим».

Обычный творческий набор $K$ определяется с помощью диагональной функции $d(x)$ имеет свое историческое развитие. Алан Тьюринг в статье 1936 года о машине Тьюринга показал существование универсального компьютера, который вычисляет $\Phi$ функция. Функция $\Phi$ определяется так, что $\Phi (w,x)=$ ( результат применения инструкций, закодированных $w$ на вход $x$ ) и универсален в том смысле, что любая вычислимая частичная функция $f$ дается $f(x)=\Phi (e,x)$ для всех $x$ где $e$ кодирует инструкции для $f$. Используя приведенные выше обозначения $\Phi (e,x)=[[e]](x)$, а диагональная функция возникает вполне естественно, когда $d(x)=[[x]](x)+1$. В конечном счете, эти идеи связаны с тезисом Чёрча , согласно которому математическое понятие вычислимых частичных функций является правильной формализацией эффективно вычислимой частичной функции, которую нельзя ни доказать, ни опровергнуть. Чёрч использовал лямбда-исчисление , Тьюринг — идеализированный компьютер, а позже — Эмиля Поста в своём подходе, и все они эквивалентны.

Дебора Джозеф и Пол Янг ( 1985 ) сформулировали аналогичную концепцию полиномиальной креативности в теории сложности вычислений и использовали ее для предоставления потенциальных контрпримеров гипотезе Бермана-Хартманиса об изоморфизме NP-полных множеств.

Ссылки

• Дэвис, Мартин (1958), Вычислимость и неразрешимость , Серия по обработке информации и компьютерам, Нью-Йорк: McGraw-Hill, MR   0124208 . Перепечатано в 1982 году издательством Dover Publications.
• Эндертон, Герберт Б. (2010), Теория вычислимости: введение в теорию рекурсии , Academic Press, ISBN  978-0-12-384958-8 .
• Джозеф, Дебора ; Янг, Пол (1985), «Некоторые замечания о функциях-свидетелях для неполиномиальных и неполных множеств в NP» , Theoretical Computer Science , 39 (2–3): 225–237, doi : 10.1016/0304-3975(85)90140-9 , МР   0821203
• Клини, Стивен Коул (2002), Математическая логика , Минеола, Нью-Йорк: Dover Publications Inc., ISBN  0-486-42533-9 , МР   1950307 . Перепечатка оригинала 1967 года, Wiley, MR. 0216930 .
• Майхилл, Джон (1955), «Творческие множества», Журнал математической логики и основ математики , 1 (2): 97–108, doi : 10.1002/malq.19550010205 , MR   0071379 .
• Пост, Эмиль Л. (1944), «Рекурсивно перечислимые множества положительных целых чисел и проблемы их решения», Бюллетень Американского математического общества , 50 (5): 284–316, doi : 10.1090/S0002-9904-1944-08111- 1 , МР   0010514
• Роджерс, Хартли младший (1987), Теория рекурсивных функций и эффективная вычислимость (2-е изд.), Кембридж, Массачусетс: MIT Press, ISBN  0-262-68052-1 , МР   0886890 .
• Соаре, Роберт И. (1987), Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо порожденных множеств , Перспективы математической логики , Берлин: Springer-Verlag, ISBN  3-540-15299-7 , МР   0882921 .