From: lucifer@dhp.com (Anonymous)
Date: Sun, 19 Jan 1997 13:15:59 -0800 (PST)
To: cypherpunks@toad.com
Subject: Numbers we cannot talk about
Message-ID: <199701192115.QAA07547@dhp.com>
MIME-Version: 1.0
Content-Type: text/plain


At 10:48 PM 1/18/1997, Secret Squirrel wrote:
>Is it REALLY true that there are real numbers that cannot be
>generated by any algorithm? Some guy said that since the set of
>algorithms is countable, but the set of real numbers is more than
>countable, there must be some numbers for which there is no
>algorithms that generate them.

There are sets of real numbers whose existence we can prove, but which
we cannot otherwise describe.  This is more extreme than being
"generated by an algorithm".  We can't even tell somebody which
numbers to generate!  (I take "to generate" here to mean "to compute a
decimal approximation.")

The set of real numbers is uncountable as is the set of subsets of the
real numbers.  Yet, we have only countably infinite ways to describe
sets of numbers.

All sets of numbers which we can describe can be described with a
finite set of symbols.  (Human beings are unable to distinguish
between an infinite number of states.)  The set of combinations of
this finite set is infinite, but countable.

"What we cannot speak about we must pass over in silence."
  - Ludwig Wittgenstein,
    closing line of "Tractatus Logico-Philosophicus"

See the early pages of "Godel's Incompleteness Theorems" by Raymond M.
Smullyan for a better exposition.

Math Man