Content deleted Content added
m -/talk |
No edit summary |
||
Line 12:
More complex primitive recursive functions can be obtained by applying the [[operator]]s given by these axioms:
#''Composition'': Given ''f'', a ''k''-ary primitive recursive function, and ''k'' ''l''-ary primitive recursive functions ''g''<sub>0</sub>,...,''g''<sub>''k''-1</sub>, the [[composition]] of ''f'' with ''g''<sub>0</sub>,...,''g''<sub>''k''-1</sub>, i.e. the function ''h''(''x''<sub>0</sub>,...,''x''<sub>''l''-1</sub>) = ''f''(''g''<sub>0</sub>(''x''<sub>0</sub>,...,''x''<sub>''l''-1</sub>),...,''g''<sub>''k''-1</sub>(''x''<sub>0</sub>,...,''x''<sub>''l''-1</sub>)), is primitive recursive.
#''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.
| |||