decidable ==>
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.
(1995-01-13)
Nearby terms:
DECdns « DEChead « dechunker « decidability »
decidable » decimal point » decision problem
|