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.