Креативные и продуктивные наборы
В вычислимости теории продуктивные множества и творческие множества представляют собой типы множеств натуральных чисел , которые имеют важные приложения в математической логике . Они являются стандартной темой в учебниках математической логики, таких как Соаре (1987) и Роджерс (1987) .
Определение и пример
[ редактировать ]В оставшейся части этой статьи предположим, что — допустимая нумерация , вычислимых функций W i — соответствующая нумерация рекурсивно перечислимых множеств.
Множество A натуральных чисел называется продуктивным , если существует тотально рекурсивная (вычислимая) функция так что для всех , если затем Функция называется продуктивной функцией для
Множество натуральных чисел А называется творческим , если А рекурсивно перечислимо и его дополнение является продуктивным. Однако не каждое продуктивное множество имеет рекурсивно перечислимое дополнение, как показано ниже.
Архетипический творческий набор – это , набор, представляющий проблему остановки . Его дополнение является продуктивным с производственной функцией f ( i ) = i (функция тождества).
Чтобы убедиться в этом, мы применим определение продуктивной функции и покажем отдельно, что и :
- : предполагать , затем , теперь учитывая, что у нас есть , это приводит к противоречию. Так .
- : на самом деле, если , то было бы верно, что , но в предыдущем пункте мы продемонстрировали обратное. Так .
Характеристики
[ редактировать ]Никакой продуктивный набор A не может быть рекурсивно перечислимым, потому что всякий раз, когда A содержит каждое число в наборе сброса Wi , он содержит другие числа, и, более того, существует эффективная процедура для получения примера такого числа из индекса i . Точно так же ни один творческий набор не может быть разрешимым , поскольку это означало бы, что его дополнение, продуктивное множество, является рекурсивно перечислимым.
Любая производительная совокупность имеет продуктивную функцию, которая является инъективной и тотальной .
Следующие теоремы Майхилла (1955) показывают, что в некотором смысле все творческие множества подобны и все продуктивные наборы похожи . [1]
Теорема. Пусть P — набор натуральных чисел. Следующие действия эквивалентны:
Теорема. Пусть C — множество натуральных чисел. Следующие действия эквивалентны:
- C – творческий.
- C 1 -полный
- C K рекурсивно изоморфен , то есть существует полная вычислимая биекция f на натуральных числах такая, что ( C ) = K. f
Приложения в математической логике
[ редактировать ]Множество всех доказуемых предложений в эффективной аксиоматической системе всегда является рекурсивно перечислимым множеством . Если система достаточно сложна, как арифметика первого порядка , то набор T гёделевых чисел истинных является рекурсивно предложений в системе будет продуктивным набором, а это означает, что всякий раз, когда W перечислимым набором истинных предложений, существует по крайней мере которого нет в W. одно верное предложение , Это можно использовать для строгого доказательства первой теоремы Гёделя о неполноте , поскольку ни одно рекурсивно перечислимое множество не является продуктивным. Дополнение множества T не будет рекурсивно перечислимым, и, таким образом, T является примером продуктивного набора, дополнение которого не является творческим.
История
[ редактировать ]В основополагающей статье Поста (1944) была определена концепция, которую он назвал «Творческий набор». Повторюсь, набор упомянутый выше и определенный как область определения функции который берет диагональ всех перечислимых 1-местных вычислимых частичных функций и добавляет к ним 1, является примером творческого набора. [2] Пост предложил версию теоремы Гёделя о неполноте, используя свои творческие наборы, где первоначально Гёдель в некотором смысле построил предложение, которое можно было свободно перевести как «Я недоказуем в этой аксиоматической теории». Однако доказательство Гёделя не основывалось на концепции истинных предложений, а скорее использовало концепцию непротиворечивой теории, что привело ко второй теореме о неполноте . После того, как Пост завершил свою версию неполноты, он добавил следующее:
«Неизбежен вывод, что даже для такого фиксированного, четко определенного корпуса математических положений математическое мышление является и должно оставаться по существу творческим». [2]
Обычный творческий набор определяется с помощью диагональной функции имеет свое историческое развитие. Алан Тьюринг в статье 1936 года о машине Тьюринга показал существование универсального компьютера, который вычисляет функция. Функция определяется так, что ( результат применения инструкций, закодированных на вход ) и универсален в том смысле, что любая вычислимая частичная функция дается для всех где кодирует инструкции для . Используя приведенные выше обозначения , а диагональная функция возникает вполне естественно, когда . В конечном счете, эти идеи связаны с тезисом Чёрча , согласно которому математическое понятие вычислимых частичных функций является правильной формализацией эффективно вычислимой частичной функции, которую нельзя ни доказать, ни опровергнуть. Чёрч использовал лямбда-исчисление , Тьюринг — идеализированный компьютер, а позже — Эмиля Поста в своём подходе, и все они эквивалентны.
Дебора Джозеф и Пол Янг ( 1985 ) сформулировали аналогичную концепцию полиномиальной креативности в теории сложности вычислений и использовали ее для предоставления потенциальных контрпримеров гипотезе Бермана-Хартманиса об изоморфизме NP-полных множеств.
Примечания
[ редактировать ]- ^ Солнце (1987) ; Роджерс (1987) .
- ↑ Перейти обратно: Перейти обратно: а б Эндертон (2010) , стр. 79, 80, 120.
Ссылки
[ редактировать ]- Дэвис, Мартин (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 .