| 释义 |
decidability
de·cide D0071900 (dĭ-sīd′)v. de·cid·ed, de·cid·ing, de·cides v.tr.1. a. To reach a conclusion or form a judgment or opinion about (something) by reasoning or consideration: decide what to do.b. To cause to make or reach a decision: "The presence of so many witnesses decided him at once to flee" (Robert Louis Stevenson).2. To settle conclusively all contention or uncertainty about: decide a case; decided the dispute in favor of the workers.3. To influence or determine the outcome of: A few votes decided the election.v.intr.1. To pronounce a judgment; announce a verdict.2. To reach a decision; make up one's mind.
[Middle English deciden, from Old French decider, from Latin dēcīdere, to cut off, decide : dē-, de- + caedere, to cut; see kaə-id- in Indo-European roots.]
de·cid·a·bil′i·ty n.de·cid′a·ble adj.de·cid′er n.Synonyms: decide, determine, settle, rule, conclude, resolve
These verbs mean to come to a decision about. Decide has the broadest range: The judge will decide the case on its merits. We decided to postpone our vacation for a week.
Determine has a similar range but often involves somewhat narrower issues: The doctor determined the cause of the infection. The jury will determine the fate of the defendant.
Settle stresses finality of decision: "The lama waved a hand to show that the matter was finally settled in his mind" (Rudyard Kipling).
Rule implies that the decision is handed down by someone in authority: The committee ruled that changes in the curriculum should be implemented.
Conclude suggests that a decision, opinion, or judgment has been arrived at after careful consideration: She concluded that the criticism was unjust.
Resolve stresses the exercise of choice in making a firm decision: I resolved to lose weight.decidability (dɪˌsaɪdəˈbɪlɪtɪ) n1. the capability of being decided2. logic the capability of being proven as having or not having a particular qualityTranslationsIdiomsSeedecidedecidability
decidability (mathematics)A property of sets for which one can determinewhether something is a member or not in a finite number ofcomputational steps.
Decidability is an important concept in computability theory. A set (e.g. "all numbers with a 5 in them") is saidto be "decidable" if I can write a program (usually for aTuring Machine) to determine whether a number is in the setand the program will always terminate with an answer YES or NOafter a finite number of steps.
Most sets you can describe easily are decidable, but there areinfinitely many sets so most sets are undecidable, assumingany finite limit on the size (number of instructions or numberof states) of our programs. I.e. how ever big you allow yourprogram to be there will always be sets which need a biggerprogram to decide membership.
One example of an undecidable set comes from the halting problem. It turns out that you can encode every program as anumber: encode every symbol in the program as a number (001,002, ...) and then string all the symbol codes together. Thenyou can create an undecidable set by defining it as the set ofall numbers that represent a program that terminates in afinite number of steps.
A set can also be "semi-decidable" - there is an algorithmthat 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 NOor run for ever.
The halting problem's set described above is semi-decidable.You decode the given number and run the resulting program. Ifit terminates the answer is YES. If it never terminates, thenneither will the decision algorithm. |