Төмен негіздік теорема - Low basis theorem - Wikipedia

Төмен негіздік теорема - солардың бірі теоремалар есептеу теориясында, олардың әрқайсысы екілік ағаштың шексіз кіші ағашын беретіндігін көрсетеді , ағаш арқылы ерекше есептеу қасиеттерімен шексіз жолды табуға болады. Төмен негіздік теорема, атап айтқанда, болатын жолдың болуын көрсетеді төмен; яғни Тюрингтен секіру жолының Тюринг эквиваленті мәселені тоқтату .

Мәлімдеме және дәлелдеме

Төмен негіздік теоремада әрбір бос емес екендігі айтылған сынып жылы (қараңыз арифметикалық иерархия ) жиынтығын қамтиды төмен дәреже (Soare 1987: 109). Бұл анықтама бойынша екілік ағаштың әр шексіз есептелетін кіші ағашы деген тұжырымға балама төменгі дәрежедегі шексіз жолға ие.

Дәлелдеуде мәжбүрлеу әдісі қолданылады сыныптар (Cooper 2004: 330). Хажек пен Кучера (1989) төмен деңгейдің ресми арифметикалық жүйеде дәлелденетінін көрсетті .

Қолдану

Төмен негіздік теореманың бір қолданылуы - тиімді теориялардың аяқталуын Тюринг дәрежесі төмен болатындай етіп құру. Мысалы, төменгі базалық теорема бар болуын білдіреді PA дәрежесі қатаң төменде .

Әдебиеттер тізімі

  • Цензер, Дуглас (1999). " есептеу теориясындағы сабақтар «. Гриффорда, Эдвард Р. (ред.) Есептеу теориясының анықтамалығы. Асыл тұқымды. Логика табылды. Математика. 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.
  • Джокуш, Карл Дж., Кіші .; Soare, Роберт I. (1972). «Π (0, 1) теориялар мен дәрежелер». Американдық математикалық қоғамның операциялары. 173: 33–56. дои:10.1090 / s0002-9947-1972-0316227-0. ISSN  0002-9947. JSTOR  1996261. Zbl  0262.02041. Қосымша нақтылайтын прозаны қоса алғанда, түпнұсқа басылым.
  • Nies, André (2009). Есептеу және кездейсоқтық. Оксфордтың логикалық нұсқаулықтары. 51. Оксфорд: Оксфорд университетінің баспасы. ISBN  978-0-19-923076-1. Zbl  1169.03034. Теорема 1.8.37.
  • Soare, Роберт I. (1987). Рекурсивті түрде есептелетін жиынтықтар мен дәрежелер. Есептелетін функциялар мен есептелетін жинақталған жиынтықтарды зерттеу. Математикалық логиканың перспективалары. Берлин: Шпрингер-Верлаг. ISBN  3-540-15299-7. Zbl  0667.03030.