# All total functions form a PRC class

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.

• Not every total function is computable. – Yuval Filmus May 15 '20 at 11:21
• The exercise is much simpler. The closure operations in the definition of a PRC class all trivially hold for the class fo all functions. – Yuval Filmus May 15 '20 at 11:22
• Perhaps you can include the definition of PRC class (I had to look it up). – Yuval Filmus May 15 '20 at 11:22
• @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 – Z.Gh May 15 '20 at 11:28
• @YuvalFilmus the initial functions are S(x) = x+1 n(x) =0. And the projection functions – 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.