Introduction of a new order of things.

Prof. Kesav Nori retired on 31st March after completing 25 years of service in the Tata Consultancy Services. A touching function took place in which all his colleagues spoke about their interaction with him.

The web site http://www.kvnori.com/ was gifted to Prof.Nori on this occasion by some of his admirers.

Speaking on the occasion Dr. V.C.S. Prasad drew the attention of the team members of the Business Systems & Cybernetics Centre of the Tata Consultancy Services to a quote from Nicolo Machiavelli. The quote is given below. He was referring to Prof. Nori's passionate advocacy of the necessity of "seeing beyond computing" in running a software company.

Many of the readers might resonate with the ideas expressed in the quote in view of their own experience of life.


"... there is nothing more difficult to take in hand, more perilous to conduct, or more uncertain in its success, than to take the lead in the introduction of a new order of things. Because the innovator has for enemies all those who have done well under the old conditions, and lukewarm defenders in those who may do well under the new. This coolness arises partly from fear of the opponents, who have the laws on their side, and partly from the incredulity of men, who do not readily believe in new things until they have had a long experience of them. Thus it happens that whenever those who are hostile have the opportunity to attack they do it like partisans, whilst the others defend lukewarmly...."

Nicolo Machiavelli

Written c. 1505, published 1515.

Turing machines - 2

Instead of starting with the definition of a Turing machine and trying to persuade the reader that such a machine can be universal, we will start with a model that a reader can easily accept to be universal and then try to show that such a model is just a Turing machine when we look at it in the right perspective.

1. What do we do when we try to do a mathematical calculation? We have a text book to refer to and a note book to write in. In a certain state of mind we read some part of a page of the text book. What we read changes our state of mind. And then we could do one or all of the following: a) Make some calculations in our note book; b) go to the previous page in the text to renew our understanding of something we learned earlier; c) go to the next page in the text to continue our effort to understand how the calculation is done.

Surely that is all any one can do, right? So one can say that we have described a universal method of doing a mathematical computation.

2. Now let us change the setting slightly. Don't let the text book and the note book be separate entities. Suppose we have a workbook in which only a part of the page has text and the rest is left blank for us to do our working. If the blank space is not enough, we are free to add one or more additional sheets at that point to help us. Surely the model continues to be universal?

3. Now comes the crucial jump. Recall that the definition of a Turing machine only requires the tape alphabet to be a finite set. There is no limit set on how large it can be.

Take a deep breath now. Can you think of the entire text and the blank space on the workbook as a single symbol from a set of finite symbols? And the entire page of the work book with all the additional sheets attached as a single square?

Don't we have a Turing machine then?

Turing Machines - 1

In the way it is usually defined a Turing machine has an infinite tape for storage. This storage tape serves also as the input device and the output device.

Even though the tape is infinite it is to be noted that the definition specifically mentions that all except a finite number of squares are blank. This means that a TM is actually dealing with a finite string. We could have a finite string with two end of the line symbols and arrange matters so that if the reading head happens to see one of them it simply moves it one square away. See the Book for a detailed definition along these lines.

But if a TM actually deals with finite but arbitrarily long strings, just like finite automata, then how is it that a TM can be universal? The reason is the ability of the head of the TM to move both forward and back and change the symbols it encounters.

In the next post I will attempt a simple argument that shows that a TM is "naturally and obviously" universal.

Diffusion of Innovation

On November 27 at the TCS Innovation Lab for Business Systems Dr.VCS Prasad made a
presentation on the diffusion of innovation in an organization that I found very interesting. I mention here only two points that he made.

One is the folly of trying to push a new idea into an unready environment: an early negative
reaction can spread quickly by word of mouth and jeopardise the idea. The other is the importance of slack (uncommitted) resources. Unless an organization has slack resources it
is not possible for it to experiment with new ideas.

When Bertrand Russel said that boredom leads to creativity, and that children should have
plenty of opportunity to be bored. he was emphasizing the importance of slack resources in
one's personal life. One has time to be playful only when all resources are not committed to
the To-Do-List. Are you a list maker? When you do something not on the list do you write it
down and then cross it out? If so it is time to pause and re-think your life.

The spirit of computing is best understood if we approach computing as play. Hope to
elaborate on this in a future post.

Computing on Paper - 2

Have designed tentative paper data formats for bubblesort, insertionsort, quicksort, and mergesort algorithms. You can find them here.

What is Mathematical Computer Science?

Here is my definition.

Find out about the book "An Introduction to Mathematical Computer Science" here.

Computing on Paper - 1

When I taught some graph and sorting algorithms the first couple of times the larger part of my energies went into understanding the algorithms as given in text books and rewriting them as mapcode theorems with proofs. The third time around, I asked myself afresh how best I could teach them. Dr. S. Durga Bhavani generously shared with me her teaching methods and references.

Would like to record here some of my observations now.

One should look at all algorithms from two different points of view. As algorithms we can work out on paper and as algorithms we have to get a machine to process. The levels of complexness differ. (The word 'complexity' has a definite technical meaning in relation to algorithms. So I am choosing a different noun form of 'complex' that is also allowed by the dictionary.)

The algorithms we learned as children for the arithmetic operations are a marvel of design. They use a two-dimensional paper data structure in which we can write to the left or right or above or below. Their design is chosen to balance what we keep in our minds and what is written down. In case the output we compute is not the 'book answer', what we have written down is enough to help us work through it again and find where the mistakes occurred. Can we design such formats for the algorithms we teach in computer science courses?

In the last month I have found that this is possible in principle. The surprise was that the paper complexness of the algorithms I looked at is far less than their machine complexness. Actually, they are not even as complex as the school arithmetic algorithms. It is perhaps a good idea to teach students to work out some examples on paper in the paper format with oral instructions from the instructor. It takes just a few minutes and three to four examples to understand the logic and the method of execution of the algorithm. After this initiation the instructor can pose the problem of converting the paper algorithm to a machine algorithm. The advantage is that the students have a good gut level comprehension of what they are trying to get the machine to do.

Will put up some paper algorithms for sorting in my next post.