Perspectives on Computing

The universality of labeled transitions systems

2012-01-16T23:34:00.000-08:00

A labeled transition system can be thought of as a directed graph with multicolored edges. In mathematical terms this is a set with a family of relations defined on it. This is the model for Robin Milner's Calculus of Communicating Systems. There is a good book now to explain the ideas of CCS and timed CCS. It is titled "Reactive Systems - Modeling, Specification, and Verification" and is written by four authors: Aceto, Ingolfsdottir, Larsen and Srba. It is published by Cambridge University Press. The Ph.D. thesis of Ken Stevens at Calgary is also useful.

What is an insight for me is that this model encompasses three other models I have been studying.

1. If all the edges are of a single color then we have a set with a relation. We have shown earlier that this model can be used to develop Dijkstra's wp-formalism.

2. If there is a single relation and it is a total function then the model reduces to Knuth's model of computation. The Mapcode model that we have been studying brings out some concepts hidden in Knuth's model and makes them explicit.

3. If there are a finite number of relations and each is a total function then the model reduces to that of Chandy and Misra. We have called this the multiflow mapcode model.

For me personally it is exciting to consider the tantalizing possibility of developing CS theory in a uniform way based on this insight!

Three things I learned from my colleagues at TCS

2011-10-31T06:43:00.000-07:00

1. I have spent a lifetime studying and teaching mathematics of many different kinds. When I started working with Prof. Kesav Nori's group at Business Systems and Cybernetics Centre, my understanding was that one could make a mathematical model of a system by writing down the differential equations concerned and analysing them. Much as we do in the prey-predator model. However from Prof. P.N.Murthy I learned that for a any social system that we set out to study initially we do not even know which are the independent and which are the dependent ones. We do not know how the dependent ones vary with the independent ones and which are the positive feedback loops and which are the negative feedback loops. So it is necessary for us first to form this understanding by appropriate "cybernetic influence diagrams". A detailed exposition of these is given here.

2. I thought that my model for mathematical computer science was very simple and easy to understand. However I was puzzled that there was not much eagerness to study it. This despite the fact that all my colleagues were doing difficult work and dealing with complex analytical and logical reasoning and all of them were engineers. Then one day talking to Swami I realized that the resistance was not to my method of approach to computer science but really only to the mathematical notation I was using. It was the abstract formulation and the use of symbols that was making the ideas opaque. So I felt that I had to find a different way of expressing my ideas that engineers could work with, not losing the rigour of expression.

3. What language should I use if not the mathematical language? I saw Doji and Ravi approaching the organizational problems they were dealing with by looking to the manufacturing domain for inspiration. So then can I think of a way of designing an algorithm so that it is similar to designing an artefact in a factory? Thus was I led to the Management Model of Computing that is explained here. You need to create an account and then go to the pages on Computational Thinking.

Computing with Multiple Discrete Flows

2011-05-28T05:12:00.000-07:00

The nearest in the literature to the model of mapcode is the UNITY work of Chandy and Misra. While mapcode considers a set X together with a map F: X -> X, UNITY considers several maps acting on X. The result is a fascinating theory of parallel and distributed programming. UNITY stands for Unbounded Nondeterministic Iterative Transformation theorY. We interpret this theory purely in mathematical terms as with mapcode. Our first paper on this subject dealing with standard sequential programs that are expected to terminate in a finite number of steps and return a value is given in our paper Computing with Multiple Discrete Flows.

Quantum Formalism and Information Retrieval

2011-05-28T03:17:00.000-07:00

In 2004 Keith van Rijsbergen published a book with the title "The Geometry of Information Retrieval". In this book he suggested that quantum formalism can be successfully used to model some of the problems of Information Retrieval. This book was given to me by my colleague Dr. Vasudev Varma of the International Institute of Information Technology, Hyderabad with a request to offer a course on the ideas of the book.

