decidability
     
         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
     
     
see also:
finite computability theory turing machine halting problem algorithm halting problem