ACC Project is devoted to organizing efforts directed towards developing practically, technically, and financially viable working technologies for software engineering, based on the current achievements in understanding the continuous features of software and software engineering.
Since the late sixties, a great progress have been made in the developing and understanding continuous models of computational objects, so that such traditionally discrete objects as programs could be represented as continuous functions. Since eighties, considerable progress have been made in developing the theory of conventional structures from functional analysis, such as measures and generalized metrics, over the topological spaces involved, and it can be said with confidence that further rapid progress in this direction is to follow.
The question is, what should be done now, in order to enable the use of traditional methods of applied mathematics, which are so efficient in, say, physics and conventional engineering, to become equally effective in the field of software engineering?
We claim, that the key problem is to learn to solve the inverse problem to the well-studied and solved problem of representing programs via continuous functions. This is the problem of how to find reasonable approximations to given Scott continuous functions, which would be sufficiently efficient from the practical point of view.
It is possible to consider most of the Scott continuous functions arising in practice as transformers of recursive enumerations. This theoretical computability is, however, insufficient for practical purposes. At least two classes of approaches to the problem of finding practically efficient approximations of this kind have emerged. One class of approaches suggests the use of this recursively enumerable structure via methods of inductive inference and learning, algorithmic probability, and Kolmogorov complexity. Another class of approaches suggests the consideration of this problem as a classical problem from the conventional numerical mathematics, similar to the problem of approximating a solution of a variational problem --- it might be fruitful not to consider the underlying recursive enumerations explicitly under this class of approaches.
We should emphasize here, that we are talking not about theoretical questions related to computational complexity --- like the question, whether an algorithm runs in polynomial time in the worst case, but about practical efficiency, where it is important for those polynomials to have low degrees and constants for a typical input, and, on the other hand, even the issue of termination, never mind polynomiality, needs not be considered important for some rare special inputs.
Often we should probably impose an even weaker requirement, such that the efficient result be only obtainable in the situations where an efficient solution is also obtainable via classical means, like writing code by hand, although with larger costs. Basically, we should only strive for practical efficiency for such typical inputs, for which it is principally possible to obtain an efficient solution, the behavior for all other inputs is irrelevant.
If you are interested in scientific, technical, and/or financial side of this project, please do not hesitate to contact the author of this note.
The work in progress was presented at Northeastern Conference on Topological Methods in Computer Science.
Back to Mishka's home page