Constituents
of a complex system interact with one another, and with the surroundings. This
interaction can be viewed as communication
of information.
I introduced
the basics of information theory in Part 21 and algorithmic information theory in Part 23. Shannon’s
formulation of information theory was originally meant for designing better communication channels. An interesting aspect of modern communication theory is that the
merit of a particular communication-channel design lies not just in how well
the actual message is sent, but also in how well the channel could have sent
all the other messages it might have been asked to convey.
It is
instructive to adopt a historical approach and trace the development of ideas
regarding the nature of information and information-processing (or what is now
better known as computation).
Let us begin
by talking about 'sets'. [A set is a
unification of well-defined objects of thought into a whole. Here are some
examples: a set of chairs; a set of red chairs; a set of integers; a set of odd
integers; the set of all odd integers.]
At the
beginning of the 20th century the mathematician David Hilbert asked a question in the theory of infinite
sets: Starting from 1, 2, 3, . . ., what is the largest integral number one can
think of? Whatever that integer is, let ω
be the first number after all the finite numbers we can think of. So we get 1,
2, 3, … , ω.
We need not
stop there, and can go on adding the next higher integers to the set: 1, 2, 3,
… , ω, ω+1, ω+2, … . Let 2ω be the next integer after all the
integers in this set: 1, 2, 3, … , ω,
ω+1, ω+2, … 2ω. We can go on and on:
1, 2, 3, .., ω,
ω+1, ω+2, .. 2ω, . . 3ω, . . 4ω, .. ω2, ω3, .. ωω,
...
Even this can
go on. We shall reach ω to the power ω to the power ω . . .; and so on, forever. The set is
infinite.
Georg Cantor proved a theorem which said that for any infinite set there is a larger infinite set which is the
set of all its subsets. This is sometimes referred to as Cantor’s diagonal argument. [A subset is
a portion of the set.]
Now suppose we
apply this theorem to the infinite 'universal' set; by definition it is the set comprising of all the sets. Application
of Cantor’s theorem here leads to a paradox because the theorem says that there
should be a set still larger than the universal infinite set.
This paradox
was noticed by Bertrand Russell. The seminal
work Principia Mathematica by Whitehead and Russell (1925-1927), the
first edition of which was published during 1910-1913, included a new formulation
of set theory by Russell; he was led to it during his sustained efforts to
solve the following problem posed by him about sets:
Consider
a set A, defined as a set
containing all sets that are not members of themselves. Does A contain itself?
Unless you are
a politician, the two possible answers are Yes or No (a politician may say 'yes
and no'). If the answer is Yes, there is a contradiction because set A
is defined as a set containing sets which are not members of themselves.
If the answer
is No, again there is a contradiction. Since A is defined as a set
comprising of all sets which do not belong to themselves, it should contain
itself. But according to the second answer, A does not contain itself.
This means
that we can have incompatible
propositions that imply one another.
This famous
paradoxical situation goes by the name of Russell's paradox. Apparently,
Yes implies No, and No implies Yes.
Here is another
example of the Russell paradox, called the Barber Paradox: There is a
barber in a small town where every man is clean-shaven. The barber shaves all
men who do not shave themselves and only those men who do not shave themselves.
The
question is: Who shaves the barber? There is a paradox here, no matter
what answer you give:
If the barber does shave himself, then the
barber (himself) must not shave himself; and if the barber does not
shave himself, then he (the barber) must shave himself.
Russell's work
for resolving this paradox that now goes by his name led to a reformulation of
mathematics in terms of his new theory of sets, mentioned above. After much
mental agony and loss of sleep, his final resolution of the problem was as
follows:
He first
imagined what we now call a theoretical computer. It was essentially a sequential
logic machine. This imaginary machine carries out one logical operation at a
time, i.e. it operates in discrete time. The answers about a set are dealt with
sequentially, and one at a time. Thus, at any given point of time
the answer may be, say, Yes. But the theoretical computer keeps running, and a
few time steps later the answer becomes No. The program runs in an infinite
loop, alternating between Yes and No. Thus there is said to be no paradox
because the answer is never Yes and No at the same time! Are you
convinced by this explanation?
Hilbert
applied an approach different from that of Russell for tackling the problems
posed by Cantor in set theory. He tried to use, and improve upon, Euclid’s
axiomatic method. The idea was to take the apparatus of symbolic logic to its
extreme. He argued that one reason we get into contradictions in set theory is
that words often have a vague meaning. So why not come up with a finite set of
formal axioms and an artificial
language for doing mathematics? This artificial language must have strictly
precise grammatical and other rules.
Did Hilbert
succeed? I shall answer that next time.
