decidability


Also found in: Dictionary, Thesaurus, Legal, Idioms, Wikipedia.

decidability

(mathematics)
A property of sets for which one can determine whether something is a member or not in a finite number of computational steps.

Decidability is an important concept in computability theory. A set (e.g. "all numbers with a 5 in them") is said to be "decidable" if I can write a program (usually for a Turing Machine) to determine whether a number is in the set and the program will always terminate with an answer YES or NO after a finite number of steps.

Most sets you can describe easily are decidable, but there are infinitely many sets so most sets are undecidable, assuming any finite limit on the size (number of instructions or number of states) of our programs. I.e. how ever big you allow your program to be there will always be sets which need a bigger program to decide membership.

One example of an undecidable set comes from the halting problem. It turns out that you can encode every program as a number: encode every symbol in the program as a number (001, 002, ...) and then string all the symbol codes together. Then you can create an undecidable set by defining it as the set of all numbers that represent a program that terminates in a finite number of steps.

A set can also be "semi-decidable" - there is an algorithm that is guaranteed to return YES if the number is in the set, but if the number is not in the set, it may either return NO or run for ever.

The halting problem's set described above is semi-decidable. You decode the given number and run the resulting program. If it terminates the answer is YES. If it never terminates, then neither will the decision algorithm.
References in periodicals archive ?
Thus, combined with the traditional judicial decidability of
The halting problem captures the issue of decidability for
On the decidability of iterated semidirect products and applications to complexity.
In other words, what comes to me from the other is not only death, calculation and decision, the calculable decidability of the instant of my death, but also life, the relation to incalculability and undecidability, the relation to the 'coming of the to-come [venue de l'a-venir]' (p256).
DL is proven powerful in expressibility and decidability for knowledge engineering and allows for making use of some handy reasoning engines, such as Pellet and Racer.
At the end of the 1990s Ilya Zhil'tsov began to study the decidability problem for the equational theory of [A.sub.fin] (considered as a class of epigroups) along with a more general question.
Wittgenstein on irrationals and algorithmic decidability, Synthese, 118, 279-304.
Dimensions defined as contestability, availability, decidability and vulnerability also have their own measurement problems.
By Chapter 18 we arrive at electronic computers, and the subjects from then on are relatively modern: algorithms, decidability, information theory, networks and plenty more.
"Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation." Spatial Information Theory 2205/2001: 431-446.
The classical problems of satisfiability decidability and algorithmic decidability are approached in [24] on the distributed programs model of message sending.
In this paper, we firstly obtain input and precondition of service from service description document OWL-S in cloud computing, model service privacy item, and user privacy preference by taking advantage of knowledge base, verify the decidability of knowledge base with Tableau algorithm, and detect the conflict between service privacy item, and user privacy preference, so as to enable user to choose service collection that meets user privacy preference.