PR is defined as "the complexity class of all primitive recursive functions" and also equivalently as "the set of all formal languages that can be decided by such a function". (wiki:http://en.wikipedia.org/wiki/PR_(complexity))

Unfortunately I fail to understand, why these two are equivalent?

  • 1
    $\begingroup$ Probably completey answered by our reference question -- community votes? $\endgroup$ – Raphael Mar 4 '15 at 17:45
  • $\begingroup$ As far as I understand, the latter is a set of decision problems, while the former consists of function problems? $\endgroup$ – hatero Mar 5 '15 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.