Räknebart

Räknebart is a Swedish term used in mathematics and theoretical computer science to describe objects and properties that can be determined or computed by an effective procedure, i.e., by a finite algorithm. In English, the closest concepts are computable or decidable, depending on the context.

A real number is räknebart if there exists an algorithm that, given a request for n digits of precision, outputs the first n digits. A function f: N → N is räknebar (computable) if there is a finite procedure that, for every input n, halts with the value f(n). A subset of N (or of any computable domain) is räknebar or decidable if its characteristic function is computable; equivalently, there exists an algorithm that decides membership in finite time.

Examples illustrate the scope: the rational numbers and algebraic numbers are räknebara; many standard transcendental numbers, such as pi and e, are also computable. The halting problem, by contrast, is not räknebar; no algorithm can determine for every program-input pair whether the program halts.

Relation to theory: The concept is central to computability theory and recursion theory and contrasts with noncomputable objects. There exist real numbers that cannot be computed to arbitrary precision by any algorithm, and there are decision problems that are undecidable. The Church–Turing thesis posits that any function that is effectively calculable can be computed by a Turing machine.

History and scope: The notion emerged in the 1930s through the work of Turing, Church, and Kleene, forming a foundational part of modern computability theory. Räknebartity is used to classify what can be algorithmically determined, with implications for logic, analysis, and computer science.