TURING'S
HALTING PROBLEM
ALGORITHMIC INFORMATION THEORY AND SHANNON'S THEORY
James
Constant
math@coolissues.com
Shannon's
Information Theory
Finds that Proofs of Turing's Halting Problem and Algorithmic
Information Theory are Invalid But Likely to Reformulate by
Setting Decisional Thresholds
Algorithmic Information
Theory (AIT)
Algorithmic Information Theory
(AIT) teaches
how a piece of information can be reproduced by an algorithm
which indicates the "complexity" or
"randomness" of the piece of information. The theory
relates to Kurt Godel's incompleteness theorem and Alan Turing's
Halting Problem (THP) from which Gregory Chaitin proves that
there is no algorithm for testing whether any algorithm is the
shortest way to compress a given piece of information, and
therefore no true measure of the complexity of any sort of formal
numeric entity.1. AIT asserts
two definitions,
its presumed axioms, and a corollary:
AIT
Complexity Axiom:
The amount of information in a given sequence of characters
(string) is defined as the length of the shortest least complex
program which will produce that string as output. One way to
think about this is to regard the AIT information content as the
lower limit to the compressibility of the string. This quantity
is known variously as Kolmogorov complexity, algorithmic
complexity and program-length complexity. AIT holds that a
compressed representation of a string and the string itself are
the same amounts of information. This differs from standard
theory which tells us that compression degrades the information
in a string.
AIT
Randomness Axiom:
A string is said to be random when its own length is equal to its
program-length complexity - i.e. the string is as short as the
shortest program that would produce it as output. This differs
from the usual definition of randomness, which is a statistical
one, specifying that all substrings (of up to a certain length)
must appear equally often in the string.
AIT
Randomness
Corollary: One interesting feature of AIT's definition of
randomness is that it is in general undecidable whether a string
is random - because the shortest program that produces a given
string as output is uncomputable, except when N is finite. These
facts tend to go against there being many practical applications
of AIT.
The
terms Algorithmic
Information Theory and program-length complexity were coined by
Chaitin to describe features of his own work on the foundations
of mathematics.
Turing's
Halting
Problem (THP)
Turing
showed that no
algorithm, no mathematical theory, can ever tell us which
computer program will halt and which will not. His proof was made
by the method of reductio ad absurdum variously
known as
"proof by double negation" or "proof by
contradiction". A proof by contradiction is a weak proof and
is rejected by some. It proves a theorem by assuming that the
conjecture is false and finding that it is a contradiction. When
a contradiction is found the conjecture is then
"proved" to be true. Marilyn vos Savant tells us that
"Proof
by double
negation is fraught with dangers. For example, lets say the human
animal can see only in black and white . . . We want to prove
that an object is white, so we manage to prove that it isn't
black. By double negation, the object is proved to be white. But
considering all the colors of the rainbow, this shouldn't be a
valid proof. Maybe the object is red. But how would we know it?
Reductio ad absurdum is an "indirect proof". Its
opposite is known as a 'direct proof', which satisfies the most
stringent requirements"2
Clearly,
the increased
strength of a proof by contradiction rests upon the decreased
absence of other colors. In the context of THP, considering all
colors of the rainbow of information, from a complete or no
correspondence between a compressed representation of a string
and the string itself, THP shouldn't be a valid proof. Maybe the
compressed representation of a string is only a fraction of the
information of the string itself. But how would we know it? The
answer follows.
Shannon's
Information
Theory
In
Claude Shannon's
standard information theory, the maximum information in a string
of N bits or bytes is equal to the capacity of the computer
H=C=logN. If the string is compressed becoming a string of n<N
bits or bytes, the maximum information in the compressed string
is Hc=CC=logn which
reduces the size of the
computer and information since Cc<C and
since Hc<H.
Generally, compression results in lost information since the
information in the compressed string is logn=klogN or n=Nk
where 0<k<1. If we are not interested in reducing the
size
of the computer Cc but only interested in
preserving
the information H in computer C, we can set Mlogn=logN or nM=N
M integer.
The
main consequence of
invalid THP for AIT is that Chaitin's proof, which rests upon the
validity of THP, is also invalid. We can now say that Shannon's
information algorithm Hc=logn is a way to
compress a
piece of information H=logN to any shortness desired provided we
either take (n=Nk k fraction) or compensate for
(n=NM
M integer) the loss of information. In this respect a computer
does not halt but continues providing a degraded "all
colors" output, contrasting THP's and AIT's presumed
"black and white" output.
Suppose
our string
consists of a single page in a book with N=10,000 ASCII bytes and
suppose we apply a 100:1 compression program to it so that n=100.
The information at the output of the computer is logn<logN. If
we accept the degradation of information at level logn=klogN or
n=Nk, the result is we are left reading a page
with
1/2 the letters missing. If N=10,000 and n=1,000 we are left
reading a page with 1/4 the letters missing, a better result. The
point is that we can always accept a degraded string at the
computer output by setting a decisional threshold. Or, if
capacity C is available, we can preserve the undegraded string by
setting N=nM M integer, by a serial recycling
the
information M times through a single program or by a parallel
arrangement of M identical programs.
The
Future of THP and
AIT
Since
the compressed
representation of a string is only a fraction of the information
of the string itself, THP and AIT can survive by reformulating
their results as decisional thresholds rather than as presumed
absolutes. THP may now be restated as "Conventional
Information Theory tells us which computer program will degrade
by a fraction k and which will not." AIT's Complexity Axiom
may be restated as "The amount of information in a given
sequence of characters (string) is defined as the length of the
shortest least complex program which will produce a degraded
copy of that string as output" and AIT's Redundancy
Axiom may be restated as "A string is said to be random when
its own length is equal than its program-length complexity".
If such or similar changes are made, AIT's Randomness Corollary
may be restated as "A string is said to be random when its
own length is equal to its program length complexity - i.e., the
string is as short as the shortest program that produces it undegraded
at its output". Underlines emphasize changes in the original
axioms. If only capacity Cc<C is
available, we must
accept the decrease in capacity and complexity by a corresponding
degradation of information by a fraction k. Or, if capacity C is
available, we can preserve the undegraded string by setting N=nM
M integer. In either case, setting decisional thresholds makes it
possible to decide the "complexity" and
"randomness" of program-lengths, opening AIT to
practical applications.
As
stated, AIT can
determine program-length complexity where it is below or equal to
N. But, program-length complexity can only be guessed when N is
infinite. As example, in the case of pi there exist short
programs which will go on producing digits of pi forever. It is
hard to see that a degraded program-length of pi represents an
undegraded pi, a presumed infinite string of digits. The problem
with N infinite is that we have no way of knowing the information
content of logN. In the pi example we do not know if its short
program length preserves a fraction or the entire content of pi.
However, since mathematicians have found no repeatability in pi,
i.e., M infinite, we can only guess the latter.
While
AIT brings some new
insights into the ideas of "complexity" and
"randomness" it is, nevertheless, a part of standard
information theory to which it must be reconciled.
1 Gregory Chaitin, "The Limits of Reason",
Scientific American, March 2006 pages 74-81
2 Marilyn vos Savant "The World's Most Famous Math
Problem", St. Martin's Press, New York 1993 pages 34-35
Copyright ©
2006 by James Constant
By same author: http://www.coolissues.com/mathematics/sameauthor.htm