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