Decidability
One of the scientific
foundations of computer science is decidability that is, what can and cannot be
computed. Since algorithms are solutions to problems, problems are examined in
the general sense. A problem (in general) is decidable if its solution halts in
some finite amount of time otherwise it is undecidable. Decidability is the
part of computability theory that does not deal with the amount of time
required in a solution, just as long as itÕs finite. (Complexity theory is the
area of computability theory that deals with time.) There are two formal
notions of decidability that we have to work with:
1. Turing Computability
2. Generalized Recursive Functions
This is more formally known
as the Church-Turing Thesis. View:
http://www.bletchleypark.net/algorithms/Church_Turing.html.
More
formally stated, a decidable algorithm halts with either a YES or NO answer
on every input string for a given language L. We can formalize a decision problem
as a problem of deciding whether a given string is a member of
a set of strings. This set of strings is called a formal language,
where an input string that belongs in this set yields a YES answer. For a
particular problem, if an algorithm is able to correctly decide for any
input string whether it is a member or not a member of the language,
then the problem is decidable. Thus, the decidability of various languages can
be determined algorithmically. For instance, we can express whether or
not a certain deterministic finite automaton (DFA) accepts an input string w by testing whether or not that
(DFA, w) pair is
a member of a language. Showing that a language is decidable, in such a
way, is equivalent to showing that the problem is decidable.
Optimization Problems
Since optimization problems
can be cast to decision problems, conceivably any problem can be a decision
problem. For instance, a boundary B can be set on an optimization problem,
and the question ÒIs the answer greater than (or less than, or equal
to) B?Ó, can be asked. Furthermore, solving the decision problem of a
corresponding optimization problem is not much more difficult. In other words,
there's only a polynomial difference in difficulty. Of course, there can theoretically
be an infinite number of problems to consider. It would be great
if we were able to decide any problem in general, in other words provide a
YES or NO answer to any problem, but this would require a decidable algorithm
for each and every problem. Unfortunately, there are some problems that are not
decidable, such as the halting problem.
Reducibility
Reducibility is a technique
used to show that problems are undecidable. In other words, since the
halting problem is the first problem that has been determined undecidable we
can reduce the halting problem to a second problem to show that the
second problem is also undecidable. An algorithm that is unable to provide
a YES/NO answer to a problem is an algorithm that loops indefinitely. If
this is the case, then we say that this algorithm is a recognizer. The
halting problem is recognizable, but not decidable. Furthermore, a problem
is decidable if and only if both it and its complement are recognizable. In the
case of the halting problem, its complement is not recognizable, thus it is not
decidable. It is beneficial to identify when a problem is algorithmically
unsolvable because an alternative course of action needs to be taken such
as finding an approximate solution. So, in essence a solvable problem
is decidable where as an unsolvable problem is undecidable.
Rice's Theorem
Rice's theorem (1953) has
important implications for decidability. Rice's theorem states that, any
trivial property of a Turing machine holds for all Turing machines or for none,
and is thus decidable. Where as a nontrivial property holds only for some
Turing machines but not all, which is undecidable. In other words, the question
of whether a given algorithm computes the function of a Turing machine with a
nontrivial property is undecidable.
Expressed more formally,
Rice's theorem states that for any TM's Ma and Mb, such
that L(Ma) = L(Mb), then Ma ë Q iff Mb ë Q, where Q is a language.
Additionally, Q is nontrivial in the sense that there are some TM's that exist
in Q, and there are others that don't. So in essence, only trivial properties
of programs are algorithmically decidable.
Thus, there exists no
automatic way to decide a non-trivial and general question on the overall
behavior of a computer program. This is actually one reason for the difficulty
of finding and fixing bugs within code. An example of an undecidable problem
is, given a program p, does p terminate for all possible inputs
of p? Most
of the interesting questions regarding program errors are undecidable.
Self-Halting
Problem
The self-halting problem is
an example of a problem that is undecidable. View http://www.bletchleypark.net/computation/Self_Halting_Problem.pdf
to see why.
Links
http://web.media.mit.edu/~rich/research/babbage/presentation/presentation.html
http://www.wikipedia.org/wiki/Decision_problem
http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?decidability
http://www.math.utu.fi/research/automata/decidres.html
http://www.cs.cornell.edu/Info/Projects/NuPrl/manual.with.index/node169.html