General recursive function

In mathematical logic and computer science, a general recursive function is a special rule that helps us understand what computers can calculate.

These functions take numbers, like 1, 2, 3, and give back other numbers. Some always give an answer, called total recursive functions. Others might not always give an answer, called partial recursive functions.

These functions are important because they show which problems computers can solve. They match what can be done by Turing machines, an idea that helps us understand how computers work. This link is part of the Church–Turing thesis.

General recursive functions build on primitive recursive functions, but they can do more. One example is the Ackermann function. Other ways to think about computation include lambda calculus and Markov algorithms.

In studying how hard problems are for computers, the total recursive functions that give answers of 0 or 1 are part of the complexity class R. This helps scientists understand which problems are easy or hard for computers.

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. Using the minimization operator can make the definitions of these functions clearer and easier to understand.

Total recursive function

A total recursive function is a special type of general recursive function. It works for every possible input. We can calculate it using a total Turing machine.

We cannot always know for sure if a general recursive function will work for every input. This is related to the Halting problem.

Equivalence with other models of computability

In the study of computation, general recursive functions are closely related to 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, meaning 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 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. These rules help describe complex calculations using just one main idea. This main idea is like a key that unlocks the calculation.

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

Symbolism

Different symbols are used in books about this topic. Symbols can make it easier to write down complicated ideas in a short way.

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 returns one of the numbers you started with. For example, one kind of symbol always returns the third number from a list.
• 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.

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. In this sequence, each number is the sum of the two numbers before it. Another example is the McCarthy 91 function. This special function always returns the number 91 when given any number that is 101 or larger. These examples show how recursive functions can solve fun math problems.