Search This Blog

Thursday, March 26, 2015

CS History 0

Are real numbers real?

Wait!! What does this have to do with programming? Or even computer science??

Sounds like angels-on-the-head-of-a-pin philosophy No??
NO!  CS came into existence because of this question!
On the Python list there was this discussion about real numbers¹.
Chris Angelico made the statement (more or less) that floats are real and reals are mythical. Someone naturally objected to this paradox.

Here is my short recap of CS-history showing the centrality of this question

Constructivism + Platonism + Formalism + ??? ⇒ CS

There have been notable mathematicians in the last 100 years who have said more or less exactly what Chris is saying: The set is nonsense.  In fact these fights are the very reason that CS came into existence.

Around 1880, Kronecker and his student Cantor were working together when Cantor started off on 'set-theory'.  For a while Kronecker was bemused with the direction of his (favorite!) student.
But he soon found it unacceptable and started disagreeing with Cantor, first privately then publicly.
Kronecker's famous statement dates from this disagreement:
"The Good Lord made the Natural numbers. All the rest is the work of man"
He was specifically implying that things like ℝ are just nonsense.
At that time almost all mathematicians were Kroneckerians.
Cantor ended up in an 'institution.'

Other famous statements of that time were from Gordon who said:
"This sir, is not mathematics, its theology!"
[referring to a standard construction of set theory called Axiom of choice]

A couple of generations later things had turned.

Mainstream mathematicians all accepted set theory, except a few trouble-makers called…

Constructivists

led by L.E.J Brouwer, who said that the other mathematicians who they called 'Platonist' (which derisively signified mystic after the cave allegory of Plato) were being ridiculously loose and + sloppy in talking about infinity as though it exists.
Hilbert – the head of the classicists/platonists – was angry with this charge, made the famous statement: "No one shall expell us from the paradise created by Cantor."²

And (in what he thought was super-cleverness) formulated

The Entscheidung problem

If the questions about mathematics could be finitistically (ie mechanically) solved, then the constructivists' charge (of mysticism) could be kicked out once and for all.


 
But then Gödel showed that the dream of a complete and consistent math was a pipe-dream.

A job that Turing completed by showing the unsolvability of the Entscheidung problem. More here

From a math/logic pov these were all disastrous results.  Yet interesting to see them through 3 orthogonal lenses:

 

Technology/Science/Philosophy

Technology
From a technical perspective,  Gödel used only one data structure – numbers – which could get humongous. Turing instead used strings – far cleaner and easier to work with³.
Science
At the science level, Turing – limits of computability – is consistent with and elaborates Gödel's  limits of logical systems.   In fact the proverbial difficulty of Gödel's theorem is taken to be evidence that its deep science. This may be true to some extent.  But its also true that its bad technology. To see how CS-technology can simplify the classic math ugliness of Gödel's proofs see Hehner.
Philosophy
The philosophical cross-currents are the most interesting.  Above Ive talked of the antipathy between the constructivists Kronecker, Brouwer and the 'classicists' Cantor, Hilbert.
Even more interesting are the contrasting outlooks of Hilbert, Gödel, Turing.
Hilbert regarded himself as a classicist but did not see wrong in wishing for a mechanical way of doing math.

Gödel, a true-blooded romantic, hated the thought, but was too timid to say so. It was easier for him to create a 'trojan-horse' – his theorem – to destroy the edifice Hilbert dreamed of than to say so directly.

Turing had the classic scientist/engineer love for mechanism.
Scientifically he could do nothing to Gödel whose theorem was unimpeachable, other than to strengthen and confirm it.  But a side-effect of his engineering outlook and his love for mechanism was something called…

A 'Universal Machine'

Nowadays called…

Computer

In short CS is constructive – or to use the modern word, algorithmic – math.

Today we see that to find and work with a set that
  • Is not nonsensical in the sense of the constructivists' objections
  • And yet is not as far removed from ℝ as float
is still open problem: Constructive real number

An entertaining and longer account by Yuri Gurevich. Particularly note the Polya-Weyl bet.
Also some of the controversiality around Cantor's set theory : here

The issue centers around the meaning of the phrase:

To Exist

Take python.

In python integers (or natural numbers) exist in different guises.
There is the builtin type int. In what sense do integers exist in the type int?

More concrete is for example the way integers exist in the generator:

def ints():
  yield 0
  n=1
  while True:
     yield n

     yield -n
     n +=1


Where for example do these numbers exist when ints is never called or called and immediately discarded?  Where do the characters of a book that is not being read live?

Still more concrete is their existence in the finite int-list [0,1,2,3,4].
Different also how they exist in range(5). Which also changes from python 2 to 3

So while the heat generated by the statement:

Real numbers are not real

was what created CS, most programmers have a more nuanced philosophy than professional philosophers. For the logician/philosopher exists(x) is boolean-valued. For the programmer it tends to be more real(!)-valued.

And in that the computer scientist of today is curiously closer to the millenia-old Plotinus, Taoism, Upanishads etc than to the scientists of the last couple of hundred years. Strangely the attempt at expurgating all form of mysticism from mathematics, mysteriously resulted in making mysticism common fare among computer scientists!

Agree & Disagree: Mystical Angels inside Nanoscule Pins

It is interesting to recapitulate the agreements and disagreements on the subject
Brouwer and Hilbert
  • Agree on banishing mysticism
  • Disagree on the existence of the infinite
Kronecker and Cantor
  • Agree that mathematics starts from God
  • Disagree on the status and place of mysticism in science
  • Both strongly committed to the existence of God (of course their own notions!)
Turing and Gödel
  • Mysticism⁴ — Neither seem to have any compunctions about that.
  • Mechanism — Gödel, the die-hard romantic, hates mechanism. Whereas Turing's basic instincts go directly counter to Gödel's theorem. Turing evinces the most weird combo – believes in souls, loves machines and wishes to put the soul into the machine – after 300 years Descartes comes full circle! 

  • However the Gödel-theorem is inviolate… Now what???

    A back-door!

    If Hilbert's program will not fly maybe a programmable machine will?
As it turns out the programmable machine turns out to be the killer idea that creates much of today's world whereas Hilbert's program, Gödel's theorem remain as little notes in the margin that most of today's generations hardly know about.

The Present

Because some nuts did the 20th century equivalent of:
"Break each others' heads about how many angels can dance on the head of a pin"
therefore much of the REAL World around us exists as it does (for better or worse) including my (and I guess your my dear reader's) degree and job.

Wait a minute!

REAL WORLD? or Virtual Worlds?

or

Real XOR Virtual?

or

Real AND Virtual?


More in posts to follow…
[Here it is CS history 1 , CS history 2 ]

¹ Python List Thread Also
² There's been some controversy around this statement.
  My favorite is the snickering of Wittgenstein: If one person can see it as a paradise of mathematicians, why should not another see it as a joke?
³ Sure string is cleaner than int, but lisp (S-exps) is even neater than string. See Neil Jones 
⁴ O yeah in western civilization it is customary to euphemize 'mysticism' as 'platonism' — a rite that looks a bit mysterious to us clueless orientals!

3 comments:

  1. Real numbers are not real. Stick with rationals, in which you can get as arbitrary picky or as large as you will ever like.

    ReplyDelete
    Replies
    1. How delightfully Pythagorean!
      And so √2 is completely meaningless?

      No to mention that much of modern computer engineering would get knocked off -- eg FFT -- when you knock off ℂ

      Delete
  2. This seems somehow appropriate...

    http://www.smbc-comics.com/comic/set-theory

    ReplyDelete