Overview

A computable function is a mapping from inputs to outputs for which there exists an effective procedure—an algorithm—that produces the correct output after a finite sequence of steps. In theoretical computer science this concept explains what problems can be solved mechanically. The idea ties closely to formal models of computation such as Turing machines and lambda calculus; see foundational discussions on computability and formal definitions at related entries.

Key characteristics

  • Algorithmic realizability: There must be a clear, finite description of a method that transforms any valid input into the corresponding output.
  • Termination: The method must halt after a finite number of steps for every input in the function's domain.
  • Representation independence: Whether a function is computable does not depend on the programming language used, provided the language can express general algorithms; this is formalized by the Church–Turing view.

History and development

The formal study of computable functions emerged in the early 20th century when logicians formalized calculation and algorithmic processes. Several equivalent models—Turing machines, recursive functions, and lambda calculus—were shown to capture the same class of functions. Modern accounts of these results are found in textbooks and surveys on computability theory and the theoretical underpinnings of algorithms.

Examples and uses

Simple arithmetic operations, string manipulation routines, and many functions used in software engineering are computable. Computability theory distinguishes these from undecidable tasks, where no algorithm can always produce a correct answer. Practical importance ranges from programming language semantics to limits on automated theorem proving; introductory resources discuss applications at educational sites.

Not every well-defined mathematical function is computable; classic examples from logic show functions with no effective procedure. The boundary between computable and noncomputable functions is central to theoretical computer science, and is treated in more depth in surveys and formal treatments available via specialist literature.