RSS
people

All About Infinities

The set theory taught to us in the secondary school levels has a big trouble — It cannot be called a theory in the first place. For it suffers a contradiction, viz.,

Let us call a set “abnormal” if it is a member of itself, and “normal” otherwise. For example, take the set of all squares. That set is not itself a square, and therefore is not a member of the set of all squares. So it is “normal”. On the other hand, if we take the complementary set that contains all non-squares, that set is itself not a square and so should be one of its own members. It is “abnormal”.

Now we consider the set of all normal sets – let us give it a name: R. If R were abnormal, that is, if R were a member of itself, then since R only contains normal sets, R must be normal, which is contradictory to our original hypothesis: R is abnormal. So, R cannot be abnormal, which means R is normal. Further, since every normal set is a member of R, R itself must be a member of R, making R abnormal. Paradoxically, we are led to the contradiction that R is both normal and abnormal.

This paradox is, often, referred to as Russell’s Paradox. Fortunately, consistent set theories exist — One of them is Zermelo–Fraenkel set theory.

Coming back to the informal set theories taught to us — these are attributed to the legendary Georg Cantor. Besides set theory, he gave us the wonderful notion of countable sets, uncountable sets and infinities. In a revolutionary result, he claims the following–

Not all infinities are of the same size! He, also, claims - Give me an infinity and I shall construct an infinity bigger than yours!

Informally, he claims In particular, the power set of a countably infinite set is uncountably infinite.

There are few more interesting things that come out of Cantor’s Results

  • The ratio number of problems that can be solved on a computer to those that cannot be solved is exactly equal to the ratio of number of Natural Numbers to Real Numbers.
  • He, also, goes on to prove that set of real numbers is the smallest infinity that one can find.
  • The number of Real numbers between 0 and 1 is exactly equal to the total number of Real numbers!
16 Comments | Tags: , ,

Title Wrapped up

No, No. I am not referring to the English(Indian) Premiere League or Serie A. Those are the ones I am least concerned about these days. The past week or so has been very hectic for me. Hmm…..Hmm….. So, after an indecision/dilemma for about an year or so - its finally decided and fixed.

I will be graduating this convocation with a B.Tech (Hons) and a Masters by Research in Computer Sciences. The last week was spent in writing and compiling the first draft of this thing.

The title of the work will be “Agreement can be Easier than Point-to-Point Communication”. Informally, it is about the following — Given a network of computers, it may be possible that the computers will not be able to reliably communicate/route messages to each other but they can agree on something. Per se, agree on whether a database operation has aborted or been committed. In this work, we characterize the networks over which agreement is possible but Point-to-Point Communication is not (that is, we give the give the connectivity requirements of the network and the ratio of faults to non-faulty computers).

The result sounds both baffling and fishy at the first look as we generally expect any sort of agreement/consensus measures to have reliable communication as a prerequisite or may be even a sub-routine call in the process of reaching a consensus. Our results, however, prove otherwise - Consensus/agreement protocols seem to be more fundamental to network/distributed computing than Point-to-Point Communication!

I am nearly done with my burden and hence, hope to get back to blogging on things I left behind. A couple of drafts have been lying on the hard disk for sometime now :-)

[Esc]:wq

7 Comments | Tags: ,

A World Without Time

 In 1942, the logician Kurt  Gödel and Albert Einstein became close friends; they walked to and from their offices every day, exchanging ideas about science, philosophy, politics and the lost world of German science in which both had grown up. By 1949,  Gödel had produced a remarkable proof - “ In any universe described by the Theory of Relativity, time cannot exist.“ 

   Einestein endorsed this result reluctantly, but he could find no way to refute it, and in the half -century since then, neither has anyone else.  Among all the contributions of  Gödel - this one is certainly the Queen and most of the times goes unnoticed.

      In case, you are intersted to know more about this particular result of Gödel – refer “The Forgotten Legacy of  Gödel and Einstein” by Palle Yourgrau.

 ——-

        For those readers, who are unaware of  Gödel’s contributions to Computer Sciences and Mathematics; I compose this brief overview about Gödel’s result from Aaronsons’ lectures.

