Primitive recursive function

Primitive recursive functions are total functions that can be formed from simple basic functions (constant 0 function, projections onto an argument and successor function) through composition and (primitive) recursion. The primitive recursion can be traced back to Richard Dedekind's 126th theorem in What are and what are the numbers? (1888). The primitive recursive arithmetic goes back to Thoralf Skolem (1923). The term primitive recursive function was coined by the Hungarian mathematician Rózsa Péter . Primitive recursive functions play in recursion theory , a branch oftheoretical computer science , a role. They occur in connection with the explication of the concept of predictability .

All primitive recursive functions can be calculated in the intuitive sense. But they do not exhaust all intuitively calculable functions, examples are the Ackermann function and the Sudan function , which are both calculable but not primitive-recursive. A complete understanding of the concept of calculability is only possible with the µ-recursive functions .

For primitive recursive functions it is possible to define a complexity measure, i. That is, the duration of the calculation of one of its function values ​​can be determined in advance.

The class of the primitive recursive functions and the LOOP computable (see LOOP program ) functions are equivalent.

definition

1. For any one the k-digit 0-function is defined by . ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle 0^{k}\colon \mathbb {N} ^{k}\to \mathbb {N} }$ ${\displaystyle 0^{k}\left(n_{1},\dots ,n_{k}\right):=0}$
2. For any and any , the k-digit projection onto the i-th parameter is defined by . ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle 1\leq i\leq k}$ ${\displaystyle \pi _{i}^{k}\colon \mathbb {N} ^{k}\to \mathbb {N} }$ ${\displaystyle \pi _{i}^{k}\left(n_{1},\dots ,n_{k}\right):=n_{i}}$
3. The successor function is defined by . ${\displaystyle \nu \colon \mathbb {N} \to \mathbb {N} }$ ${\displaystyle \nu \left(n\right):=n+1}$
4. For any , the composition of a function with m functions is defined as the function with . ${\displaystyle k,m\in \mathbb {N} }$ ${\displaystyle g\colon \mathbb {N} ^{m}\to \mathbb {N} }$ ${\displaystyle h_{1},\dots ,h_{m}\colon \mathbb {N} ^{k}\to \mathbb {N} }$ ${\displaystyle C[g,h_{1},\dots ,h_{m}]\colon \mathbb {N} ^{k}\to \mathbb {N} }$ ${\displaystyle C[g,h_{1},\dots ,h_{m}]\left(n_{1},\dots ,n_{k}\right):=g\left(h_{1}\left(n_{1},\dots ,n_{k}\right),\dots ,h_{m}\left(n_{1},\dots ,n_{k}\right)\right)}$
5. For any one is the primitive recursion of two functions and is defined as the function with ${\displaystyle k\in \mathbb {N} \setminus \{0\}}$ ${\displaystyle g\colon \mathbb {N} ^{k-1}\to \mathbb {N} }$ ${\displaystyle h\colon \mathbb {N} ^{k+1}\to \mathbb {N} }$ ${\displaystyle R[g,h]\colon \mathbb {N} ^{k}\to \mathbb {N} }$

${\displaystyle R[g,h]\left(n_{1},n_{2},\dots ,n_{k}\right):={\begin{cases}g\left(n_{2},\dots ,n_{k}\right),&{\mbox{falls }}n_{1}=0\\h\left(R[g,h]\left(n_{1}-1,n_{2},\dots ,n_{k}\right),n_{1}-1,n_{2},\dots ,n_{k}\right),&{\mbox{sonst.}}\end{cases}}}$

The set of primitive recursive functions is then defined as the smallest set which contains all null functions, all projections and the successor function, and which is closed under composition and primitive recursion. In more everyday terms this means: A function is primitive-recursive if and only if it can be written down as an expression using the means mentioned. Functions that have already been proven to be primitive-recursive may appear in the expression, because they can be eliminated by inserting their expression. ${\displaystyle Pr}$

Every k-place primitive recursive function is in particular always completely defined. Functions with a smaller domain must first be appropriately continued to completely in order to obtain primitive-recursive functions. ${\displaystyle \mathbb {N} ^{k}}$ ${\displaystyle \mathbb {N} ^{k}}$

Examples

addition

The addition is defined recursively by ${\displaystyle +\colon \mathbb {N} ^{2}\to \mathbb {N} }$

${\displaystyle m+n={\begin{cases}n,&{\mbox{falls }}m=0,\\((m-1)+n)+1,&{\mbox{sonst}}\end{cases}}}$

