General recursive function

In mathematical logic and computer science, a general recursive function is a special kind of rule that helps us understand what can be calculated by computers. These functions take natural numbers—like 1, 2, 3—and give back other natural numbers. Some of these functions always give an answer for any input, and these are called total recursive functions. Others might not always give an answer, and these are called partial recursive functions.

These functions are very important because they show us exactly which problems can be solved by computers. In fact, they match what can be done by Turing machines, a simple idea that helps us understand how computers work. This connection is a big part of something called the Church–Turing thesis.

General recursive functions build on another idea called primitive recursive functions, but they can do more. One famous example that is a total recursive function but not a primitive recursive function is the Ackermann function. There are also other ways to think about what can be computed, like using lambda calculus or Markov algorithms.

In the study of how hard problems are for computers, the total recursive functions that only give answers of 0 or 1 are part of a group called the complexity class R. This helps computer scientists understand which problems are easy or hard for computers to solve.

Definition

The μ-recursive functions (or general recursive functions) are special types of functions that take in numbers and give out numbers. They are important because they help us understand what kinds of problems computers can solve.

These functions are built using a few basic rules:

• Basic functions like always returning a fixed number, adding one to a number, or picking out one number from a list.
• Combining functions together in steps, like doing one function and then using its result in another.
• Repeating a calculation many times, step by step.
• Searching for the first number that makes a certain condition true.

These ideas show how many different calculations can be done step by step, which is a key part of how computers work.

Examples

Some examples of general recursive functions are shown in the article on Primitive recursive function#Examples. These examples show how the minimization operator is used to create functions that cannot be defined as primitive recursive functions. While these functions could sometimes be defined in more complex ways without the minimization operator, it helps make their definitions clearer and easier to understand.

Total recursive function

A total recursive function is a special kind of general recursive function that works for every possible input. It can be calculated by a total Turing machine. Importantly, there is no way to know for sure whether a general recursive function will work for every input—this is linked to the Halting problem.

Equivalence with other models of computability

In the study of how we can understand computation, there is a special connection between general recursive functions and Turing machines. A Turing machine is a theoretical device that can simulate any computer algorithm. Sometimes, a Turing machine might run forever on certain inputs, which means it cannot give a result for those inputs. This is similar to how some recursive functions do not give a clear answer for certain numbers.

The rules that define basic recursive functions cannot create processes that run without stopping. This shows that general recursive functions and Turing machines share the same abilities and limits when it comes to solving problems with numbers.

Normal form theorem

A normal form theorem by Kleene explains that for any group of inputs, there are special math rules that help describe complex calculations using just one main idea. This main idea acts like a key that unlocks the calculation.

This idea is similar to a universal Turing machine, which is a smart way to handle many different tasks by following set rules. Creating this idea takes effort and thought, much like building a machine that can solve many problems on its own.

Symbolism

Different symbols are used in books about this topic. One reason to use symbols is that they can make it easier to write down complicated ideas in a short way by nesting them inside each other.

There are several important symbols:

• Constant function: This gives the same number no matter what numbers you start with. For example, one kind of symbol always gives the number 13.
• Successor function: This adds one to a number. For example, starting from zero, the first use of this gives one, the next gives two, and so on.
• Identity function: This simply returns one of the numbers you started with. For example, one kind of symbol always returns the third number from a list of seven numbers.
• Composition (Substitution) operator: This lets you combine smaller functions into a bigger one.
• Primitive Recursion: This is a way to build up more complicated functions by repeating a simple pattern, like adding one number to another by starting from zero and counting up.

These symbols help mathematicians and computer scientists describe how to perform calculations step by step.

Examples

Some well-known examples of recursive functions include the Fibonacci number, which is a sequence where each number is the sum of the two preceding ones, and the McCarthy 91 function, a special function that always returns the number 91 when given any number greater than or equal to 101. These examples help show how recursive functions can solve interesting mathematical problems.