Last semester I did so. I had hoped for senior students who already knew Linear Algebra, but none of those who joined was clear about the basics of Linear Algebra. So almost the entire course was spent teaching them linear algebra and then some of the basics of quantum terminology. At the end I was left with only one class to explain how quantum formalism relates to Information Retrieval.

There was another difficulty. The book of Rijsbergen used the physics notation for the inner product according to which it is the second term of the inner product that is linear and the first term antilinear. The mathematics text books have the opposite convention. So there was a need to rewrite the basics of Hilbert Space theory in the mathematical tradition but using the physics notation. This is now summarized in a document and attached here as Review of Hilbert Space Theory. Also attached is my write-up on the Hilbert Space Model for Information Retrieval.

Fifth meeting of the Formal Methods Reading Group

2010-03-21T04:15:00.000-07:00

Chapter 3 was concluded by me and Dr. Venkatesh began discussing the concept of concurrency in Chapter 4. My notes of the part of my lecture are here as FMRG-5. Dr. Venkatesh will also put up his notes soon at the wiki of http://enhanceedu.iiit.ac.in. You may send mail to choppell@gmail.com for the login name and password that are necessary to access the wiki.

Fourth Meeting of the Formal Methods Reading Group

2010-03-14T03:34:00.000-07:00

The fourth set of notes is up as FMRG-4. In this we study automata for which there is no start state specified and all states are considered to be accepting states. This is defined as a set together with a collection of choice maps on the set. We define the notion of a strong simulation as a choice map that carries a transition between states to a transition between sets of states. Other ideas of Milner are expressed in similar terms. Would like to know from the readers if this makes it easier to understand Milner's ideas.

Third Meeting of the Formal Methods Reading Group

2010-03-08T00:04:00.000-08:00

The third meeting took place on 3rd March. Most of the time was spent discussing the example of the faulty vending machine given by Milner as motivation for the notion of bisimilarity. It became clear that the example needs to be discussed more fully than in the earlier meeting. Accordingly the set of notes were written up. They are available here as FMRG-3. Lesson 3 is in the form of a story: "The Case of the Faulty Vending Machine - An Allegory for Software Engineers".

Second meeting of the formal methods reading group

2010-02-26T23:18:00.000-08:00

In the second meeting we discussed the second chapter of the book. In the notes I have posted on my web site at pi-calculus I have omitted the state space diagrams. Have made do with tables describing the state diagrams. A little patience and practice will help the reader feel comfortable with them. If the readers really miss the diagrams, when I find some time I will try to draw and upload them at the appropriate places.

Formal Methods Reading Group

2010-02-16T23:19:00.000-08:00

Dr. Venkatesh Choppella and I, supported by several of our colleagues, have started a Formal Methods Reading Group. We plan to have meetings once a week to pursue a learning path. To begin with we have chosen Robin Milner's 1999 book on "Communicating and Mobile Systems: the pi-calculus". Skeletal notes of the first lecture are posted on my web site as pi-calculus-1. Comments by readers, and corrections where needed, are welcome.

TCS Excellence in Computer Science Week in Pune

2010-01-18T03:16:00.000-08:00

Haven't posted in a while. Been busy with my course on Program Dynamics and preparing lectures for two workshops.

Attended the TCS Excellence in Computer Science (TECS) week in Pune during Jan.3 to Jan.8. The theme this year was "Formal Methods in Software Verification, Testing, and Debugging". For details the reader may go to http://121.241.184.234:8000/tecsweek/tecsweek_home.html.

Shankar Natarajan's lectures were especially exciting as also his method of lecturing. He also drew my attention to the work of Dick Lipton. I am surprised by the following item from the wikipedia article on Richard Lipton:

"De Millo, Lipton and Peris criticized the idea of formal verification of programs and argued that

Formal verifications in computer science will not play the same key role as proofs do in mathematics.
Absence of continuity, the inevitability of change, and the complexity of specification of real programs will make formal verification of programs difficult to justify and manage."

How about that! All power to the mathematical proofs of mapcode! All power to further research to scale it up to industrial strength!

