Күріш – Шапиро теоремасы - Rice–Shapiro theorem

Жылы есептеу теориясы, Күріш – Шапиро теоремасы жалпылау болып табылады Күріш теоремасы, және атымен аталады Генри Гордон Райс және Норман Шапиро.[1]

Ресми мәлімдеме

Келіңіздер A ішінара-рекурсивті унардың жиынтығы болуы керек функциялары доменінде натурал сандар жиынтығы осындай болып табылады рекурсивті түрде санауға болады, қайда дегенді білдіреді а-да ішінара-рекурсивті функция Gödel нөмірлеу.

Онда кез-келген унарлы жартылай-рекурсивті функция үшін , Бізде бар:

ақырлы функция осындай

Берілген тұжырымда ақырлы функция - бұл ақырғы домені бар функция және бұл әрқайсысы үшін дегенді білдіреді оны ұстайды анықталған және тең .

Тиімді топологияның перспективасы

Кез келген ақырлы унарлы функция үшін бүтін сандарда, рұқсат етіңіз анықталған және келісілген барлық ішінара-рекурсивті функциялардың 'ашуын' белгілеңіз , бойынша домен.

Барлық ішінара-рекурсивті функциялар жиынтығын осы фруста жасаған топологиямен жабдықтаңыз негіз. Назар аударыңыз, кез-келген күйзеліс үшін , рекурсивті түрде санауға болады. Жалпы алғанда, бұл әр жиынтыққа арналған ішінара-рекурсивті функциялар:

iff рекурсивті түрде саналады бұл фустаның рекурсивті түрде есептелетін одағы.

Ескертулер

  1. ^ Кіші Роджерс, Хартли (1987). Рекурсивті функциялар теориясы және тиімді есептеу. MIT түймесін басыңыз. ISBN  0-262-68052-1.

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

  • Кутленд, Найджел (1980). Есептеу: рекурсивті функция теориясына кіріспе. Кембридж университетінің баспасы.; Теорема 7-2.16.
  • Кіші Роджерс, Хартли (1987). Рекурсивті функциялар теориясы және тиімді есептеу. MIT түймесін басыңыз. б. 482. ISBN  0-262-68052-1.
  • Одифредди, Пьерджорджо (1989). Классикалық рекурсия теориясы. Солтүстік Голландия.