Mathematics and Computing

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"

"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

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

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

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

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

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

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

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

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

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

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

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.

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.