There’s an amazing result called Gödel’s Completeness Theorem, which says that these rules are all you ever need. In other words: if, starting from some set of axioms, you can’t derive a contradiction using these rules, then the axioms must have a model (i.e., they must be consistent). Conversely, if the axioms are inconsistent, then the inconsistency can be proven using these rules alone.

Well, alright, I guess a year later he proved the Incompleteness Theorem. See, the Completeness Theorem was his Master’s thesis, and the Incompleteness Theorem was his PhD thesis. Apparently, one of his PhD examiners didn’t want to give him a degree because the PhD thesis was “too similar to the Master’s thesis.”

The Incompleteness Theorem says that, given any consistent, computable set of axioms, there’s a true statement about the integers that can never be proved from those axioms. Here consistent means that you can’t derive a contradiction, while computable means that either there are finitely many axioms, or else if there are infinitely many, at least there’s an algorithm to generate all the axioms. (If we didn’t have the computability requirement, then we could simply take our “axioms” to consist of all true statements about the integers! In practice, that isn’t a very useful set of axioms.)

Once you have Turing’s results(there doesn’t exist a computer to solve the Halting problem), Gödel’s results fall out for free as a bonus. Why? Well, suppose the Incompleteness Theorem was false — that is, there existed a consistent, computable proof system F from which any statement about integers could be either proved or disproved. Then given a computer program, we could simply search through every possible proof in F, until we found either a proof that the program halts or a proof that it doesn’t halt. (This is possible because the statement that a particular computer program halts is ultimately just a statement about integers.) But this would give us an algorithm to solve the halting problem, which we already know is impossible. Therefore F can’t exist.

By thinking more carefully, we can actually squeeze out a stronger result —  if a system is consistent, then it can’t prove its own consistency!! 

Let P be a program that, given as input another program Q, tries to decide whether Q halts by the strategy above (i.e., searching through every possible proof and disproof that Q halts in some formal system F). Then , suppose we modify P to produce a new program P’ that

  1. runs forever if Q is proved to halt given its own code as input, or
  2. halts if Q is proved to run forever given its own code as input.

Now suppose we feed P’ its own code as input. Then we know that P’ will run forever, without ever discovering a proof or disproof that it halts. For P’ finds a proof that it halts, then it will run forever, and if it finds a proof that it runs forever, then it will halt, which is a contradiction.But there’s an obvious paradox: why isn’t the above argument, itself, a proof that P’ will run forever given its own code as input? And why won’t P’ discover this proof that it runs forever — and therefore halt, and therefore run forever, and therefore halt, etc.?

The answer is that, in “proving” that P’ runs forever, we made a hidden assumption: namely that the proof system F is consistent. If F was inconsistent, then there could perfectly well be a proof that P’ halts, even if the reality was that P’ ran forever.

But this means that, if F could prove that F was consistent, then F could also prove that P’ ran forever — thereby bringing back the above contradiction. The only possible conclusion is that if F is consistent, then F can’t prove its own consistency. This result is sometimes called Gödel’s Second Incompleteness Theorem.

3 Comments | Tags: ,

Good Bye from Prof. Venkaiah

It is, indeed, sad that Prof. Venkaiah will be joining the CR Rao’s Advanced Institute of Mathematics, Statistics, and Computer Science. He has contributed a lot to IIIT and has certainly left his marks on us as well as the Institute. The void created from his sabbatical at IIIT (officially, Prof. Venkaiah will be on leave for an year) will be greatly felt. I hope he returns back to offer courses and projects here at IIIT, Hyderabad.

