Dictionary.net

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 computabilitytheory. 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 haltingproblem. 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.