Primitive recursive function: Difference between revisions

Revision as of 12:23, 30 May 2004

Revision as of 12:25, 30 May 2004

Line 31:

::add(S(''n''),''x'')=''S''(''P''₁³(add(''n'',''x''),''n'',''x''))

:Note that ''P''₀₁¹ is simply the [[identity function]]; its inclusion is required by the definition of the primitive recursion operator above; it plays the role of ''h''. The composition of ''S'' and ''P''₀₁³, which is primitive recursive, plays the role of ''g''.

;[[Subtraction]]: We can define ''limited subtraction'', i.e. subtraction that bottoms out at 0 (since we have no concept of negative numbers yet). First we must define the "predecessor" function, which acts as the opposite of the successor function.

Line 47:

:Now we can define subtraction in a very similar way to how we defined addition.

::sub(0,''x'')=''P''₀₁¹(''x'')

::sub(S(''n''),''x'')=pred(''P''₀₁³(sub(''n'',''x''),''n'',''x''))

:(Note that for the sake of simplicity, the order of the arguments has been switched from the "standard" definition to fit the requirements of primitive recursion, i.e. sub(''a'',''b'') corresponds to ''b''-''a''. This could easily be rectified using composition with suitable projections.)