Prof. Venkaiah has got his doctorate from IISc bangalore and has done a lot of work on number theoretic, graph theoretic problems like factorizations of a graph and designing crypto systems. Rather, his doctoral thesis was entirely on the knapsack problem and its variants. The courses offered by him viz Data Compression, Algorithms, Cryptography and Network Security have been phenomenal successes (in terms of shear numbers of students willing to register and attend his lectures).  If I am not wrong - his courses have the highest number of registrations year after year. For when I was in the first year of my study at the Institute - I always wondered how can Prof. Venkaiah teach 150+ students. It was not until my 3rd semester when I got an opportunity to do a course with him. It was when I realized the amount the work he puts in to his course and the background study/reading he does. I still remember the professionalism and the formalism with which he teaches and carries himself around. Besides all this, his contributions to the Campus Green Club have been staggering - We have seen an unprecedented improvement in the percentage of green areas one can find in the campus. All I can is - We will greatly miss you, Sir.

This was probably the first time a Professor said a Good Bye to his students at IIIT and following mail will remain in my heart forever.

Dear All,

I have an offer from CRRao’s Advanced Institute of Mathematics,
Statistics, and Computer Science. So, I have resigned for my post at IIIT,
Hyderabad. I will be leaving around 20th May 2009 or latest by 20th July
2009.

In case you want to meet me, you may do so by reaching CRRao’s institute
located in Central University of Hyderabad.

You may also sparingly use my cell number XXXXX to contact me.

Wish You Good Luck,
Venkaiah

Let us all convey our best wishes to Prof. Venkaiah when he takes up a position at the CRRao’s Institute. On behalf of all the students of IIIT, I hope that Prof. Venkaiah enjoys the same phenomenal success which has tasted all through his years in IIIT.

Adios.

6 Comments | Tags:

Jivan Vidya and The Lost World of Atlantis

Let say a cricket match is being played out  between India and Pakistan and 3 spectators - A, B, C - are watching the match. A is from mumbai and loves a mumbaikar doing well. Rather, due to regional differences hates Dada, laxman or even Dravid performing. B loves India and likes Indians to perform well and hates Pakistan winning/playing well. C, on the other hand, is an ardent cricket fan and enjoys cricket. It is but for obvious that A, B, C are in third different classes and have different levels of understanding. Rather, what is also obvious - all the three do not understand/appreciate the same language (in our example - language is cricket). All three of them need not enjoy the same fact/sequence equally. Along similar lines - I think the questions, concerns raised in the previous post were at the very first level. This post tries to raise questions(answers) at the next level.

Understand that - it is fine if the student aims to get into Google/M$/Amazon. But, understand that an Institute cannot have aims like - place all student in an MNC. An Institute has bigger vision and plans. IIIT aims at creating a good university for Indian conditions - make higher eduction more accessible to the masses.

At the fundamental level - the education models (10th,+1,+2 and then engineering) and their evaluation criteria itself call for debate. The current day models have been lifted from western ones created earlier. But, one needs to understand that the demands of a western society and Indian society differ drastically.

In short, we need to create universities with processes that address our needs. We need to create our own Atlantis. Our own India. For that, we cannot expect others to make models/solutions for us. We have to indigenously work out models that work for us.

IIIT has set itself goals of national importance. It is in that plane Prof. Sangal and IIIT speaks, where as the students speak/address from a different plane and perspective. It is important for us to understand from which plane we are speaking and at what level are we attempting to find solutions. The solutions that the Institute is looking for are in a different plane altogether. IIIT wants to create models to make an Atlantis from every university in India. Clearly, this is a much tougher job.

One such model which might help us to achieve the optimal from an university is Jivan Vidya. Jivan Vidya aims to optimally utilize resources in an Indian environment. It is obvious that we should play to our strengths and in particular - the strengths of Indian Civilization. No matter whether you like or not - you carry the luggage of a 2000+ years culture.  The questions raised by the Western civilization for the need of higher education are valid for any setting - however the solutions may drastically differ. In order to create solutions for our setting, we should understand the differences between the two settings. Below is a speech of Prof. Sangal making an attempt to identify the differences and create models to suit the current day needs of the country. This is one is remarkably different from all the ones being delivered under the banner of Jivan Vidya. One particular significance of this one lies in the fact that - Prof. Sangal dons the hat of a researcher and analyses the needs for new models. It is not a yet another JV talk! There are no Human Values being discussed here!

