Godel, Escher, Bach

Part 1 - Godel's theorem.

Godel, Escher, Bach ( GEB ) is the author's personal attempt at understanding the evolution of life, intelligence, intuition, free will and many other question which have puzzled philosophers, biologists, mathematicians, AI developers and such. At the essence of his book lies a very deep and unsettling mathematical discovery - The Godel's incompleteness theorem, and much of the analogies he draws find their root back to this theorem. Hence, I'll first try to describe what this theorem means.
Mathematics is a form of systematic reasoning composed of axioms and theorems. Essentially, all other sciences use math as their base to perform derivations, and to try and explain the real world. Math is what's supposed to be the constant, unfaltering, all powerful tool which settles all disputes by unambiguous method of "proof". The story is that this axiom-theorem approach has what appears to be a big gaping hole in it. It turns out that if the theory is sufficiently complicated then there exist true statements which cannot be derived from the axioms. And if you try to include that in your set of axioms, then you can prove a theorem which will contradict the axiom. In this sense all formal systems are logically either incomplete or inconsistent.
What are formal systems?
Well, lets look at a system which uses three symbols - 'P','Q' and '-'. Here are the axioms
1) xP-Qx- is an axiom when x contains hyphen's only. ( for e.g. ---P-Q---- is an axiom )
2) Suppose x,y,z are all strings containing hyphens and xPyQz is a theorem, then xPy-Qz- is a theorem.
( Ok. I'll give this to you. Interpret the axioms by assigning the meanings "plus" and "equal" to P and Q. )
By using this we can generate many strings ( --P-Q--- is an axiom (1) and --P--Q---- is a theorem ( applying (2)))
( Given 2+1=3, this theorem proves that 2+2=4 etc )
So, this is fairly simple - we have a bunch of strings which can be generated and many more which cannot. For instance apply 2+2=4 again on (2) and you get --P---Q---- meaning 2+3=5 and so on. Observe how we can never produce a string like --P-Q- ( 2+1=1 ).
By successive application of the generated theorems on (2), we generate more theorems. And all these theorems are true ( as in they can be proved from their axioms ). In a nutshell this a what a formal system looks like. The point to note here is that this is not a sufficiently complex formal system. It is a truth-producing system but very limited in scope. You can easily see how formal systems could get more complicated. Our entire number theory ( additive axioms x+0=x, multiplicative axioms x*1=x, commutative axiom a+b=b+a etc ) has been formalized in these formal systems (Peano arithmetic et. al ). In GEB, the author comes up with a what he calls Typographical Number Theory (TNT) ( which is way more complex than the p-q system - containing many more symbols and much longer strings to express truths ). But like the previous system this also churns out strings of symbols which are true statements. So, this entire TNT is like a big bucket of strings which are either axioms or theorems generated by successive application of these axioms. Now what Godel's theorem says is that there exists a string outside this bucket which is true in this system. The obvious question is "what does true mean, if it is not generated from axioms". Well, it means, that this statement and the negation of this system both lie outside the bucket. Basically, in pq system, if I give you a string, you can immediately tell me whether it is a valid string. ( For e.g -PQ---, -P-Q---, PQ, PQRT are all invalid strings and -P-Q--, -P--Q--- are valid strings ), i.e you can tell whether a given string falls in the bucket or outside it.
But, as it turns out, when systems get sufficiently complex and cross a threshold, you cannot make this distinction anymore. This threshold level occurs when systems start talking about themselves. When self-reference is brought into play, for e.g ( suppose PQ system had a string which would answer the question of whether -P--Q----- was a theorem in PQ system). I know in the PQ system, such a string is not possible, but in "sufficiently" complex systems, such strings are possible. In these systems it becomes possible to write strings which say "I am not a theorem of TNT". Then it becomes impossible to assign a truth value to these strings. Quite like the Epimendis paradox "This statement is false" cannot be assigned a truth value. Another statement - "TNT is consistent" when codified into TNT as a string turns out to be a non-theorem of TNT ( falls outside the bucket ), as long as TNT is consistent. The process of codifying such statements into strings in the system is through the process of Godel numbering, which I will not describe here.
OK. So where is the catch?
The catch is to realize that systems, much like humans, though being excellent in stating truths about the world in general, become pretty weak when trying to talk about themselves. The realization is this : when a system has the power to mirror itself in it, i.e it becomes possible to write meta-theorems ( theorems about theorems etc ) in it, the layers in the system become entangled, where a statement means a truth in the one layer and false in the other, making even the most powerful systems collapse. Godel's Incompleteness theorem is a way to telling us that even mathematics cannot inspect itself from the outside. In reference to the system that you are a part of, your attempts to describe the system from the "inside" will always result in an incomplete analysis ( with some truths left out ) however hard you try to look at it from the outside.
Douglas R. Hofstadter describes the struggle to understand this from various perspectives. Some version or the other of this message can be found in Zen Buddhism, paintings by M.C. Escher, music by Bach ( although the music remains alien to me ). With this as the basic idea in mind, the journey in the book takes the reader through the realms of the genetic code to artificial intelligence. The quest to find where intelligence resides, whether the transistors in a CPU, or the neurons of the brain, whether the Operating system of a PC or the mind of a person. The entire book is sprinkled with allusions and isomorphisms to the Godel's theorem and the author believes that the concept of Strange Loops or Tangled Hierarchies is what lies at the core of life.

I'll follow up on this post soon, with many more profound observations ( Author's, not mine ), but if this was not impetus enough, I shall explicitly ask you to please go pick up this book and study it ( yeah! it makes for a pretty heavy read ).

