Sunday, March 21, 2010
Fifth meeting of the Formal Methods Reading Group
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.
Sunday, March 14, 2010
Fourth Meeting of the Formal Methods Reading Group
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.
Monday, March 8, 2010
Third Meeting of the Formal Methods Reading Group
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".
Friday, February 26, 2010
Second meeting of the formal methods reading group
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.
Tuesday, February 16, 2010
Formal Methods Reading Group
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.
Monday, January 18, 2010
TCS Excellence in Computer Science Week in Pune
| 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
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. |
Tuesday, September 15, 2009
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.
"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.
Subscribe to:
Posts (Atom)