I request the readers to go through this (may be slightly large, but nevertheless gives an Idea of what the bigger picture is!) and not start with any prejudiced opinions. I think this speech answers all the questions being raised in various blogs and other places. I think this speech is scientific and has a lot of thought put into. I also think anyone who has not read/understood this cannot really understand the questions being raised and the stand of Institute on various things.

There is some minor editing done.  This was said in the PPST (Patriotic People Oriented Science & Technology group) meeting. You may read more about PPST online. It  is a group that was started at IIT K when Prof. Sangal et al were all of our age group. Just read through it:

Prof. Sangal then spoke of his thoughts and said  -  We are searching for what is it that will leads us to human civilization. It appears that Indian Civilization has achieved - sort of the right direction - has gone towards this human civilization - then the historical interventions took place and changed our path to go towards the Western Civilization. In some ways the West was perhaps not acquainted with Indian Civilization in that sense, otherwise even they would have wanted to go towards what is the human civilization.

Western Civilization - the causal closure of matter and the engagement of science and technology with it - you assume that everything - mind-body divide and everything you need to know - we have to study matter and in some sense there is nothing outside that, and in some sense that course also has run through and we reached where we are today. In that course,we have split the atom. Two atoms have been split. One at the physical level - to create the nuclear bomb - the other atom is at the social organization level - the family. That split is also completed. Just learned that divorce rate has now crossed 50%.

Western Civilization with its assumptions and largely the science and technology which developed with those assumptions rapidly - something was thrown out, the other things are thrown away as and what remained are residues which are to be housed in humanities and some times other things and I think that what was thrown out was human being. So in the Western Civilization what was thrown out was human being retained was matter - the conclusion is strife within family, strife within society, strife with world, strife with nature. Human being could not fit in this order, we will change the human being and create a industrial worker, if that were not sufficient, we will create IT worker but at most we will create a citizen and certainly not human being. Citizen is someone who obeys all these rules and whatever there in a human being is thrown out and he need to be made to a template of at most a citizen - but mostly as a white-collared worker, blue collared worker. There appears to be - may be you could call it crisis, because there is no good answer to it - you go to Iraq but you do not know what to do. The other thing which has happened appears to be serious is - if India and China follow the same path then earth is finished, it appears. Earth may be more resilient, but it appears that greenhouse gases and all kinds of things may happen. We have sort of reached a dead end. What is the way out of this situation? We have to bring back the elements that we have thrown out of knowledge. The element that was thrown out was human being. The element to bring back is the human being. When you look at Human being - he seems to be unpredictable, indefinite - so you cannot study an indefinite - when you study him - you cannot bring morality in your knowledge - you can only curb it, you can curb his evil tendencies - you can make him into a citizen - you can make him into a disciplined him - you can control him - that can not be part of knowledge - knowledge is exploration, - there is no space for study of human being. The people of who study human - religion can’t be part of scientific study, there will be mystical elements; things may or may not be logical - thanks to various things - people need that - man is a questioning mind - common man - at the physical dead end; at the knowledge level that is the dead end. Those were the two dilemmas that allude us. - that is where we were looking, sudden - we found Jivan Vidya - firstly human being is not indefinite - which means there are invariants; there is an invariant we can study about. we can reason about - that is the method which we can study - and that is - one new element that is needed - when science understood observation and theorizing, then it said you cannot observe yourself - you can only observe something outside. Any observation of the self is not admissible. When you study a human being, you study him as a psychologist, you conduct experiments on him you study some external parameter,if he says that I am so and so, it appears to me, that at the epistemological, I do not what the right words here are,that observation has to be brought into admissible nature for theory making. A month ago, there was this large Intl. Conference - one of the invited speakers, who is a serious researcher - he put up this slide - You need to rethink what AI is all about - and then he talked of the characteristics of east and west - and then he gave a technical talk, gave some interesting examples and then said - if you shift the viewpoint - then there is a solution to the frame problem - which is an unsolved problem in AI. After the talk I went and talked to him - he also heading a IIIT, newly formed, in Japan, I talked to him about it and he said I have a paper on that. I immediately downloaded it, and was surprised that he was talking of the observation of the admissibility of the self and what needs to be done.

