Computable function

Computable functions are the fundamental objects of study in computability theory. A function is considered computable if there exists an algorithm that can calculate its value for every valid input. In mathematics, a function often takes a tuple of natural numbers as an argument and produces a single natural number as an output. While the concept of an algorithm is intuitive, it lacks a single, precise definition. Therefore, mathematicians must use specific formal models of computation to define what is truly computable.

Several distinct models of computation have been proposed to provide this formal rigor. These include Turing machines, register machines, lambda calculus, and general recursive functions. Other models, such as post machines or tag machines, also exist. Although these models appear to be of a very different nature, they are mathematically equivalent. They all describe the exact same class of computable functions. This equivalence suggests that the concept of formal computability is a natural property of mathematics rather than an arbitrary invention.

To understand the mechanism of a computable function, one must look at the requirements of a procedure. According to scholars like Enderton, a procedure must consist of exact, finite instructions. This means the program must be a finite length and require no guessing or special insight. When the procedure receives an input within its domain, it must terminate after a finite number of discrete steps. If the input is not in the domain, the procedure may run forever or get stuck. However, it must never pretend to produce a value if the function is undefined for that input.

There are important distinctions regarding how these procedures operate in a theoretical sense. A computable procedure must be able to handle arbitrarily large arguments. It is not limited by physical constraints, such as the number of atoms in the Earth. While the procedure must halt to produce an output, there is no limit on how many steps it may take. Similarly, there is no bound on the amount of storage space the procedure might require. As long as additional storage can be provided, the computation can continue.

A central idea in this field is the Church–Turing thesis. This is an unprovable assertion regarding the limits of computation. It suggests that any notion of computability that can be imagined can only compute functions that are computable by the established models. This thesis links our intuitive understanding of calculation to formal mathematical models. It implies that no matter how advanced a machine becomes, it cannot exceed the logical bounds set by these fundamental functions.

It is vital to distinguish between effective computability and computational efficiency. A function is effectively calculable if an algorithm exists to solve it. However, this does not mean the function can be computed quickly. Some functions are so inefficient that their running time increases exponentially or even superexponentially as the input grows. The study of these time and space constraints is known as computational complexity theory. Within this field, researchers distinguish between function problems and decision problems, which only require a "yes" or "no" answer.

We can find many examples of computable functions in mathematical practice. Basic operations like addition and finding the greatest common divisor are computable. Even complex tasks, such as finding the smallest prime factor of a number, fall into this category. Interestingly, some functions are known to be computable even if we do not know the specific algorithm. For instance, a function based on the decimal expansion of pi might be computable even if we do not know if certain patterns exist within those digits. This highlights the deep connection between logic, possibility, and the limits of human knowledge.