decidability

(redirected from decide)
Also found in: Dictionary, Thesaurus, Legal, Acronyms, 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 classic literature ?
"Now, suppose you tell Leslie and she decides to have the operation.
After having combined with the Executive in betraying the interests of the nation in a ruinous treaty, what prospect, it is asked, would there be of their being made to suffer the punishment they would deserve, when they were themselves to decide upon the accusation brought against them for the treachery of which they have been guilty?
The full score of men shot three times at each target, and then three times again to decide a tie.
At the bidding of the King, the herald announced that the open target was to be shot at, to decide the title of the best archer in all England; and any man there present was privileged to try for it.
"How say you, if first we decide this open target and then match the five best thereat against your unknown champions?"
"You will do as the majority decide, or you will be `the first' without the formality of drawing lots," said Monsieur Thuran threateningly.
Spider bent, wide-eyed, toward the hand that was to decide his fate, for whatever luck was Clayton's on this last draw, the opposite would be Spider's.
Wait and see what the chances of the next eight-and-forty hours might bring forth, and then write to her, or desert her, as the event might decide. It lay in a nut-shell, if you could only see it.
Since our govt ends today, and new prices of Petrol, Diesel and Kerosene Oil go in effect from tomorrow, therefore on Min of Finance's recommendation the Prime Minister has decided to leave their prices unchanged till June 7, so that the incoming govt can decide new prices.
The Germans wanted to see one to decide whether to license it out.
Well, if Canada had any pretence to being a democracy, the electorate, through their parliamentary representatives, would decide. But Canada is not a democracy, and hasn't been since 1983 when the Charter of Rights became the supreme law of the land; since the Charter is not self-interpreting, its interpreters--our judges--became de facto rulers.
Outlining the situation, Nourse says Peterson had to decide whether "to take advantage of the package either as a lump sum or an annuity.