PR (složenost)
PR je klasa složenosti svih primitivnih rekurzivnih funkcija, ili ekvivalentno – skup svih formalnih jezika koji se mogu opredeliti takvom funkcijom. To uključuje sabiranje, množenje, stepenovanje, tetraciju itd. Akermanova funkcija je primer funkcije koja nije primitivno-rekurzivna, što pokazuje da je PR strogo sadržan u R.[1]
Sa druge strane, možemo da „prebrojimo“ svaki rekurzivno-prebrojiv skup (pogledaj odgovarajuću klasu kompleksnosti RE) pomoću primitivno-rekurzivne funkcije. Ovo radimo na sledeći način: za zadati ulaz (M, k), gde je M Tjuringova mašina, a k ceo broj, ako se M zaustvi u okviru k koraka izlaz je M. U ostalim slučajevima se na izlazu ne pojavljuje ništa. Unija izlaza za sve moguće ulaze (M, k) je tačno skup mašina M koje se zaustavljaju.
PR strogo sadrži ELEMENTARY.
Reference uredi
- ^ Cooper 2004, str. 88.
Literatura uredi
- 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.