Теорема о низком базисе - Low basis theorem - Wikipedia

Теорема о низком базисе - одна из нескольких базисные теоремы в теории вычислимости, каждый из которых показывает, что, учитывая бесконечное поддерево двоичного дерева ${\displaystyle 2^{<\omega }}$, можно найти бесконечный путь по дереву с определенными свойствами вычислимости. Теорема о низком базисе, в частности, показывает, что должен быть путь, который низкий; это Прыжок Тьюринга пути эквивалентна Тьюрингу проблема остановки ${\displaystyle \emptyset '}$.

Заявление и доказательство

Теорема о низком базисе утверждает, что каждое непустое ${\displaystyle \Pi _{1}^{0}}$ учебный класс в ${\displaystyle 2^{\omega }}$ (видеть арифметическая иерархия ) содержит набор низкая степень (Соаре 1987: 109). По определению это эквивалентно утверждению, что каждое бесконечное вычислимое поддерево двоичного дерева ${\displaystyle 2^{<\omega }}$ имеет бесконечный путь низкой степени.

Доказательство использует метод принуждения с помощью ${\displaystyle \Pi _{1}^{0}}$ классы (Купер 2004: 330). Хайек и Кучера (1989) показали, что низкий базис доказуем в формальной системе арифметики, известной как ${\displaystyle {\text{I-}}\Sigma _{1}}$.

Заявление

Одно из приложений теоремы о низком базисе состоит в построении дополнений эффективных теорий так, чтобы дополнения имели низкую степень Тьюринга. Например, из теоремы о низком базисе следует существование Степени PA строго ниже ${\displaystyle \emptyset '}$.

Рекомендации

• Кензер, Дуглас (1999). "${\displaystyle \Pi _{1}^{0}}$ занятия по теории вычислимости ". В Гриффоре, Эдвард Р. (ред.). Справочник по теории вычислимости. Stud. Логика найдена. Математика. 140. Северная Голландия. стр.37–85. ISBN  0-444-89882-4. МИСТЕР  1720779. Zbl  0939.03047.
• Купер, С. Барри (2004). Теория вычислимости. Чепмен и Холл / CRC. ISBN  1-58488-237-9..
• Гайек, Петр; Кучера, Антонин (1989). «О теории рекурсии в I∑1». Журнал символической логики. 54 (2): 576–589. Дои:10.2307/2274871. JSTOR  2274871.
• Jockusch, Carl G., Jr .; Соаре, Роберт I. (1972). «Π (0, 1) Классы и степени теории». Труды Американского математического общества. 173: 33–56. Дои:10.1090 / с0002-9947-1972-0316227-0. ISSN  0002-9947. JSTOR  1996261. Zbl  0262.02041. Оригинальная публикация, включая дополнительную разъясняющую прозу.
• Нис, Андре (2009). Вычислимость и случайность. Oxford Logic Guides. 51. Оксфорд: Издательство Оксфордского университета. ISBN  978-0-19-923076-1. Zbl  1169.03034. Теорема 1.8.37.
• Соаре, Роберт I. (1987). Рекурсивно перечислимые множества и степени. Изучение вычислимых функций и вычислимых множеств. Перспективы математической логики. Берлин: Springer-Verlag. ISBN  3-540-15299-7. Zbl  0667.03030.