Content deleted Content added
m Therfore -> Therefore |
No edit summary |
||
Line 15:
#''Primitive recursion'': Given ''f'' a ''k''-ary primitive recursive function and ''g'' a (''k''+2)-ary primitive recursive function, the (''k''+1)-ary function defined as the primitive recursion of ''f'' and ''g'', i.e. the function ''h'' where ''h''(0,''x''<sub>0</sub>,...,''x''<sub>''k''-1</sub>) = ''f''(''x''<sub>0</sub>,...,''x''<sub>''k''-1</sub>) and ''h''(''S''(''n''),''x''<sub>0</sub>,...,''x''<sub>''k''-1</sub>) = ''g''(''h''(''n'',''x''<sub>0</sub>,...,''x''<sub>''k''-1</sub>),''n'',''x''<sub>0</sub>,...,''x''<sub>''k''-1</sub>), is primitive recursive.
(Note that the projection functions allow us to get around the apparent rigidity in terms of the [[arity]] of the functions above, as via composition we can pass any subset of the arguments.)
A function is primitive recursive if it is one of the basic functions above, or can be obtained from one of the basic functions by applying the operations a finite number of times.
| |||