General recursive function

In mathematical logic and computer science, a general recursive function is a tool for describing what can be computed. These functions take natural numbers as inputs and return a single natural number as an output. They are often called μ-recursive functions. A key distinction exists between partial and total functions. A partial recursive function might not provide an answer for every input. If the process never ends, the function is considered undefined for that input. However, if a function provides a valid result for every possible input, it is called a total recursive function. In computational complexity theory, the set of all total recursive functions is known as the complexity class R.

To understand how these functions work, we must look at how they are built from simple parts. The system starts with a set of initial functions. These include constant functions, which always return a specific number. The successor function is another building block; it simply finds the next number in a sequence. We also use projection functions, which are also known as identity functions. These functions allow us to pick out specific values from a group of numbers. By using these basic ingredients, we can construct much more complex mathematical rules.

There are three main operators used to combine these initial functions. The first is the composition operator, or substitution operator. This allows us to take one function and plug it into another. The second is the primitive recursion operator. This operator allows us to build new functions by repeating steps in a structured way. The third and most powerful tool is the minimization operator, often called the μ-operator. This operator performs an unbounded search. It starts at zero and counts upward to find the smallest number that makes a specific condition true. If the search never finds a result, the function remains undefined.

These operators create a hierarchy of mathematical complexity. The smallest class of functions built from the initial functions using only composition and primitive recursion is the class of primitive recursive functions. All primitive recursive functions are total, meaning they always produce an answer. However, the class of general recursive functions is much larger. General recursive functions include the primitive recursive ones but also add the power of the minimization operator. This addition allows for functions that can simulate infinite loops. Because of this, some general recursive functions are partial rather than total.

History shows that several different mathematical models arrived at the same conclusion. Alan Turing introduced the concept of Turing machines to define computation. Around the same time, Alonzo Church introduced lambda calculus. It was discovered that μ-recursive functions, Turing-computable functions, and lambda-definable functions are all equivalent. This means they all describe the exact same set of computable processes. This discovery is a major part of the Church-Turing thesis. It suggests that our mathematical definition of computation matches what a physical machine can actually do.

One famous example of the gap between these function classes is the Ackermann function. The Ackermann function is a total recursive function, so it always provides an answer. However, it is not a primitive recursive function. It grows much too quickly to be captured by the rules of primitive recursion alone. Another important result is Kleene's normal form theorem. This theorem states that any μ-recursive function can be expressed using just one instance of the minimization operator. This is applied to a total primitive recursive function. This result is similar to the concept of a universal Turing machine.

Understanding these functions helps scientists explore the limits of logic. There is no way to computably determine if a given general recursive function is total. This difficulty is closely linked to the famous Halting problem. We can use a strong equality relation to compare two partial functions. This relation holds if both functions are defined and equal, or if both are undefined. By studying these mathematical structures, researchers in computability theory can map the boundaries of what is possible to calculate in our universe.