berechenbar

Berechenbar is a German adjective meaning capable of being calculated or computed by an algorithm. In mathematics and computer science, the term is used in the broader concept of berechenbarkeit (computability), which concerns which functions or problems can be carried out by effective procedures.

A function is considered berechenbar if there exists a finite, mechanical procedure that, for every valid input, terminates with the correct output. The field studies formal models of computation, such as Turing machines, lambda calculus, and Kleene’s notion of recursive functions. The Church–Turing thesis posits that these models capture the intuitive notion of effective computability, so a function is berechenbar if and only if it can be computed by a Turing machine (or an equivalent model).

The development of computability theory began in the 1930s with work by Alonzo Church, Alan Turing, and others, as part of foundational inquiries into mathematics and logic. A core distinction is between decidable (or recursive) problems, for which an algorithm yields a yes/no answer for every input, and undecidable or non-computable problems, such as the halting problem.

Computability theory underpins the limits of automation and informs related areas like complexity theory and formal language theory. In German-language literature, berechenbar and Berechenbarkeit are discussed alongside Rekursion (recursive), Rekursiv Aufzählbar (recursively enumerable), and Entscheidbarkeit (decidability), reflecting a taxonomy of computability and related notions.