Los Angeles ACM Chapter Meeting

Wednesday, December 1, 1999 

A New Paradigm for Computation and its Applications to Global Networks, Huge Databases, and Embedded Systems 

Prof. Mark Burgin, Visiting Scholar, UCLA 

The theory of algorithms provides diverse mathematical models for computation and information processing -- influencing the development in this area by new understanding and advanced paradigms. The main achievement of the theory of algorithms has been the elaboration of an exact mathematical model of an algorithm. It was done less than seventy years ago by introducing recursive and partial recursive functions, Turing machines, and Post formal systems. The famous Church-Turing Thesis claims that recursive algorithms are the most general. All later mathematical models of algorithms were either equivalent to or even weaker than Turing machines (or equivalently, partial recursive functions). 

Several decades ago the theory of super-recursive algorithms appeared. This theory refutes the Church-Turing Thesis because the computing power of super-recursive algorithms is much greater than that of the conventional, or recursive, algorithms. Consequently, the discovery of super-recursive algorithms provides a new paradigm for computations. Prof Burgin will expose the fundamentals of the theory of super-recursive algorithms and demonstrate that while recursive algorithms gave a correct theoretical representation of computers at the beginning of the "computer era", super-recursive algorithms are more adequate as mathematical models for modern computers. In addition to this, super-recursive algorithms provide for a better theoretical framework for computing methods in various areas: for numerical analysis, global networks, and embedded systems, for search and other operations with huge and dynamic data arrays, etc. The lecture will emphasize applications related to global networks and dynamic databases. 

- - - - - - - - - - 

Mark Burgin was born in Kiev, Ukraine. After graduation from high school with honors, he entered the School of Mathematics and Mechanics at the Moscow State University, then one of the best in the world. He got a Ph.D. in mathematics and began to work as a programmer and system analyst at the Institute of Computing Systems (Moscow) initiating research in Computer Science. Returning to Kiev, he became D.Sc. in Logic and Philosophy. His interests and publications include mathematics, computer science, artificial intelligence, logic, information sciences, methodology of science, psychology, pedagogical sciences, and science of science. At Kiev, he lectured on, among others, Theory of Algorithms, Algebra and Analysis, Mathematical Theory of Organization, and Foundations of Mathematics and is the founding head of the Interdisciplinary Seminar "Foundations of Mathematics and Information Sciences" . He is a member of many professional societies and academies. 

Meeting Summary

Professor Mark Burgin said his presentation had three main parts, theoretical models and algorithms, methodological on mathematical paradigms, and practical indicating applications to practical uses and devices. An algorithm is a clerical, domestic bookkeeping, procedure which is applied to symbolic inputs and which will eventually lead to a symbolic output. A formal counterpart to the idea of the algorithm, the L-P specification was developed and uniform mathematical specifications were also provided. There are three essential conditions:

1. Finiteness and constructibility of the input, processor and output information.

2. Finiteness and constructibility of the system of rules.

3. Purposefulness of the system of rules.

There are many mathematical algorithms including Turing machines, partial recursive functions, normal Markov algorithms, Minsky machines, random access machines and others. The Church-Turing thesis combines the statement by Turing that any algorithm is functionally equivalent to a Turing machine and the statement of Church that any computable function is computable by some Turing machine. It is impossible to completely prove the Church-Turing thesis, but there is more and more experimental evidence that is consistent with it. No theoretical way has been found to disprove the Church-Turing theorem. The Turing machine that was developed in the 1930's well before the first electronic computer was designed resembles a computer and Von Neuman's computer architecture reflects a universal Turing machine. It is no coincidence that Von Neuman was a mathematician. To obtain a result the computation must come to an end and algorithms do not necessarily depend on stopping in their basic concepts, and if a Turing machine does not stop it gives no result.

Recently, super-recursive algorithms have been developed that are more efficient and do a better job of modeling many real world applications. The first published description of these algorithms was in 1965, and in 1974 the first description of a Turing machine for realization of the super-recursive algorithms was described. Professor Burgin described a more powerful inductive Turing machine with a structured memory in 1983, and he developed a theorem on super-recursive representation of arithmetical hierarchy and its implications for Godel incompleteness in the 1987-88 time period. He continued his work on implementation of topological principles in the theory of super-recursive algorithms in 1992 and has obtained proof of results demonstrating that the efficiency of the super-recursive algorithms is much higher than efficiency of recursive algorithms to date.

Professor Burgin referred to recursive algorithms in a sequential program as comparable to taxis and single passenger cars, recursive with program concurrency as comparable to buses and multiple passenger cars, and super-recursive algorithms as comparable to clocks and watches. The clocks and watches operate all of the time rather than with the periodic starts and stops of the transportation models.

The practical example he gave for something best modeled by super-recursive algorithms is the concurrency of operations of the large number of computers on the net that continually run without stopping. The super-recursive functions can solve some mathematical functions incapable of solution by recursive methods and do a better job of modeling web searches for data. In answer to the question "How do we know we have the final result of the calculation?" Professor Burgin responded that in some cases we may never know. There is not an absolute law, but the super-recursive functions provide a better model of the real world. Another question was "What if the calculation resulted in a repeated oscillation?" and he said this was equivalent to the calculation stopping.

Professor Burgin said that the super-recursive algorithms refute the Church-Turing machine by calculating some functions that the Turing machine cannot. There was a spirited question and answer session. For more information go to Professor Burgin's web site at www.math.ucla.edu/~mburgin

This was fourth meeting of the LA Chapter year and was attended by about 32 persons, with more mathematicians than usual in the audience. Professor Burgin was very impressive in the way he presented a highly theoretical topic in a very clear manner. Any problem in following his talk resulted from lack of background of members of the audience (such as myself), as the presentation was very well done.

Mike Walsh, LA ACM Secretary