PR (сложеност)
PR је класа сложености свих примитивних рекурзивних функција, или еквивалентно – скуп свих формалних језика који се могу определити таквом функцијом. То укључује сабирање, множење, степеновање, тетрацију итд. Акерманова функција је пример функције која није примитивно-рекурзивна, што показује да је PR строго садржан у R.[1]
Са друге стране, можемо да „пребројимо“ сваки рекурзивно-пребројив скуп (погледај одговарајућу класу комплексности RE) помоћу примитивно-рекурзивне функције. Ово радимо на следећи начин: за задати улаз (M, k), где је M Тјурингова машина, а k цео број, ако се M заустви у оквиру k корака излаз је M. У осталим случајевима се на излазу не појављује ништа. Унија излаза за све могуће улазе (M, k) је тачно скуп машина M које се заустављају.
PR строго садржи ELEMENTARY.
Референце уреди
- ^ Cooper 2004, стр. 88.
Литература уреди
- 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.