Dictionary    Maps    Thesaurus    Translate    Advanced >   


Tip: Click Thesaurus above for synonyms. Also, follow synonym links within the dictionary to find definitions from other sources.

1. The Collaborative International Dictionary of English v.0.48
Decidable \De*cid"a*ble\, a.
   Capable of being decided; determinable.
   [1913 Webster]

2. The Free On-line Dictionary of Computing (30 December 2018)
decidability
decidable

    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)


Common Misspellings >
Most Popular Searches: Define Misanthrope, Define Pulchritudinous, Define Happy, Define Veracity, Define Cornucopia, Define Almuerzo, Define Atresic, Define URL, Definitions Of Words, Definition Of Get Up, Definition Of Quid Pro Quo, Definition Of Irreconcilable Differences, Definition Of Word, Synonyms of Repetitive, Synonym Dictionary, Synonym Antonyms. See our main index and map index for more details.

©2011-2024 ZebraWords.com - Define Yourself - The Search for Meanings and Meaning Means I Mean. All content subject to terms and conditions as set out here. Contact Us, peruse our Privacy Policy