μ-recursion

The class Pr of the μ-recursive functions or partially recursive functions plays an important role in recursion theory , a branch of theoretical computer science ( µ for the Greek μικρότατος , “the smallest”). According to the Church-Turing thesis , it describes the set of all functions that can be calculated in the intuitive sense . An important real subset of the μ-recursive functions are the primitive recursive functions .

The class of μ-recursive functions corresponds to the class of Turing-computable functions as well as other equally powerful computability models such as the lambda calculus , register machines and WHILE programs .

The primitive recursive functions are made up of simple basic functions (constant 0 function, projections onto an argument and successor function) through composition and primitive recursion. This always gives total functions, i.e. functions in the real sense. The μ-recursive functions, on the other hand, are partial functions that can be formed from the same constructs and additionally by using the μ operator. Using the μ operator introduces partiality. However, not every μ-recursive function is non-total. For example, all primitive recursive functions are also μ-recursive. An example of a non-primitive recursive, total, μ-recursive function is the Ackermann function .

Definition of the μ operator

For a partial function and natural numbers, let the set ${\displaystyle f\colon \mathbb {N} ^{k+1}\to \mathbb {N} }$ ${\displaystyle x_{1};\dots ;x_{k}\in \mathbb {N} }$

${\displaystyle M(f,x_{1},\dots ,x_{k})=\{n\in \mathbb {N} \mid f(x_{1},\dots ,x_{k},n)=0\ \land \ \forall 0\leq m\leq n\colon f(x_{1},\dots ,x_{k},m)\downarrow \}}$

retained, so the entirety of all , such that at the location is identically 0, and in addition for all points with defined. ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle (x_{1},\dots ,x_{k},n)}$ ${\displaystyle (x_{1},\dots ,x_{k},m)}$ ${\displaystyle m\leq n}$

It should be noted that the set of natural numbers has a minimum if and only if it is not empty. (see well-being ) ${\displaystyle M(f,x_{1},\dots ,x_{k})}$

Applying the operator to the result is the partial function defined by: ${\displaystyle \mu }$ ${\displaystyle f}$ ${\displaystyle \mu f\colon \mathbb {N} ^{k}\to \mathbb {N} }$

${\displaystyle \mu f(x_{1},\dots ,x_{k})={\begin{cases}\min M(f,x_{1},\dots ,x_{k})&{\mbox{falls }}M(f,x_{1},\dots ,x_{k})\not =\emptyset \\{\mbox{undefiniert}}&{\mbox{sonst}}\\\end{cases}}}$

In particular, the operator maps a -digit partial function to a -digit partial function. ${\displaystyle \mu }$ ${\displaystyle (k+1)}$ ${\displaystyle k}$

For calculable things , the program for calculating can be understood as a while loop that counts up and therefore does not have to terminate : ${\displaystyle f}$ ${\displaystyle \mu f}$

Parameter:  ${\displaystyle x_{1},...,x_{k}}$.
Setze  ${\displaystyle n}$ auf  ${\displaystyle 0}$;
Solange  ${\displaystyle f(x_{1},\dots ,x_{k},n)\not =0}$ erhöhe  ${\displaystyle n}$ um  ${\displaystyle 1}$;
Ergebnis:  ${\displaystyle n}$.

Definition of the μ-recursive functions

The class of μ-recursive functions (of ) comprises the following basic functions: ${\displaystyle Pr}$ ${\displaystyle \mathbb {N} ^{k}\to \mathbb {N} }$

1. constant 0 function: ${\displaystyle f^{k}\left(n_{1},\dots ,n_{k}\right):=0}$
2. Projection on one argument: , ${\displaystyle \pi _{i}^{k}\left(n_{1},\dots ,n_{k}\right):=n_{i}}$ ${\displaystyle 1\leq i\leq k}$
3. Successor function: ${\displaystyle \nu \left(n\right):=n+1}$

The μ-recursive functions are obtained as the conclusion of the basic functions with regard to the following three operations:

1. The composition: if ${\displaystyle f\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)}$ ${\displaystyle g,h_{1},\dots ,h_{m}\in Pr}$
2. The primitive recursion: and , if ${\displaystyle f\left(0,n_{2},\dots ,n_{k}\right):=g\left(n_{2},\dots ,n_{k}\right)}$ ${\displaystyle f\left(n_{1}+1,n_{2},\dots ,n_{k}\right):=h\left(f\left(n_{1},\dots ,n_{k}\right),n_{1},\dots ,n_{k}\right)}$ ${\displaystyle h,g\in Pr}$
3. The μ operator.

Equivalence of the μ-recursive functions with the Turing machine

It can be proven that a Turing machine (TM) can be simulated by μ-recursive functions. It can also be shown that the set of μ-recursive functions corresponds exactly to the set of Turing-computable functions.

Proof sketch for the simulation of the TM with μ-recursive functions

One can show the configuration of a TM that by three numbers , , can be represented. This is exactly how a function (a bijective mapping ) can be defined, which is a suitable coding of the TM. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle h(a,b,c)=y}$ ${\displaystyle \mathbb {N} ^{3}\to \mathbb {N} }$

So let's take a primitive recursive function

${\displaystyle f(n,x)=y}$,

which provides a suitable coding of the TM for the input according to calculation steps, ${\displaystyle x}$ ${\displaystyle n}$

and a second primitive recursive function

${\displaystyle g(y)=0\lor g(y)=1}$,

which returns 0 as a result for a coding if it represents a final state of the TM, and 1 otherwise. ${\displaystyle y}$ ${\displaystyle y}$

Then results

${\displaystyle \mathrm {Anzahl} (x)=\mu (g(f(n,x)))}$

the number of steps a TM takes to complete the calculation. So we get along

${\displaystyle \mathrm {Berechnung} (x)=f(\mathrm {Anzahl} (x),x)}$

the calculation of the TM in a final state when entering . ${\displaystyle x}$

comment

• The calculability of a μ-recursive function relates to values ​​from its domain. There is no general procedure that returns all values ​​that do not belong to the domain of a μ-recursive function.
• The μ-operator realizes a search process that terminates exactly when the searched value exists.

Examples

• All primitive recursive functions are μ-recursive.
• The Ackermann function and the Sudan function are total μ-recursive functions that are not primitive-recursive.
• The function Hardworking Beavers (busy beaver) is recursive μ-not.
• The sequence of digits of the holding probability ( Chaitin's constant ) is not μ-recursive. The holding probability is defined by , where is a holding program and denotes the length of the program in bits . ${\displaystyle \Omega }$ ${\displaystyle \Omega :=\sum _{p}2^{-\left|p\right|}}$ ${\displaystyle p}$ ${\displaystyle \left|p\right|}$

literature

• Heinz-Dieter Ebbinghaus , Jörg Flum, Wolfgang Thomas: Introduction to mathematical logic (= spectrum university paperback. ). 4th edition. Spectrum - Akademischer Verlag, Heidelberg et al. 1996, ISBN 3-8274-0130-5 .
• Hans Hermes : Enumerability, decidability, predictability. Introduction to the theory of recursive functions (= Heidelberger Taschenbücher. 87). 2nd Edition. Springer, Berlin et al. 1971, ISBN 3-540-05334-4 .
• Arnold Oberschelp : Recursion Theory. BI-Wissenschaftlicher-Verlag, Mannheim et al. 1993, ISBN 3-411-16171-X .
• Wolfgang Rautenberg : Introduction to Mathematical Logic. A textbook . 3rd, revised edition. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2 .