computabili

Computabili is the Italian term used in the theory of computation to denote computable structures and problems. In formal terms, a function is computable if there exists an algorithm that, given any valid input, produces the output after a finite number of steps.

The standard models of computability include Turing machines, partial recursive functions, and lambda calculus. The Church–Turing thesis asserts that these models capture the intuitive notion of effective computability; that is, every function that can be computed by any effective procedure is computable by a Turing machine (and by equivalent formalisms).

Problems are classified as computable (decidable) if a terminating algorithm can determine the answer for every input. If no such algorithm exists, the problem is non-computable. A distinction is made between total computable functions, which produce an output for every input, and partial computable functions, which may be undefined for some inputs. The halting problem is a canonical example of a non-computable problem, though it is semi-decidable (recursively enumerable) in the sense that a program can verify halting for some instances.

Computability theory also differentiates between what can be computed in principle and the resources required to compute it; the latter topic is the domain of computational complexity. Nonetheless, computability focuses on existence: whether an algorithm exists at all, regardless of time or space.

Historically, foundational work by Alonzo Church, Alan Turing, Stephen Kleene, and others in the 1930s established the field, with Gödel’s incompleteness theorem highlighting intrinsic limits of formal systems. Today, computability informs areas such as formal verification, programming language design, and the study of undecidable problems.