It was a treat to hear Sir Tony Hoare speak about the importance of taking the initiative and going ahead with one's plans even if they appear to be not in step with what others are doing. A boost for Prof. Nori and me. That is exactly what we have been doing over the last few years.

Interactions with Prof. Jayadev Misra and Prof. C.R.Muthukrishnan were illuminating and enlightening.

At the conclusion of the programme I was given an opportunity to present mapcode ideas. The slides of the presentation have been uploaded here. The novelty of the approach received a good response from some of the younger participants especially. Looks like there is a gap in pedagogics that mapcode fills. Definitely encouraging.

Mathematics and Computing

2009-09-15T21:35:00.000-07:00

The book "Structure and Interpretation of Computer Programs" by Abelson and Sussman has this to say in the preface to the first edition:

"The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is an emergence of what might best be called *procedural epistemology* -- the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects.
Mathematics provides a framework for dealing precisely with notions of "what is." Computation provides a framework for dealing precisely with notions of "how to.""

This statement has always bothered me. Seemed to me that mathematics and mathematicians were not being given their due. An exchange of ideas with Professor Tim Poston has helped me clarify my position vis a vis this passage.

1. The revolution is not "in the way we think" but in the technology that became available to express what we think. Mathematicians have always bothered about procedures. Whether it is a procedure in Euclidean geometry or a procedure to solve an equation. In fact, Knuth says somewhere that the history of number theory can be seen as the history of algorithms. Gauss's work and Galois's work were also motivated by an interest in procedures.

However, as Professor Tim Poston pointed out to me, mathematicians did not emphasize procedures as much as they did the statements they arrived at using the procedures. Perhaps this was because mathematicians felt that they were "discovering" an area of (Platonic) reality and their statements represented "truths" about this reality. The procedures that led them to these truths were not considered to be important.

This viewpoint was gradually eroded starting with the discovery of non-Euclidean geometries and climaxing with the work of Godel.

2. The problems with the second sentence in the quotation is about the use of the words "emergence" and "knowledge". If the claim is that "procedural epistemology" *began* in the 20th century as the aftermath of Turing's work, then that is difficult to accept. Also it is difficult to accept that either mathematics or computing is studying "the structure of knowledge". Seems to me that both mathematics and physics have given up any claims they might have had that they were discovering knowledge. They are just playing with models and some of them seem to fit some aspects of reality to a useful level of approximation.

3. And finally the last sentence. As I said above, mathematics has always been interested in dealing precisely with both the notions of "what is" and "how to". What has changed is the meaning of the word "precisely". The idea that this means that a machine should be able to execute the procedure is new.

4. In my presentation on "The Nature of Computing" I have tried to present the concerns of computing as part of a historical continuity.

"On the cruelty of really teaching computing science"

2009-09-08T00:42:00.000-07:00

"On the cruelty of really teaching computing science" is an article by Dijkstra in 1988. Wikipedia reviews this and says that " Dijkstra argues that computer programming should be understood as a branch of mathematics, and that the formal provability of a program is a major criterion for correctness.... Specifically, Dijkstra made a “proposal for an introductory programming course for freshmen” that consisted of Hoare logic as an uninterpreted formal system....Computer science as taught today generally does not follow Dijkstra's advice."

I venture to suggest that one of the reasons that Dijkstra's advice is not followed could be the fact that learning formal logic requires a huge overhead of investment of time and energy on the part of a student. Instead of using formal logic, if we could convey the same content using the simple set algebra the students any way learn when they take their course on discrete mathematics, then the cruelty may be considerably reduced and Dijkstra's ideals can be made practical realities.

In the last post, we showed how Hoare's axioms may be interpreted as mapcode theorems. In this post we point to the article here that shows how to interpret Dijkstra's wp-formalism in terms of nondeterministic mapcode.

Hoare Logic, Pascal P, and Kesav Nori

2009-09-06T00:51:00.000-07:00

Here is a short description of how Prof. Kesav Nori used Hoare logic, in his own words:

