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

Теорема о низком базисе - одна из нескольких базисные теоремы в теории вычислимости, каждый из которых показывает, что, учитывая бесконечное поддерево двоичного дерева , можно найти бесконечный путь по дереву с определенными свойствами вычислимости. Теорема о низком базисе, в частности, показывает, что должен быть путь, который низкий; это Прыжок Тьюринга пути эквивалентна Тьюрингу проблема остановки .

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

Теорема о низком базисе утверждает, что каждое непустое учебный класс в (видеть арифметическая иерархия ) содержит набор низкая степень (Соаре 1987: 109). По определению это эквивалентно утверждению, что каждое бесконечное вычислимое поддерево двоичного дерева имеет бесконечный путь низкой степени.

Доказательство использует метод принуждения с помощью классы (Купер 2004: 330). Хайек и Кучера (1989) показали, что низкий базис доказуем в формальной системе арифметики, известной как .

Заявление

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

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

  • Кензер, Дуглас (1999). " занятия по теории вычислимости ". В Гриффоре, Эдвард Р. (ред.). Справочник по теории вычислимости. 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.