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 ?
On the decidability of iterated semidirect products and applications to complexity.
At the end of the 1990s Ilya Zhil'tsov began to study the decidability problem for the equational theory of [A.
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.
Wittgenstein on mathematical meaningfulness, decidability, and application, Notre Dame Journal of Formal Logic, 38, 195-225.
To restore decidability, Alur & Henzinger (1998) proposed to restrict the behavior of clocks.
Clearly there is no one decision that is made once and for all, no tie that can be held forever or withstand 1000 cuts or 400 blows, and no defining decidability that can consecrate the forms of practice that work to enrich those relations rather than enact parasitism on them.
At the beginning of this paper, we said that decidability, set-oriented operations, and homomorphism were the three essential features of data models.
Post and the development of logic, John von Neuman and the ideas of David Hilbert, the contribution of Polish logicians to decidability theory and predicate calculus, and the development of symbolism in logic and its philosophical background.
Henzinger, Probabilistic Automata on Infinite Words: Decidability and Undecidability Results, Springer-Verlag, 6252(2010), 1-16.
Such temporal models have decidability problems: the most general interval-based temporal extension of DL is undecidable (Artale & Franconi, 2000).
According to Crispin Wright (on Salerno's interpretation) all parties to the debate over logical revisionism should affirm the "a priori unwarrantability of the decidability thesis.
The decidability problem is compounded by the fact that the human mind does not act like a computer.