At the level of the method, there is no reason to assume that observation of the self cannot be made or cannot be formalized so that I don’t feel what comes to me without proper observation or without proper control - just like in science we have control in what is observed there is no reason to believe that a similar control cannot be exercised for observation on the self. If I am feeling happy or if I am feeling, psychology says none of this is admissible, and we have to watch your behavior to feel whether you are happy or sad. and that will bring us to the Searle’s Chinese Room experiment.

That there is a fundamental problem in trying to say that you can create awareness through mechanical means. No matter how intelligent a machine you make - it cannot be aware. So it seems to me that the advance in science also is required to incorporate this.

And in one way - the two problems in civilization - we have run into the dead end at the physical level and dead end at the knowledge level. The way out in the knowledge level would be - we need to bring human being back into knowledge. The self and consciousness of the human being need to be brought back, the body was retained by the medical people. If we do that, and Jivan Vidya says and talks about the invariance in the self and consciousness. And it is possible to do experiment, it is possible to study human beings scientifically - once we do that, an empirical claim that it makes is that all human beings feel happy when they behave in a certain way that is which creates harmony - that is good news. If human beings feel happy while creating harmony that is good news, but if it were not so, that is bad news, nothing can be done about it.

And what we need to do so this artificial man that was created through society, education - the society keeps constantly telling us - you have to cheat, hurt to succeed - then we say that - in fact if you cheat you feel unhappy. Actually the thing starts from there, there is a notion of preconditioning that is brought in here. When you make an observation, the observations are very direct, very raw. If you remove the preconditioning and that is the part of the practice of Jivan Vidya. It is not that the moral philosophers need not be a moral man - a moral philosopher will be a moral man if he wants to be happy.

Once we do this , then whole thing actually connects up - it relates with relationships very strongly. It relates to society, but large questions of society JV has left open. It has given that these are the elements of society - there is an element of production, element of trade, element of education, element of justice, … and after that how it needs to applied needs to be worked out.

It is sort of giving a definition for what is human civilization. And that human civilization is not artificial, it springs out of naturalness of human being, that is the good news. We need to work towards that human civilization to be happy which turns out to be the goal of everybody. So if that becomes a goal, it connects up with the society and opens up large spaces for inquiry about what kind of society we want to build and with respect to the criteria laid out, only the criteria - in fact - you judge these criteria yourself - it is not going to say do this and don’t do this - it will give you general criteria, it will give a process actually, and you follow that process and apply it in your own way. And then fairly remarkable set of conclusions are there, which if I say you would say it can’t be. Economics begins by saying -resources are limited and desires are unlimited, then there is going to be strife.

Jivan Vidya says the opposite - needs are limited, resources are unlimited - practically. So, those conclusions don’t take it because Jivan Vidya is saying it, but do it by applying a process and that process itself is open to question - the process is called - Sahaj Sweekriti is also open to investigation.

So if we talk of a human civilization - what is our notion of what human civilization ought to be - JV does not say ought to be it say that is what it is because that is what is natural. What is the notion of human civilization - then we can compare the Chinese Civilization - Indian Civilization - Western Civilization - and take the best. What choices they made and if we look at that -it appears that perhaps Indian Civilization made very conscious choices of simplicity, of making it not on hierarchy, but based on relationships - where the role of the king was so little and one can look at the past. How does one look into the future? Can those ideas be taken and applied to this world? Given those ideas how do you apply today? How will you come up with a new idea? You have a bench mark and a standard - in some sense the situation is ripe today in India. At the knowledge level, Neural Sciences and Cognitive Sciences moving in a certain direction. Internet - from the knowledge point of view, things are very ripe. Jivan Vidya claim is universal. It will even stand on a plane that is like a scientific and as strong a claim as that - at the implementation level - it will be very local, looking at the scenario and surroundings - how we apply. Knowledge level is ripe, but that is at the large - international level. In India, I do not know about the social sciences, and humanities level, we do not have a large effort in Cognitive Sciences, at the physical level or the social organizational level - things are very ripe - there is a large middle class - which appears to see that which aspirations can be met and it can move ahead. The changes are so rapid, if the change is slow - one does not see the the good and bad cannot be seen so fast. The change is so fast that people are suddenly not able to see the bad, but they see the good part - physical facilities part - what the earlier generation earned at the end of their generation are now able to earn them in their beginning itself - small number but not so small number.