for everyone . It is therefore true that the addition is primitive-recursive. ${\displaystyle m,n\in \mathbb {N} }$ ${\displaystyle +=R[\pi _{1}^{1},C[\nu ,\pi _{1}^{3}]]}$

multiplication

The multiplication is defined recursively via the addition: ${\displaystyle \cdot \colon \mathbb {N} ^{2}\to \mathbb {N} }$

${\displaystyle m\cdot n={\begin{cases}0,&{\mbox{falls }}m=0,\\(m-1)\cdot n+n,&{\mbox{sonst}}\end{cases}}}$

for everyone . The multiplication is primitive-recursive because it holds . ${\displaystyle m,n\in \mathbb {N} }$ ${\displaystyle \cdot =R[0^{1},C[+,\pi _{1}^{3},\pi _{3}^{3}]]}$

power

The power with the meaning is defined recursively via the multiplication: ${\displaystyle pot\colon \mathbb {N} ^{2}\to \mathbb {N} }$ ${\displaystyle pot(m,n)=m^{n}}$

${\displaystyle pot(m,n)={\begin{cases}1,&{\mbox{falls }}n=0,\\pot(m,n-1)*m,&{\mbox{sonst}}\end{cases}}}$

for everyone . The power is primitive-recursive because it holds . The purpose of the context here is to swap the two parameters m and n with one another. ${\displaystyle m,n\in \mathbb {N} }$ ${\displaystyle pot=C[R[C[\nu ,0^{1}],C[*,\pi _{1}^{3},\pi _{3}^{3}]],\pi _{2}^{2},\pi _{1}^{2}]}$ ${\displaystyle C[\_,\pi _{2}^{2},\pi _{1}^{2}]}$

Predecessor function

The predecessor function is not defined at position 0. So it is not primitive recursive. However, by continuing at the position 0, for example with the value 0, a primitive recursive function can be made out of it.

The modified predecessor function , defined by ${\displaystyle p\colon \mathbb {N} \to \mathbb {N} }$

${\displaystyle p(n):={\begin{cases}0,&{\mbox{falls }}n=0,\\n-1,&{\mbox{sonst}}\end{cases}}}$

for all is primitive-recursive, because it holds . ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle p=R[0^{0},\pi _{2}^{2}]}$

subtraction

Subtraction is also not defined on all pairs of natural numbers. So you continue the subtraction by padding with zeros to whole . This total subtraction can be characterized recursively by ${\displaystyle \mathbb {N} ^{2}}$ ${\displaystyle sub\colon \mathbb {N} ^{2}\to \mathbb {N} }$

${\displaystyle sub(m,n)={\begin{cases}m,&{\mbox{falls }}n=0,\\p(sub(m,n-1)),&{\mbox{sonst}}\end{cases}}}$

for everyone . The following applies to the total subtraction ; so it is primitive-recursive. This modified difference is also called the arithmetic difference . ${\displaystyle m,n\in \mathbb {N} }$ ${\displaystyle sub=C[R[\pi _{1}^{1},C[p,\pi _{1}^{3}]],\pi _{2}^{2},\pi _{1}^{2}]}$

Further examples

• The two-digit functions and are primitively recursive. ${\displaystyle \max }$ ${\displaystyle \min }$
• The sequence of prime numbers is a primitive recursive function.
• The function that finds the number of prime factors of in for a natural number and a prime number is primitive recursive. ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle n}$
• There are primitive recursive arithmetic operations of finite sequences of natural numbers.
• The Ackermann function and the Sudan function are not primitive recursive, but µ-recursive .
• The function Hardworking Beavers (busy beaver) is not primitive recursive and non- recursive μ- .

See also

• µ recursion
• Turing machine

literature

• Hans Hermes : Enumerability, decidability, predictability . 2nd Edition. Springer Berlin, Heidelberg, New York, 1971, ISBN 3-540-05334-4 .
• Heinz-Dieter Ebbinghaus , Jörg Flum, Wolfgang Thomas: Introduction to mathematical logic . 4th edition. Spectrum, Academic Publishing House, Heidelberg a. a. 1996, ISBN 3-8274-0130-5 ( university paperback ).
• Arnold Oberschelp : Recursion Theory . BI-Wissenschaftlicher-Verlag, Mannheim u. a. 1993, ISBN 3-411-16171-X .
• Wolfgang Rautenberg : Introduction to Mathematical Logic . 3. Edition. Vieweg + Teubner , Wiesbaden , ISBN 978-3-8348-0578-2 .

Individual evidence

1. ↑ Peter Schroeder-Heister , Mathematical Logic II (Gödel's incompleteness theorems), script, p. 39