PA дәрежесі - PA degree

Математикалық өрісінде есептеу теориясы, а PA дәрежесі Бұл Тюринг дәрежесі толық кеңейтілуін есептейді Пеано арифметикасы (Джокуш 1987). Бұл дәрежелер бекітілген нүктесіз (DNR) функциялармен тығыз байланысты және рекурсия теориясында мұқият зерттелген.

Фон

Рекурсия теориясында, дегенді білдіреді есептелетін функция индексімен (бағдарлама) e есептелетін функциялардың кейбір стандартты нөмірлеуінде және дегенді білдіреді eжиынтығын пайдаланып есептелетін функция B натурал сандардың оракул ретінде

Жинақ A натурал сандар Тьюринг төмендейді жиынтыққа B егер бар болса есептелетін функция жиынтыққа арналған оракул берілген B, есептейді сипаттамалық функция χA жиынтықтың A. Яғни, бар e осындай . Бұл қатынас белгіленеді AТ B; қатынас relationТ Бұл алдын ала берілетін тапсырыс.

Натурал сандардың екі жиынтығы Тюринг баламасы егер әрқайсысы бір-біріне келтірілетін Тьюринг болса. Белгілеу AТ B көрсетеді A және B Тюринг эквиваленті болып табылады. The қатынасыТ - бұл Тюринг эквиваленттілігі деп аталатын эквиваленттік қатынас. A Тюринг дәрежесі - бұл натурал сандар жиынының жиынтығы, сондықтан коллекциядағы кез-келген екі жиын Тьюринг эквиваленті болады. Эквивалентті, Тюринг дәрежесі - бұл the қатынастың эквиваленттік класыТ.

Тюринг дәрежесі ішінара тапсырыс берді Тьюрингтің төмендеуі бойынша. Белгілеу аТ б дәреженің жиынтығы бар екенін көрсетеді б дәрежесін есептейді а. Эквивалентті, аТ б егер әрқайсысы орнатылған болса ғана ұстайды б әрбір жиынтығын есептейді а.

Функция f натурал сандардан натурал сандарға дейін дейді диагональ бойынша рекурсивті емес (DNR) егер, бәріне n, (мұнда теңсіздік егер анықтама бойынша орындалса анықталмаған). Егер f {0,1} жиынтығы f DNR болып табылады2 функциясы. Ешқандай DNR есептемейтін DNR функциялары бар екені белгілі2 функциясы.

Пеано арифметикасының аяқталуы

Аяқтау Пеано арифметикасы бұл Пеано арифметикасы тіліндегі формула жиынтығы, жиын бірінші ретті логикаға сәйкес келеді және әр формула үшін сол формула немесе оны терістеу жиынға енгізіледі. PA тіліндегі формулалардың Gödel нөмірленуін анықтағаннан кейін, PA-дың натурал сандар жиынтығымен аяқталуын анықтауға болады, осылайша осы толықтырулардың есептелетіндігі туралы айтуға болады.

Тюринг дәрежесі а деп анықталады PA дәрежесі егер Peano арифметикасының аяқталуын есептейтін дәрежеде натурал сандар жиынтығы болса. (Бұл дәреженің барлық жиынтығы ПА-ны аяқтайды деп болжауға тең.) ПА-ның есептелетін аяқталуы болмағандықтан, дәреже 0 натурал сандардың есептелетін жиынтығынан тұратын PA дәрежесі емес.

ПА тиімді бірінші ретті теория болғандықтан, ПА-ның аяқталуы белгілі бір есептелетін кіші ағаш арқылы өтетін шексіз жолдар ретінде сипатталуы мүмкін.. Осылайша, PA дәрежелері - бұл осы ағаш арқылы өтетін шексіз жолды есептейтін дәрежелер.

Қасиеттері

PA дәрежелері Тьюринг градусында жоғары жабылады: егер а PA дәрежесі және аТ б содан кейін б PA дәрежесі.

Тюринг дәрежесі 0‘, Бұл дәрежесі мәселені тоқтату, PA дәрежесі. Сондай-ақ, жоғары емес PA дәрежелері бар 0‘. Мысалы, төмен негіздік теорема PA деңгейінің төмен екендігін білдіреді. Басқа жақтан, Антонин Кучера -дан төмен дәреже бар екенін дәлелдеді 0‘Бұл DNR функциясын есептейді, бірақ PA дәрежесі емес (Jockusch 1989: 197).

Карл Джокуш және Роберт Соар (1972) PA дәрежелерінің дәл DNR дәрежелері екенін дәлелдеді2 функциялары.

Анықтама бойынша, егер Пеано арифметикасының аяқталу ағашынан өтетін жолды есептеген жағдайда ғана дәреже PA болып табылады. Мықты қасиет: дәреже а PA дәрежесі болып табылады және егер болса а арқылы өтетін жолды есептейді әрқайсысы шексіз есептелетін кіші ағаш (Симпсон 1977).

Арслановтың толықтығы критерийі

М.М.Арсланов сипаттама берді, с.е. жиынтықтар толық (яғни Тьюринг баламасы ). C.e. үшін орнатылды , егер және егер болса DNR функциясын есептейді. Атап айтқанда, әрбір PA дәрежесі - DNR2 және, демек, DNR, сондықтан жалғыз б.э.д. PA дәрежесі.

Сондай-ақ қараңыз

Пайдаланылған әдебиеттер

  • Карл Джокуш (1987), «Белгіленген нүктелері жоқ функциялар дәрежесі», Логикалық коллоквиум '87, Фенстад, Фролов және Хилпинен, эд., Солтүстік Голландия, ISBN  0-444-88022-4
  • Карл Джокуш пен Роберт Соар (1972), «Π01 теориялар кластары мен дәрежелері », Американдық математикалық қоғамның операциялары, т. 173, 33-56 бб.
  • Стивен Дж. Симпсон (1977), «Шешілмейтін дәрежелер: нәтижелерге шолу», Математикалық логиканың анықтамалығы, Barwise (ред.), Солтүстік-Голландия, 631–652 бб. ISBN  0-444-86388-5