Copyright © Philip M. Parker, INSEAD. Terms of Use.

DECIDABILITY

Specialty Definition: DECIDABILITY

Domain	Definition
Computing	Decidability 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. (1995-01-13). Source: The Free On-line Dictionary of Computing.
Source: compiled by the editor from various references; see credits.

Crosswords: DECIDABILITY

Specialty definitions using "DECIDABILITY": decision problem. (references)

Commercial Usage: DECIDABILITY

Domain	Title
Books	Countable Boolean Algebras and Decidability (Sibirskaia Shkola Algebry I Logiki.) (reference) Recursive Functions and Metamathematics: Problems of Completeness and Decidability, Godel's Theorums (Synthese Library, 286) (reference) (more book examples)
Source: compiled by the editor from various references; see credits.

Modern Translation: DECIDABILITY

Language		Translations for "DECIDABILITY"; alternative meanings/domain in parentheses.
Russian		разрешимость (solvability). (various references)
Source: compiled by the editor from various translation references.

Derivations: DECIDABILITY

Derivations
	Words ending with "DECIDABILITY": undecidability. (additional references)
Source: compiled by the editor, based on several corpora (additional references).

Anagrams: DECIDABILITY

Scrabble® Enable2K-Verified Anagrams
	Words within the letters "a-b-c-d-d-e-i-i-i-l-t-y"
	-3 letters: edibility.
	-4 letters: biacetyl, ciliated, debility, deicidal, diabetic, diacetyl, dialytic, didactyl, ideality.
	-5 letters: ability, acidity, addible, albitic, alibied, beadily, ciliate, citable, citadel, dactyli, datedly, deltaic, dialect, dilated, edacity, edictal, lyddite.
	Words containing the letters "a-b-c-d-d-e-i-i-i-l-t-y"
	+2 letters: undecidability.
Source: compiled by the editor from various references; see credits. SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the U.S.A and Canada by Hasbro Inc., and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc. Mattel and Spear are not affiliated with Hasbro.

INDEX

1. Crosswords
2. Usage: Commercial
3. Translations: Modern
4. Derivations

5. Anagrams
6. Bibliography

Copyright © Philip M. Parker, INSEAD. Terms of Use.