Computable & Non-Computable Functions - Theory of Computation - Computer Science

Computable Functions

Computable functions are the central objects of study in the theory of computation. Informally, a function is computable if there exists a mechanical procedure (an algorithm) that, given suitable inputs, produces the function's output after a finite number of steps. In formal models this is usually expressed by the existence of a Turing machine that, on any input from the function's domain, halts and outputs the corresponding value.

Formal notions

A function f that takes k natural numbers as arguments is written as f(n₁, n₂, ..., n_k). Two important formal classes are distinguished:

• Partial computable (partial recursive) functions: functions for which there exists a Turing machine that, on every input in the function's domain, halts and outputs the value f(x). For inputs not in the domain the machine either never halts or fails to produce an output. Partial computable functions correspond to algorithms that may not terminate on some inputs.
• Total computable (total recursive) functions: partial computable functions whose domain is all k-tuples of natural numbers; that is, the corresponding Turing machine halts on every input and thus defines a value for every argument.

Characterising properties of a computable function

• There is a finite, exact description of the procedure (for example, a program, a Turing machine description or an equivalent finite representation).
• If the input belongs to the domain of the function, the procedure terminates after a finite number of steps and produces the correct output.
• If the input does not belong to the domain (for a partial function), the procedure does not produce an output; formally it may never halt.

Equivalent formal frameworks

Several equivalent formalisms capture the same intuitive notion of computability: Turing machines, the lambda calculus, and the class of (partial) recursive functions (built from initial functions using composition, primitive recursion and the minimisation operator). This equivalence is captured by the Church-Turing thesis, which states that any function intuitively computable by an effective procedure is computable by a Turing machine. The Church-Turing thesis is not a formal theorem but a widely accepted identification of the informal notion of algorithm with these formal models.

Examples of computable functions

• Every function with a finite domain. Such a function can be implemented by a finite lookup table.
• Every constant function f: N^k → N defined by f(n₁,...,n_k) = c for fixed natural number c.
• Addition f(n₁, n₂) = n₁ + n₂ and multiplication g(n₁, n₂) = n₁ × n₂. Standard algorithms or Turing machines compute these.
• The greatest common divisor function gcd(a,b). The Euclidean algorithm is an effective procedure that always terminates and produces gcd(a,b).
• The function that outputs the list of prime factors of a given natural number. There are algorithms that produce the full prime factorisation; these define a computable function if the output format is encoded suitably as a natural number or a sequence.

Why some intuitive tasks are computable

When a task can be specified by a finite set of exact rules that transform input symbols to output symbols, that task is computable. The computability notion depends on the representation of inputs and outputs, and on the requirement of finite termination for every valid input (for total functions).

Non-Computable Functions

Non-computable (uncomputable) functions are functions for which there is no Turing machine that computes the function for all inputs in its domain. Equivalently, no algorithm exists that, given any valid instance, always halts and returns the correct answer.

Counting argument: why most functions are uncomputable

The set of all Turing machines (or programs written in any fixed formal language) is countable. The set of all functions from the natural numbers to the natural numbers is uncountable. Therefore most functions N → N are not computable. A similar argument shows that most real numbers are not computable: the computable reals form a countable subset of the uncountable set of all real numbers.

Undecidable problems and uncomputable functions

Decision problems can be seen as functions whose outputs are "yes" or "no" (or 1 and 0). A decision problem is decidable (or recursive) if its characteristic function is total computable. A problem is undecidable if no Turing machine decides it for all inputs. Many undecidable problems correspond directly to non-computable functions.

Standard examples of non-computable functions and undecidable problems

• Halting problem: Given an encoding of a Turing machine M and an input x, determine whether M halts on x. The halting function HALT(M,x) that outputs 1 if M halts on x and 0 otherwise is not computable. The halting problem is undecidable but its positive instances form a recursively enumerable (semi-decidable) set.
• Post Correspondence Problem (PCP): Given a finite list of dominoes (pairs of strings), determine whether a sequence of dominoes exists whose top and bottom concatenations are identical. PCP is undecidable; no algorithm exists that always answers correctly for every instance.
• Many other natural problems in logic, number theory and automata theory are undecidable; undecidability results are typically proved by reduction from the halting problem or other known undecidable problems.

Semi-decidability and recursively enumerable sets

A set S ⊆ N (or a decision problem) is recursively enumerable (r.e.) or semi-decidable if there is a Turing machine that halts and accepts exactly the elements of S, while on inputs not in S the machine may run forever. Every decidable set is r.e., but there are r.e. sets that are not decidable; the halting set is a canonical example.

Partial functions versus total functions

Partial computable functions occur naturally when an algorithm may fail to halt for certain inputs. The class of partial computable functions is closed under composition and primitive recursion; adding the minimisation operator yields the full class of partial recursive functions. Total computable functions are a proper subset of partial computable functions.

Related facts and consequences

• There are only countably many computable functions but uncountably many total functions N → N; therefore the majority of total functions are uncomputable.
• Many natural mathematical questions reduce to whether a particular function is computable; undecidability implies that no uniform algorithm exists for all instances.
• The existence of a universal Turing machine shows that a single machine can simulate any other machine given its description; this leads to the notion of programs as data and is fundamental to general-purpose computation.
• The Church-Turing thesis identifies the intuitive notion of effective calculability with computability by Turing machines (or equivalent formalisms). This is an empirical/ philosophical thesis strongly supported by wide equivalence of formal models.

Short worked examples and intuitive algorithms

Example - Addition: An algorithm that computes f(a,b) = a + b can be described by repeated incrementing of one value by one, b times, or by binary addition using standard carry rules; both give finite procedures that always terminate and therefore define a total computable function.

Example - gcd(a,b): The Euclidean algorithm repeatedly replaces the larger of a and b by its remainder on division by the smaller until a remainder is zero. The final non-zero value is gcd(a,b). The algorithm always terminates on natural numbers and so gcd is a total computable function.

Conclusion

The distinction between computable and non-computable functions is fundamental in theoretical computer science. Computable functions are those realised by finite, terminating algorithms (or by Turing machines); non-computable functions cannot be obtained by any algorithm. Understanding this boundary - and the finer notions of decidability, semi-decidability and partial versus total functions - is essential for reasoning about what can and cannot be achieved by computation.