Теорема о низком базисе - одна из нескольких теорем о базисе в теории вычислимости, каждая из которых показывает, что для бесконечного поддерева двоичного дерева, можно найти бесконечный путь по дереву с определенными свойствами вычислимости. Теорема о низком базисе, в частности, показывает, что должен быть путь с низким уровнем ; то есть скачок Тьюринга на пути эквивалентен проблеме остановки по Тьюрингу. .
Заявление и доказательство
Теорема о низком базисе утверждает, что каждое непустое класс в(см. арифметическую иерархию ) содержит набор низкой степени (Soare 1987: 109). По определению это эквивалентно утверждению, что каждое бесконечное вычислимое поддерево двоичного дерева имеет бесконечный путь низкой степени.
Доказательство использует метод принуждения с классы (Купер 2004: 330). Хайек и Кучера (1989) показали, что низкий базис доказуем в формальной системе арифметики, известной как.
Заявление
Одно из применений теоремы о низком базисе - построение дополнений эффективных теорий так, чтобы дополнения имели низкую степень Тьюринга. Например, из теоремы о низком базисе следует существование степеней PA строго ниже.
Рекомендации
- Кензер, Дуглас (1999). "классы по теории вычислимости » . В Гриффоре, Эдвард Р. (ред.). Справочник по теории вычислимости . Stud. Logic Found. Math. 140. North-Holland. pp. 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. DOI : 10.2307 / 2274871 . JSTOR 2274871 .
- Jockusch, Carl G., Jr .; Соаре, Роберт I. (1972). «Π (0, 1) Классы и степени теории» . Труды Американского математического общества . 173 : 33–56. DOI : 10,1090 / s0002-9947-1972-0316227-0 . ISSN 0002-9947 . JSTOR 1996 261 . 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 .