Search This Blog

Friday, July 31, 2015

Faith and Rats, Gödel and Computer Science

Computer scientists dismiss Gödel as mathematics
Mathematicians classify Gödel as logic
Logicians slot Gödel into meta-mathematics
Meta-mathematicians know the truth of the matter…
…and have been dead for a century

I would like to suggest that this misunderstanding (or rather non-understanding) does not make it non-true.¹ Many educated people do know that Gödel’s theorem(s) is important even portentous. But somehow – like war – Yeah its bad but not my problem.

Let’s use the services of
A fever is raging in the town.
People are dying.

And I happen to find…
In the closet…
A dead rat

“What do rats have to do with…”

The Plague?

Do we need to start having a fever and swelling in the armpits to change our minds?
To my mind the mathematicians and CSists who think of Gödel as irrelevant are like people with a dead rat in their closet who are now beginning to run a fever and who still keep insisting:
“Whats a dead rat to do with the plague? Why should I bother?”
Gödel’s theorem is a dead rat in plague infested town. In the 1930s, people understood this. Somehow now everyone has forgotten. This post is to remind of these well-known and more well-forgotten facts.

The Terrible Theorem

Starting with the cute paradoxical statement

This statement is false

which is true if its false and false if true,  Gödels theorem maps out the large gulf between what is provable and what is true.
Now on the face of it this seems like a ridiculous thing to make a song-n-dance about. Surely there are truths that we dont know (yet)? What of it? Then science studies better... Then some more truths are revealed... etc...

To understand why its a big deal we need to understand the difference between

Analytic and Synthetic Truths

Excerpted from http://plato.stanford.edu/entries/analytic-synthetic/
Consider these statements:
  1. Some doctors that specialize on eyes are rich.
  2. Some ophthalmologists are rich.
  3. Many bachelors are ophthalmologists.
  4. People who run damage their bodies.
  5. If Holmes killed Sikes, then Watson must be dead.

  6. All doctors that specialize on eyes are doctors.
  7. All ophthalmologists are doctors.
  8. All bachelors are unmarried.
  9. People who run move their bodies.
  10. If Holmes killed Sikes, then Sikes is dead.
Most people would understand that the ‘truthiness’ of 1-5 is fundamentally different from that of 6-10. 1-5 are examples of synthetic statements; ie they are verified or disproved by objective facts, ie facts about the world.
6-10 – the analytic statements – are true independent of any facts. Their ‘truthiness’ is inherent in the sentence itself, ie by definition.
One can easily imagine a world in which 1-5 are not true. However if someone claims that statements like 6-10 are untrue then we would rightly conclude that (s)he’s loony.
Whereas our normal common sense comprehends the gap between what is true and what we can prove in the synthetic domain ie in the world, Gödel shows the same gap in our language, in our thoughts, in our understanding, in us!

History

Most CSists know that Computer Science as we know it started with Turing’s 1936 paper. But that paper was a followup to Gödel’s 1931 incompleteness results. Yeah Turing used better data structures – strings – than Gödel’s numbers. A B-grade CS-sophomore would be able to point this out today. There were no CS-sophomores then, so Gödel’s technology was – by current standards – clunky.

But today I dont want to concentrate so much on Gödel's technology as his wider philosophical impact. And from that pov CS starts with Gödel — Turing just added an important footnote.
Now given that plague rats dont distinguish between mathematicians, philosophers, CSists and other men, lay or professional, it should be no surprise that it affects all these…

Math

Mathematicians traditionally are ‘proof-freaks’ – you dont just make statements, you prove them. Gödel demolished this agenda – there are true statements that are not provable.
Most practising mathematicians believe that yes this is a disaster but its far away.

Black holes exist in the universe and they can swallow up every thing in sight including space and time…
But they dont happen ‘around here’… 

Or so they think…  Until one turns to…

Computer Science

There have been a few odd ’proof-freaks’ in CS also such as Dijkstra, Hoare and their followers who’ve made a religion of proving (all) their programs.
Most practising CSists ignore them saying that in practice:

Real programs are unprovable, Provable programs are unreal

Gödel shows this is not just true in practice but in principle as well.

Consider this scenario:
I want to prove that my python interpreter does not have an infinite loop. But it obviously has! The program
   while True:
       pass

loops which means that when given as data to python throws python (the interpreter) into a loop.
So we need to refine our proof requirement from
     python interpreter does not loop
to
     python interpreter does not loop for a program that does not contain an infinite loop

But detecting whether an input program contains a loop is exactly the halting problem and so we cant solve it!
In short Gödels theorem is hitting us every day all the time via unproved programs. And Dijkstra/Hoare’s program to prove all programs is just an anachronism of Hilbert’s program to prove all math.

In short these gentlemen are vastly well-meaning and more vastly deluded.
Plague rats dont discriminate! In fact they even (gasp!) catch the religious faithful!

