Beslutsbart

Beslutsbart is a term used in logic and theoretical computer science to describe a problem for which there exists a finite procedure, an algorithm, that always terminates with a correct yes or no answer. In Swedish usage the adjective besltutsbart is applied to decision problems or to languages to indicate that they are decidable.

Formally, a decision problem is a set S of strings over a fixed alphabet. S is beslutsbart if there exists a Turing machine that, for every input w, halts and correctly accepts w if w is in S and rejects w otherwise. Equivalently, S is decidable if there is a procedure that yields a final yes/no decision for every possible input.

Beslutsbarhet is distinguished from related concepts such as recognizability or semi-decidability. A language is recognisable (recursively enumerable) if there is a Turing machine that accepts all strings in the language, though it may not halt on inputs outside the language. Some problems are semi-decidable but not decidable; the halting problem is a classic example: there is a procedure that will identify programs that halt, but no algorithm that halts on all inputs to decide halting in every case.

Historical and theoretical context includes the Entscheidungsproblem and the work of Church and Turing, which showed that general first-order logic validity is undecidable. In contrast, many practical domains have decidable problems (for example, certain questions about regular languages, or propositional logic with truth-tables). Yet even decidable problems can have high computational complexity, so decidability does not imply practical computability.

In summary, beslutsbart characterizes problems with guaranteed terminating algorithms, forming a core concept in the study of computation and formal logic.