Primitive recursive function: Difference between revisions

Revision as of 20:03, 4 January 2025

Revision as of 20:04, 4 January 2025

Line 13:

{{ordered list|start=1

|1=''Constant functions <math>C_n^k</math>'': For each natural number <math>n</math> and every <math>k</math>, the ''k''-ary constant function, defined by <math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ n</math>, is primitive recursive.{{efn|It is also sufficient to instead define ''zero functions'' <math>0^k</math>, which for any <math>k</math>-ary input returns <math>0^k(x_1, \ldots, x_k) = 0</math>, as primitive recursive. <br/><br/>

Any constant function may then be formed from finite applications of the primitive recursive functions <math>(S, 0^k, \circ)</math>: <math>C_n^k = \underbrace{S \circ S \circ \ldots S}_n \circ 0^k</math>.}}

| 2=''Successor function'': The 1-ary successor function ''S'', which returns the successor of its argument (see [[Peano postulates]]), that is, <math>S(x) \ \stackrel{\mathrm{def}}{=}\ x + 1</math>, is primitive recursive.