And for the religious believer the destructive Gödel-question is:

Is faith analytic or synthetic?

Do we smell a plague-rat?…

You see if faith is synthetic, ie dependent on observation, then its only a question of time before its destroyed.
OTOH if the faith is analytic that is not dependent on any observable datum then its of course indestructible but it is also empty – a tautology.
So the plague-rat evidently does not spare the true believer any more than the CSists and the mathematicians.
Whew!” we sigh “I am just an ordinary lay(wo)man going about my work. Not a CSist, not a mathematician, certainly not a religion freak.

Hmm… By now I would have thought that we understood the shameful lack of discrimination shown by plague rats… Anyway here goes.

    You do use some basic amenities of life provided by modern technology?
    Which is based on modern science?
    Which has some assumptions?
    And how is an ‘assumption’ different from a ‘belief’?

Some stories of how when Gödel infects faith, it can range from being mildly amusing to literally dead-ly.

Story 1

Some years ago there was a great furore that “God-ganesh was drinking milk!! Supposedly all across the country in temples of Ganesh, the idol was drinking milk. Some of us may remember…
What actually happened then I have no idea but I vividly remember the extreme eagerness (desperation?) with which the rationalist (so-called) establishment was rushing off with their explanations – capillary action and more and more far out ones which have not survived into the wikipedia link above.

The overwhelming impression was of fear: “What if Ganesh actually did drink the milk?!? Calamity for science!!!”² The overall impression I had of that time was that the scientists (so-called) were super-desperate to give ‘explanations’ and had no compunctions of doing so without any attendant data or facts.

An impartial careful investigation would show that the scientific community is more full of unfounded beliefs than the religious. They believe that their so-called ‘controlled experiments’ can actually control the variables to such an extent that universal laws can be revealed. And all kinds of other well-known ‘assumptions of science

Here is some more

Scientific Faith 

that scientists subscribe to knowing full-well they cannot exist in nature; ie balderdash:
  • Straight lines
  • Ideal Gases
  • Continuous Processes
and dozens of others.

In fact it would be accurate to say that among all the religions, one popular one is ‘science’ and it is among the more unrefined and stupid of the available religions because the religious faithful (at least the more refined among these)
  • knows he has faith
  • knows it is fragile
  • yet cherishes it
The scientist on the other hand
  • is completely unaware of his many sundry beliefs
  • sees nothing questionable about these
  • gets mad and wants to eliminate anyone who questions these
In CS-lingo, for the religious person, more than for the typical scientist…

Faith is first-class

[Psychology/philosophy calls it reification]
For the weight-lifter or body-builder, his body is his resource but its not a given.
ie he needs to work at it, develop it.

For the religious person, faith is likewise a valuable resource but it needs to be developed.  This is in fact the

Transaction of Faith

Whats's a 'transaction' in business?
Quite simply in order to receive, one first has to spend
  • A manufacturer needs to spend on workers and materials
  • A service provider needs to spend at the least on time, effort, education and usually also attendant materials 
  • etc
before they can earn.
Apart from the 'business of begging' this is the universal law.
The same applies in religious matters -- we need to believe before we receive conviction of the belief.

Stupid-skeptics find this requirement objectionable.
Not realizing that this requirement is universal. Say I go to a piano teacher and say "I want to play Beethoven's last sonata (or play like Art Tatum)" Lets see two possible answers:
  1. Wonderful! Lets start
  2. Umm.. Can I check your scales please?
Most sensible people would see that 2 is more honest. And it requires more faith on the part of the aspiring pianist. "Awww! I see/hear no scales in Beethoven/Art Tatum! Why do I need to waste my time?" To which the appropriate answer would be: "Very well! Find someone who you trust then!"

Personal note: As a teacher in a CS dept who often had to teach math/theory courses, I was often faced with the question (sometimes very silently!): "Why the &*#^% do we need all this stuff!?!"
"You need to trust that the people who made the curriculum know more about CS than you do." In one word -- Faith!

Coming to Gödel: the dialogue basically is this:
Hilbert:
If we can have a mechanized way of proving theorems, all our doubts are dissolved.
Gödel:
You want a freebie. There are no freebies. You must pay with faith before you receive understanding. Mechanized proofs – like perpetual motion machines, minting one's own money etc – nice ideas, nonsense in practice. Math is too divinely beautiful to be caught in your mechanized machinations.
Just as a successful business happens by spending towards earning; earning to spend, a successful, effective faith needs to swing between analytic and synthetic modes.  Maximally analytic would run along the lines:
Since God is by definition God, all's right with the world.
Sounds nice but does it help me? Notice the tautology and the disconnection

Maximally synthetic would run along the lines:
<Favorite divine personality> is such a nice guy/gal 
(because) (s)he always tickles my ... when I need these services.

