Undecidability and Incompleteness
In the previous post
we looked at a Turing Machine and the Halting problem. A Halting
problems is type of decision problem for a Turing Machine.
Recall that a Turing Machine has three final states:
- Accept -> The machine accepts the string
- Reject -> The machine rejects the string
- Loop indefinitely -> The machine neither accepts nor rejects the string; its still processing it
Now it is quite evident that in the Accept and Reject states the
Turing Machine can tell you something definite about the string that
it is processing. Thus, when a Turing Machine reaches one of these
states we say that the Turing Machine has decided the language
(recall that all TM problems are represented in the form of Languages).
On the other hand we have situations where the Turing Machine fails to
decide a language. In fact we have a whole class of such
languages. These languages are called undecidable languages.
The Halting Problem that we looked at in the last essay is one such problem.
Undecidability and Undecidable Problems¶
Undecidability is one of those concepts in Theoretical Computer
Science that fascinates me in ways I can not even begin explain.
There are certain types of decision-problems for which there is no
algorithm that can reliably give a yes-no answer.
The implications of this are quite interesting.
This means that you can not have a program that tells you whether a
program will produce an output or not (and consequently keep running
for-ever). Like how our compilers still can not tell us when we will hit
an infinite-loop. The only way to find out is to actually run the
program. This is serious research topic in computer science; designing
accurate static analyzers.
Hilbert's problems¶
In 1900 mathematician David Hilbert published a list of 23
problems. In 1928 he returned to the second question out of these 23
asking three fundamental questions about mathematics.
- Is mathematics complete ?
- Is mathematics consistent ?
- Is mathematics decidable ?
The main reason for these questions was to establish a set of
fundamental axioms about mathematics using which you could prove any
theorem in mathematics. Now, the idea was that even if all of such
axioms were not known we could find them out.
Three years later in 1931 Kurt Godel published solutions to the first
two questions, these are known as Godel's incompleteness theorems.
The Wikipedia page
for
Godel's incompleteness theorem states
that
The first incompleteness theorem:
no consistent system
of axioms whose theorems can be listed by an effective procedure
(i.e., an algorithm) is capable of proving all truths about the
arithmetic of the natural numbers. For any such formal system, there
will always be statements about the natural numbers that are true, but
that are unprovable within the system.
The second incompleteness theorem:
the system in question cannot demonstrate its own consistency.
All this is fine; but what does it actually mean for mathematics and computer science ?
For mathematics it means that mathematics is not complete. Hence there
is a very good possibility that certain problems exist in mathematics
which can never be proven. (For
example. the
Riemann hypothesis
etc)
For Computer Science this means that there are certain programs that
are non-computable. Yes, this basically puts a limit on the type of
programs that you can write.
Entscheidungsproblem (or the Decision problem)¶
This problem is referred to as
the
Decision problem
posed by David Hilbert. This problem asks for an algorithm that takes
in a logical statement statement and then says either "yes" or "no" as
to whether the statement is true or not. For the sake of simplicity
we can assume that the algorithm is aware of all the axioms (or rules)
that is needed to say "yes" or "no".
The solution of this problem was given by both Alan Turing and Alonzo
Church in 1936. Alonzo Church created a method of defining functions
called the Lambda Calculus while Alan Turing created a model of
computation called the Turing Machine.
The final result was the no such algorithm can exist.
What does this mean for mathematics and computer science ?
For mathematics it means that not only are there certain problems that
can not be solved (or proved) but there is no way for us to know
whether a problem is solvable or not without actually trying to
solve the problem.
For
example
Fermat's Last theorem was
assumed to unsolvable and it remained unsolved for about 358 years
until Andrew Wiles solved it.
Similarly we have other challenging problems such as the Riemann
Hypothesis etc.
For computer science it means that we can not have some program that
tells you whether your program will work or not. Lets break this in a
lil bit more.
Thinking exercise for CS people.¶
Sit down.
Write a program that will take any other program and tell you if that
other program will stop or not.
Disclaimer¶
I am not expert in any of this by any stretch of the
imagination. I'm just starting out and there is a of chance that I do
not understand this fully. Maybe 20 years later I will look at these
and laugh at myself. Maybe my understanding of these is completely
wrong or misguided.
But, right now I love reading about these and that i good enough for
me and honestly the the presented above are good enough.
I would rather be wrong about these right now than not study waiting
for the correct time or the correct opportunity or the correct
resource to study from. I've made that error before and I do not want
to make it again.