A class of total functions is a PRC class if:

  1. The class includes all projection functions $p_i(x_1,\ldots,x_n) = x_i$ and the initial functions $n(x) = 0$ and $s(x) = x+1$.
  2. The class is closed under composition and primitive recursion.

Prove that the class of all total functions is a PRC class.

Is it true if I say every total function is computable? And then say because the class of computable functions is a PRC class, so is the class of total functions.

  • $\begingroup$ Not every total function is computable. $\endgroup$ – Yuval Filmus May 15 '20 at 11:21
  • $\begingroup$ The exercise is much simpler. The closure operations in the definition of a PRC class all trivially hold for the class fo all functions. $\endgroup$ – Yuval Filmus May 15 '20 at 11:22
  • $\begingroup$ Perhaps you can include the definition of PRC class (I had to look it up). $\endgroup$ – Yuval Filmus May 15 '20 at 11:22
  • $\begingroup$ @YuvalFilmus The PRC class definition : We call a class of total functions a PRC class if: 1. It includes initial functions 2. It is close under composition and recursion $\endgroup$ – Z.Gh May 15 '20 at 11:28
  • $\begingroup$ @YuvalFilmus the initial functions are S(x) = x+1 n(x) =0. And the projection functions $\endgroup$ – Z.Gh May 15 '20 at 11:29

You cannot say that every total function is computable, since that is not true. For example, the function $f(n)$ which returns $1$ if the $n$'th Turing machine halts and $0$ otherwise is not computable.

However, the question is much simpler. The definition of a PRC class specifies several closure properties, of the form: if so-and-so belong to the class, then such-and-such also belongs to the class (these include the "axioms", in which the premise is empty). Since the class of all (total) functions contains all functions, it automatically satisfies these constraints.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.