Nice Until the next time the services are not forthcoming and my faith is shattered

And so

The Active Practice of Faith

consists of
  • Strengthening by making it more independent of people, things events ie analytic
  • Real-izing by making it more objectively verifiable ie synthetic
Do we notice that like investing and earning these two pull in opposite directions?

What Gödel's theorem does is it precisely maps out arena where faith is necessary:
  • Things that are provable dont require faith.
  • On the other side, completely unbelievable things cannot be buttressed by faith.
  • It is the interim arid but not completely dry patch that is fertilized by faith.
For example Gödel himself had a deep faith in platonism, something which most philosophers (in western civilization) regard as quasi-religious rubbish.

Rather than a mere academic matter, it was something that deeply mattered to him. Hilbert's program of mechanizing mathematics was violently offensive to him and it was this faith and the corresponding conviction that Hilbert needed to be stopped that drove him to produce his terribly destructive theorems.

As also Hilbert.  Gödel seemingly destroyed this. But it lives on billion-fold multiplied by every computer – and program! – that is made.
Hilbert formulated his program out of his faith that mathematics could be saved. [His grave carries the inscription: We must know! We will know! 

Faith is the Fundamental Investment

Businessmen roll their money. Some get miraculously rich; some have a limitless possibility losing to their gambles. That is to say they of course need money to start with, but more important, faith in the rightness of the investment. 
So it is in all walks of life — science, art — something personally valuable is staked and these stakes can at times go horribly wrong.
The speciality of the religious-faithful is that like businessmen rolling their money, they roll their faith but for them more than for most others there is the awareness that the faith is first-class. Usually this is expressed in terms such as faith is a valuable gift and must be guarded jealously.  Scriptural statements such as:
  • Do not take the name of God in vain
  • The sin against the Father can be forgiven and also the sin against the Son but not the sin against the Holy Spirit
are really just corollaries to this recognition of the preciousness+fragility of faith.

Investment can only ever be unsafe — imagine an old pensioner who puts all his money into the safest place – govt bonds – who happens to be a Greek!
No! Resting safely is only an option when we  ‘rest in peace!’
  • Marie Curie got a Nobel and death thanks to her science
  • Bolyai went mad by his non-Euclidean researches... which led on through Lobachevski and Riemann to Einstein.
  • Beethoven almost killed himself when his faith in his music was unable to withstand the fact of his deafness which would later become a factor for the reunification of Europe
  • Abe Lincoln, Mahatma Gandhi, by most accounts achieved superhuman feats by superhuman faith in their calling. They also got death for the same
In short faith is a terrific and terrible force — miracles, death, both.

Ironically scientists who deal with force at the material level don't (typically) understand that faith is a terrific force at a spiritual level, irrespective of whether the label applied to the faithful is ‘scientist’ or ‘religious’

Unsurprisingly then, belief can be deadly dangerous as illustrated by the second

Story 2

A certain godman – lets call him A – was famous for ‘materializing’ gifts for his devotees. One rich old and ardent devotee went to meet him and presented him with an expensive jewel-studded watch. After staying with him a few days as he was about to leave, a new devotee came to him and enthusiastically informed him that A had materialized a wonderful gift for him. And showed him the ‘materialized’ gift – the identical watch the first devotee had presented him.
The guy was naturally in a tizzy. He went to A and said: “You are my guru, You are god, So what you do with my gifts is completely up to you. But please tell me you didn’t materialize that watch!

A was furious and threw him out.

The man was completely devastated and for a few days wandered about unable to do his work. In the end he was found under a train – he had committed suicide.

As a thought experiment let's ask ourselves the question: 

Of the psychic energy he invested in his belief-system, if he had spent a small fraction on the question: "Is my faith analytic or synthetic?" would he have killed himself?


Today is

Guru Purnima

So my offering to the guru-principle is the meditation on the questions:
  • What does ‘guru’ mean?
  • How much faith is dangerously too much?
  • How many of my sundry, unexamined faiths can be discarded?
  • And which faiths are so precious that at peril to life, I would still keep them?

Acknowledgement

An old student of mine expressed his gratitude to me in a form too strong for my comfort.  I suggested to him the need to inject his faith with a healthy dose of doubt. This post is the result of these arguments.

Whether he minds my words or not, lets hope he minds a smelly old rat!

Footnotes:

¹ Yeah this is a meta-circular application of Gödel to this discussion!
² Like the series of popular "change a light bulb" jokes current today, my dear father used of have a series of jokes about the fly in the tea served by the irani restaurant. One of these ran: Its just a housefly; How much of your tea will it drink?

1 comment:

  1. Mmm.. good to be here in your article or post, whatever, I think I should also work hard for my own website like I see some good and updated working in your site.
    Bios Chip Asrock

    ReplyDelete