On Mon, 7 Feb 2000, Bill Halchin wrote:
1) The method of specification defined in this section seems to be essentially a rewrite system, i.e. we do a series of rewrites or reductions on "data" (actually a certain kind of path in a Data graph) until we possibly terminate. Hence the finite set of Equation that Walters' describes is basically a set of rewrite rules, i.e. one-way rules in Rewriting Systems parlance.
Yes. Indeed as part of my Ph.D. dissertation I wrote a complete specification of the interpreter in ASF+SDF, a rewrite rule-based system for algebraic specifications used at the University of Amsterdam. It can execute programs of that kind. I can send it to you if you want so. The interpreter is partially described also in the following papers: Sebastiano Vigna. Specifying IMP(G) using ASF+SDF: A case study. In Proc. of the ASF+SDF95 workshop on generating tools from algebraic specifications. Technical Report P9504 of the University of Amsterdam, 1995. Sebastiano Vigna. Towards an efficient implementation of distributive programs. In Proc. of the 2nd International Workshop on the Theory and Practice of Algebraic Specifications ASF+SDF, Workshops in Comput. Springer-Verlag, 1998.
3) On pg. 118, there is a "Note" about work that Robie Gates did to show that we can achieve Turing completeness with this method of function specfication.i.e. we can compute all parial recursive functions from N to N. Hence the computation may not be terminating!!!! Otherwise, we would not have Turing completeness and could solve Halting problem.
Of course (the book is a bit confusing about this issue). Turing completeness is proved in Nicoletta Sabadini, Sebastiano Vigna, and Robert F.C. Walters. A note on recursive functions. Math. Struct. Comp. Sci., 6:127-139, 1996. and BSS (real numbers computability) completeness is proved in Sebastiano Vigna. On the relations between distributive computability and the BSS model. Theoret. Comput. Sci., 162:5-21, 1996.
5) Finally and important to me, has work been continued by anyone else in this area?? I don't see any papers in Walters' groups archive!! This
Not to my knowledge, but you should ask Bob Walters directly. Greetings, Sebastiano Vigna