"I do not recall what I told you about Hoare logic, but in order to prove correctness of the Pascal P compiler, I proposed Axioms a la Hoare Logic for each P-code instruction (including jumps and conditional jumps) and the rule of inference for sequential composition, and then showed that every axiom and rule of inference of Pascal P was a theorem for the compiler geberated code schema. This way, any proof of a program property for a Pascal Program could be treated as a proof for the generated P code, citing the code generation theorems, and that would be a means of asserting semantic preservation, i.e., a compiler is a bridge between two proof systems, respectively for the source and target languages. Hoare logic (or any specification language for semantics of a Programming Language) is a meta language in which the bridge can be specified."

"... it was clear as mud, but it covered the ground ..." !

Hoare Axioms are Mapcode Theorems

2009-09-04T22:34:00.000-07:00

C.A.R. Hoare in 1969 suggested a set of axioms that may be used to build proofs of program correctness. Despite their general acceptability even after a period of 40 years the method suggested by Hoare is not generally taught and used.

Prof. Kesav Nori once suggested a possible reason why correctness proofs of programs are not more popular than they are. Natural languages that have evolved over the course of years have too complicated a structure to study mathematically. Programming languages, even though man-made, still are very complicated, and hard to study mathematically. There is a vast variety of programming styles and it is a daunting task to tackle each program and try to reduce it to a series of Hoare logic links.

The mapcode style of programming we suggest uses only a very simple program template: a single while loop. So it may not be so hard to reason about their correctness using Hoare rules. However, we can show that the Hoare rules can be stated and proved as theorems in mapcode. An exposition is given here. This shows that any program that may be proved correct using Hoare rules, can also be proved correct using mapcode. At the same time this result suggests that we do not need to confine ourselves to Hoare rules: any argument that is correct in terms of set algebra may be used. We thus have a very simple way of proving programs correct.

Knuth's Effective Algorithms

2009-09-04T22:17:00.000-07:00

Donald Knuth in the first volume of his book presents a mathematical definition of an algorithm that satisfies the first four criteria for a list of instructions to be an algorithm (finiteness, definiteness, input and output). He defines his fifth criterion as "effectiveness". He explains this to be "computable in principle exactly in a finite amount of time by someone with pencil and paper".

He then gives a method of computation that qualifies for this fifth criterion also. This is a modification of the model that involves symbol manipulation proposed by A.A. Markov. N.J. Cutland in his book "Computability" says on page 65 that "Markov-computability on N (the set of natural numbers) is defined by using some system of representing numbers in the usual way, and thus coincides with the other approaches to computability". This seems to suggest that the class of Markov-computable functions coincides with the class of, for example, Turing-computable functions. This is probably true of Knuth-computable functions also. Nevertheless, it would be nice to have a direct proof that Knuth-computable functions are the same as partial recursive functions.

An exposition of Knuth-computability is given here.

The Program Dynamics Course - 2009

2009-09-01T06:59:00.000-07:00

Last year I had given a semester course based on my book IMCS with the title "Program Dynamics" at the International Institute of Information Technology, Hyderabad, India. This year I am offering it again. On occasion, I hand around some supplementary material to the class. All such material is gathered here.

Egyptian Multiplication and Chinese Division

2009-08-24T08:53:00.000-07:00

These are two simple algorithms which have been derived using the Dijkstra-Gries methodology in the book. The easiest way to understand the reasoning behind them is by the use of appropriate calculation methods on paper. Such methods are presented here.

Text and Context of Computer Science

2009-08-17T03:10:00.000-07:00

This blog is the record of an exploration. What is the academic content of computer science? Is computer science a mushroom that burst upon the landscape of science in the 20th century or does it have roots in classical mathematics and physics? What is the nature of the activity of computing?

Groping towards some answers. The slide presentation Nature of Computing tries to locate
the context of computer science firmly in the area of classical mathematical problems. At
the same time it tries to say that computing may be understood as the game of constructing
required structures from specified pieces using specified methods, much like LEGO.

