besluttelig

Besluttelig is a term used in Norwegian-language logic and computer science to describe a decision problem that can be resolved algorithmically. An instance of a besluttelig problem admits a finite procedure that, for any input, halts and returns a correct yes or no answer. In English, the term is commonly rendered as decidable. The related noun is besluttelighet.

Besluttelighet is a central notion in computability theory and formal language theory. A problem or language is besluttelig if there exists an algorithm that decides membership for every string in finite time. Informally, this means that automated procedures can determine truth values or recognize members of a language for all possible inputs. Classic decidable examples include regular languages and context-free languages. By contrast, the Halting problem is undecidable, which means no general algorithm can decide it for all possible inputs.

In Norwegian usage, besluttelighet is a foundational concept in the study of algorithms and formal systems. It is distinct from, but related to, notions of tractability and complexity: a problem can be decidable yet require exponential time to solve. Decidability plays a key role in fields such as formal verification, automated reasoning, and the theory of computation.