Μ-recursive function

The class Pr of the μ - recursive functions or partial recursive functions plays in the recursion theory, a branch of theoretical computer science, an important role. According to the Church - Turing thesis describes the set of all functions that are computable in the intuitive sense. An important proper subset of the μ - recursive functions are the primitive recursive functions.

The class of μ - recursive functions is consistent with the class of Turing - computable functions as well as other equally powerful predictability models such as the lambda calculus, register machines and WHILE programs.

The primitive recursive functions from simple basic functions (constant 0 function, projections to an argument and successor function ) by composition and primitive recursion built. This always gives total functions, ie functions in the proper sense. The μ - recursive functions are partial functions other hand, can be formed of the same constructs, and in addition by the application of the μ - operator. By the application of the μ - operator is inserted partiality. However, not every μ - recursive function non-totally. 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 is the set of

Retained, that is the total of all such a way that at the location identical to 0 and disappears is also defined for all points.

It should be noted that, as a set of natural numbers has a minimum if and only if it is not empty. ( cf. well-ordering )

By applying the operator to now arises the partial function defined by:

In particular, the operator so one - digit partial function on one - digit partial function maps.

For predictable the program for the calculation of can be understood as a while loop that counts up, and therefore does not have to terminate:

Parameters:. Set on; As long as to increase; Result:. Definition of μ - recursive functions

The class of μ - recursive functions (from) includes the following basic functions:

The μ - recursive functions is obtained as the completion of basic functions concerning the three following operations:

Equivalence of μ - recursive functions with the Turing machine

It can be proved that a Turing Machine ( TM) can be simulated by μ - recursive functions. It can be demonstrated also that the amount of μ - recursive functions is exactly the set of Turing - computable functions.

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

One can show that the configuration of a TM can by three numbers represent. Just such a function ( a bijective mapping ) can be defined, which is a suitable encoding of the TM.

So let's assume a primitive recursive function

The appropriate coding of the TM provides for input by calculating steps,

And a second primitive recursive function

Which provides for an encoding as a result of 0 if a final state represents the TM, and otherwise 1

It then follows

The number of the steps required to calculate a TM to the end. So we get with

The calculation of the TM in a final state when typing.

Remark

• The predictability of a μ - recursive function refers to values ​​from their domain. There is no general method which returns all values ​​that do not belong to the domain of a μ - recursive function.
• The μ - operator implements a search process that if and aborts if the search value exists.

Examples

• All primitive recursive functions are μ - recursive.
• The Ackermann function and the Sudan function are total μ - recursive functions.
• The function Hardworking beaver (busy beaver ) is not μ - recursive.
• The sequence of the digits of the holding probability ( Chaitinsche constant) is not μ - recursive. Holding the probability is defined by, a retaining program and indicates the length of the program bits.