The slide presentation Dynamical Systems tries to show that the concepts of attractors,
chaos, fractals, artificial life, and models for evolution, memory, and dreams all arise
from the study of special cases of the program "repeat x := F(x)".

The 10 Step Design Process

2009-08-13T02:08:00.000-07:00

There was a one day national workshop on the "Latest Applicable Trends in Mathematical Sciences" on August 7, 2009 at the Al-Ameer College of Engineering & IT at Visakhapatnam. Gave a lecture there with the title "A Mathematical Approach to Computing and Programming". It was attended by about 70 college lecturers of mathematics. I spoke about the motivation behind the Tata Consultancy Services Initiative, the work we have done so far, and the work still to be done. The technical part of the talk was the 10 Point Design Process .

The workshop was extremely well organized by Sri P. Veeraiah, head of the Department of Basic Sciences and Humanities.

Recent work

2009-06-24T01:51:00.000-07:00

Haven't posted for a while. Have been working hard on three topics.

1. A characterization of partial recursive functions using mapcode: For new comers to this
blog this is equivalent to using Knuth's definition of an algorithm given on page 7 of
Volume 1 of his book "Art of Computer Programming". This effort began nearly 5 years ago.
About 3 years ago my friend Ashok Maitra showed me how to prove a crucial theorem. (Sadly
Ashok is not with us any more). It has taken us all this time to find the right definitions
and the best proofs. This is joint work with K.Venkata Rao. We have now written it up. Will announce details some time later.

2. A simplified approach to Dijkstra's wp-calculus: We (Venkata Rao & I) have found that
there are three intuitive ways of defining the concept of a non-deterministic mechanism. One
of them is Dijkstra's. One is a formalization of the simple concept that at one step the
state changes from a state x to one of the states in a set D(x). The third is an unexpected
dual to Dijkstra's definition. This also turns out to be actually used in the theory of
computation though not explicitly noted. The best thing is that all these three definitions
turn out to be mathematically equivalent! Because of this there arises the possibility of
implementing the Dijkstra-Gries methodology for deriving algorithms using an easier
formalism. Indications of this have been already given in the book. But now there is the
possibility of extending this work to the non-deterministic case.

3. As noted earlier in this blog the mapcode formalism was evolved to help the mathematically minded appreciate computing concepts. This was expounded at length in the book. A recent insight is that the mapcode point of view has actually two parts. One is a philosophical approach to programming that is based on the 10-step design process and the other is the language in which the philosophy is conveyed. In the book the mathematical language of sets and maps was used to formulate and convey the philosophy. But the philosophy can be taught using any programming language!

With the help of my friend and colleague Anand of TCS I have been studying the languages HASKELL and ERLANG. Now I should write up how to teach mapcode computing with the help of either of these languages. Hopefully the notes should be ready in a few weeks.

Qualitative vs Quantitative Modeling

2009-04-28T23:14:00.000-07:00

Prof. P.N.Murthy retired last year as Advisor to Tata Consultancy Services when he reached the age of 80. The retirement is only from his official position. He is still invited repeatedly to the Business Systems & Cybernetics Centre of TCS to participate in its activities and deliver special lectures.

Among his many achievements is his development and use of Cybernetic Influence Diagrams to understand complex social situations. This is a method of qualitative modeling. People who believe in quantitative modeling find it difficult to accept that qualitative modeling can be yield any results at all. So I have written up an article, in the form of a conversation, explaining the value of and need for qualitative modeling. The article is located on my web site here. Please read it and let me know if you find it convincing.

The Core Product and the Whole Product

2009-04-25T00:23:00.000-07:00

I have already referred to Dr. V.C.S. Prasad twice on this blog. He figures again in today's post. His understanding of matters is very useful to all of us in moving our inventions ( new products) to innovations (new processes in the organization that incorporate the products).

He explains the difference between Core Product and the Whole Product using the example of a water filter. (In some circles 'water filter research' refers to research that may have scientific value but no practical value.)

