computabile

Computabile, in the context of theoretical computer science, refers to functions or problems that can be resolved by an algorithm in a finite amount of time for every input. A function from natural numbers to natural numbers is computabile if there exists a mechanical procedure that, given any input, halts with the correct output. The same notion applies to decision problems, where an algorithm eventually answers yes or no.

Multiple equivalent models establish computability, including Turing machines, lambda calculus, and total recursive functions. The Church–Turing thesis posits that these formal models capture the intuitive notion of an effectively calculable procedure. A key distinction is between total computable functions and partial computable (semi-decidable) ones: a total computable function halts on all inputs, whereas a partial computable function may not halt for some inputs. The halting problem illustrates a non-computable total function, while certain problems are computable in principle but may require impractically long resources.

Examples and limits: basic arithmetic operations are computabile, and many well-defined functions are computable, including some that are not primitive recursive. Conversely, some questions are proven non-computable, meaning no algorithm can decide them for all inputs. The study of computability clarifies what can be algorithmically determined and sets fundamental limits for automated reasoning, formal verification, and the design of programming languages.

Historically, foundational work in the 1930s by Gödel, Church, and Turing established the concept and models of computability, influencing subsequent developments in computer science and mathematics.