PR (сложеност)

PR је класа сложености свих примитивних рекурзивних функција, или еквивалентно – скуп свих формалних језика који се могу определити таквом функцијом. То укључује сабирање, множење, степеновање, тетрацију итд. Акерманова функција је пример функције која није примитивно-рекурзивна, што показује да је PR строго садржан у R.

Са друге стране, можемо да „пребројимо“ сваки рекурзивно-пребројив скуп (погледај одговарајућу класу комплексности RE) помоћу примитивно-рекурзивне функције. Ово радимо на следећи начин: за задати улаз (M, k), где је M Тјурингова машина, а k цео број, ако се M заустви у оквиру k корака излаз је M. У осталим случајевима се на излазу не појављује ништа. Унија излаза за све могуће улазе (M, k) је тачно скуп машина M које се заустављају.

PR строго садржи ELEMENTARY.

Литература

• S. Barry Cooper (2004), Computability Theory, Chapman & Hall. ISBN 978-1-58488-237-4.
• Enderton, Herbert (2011). Computability Theory. Academic Press. ISBN 978-0-12-384-958-8.