Surrealism and Ki-Duk Kim

An attempt to document my thoughts after yet another Ki-Duk Kim movie. This time it was Bi-Mong aka Dream. Like any of his other movies, this left me speechless, my mouth dry, and my thoughts out-of-world. Spoilers ahead!
As far as I could understand ( haven't IMDB'd it yet ), this movie was about the limitations of our reality and how resolving certain issues requires one to end all association with the current reality. In mundane terms, this is perhaps one of the few films which shows a person suffering, working hard to fix his issues, and then shows suicide as the only resolution. Though the issues faced by both the people aren't based on typical sound reasoning, that is besides the point. Adequate mix of reason in mystic themes and added Arabian-ish Music is perhaps the best stimulus for an open mind. During the one and a half hours of the movie and an hour after, your mind cannot simple fathom the trivialities of this world. For a while _nothing_ really matters.
Ki-Duk Kim's movies are almost like a new form of stimulating the brain - just like Audio and Video. But using combination of these at the base layer, this director takes you to another level, where you are not analysing the song, or watching the movie as a bunch of sequences or like a story line. His movies talk to you in a language you cannot express, but you understand. It amazes me how he pulls out these highly abstract ideas, and their meta-ideas, effortlessly.
If you are planning to watch your first Ki-Duk Kim, I strongly suggest Bin Jip aka 3-Iron. It is my favourite and has relatively unambiguous interpretations. Other movies like The Isle, and The Bow require deeper levels of appreciation, some perhaps bordering on the edge of sanity.

You can kill only if it is alive

I posted this a long time ago, then read it, found it controversial and deleted it.
Apparently it was being shared in Google Reader.
I've decided to post it up again.
( Now that I am thinking of ideas far more controversial than this )
Here it goes ...
by Saran on 5/12/09
-------------------------------------------------------------------------------------
My Final year Project is finally done and my mind can't wait to resume day dreaming.

Saw a Romanian movie a couple of weeks ago. 4 months, 3 weeks and 2 days. It is basically about a 20-something woman trying to get an abortion, during the times when it was illegal. There was not really anything much to the movie, but the topic is thought provoking enough to keep one interested. Abortion.

In most countries there is a time after which you cannot legally terminate a pregnancy. It is usually around 25 weeks. The reasons stem from both ethical and practical concerns, but I am going to discuss only about ethics here. A major issue is to distinguish murder from abortion. And to do that we need to define when a mass of cells come alive. And to do that we need to define what is Alive.
And sure billions of human hours must have been spent on trying to define this. I'll attempt to do that trying to be cogent enough to an average individual.
As far as I am concerned, I am as alive as a Computer, but we'll come to that later.

Is a virus alive? Even medically it is a cat on the wall. Is bacteria alive? say single celled bacteria? Medically yes. Is the sperm and the egg alive? They are single cells. Well anyway, when they meet and form embryo and cells start to reproduce ( mitosis, meiosis ) they cells are alive. ( Only living things reproduce ). So when you terminate a three month old foetus, its cells are alive, but it is not alive as such ( going by law ). If it were, then the act would be murder. So, we can conclude that there is a difference between a clutter of live cells and the organism being alive.

When should we say, the baby comes alive? Heartbeat? No. Heart starts beating in the fifth week. How about this? As soon as the baby receives sensory inputs from its surroundings, its brain starts to process them and generate results and observations. The process of learning begins after the baby has opened its eyes and ears - when it is out of the womb. How about calling this alive?
So basically, a mother has the right to kill her child until the time the child's brain processes external stimuli. Until then, it is simply the mother's property. Just like her fingernail, her hand, her computer. It is all hers.
Well. OK. Now lets talk about what right a mother has to her baby. Can she filter sensory inputs? Yes. ( Parental filter etc on the web :P ). To what extent? Now, what if the mother, when the baby was her property, decides to block all input to its brain. ( Say she suddenly decides that the world is an evil place ). She keeps the baby in a dark room, sound proof and all that. No sensory input. No brain development.
She can still destroy her baby? Can't she?

Well, that was a question for you people.
As for me, acknowledging that I am no more than a computer, my mother can ethically terminate me whenever she wants. It is through her kindness, that I am free.