calcolabile

Calcolabile is an Italian term used in computability theory to describe functions or problems that can be computed by an algorithm. In its standard use, a function f: N -> N is calcolabile if there exists a finite procedure that, given any input n, halts and outputs f(n). More generally, a problem is calcolabile if its characteristic function is computable. In many texts, calcolabile refers to total computable functions, while partial computability concerns functions that may be undefined for some inputs.

Several formal models capture the same class of calcolabile functions: Turing machines, μ-recursive functions, recursive functions, and the lambda calculus all characterize effective computability. The Church-Turing thesis posits that these models express the same notion of what can be computed by an algorithm, providing a robust foundation for the concept of calcolabilità.

Not all questions are calcolabili. Some problems are undecidable, meaning that no algorithm can determine the answer for all possible inputs. A classic example is the halting problem: there is no general procedure that decides, for every program and input, whether the program halts. This demonstrates the existence of limits to calcolabilità and motivates the study of decidability and complexity.

Historically, the theory of computability emerged in the 1930s from the work of Turing, Church and Kleene, among others. In Italian mathematical literature, calcolabile remains the standard term for describing what can be computed algorithmically.

Applications of the concept include the analysis of what problems are solvable by machines, the classification of problems by decidability, and the development of models of computation in computer science and logic.