Jump to content

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

(Перенаправлено из Креативного набора )

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

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

[ редактировать ]

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

Множество A натуральных чисел называется продуктивным , если существует тотально рекурсивная (вычислимая) функция так что для всех , если затем Функция называется продуктивной функцией для

Множество натуральных чисел А называется творческим , если А рекурсивно перечислимо и его дополнение является продуктивным. Однако не каждое продуктивное множество имеет рекурсивно перечислимое дополнение, как показано ниже.

Архетипический творческий набор – это , набор, представляющий проблему остановки . Его дополнение является продуктивным с производственной функцией f ( i ) = i (функция тождества).

Чтобы убедиться в этом, мы применим определение продуктивной функции и покажем отдельно, что и :

  • : предполагать , затем , теперь учитывая, что у нас есть , это приводит к противоречию. Так .
  • : на самом деле, если , то было бы верно, что , но в предыдущем пункте мы продемонстрировали обратное. Так .

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

[ редактировать ]

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

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

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

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

  • П продуктивен.
  • сводима 1- к P .
  • сводима m- к P .

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

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

[ редактировать ]

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

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

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

Обычный творческий набор определяется с помощью диагональной функции имеет свое историческое развитие. Алан Тьюринг в статье 1936 года о машине Тьюринга показал существование универсального компьютера, который вычисляет функция. Функция определяется так, что ( результат применения инструкций, закодированных на вход ) и универсален в том смысле, что любая вычислимая частичная функция дается для всех где кодирует инструкции для . Используя приведенные выше обозначения , а диагональная функция возникает вполне естественно, когда . В конечном счете, эти идеи связаны с тезисом Чёрча , согласно которому математическое понятие вычислимых частичных функций является правильной формализацией эффективно вычислимой частичной функции, которую нельзя ни доказать, ни опровергнуть. Чёрч использовал лямбда-исчисление , Тьюринг — идеализированный компьютер, а позже — Эмиля Поста в своём подходе, и все они эквивалентны.

Дебора Джозеф и Пол Янг ( 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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: bc2c7f5b4f63a0b0f7c594545184d901__1699034460
URL1:https://arc.ask3.ru/arc/aa/bc/01/bc2c7f5b4f63a0b0f7c594545184d901.html
Заголовок, (Title) документа по адресу, URL1:
Creative and productive sets - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)