A scientist gets a grant to design a new and cheap water filter that will filter not only the impurities that other filters do but also some harmful chemicals. He succeeds and a model is ready. To continue the research he asks for a further grant.

The funding agency has some questions. What steps is he taking to manufacture the containers for the water filter and the filtering substance? Are the chemicals necessary for the filtering substance easily available in the market? Does he have a business plan? Can he find some one to invest in the manufacture? How is he going to market the product? Has he done a market survey to find out if there is acceptability for his product?

The agency is accepting that there is a Core Product. It wants the Whole Product. Unless that is ready it considers its money wasted.

The scientist applies to a different agency to continue his research to find out how to filter out arsenic.

Dr. Prasad points out that most of us scientists owe our allegiance to our specialization rather than to an organization, be it a company, a funding agency, or the society that supports us.

Prof. P. Balaram (Director, Indian Institute of Science, Bangalore) said in his recent 10-th Anniversary Distinguished Lecture at IIIT-H that academic research is of unspecified utility whereas applied research has clear goals that need to be met. In Dr. Prasad's terminology one could say that academic research is satisfied with the Core Product whereas applied research seeks the Whole Product.

Title of this blog

2009-04-23T23:19:00.000-07:00

Experience of blogging on this site over the last few months helped me see that there are many larger issues related to computing that need to be discussed to further the main aim of evolving better teaching strategies. It seemed to me that the title "Computing and Computability" is too restrictive in its connotations. So I tried to think of a more general term.

First I thought of "Joy of Computing". But then it is not as if computing by itself gives joy. The joy depends on the spirit with which one approaches it. Besides I found that there is already a book of that title --- a book for librarians!

Then I considered the "Tao of Computing". I gave up that idea too because it seemed to me a little pretentious on my part to claim to know that. And again there is already a book by that name!

Trying for a third time, I considered a phrase suggested by Mr. MGPL Narayana, Vice President of Tata Consultancy Services and the head of their Business Systems & Cybernetics Centre: "Principles of Computing". Googling this I discovered a great web site called the "Great Principles of Computing". This project gives far deeper and more comprehensive insights than I can ever hope to discover or formulate on my own. So that too needed to be given up.

I finally settled on the present title: "Computing as Play". That is how I look at computing any way. In addition, this title gives me a certain freedom to play around with and around the ideas of computing, computability, computation, and programming. It also has a certain philosophical ring to it. There is a classical Indian point of view that looks at the entire creation as play!

Introduction of a new order of things.

2009-04-03T20:08:00.000-07:00

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

2009-03-30T02:10:00.000-07:00

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

2009-03-22T21:45:00.000-07:00

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

2008-12-01T20:41:00.000-08:00

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

2008-11-23T20:58:00.000-08:00

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

What is Mathematical Computer Science?

2008-11-22T22:20:00.000-08:00

Here is my definition.

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

Computing on Paper - 1

2008-11-20T23:41:00.000-08:00

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.

Exploring Computer Science

2008-10-16T03:27:00.000-07:00

What are the concerns and goals of computer science?

What are the foundations?

What are its methods?

What is its academic content?

What are some good ways of teaching it?

In what way is computer science related to mathematics?

These are the large questions I would like to address in this blog. I know that I am not competent to address such grand themes, but my hope is that the very effort to formulate answers to these questions will help me grow. Besides, there are real experts out there. Some of them may feel like helping me out.

Several computer scientists, friends, colleagues, and students have been helping me in my studies. Will acknowledge their help when I refer to it. However, I would like to acknowledge right at the beginning the help, guidance, and mentoring I have received from Prof. Kesav Nori. In a series of conversations around the year 2000 he communicated to me the essential concerns of the discipline and pointed out the direction I had to travel, and, more importantly, the directions I could temporarily ignore. Since then, I have relied on him to show me the way out of every thicket I got into. But for him, I would have not been able to make any progress at all in my understanding of this fascinating area.

My work of about seven years has been summarized in the book "An Introduction to Mathematical Computer Science". You can know more about the book from here.