There are associated ills - a very strong consumerism - that is why this disturbance. When JV shibirs are held - who are the people most attracted? It is the young people, it is also the old people. As a remark - when I went to Mussoorie for the I shibir - I came here to see some old people - but these are all young people in their 20s, 30s and 40s; because the young people have suddenly seen this rapid, and easily there are 10% of the population who would come to PPST, without doing anything - who are concerned about issues but they were not finding space, or rest of them were telling them you will spoil your life.

Suddenly they find a path, that path is by answering their own self, by focus on the self. And the focus on self, can be as rigorous as science. That is what Jivan Vidya tells, provided we include one observation that observation of self is admissible. We do not have to talk of mysticism, we do not have to talk of after life, you talk of life here and now. You talk about - people from industry are enthused, urban people, housewives, normal family life, even they have to face all these struggles - because it is talking of the life, of the self and relationships. People of the - suddenly realise I have trying to tell people that they have given 10 years of my life, 20 years of my life, to raise the standard of life, the moment there is a betterment of life - they want a TV, want a car - JV says that is fine - but at the same time alcoholism, kidnapping and the family break - so that both the atom - I put in all the effort - and the people are not going beyond, because that is the logic of Western Civilization, that is where it will take it. Because you have left out the Civilization, it is the NGOs - I should address the human being. When religious leaders who come, the highest Buddhist scholar who has come Rinpochet, himself a scholar and VC of Tibetan Institute - he sat for 7 days and he said he will come again. He normally does not spend time anywhere. Another scholar who came from Sarnath - he wondered- Oh Buddha - this must have been the logic that Buddha followed and we are following it as a recipes. Perhaps recipes are needed, were needed, but with the modern man with modern facilities of communication, that is where the Internet comes - it has the potential to put people, databases together… -  in that situation, even the common man also has unprecedented opportunity to develop. When one looks at the Indian Civilization - it might have said only few people will reach higher levels - but with this modern technology, potential is immense. JV starts with every man can reach the highest without recourse to scriptures, without recourse to anything - it is a synthesis of bringing the self back into knowledge, which was discarded and left out. It can rightfully be brought back and that is an opportunity for us. Because as a civilization as continuous - which was sort of in the right direction, so we need to bring it back to Loka Vidya - into Internet. Into Internet - I do not know how to bring it. But human to human interaction certainly. It also leaves a lot of areas for research in all areas -  for many of us the concerns are societies, the public sphere - which requires lots of efforts - Our goal should be human civilization - how do we establish human civilization - we will evaluate every civilization with respect to that benchmark. Then the goal becomes, what do we do to reach that human civilization not 250 years ago but now - so that is Jivan Vidya.

Benchmark is in human development.

There was a question which raised a point about the importance of having after life in the structuring of a theory of human civilization. In reply, Prof. Sangal replied saying:

What JV says is that - this minimum is sufficient. It will base its argument on what you should be doing this because you want to be happy here. But if you want to posit something more, you are welcome. This becomes the issue of maanyata, to be individually happy - happiness is always self-only - if I am happy with the self - my own interest and negating group interest - I am actually unhappy - the standard notions of the success actually fall flat. The hollowness of that comes out easily - it does require one to come out of the maanyata what is taught by the society, or the scriptures as to be done to be happy, JV would say you have to decide at your own level. It then talks of six level of harmony - at self, family, society, nature and existence - at all levels. Program of action is open to all of us to design - and that will lead to a human civilization.

I think now we are in a better to talk about the institute and its goals.

23 Comments | Tags: