Творческие и продуктивные наборы

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

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

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

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

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

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

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

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

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

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

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

• P — продуктивный.
• ${\displaystyle {\bar {К}}}$является 1- сводимым к P.
• ${\displaystyle {\bar {К}}}$является m- сводимым к P.

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

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

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

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

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

Обычное творческое множество , определяемое с помощью диагональной функции, имеет свое собственное историческое развитие. Алан Тьюринг в статье 1936 года о машине Тьюринга показал существование универсального компьютера, который вычисляет функцию. Функция определяется таким образом, что ( результат применения инструкций, закодированных с помощью, к входным данным ), и является универсальной в том смысле, что любая вычислимая частичная функция задается как для всех , где кодирует инструкции для . Используя приведенные выше обозначения , и диагональная функция возникает вполне естественно как . В конечном счете, эти идеи связаны с тезисом Чёрча , который гласит, что математическое понятие вычислимых частичных функций является правильной формализацией эффективно вычислимой частичной функции, которая не может быть ни доказана, ни опровергнута. Чёрч использовал лямбда-исчисление , Тьюринг — идеализированный компьютер, а позже Эмиль Пост в своем подходе, все из которых эквивалентны.${\displaystyle К}$${\displaystyle d(x)}$${\displaystyle \Фи}$${\displaystyle \Фи}$${\displaystyle \Фи (w,x)=}$ ${\displaystyle w}$ ${\displaystyle x}$${\displaystyle f}$${\displaystyle f(x)=\Фи (e,x)}$${\displaystyle x}$${\displaystyle е}$${\displaystyle f}$${\displaystyle \Phi (e,x)=[[e]](x)}$${\displaystyle 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», Теоретическая информатика , 39 ( 2– 3): 225– 237, doi : 10.1016/0304-3975(85)90140-9 , MR  0821203
• Клини, Стивен Коул (2002), Математическая логика , Минеола, Нью-Йорк: Dover Publications Inc., ISBN 0-486-42533-9, МР  1950307. Перепечатка оригинала 1967 года, Wiley, MR 0216930.
• Майхилл, Джон (1955), «Творческие множества», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 1 (2): 97–108 , doi :10.1002/malq.19550010205, MR  0071379.
• Пост, Эмиль Л. (1944), «Рекурсивно перечислимые множества положительных целых чисел и проблемы их решения», Бюллетень Американского математического общества , 50 (5): 284–316 , doi : 10.1090/S0002-9904-1944-08111-1 , MR  0010514
• Роджерс, Хартли-младший (1987), Теория рекурсивных функций и эффективная вычислимость (2-е изд.), Кембридж, Массачусетс: MIT Press, ISBN 0-262-68052-1, МР  0886890.
• Соаре, Роберт И. (1987), Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо генерируемых множеств , Перспективы математической логики, Берлин: Springer-Verlag, ISBN 3-540-15299-7, МР  0882921.