Jump to content

Вычислимо неразделимы

В теории вычислимости два непересекающихся множества натуральных чисел называются вычислимо неразделимыми или рекурсивно неразделимыми, если они не могут быть «разделены» вычислимым множеством . [1] Эти множества возникают при изучении самой теории вычислимости, особенно в связи с классы . Вычислимо неразделимые множества возникают также при изучении теоремы Гёделя о неполноте .

Определение

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

Натуральные числа – это набор . Учитывая непересекающиеся подмножества и из , разделительный набор является подмножеством такой, что и (или, что то же самое, и , где обозначает дополнение ). Например, сам по себе является разделяющим набором для пары, как и .

Если пара непересекающихся множеств и не имеет вычислимого разделяющего множества, то эти два множества вычислимо неразделимы .

Если невычислимое множество, то и его дополнение вычислимо неразделимы. Однако существует множество примеров множеств. и которые не пересекаются, не дополняют друг друга и вычислимо неразделимы. Более того, возможно для и быть вычислимо неразделимыми, непересекающимися и вычислимо перечислимыми .

  • Позволять — стандартная индексация частично вычислимых функций . Тогда множества и вычислимо неразделимы ( William Gasarch 1998, стр. 1047).
  • Позволять — стандартная нумерация Гёделя для формул арифметики Пеано . Тогда набор доказуемых формул и множества опровержимых формул вычислимо неразделимы. Неразделимость множеств доказуемых и опровержимых формул справедлива для многих других формальных теорий арифметики (Смальян, 1958).
  1. ^ Монк 1976, с. 100
  • Цензер, Дуглас (1999), "П. 0
    1
    класс теории вычислимости», Справочник по теории вычислимости , Stud. Logic Found. Math., т. 140, Амстердам: Северная Голландия, стр. 37–85, doi : 10.1016/S0049-237X(99)80018-4 , МР   1720779
  • Гасарч, Уильям (1998), «Обзор рекурсивной комбинаторики», Справочник по рекурсивной математике, Vol. 2 , Студ. Логика найдена. Матем., вып. 139, Амстердам: Северная Голландия, стр. 1041–1176, doi : 10.1016/S0049-237X(98)80049-9 , MR   1673598.
  • Монк, Дж. Дональд (1976), Математическая логика , Тексты для выпускников по математике, Берлин, Нью-Йорк: Springer-Verlag , ISBN  978-0-387-90170-1
  • Смалльян, Раймонд М. (1958), «Неразрешимость и рекурсивная неразделимость», Журнал математической логики и основ математики , 4 (7–11): 143–147, doi : 10.1002/malq.19580040705 , ISSN   0044-3050 , MR   0099293
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 756ff04e5b88e7d030f2fd32276c93e8__1705602480
URL1:https://arc.ask3.ru/arc/aa/75/e8/756ff04e5b88e7d030f2fd32276c93e8.html
Заголовок, (Title) документа по адресу, URL1:
Computably inseparable - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)