Click here for More Activities
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.
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:
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
The Los Angeles Chapter normally meets the first Wednesday of each month at the Ramada Hotel, 6333 Bristol Parkway, Culver City. The program begins at 8 PM. From the San Diego Freeway (405) take the Sepulveda/Centinela exit southbound or the Slauson/Sepulveda exit northbound.
6:30 p.m. Social
7:00 p.m. Dinner
$5 - Students, with
$5 - Unemployed who are seeking employment, with reservation.
$10 - All others, with reservation.
$22 - Without a reservation.
50% off any dinner with new membership in LA ACM.
8:00 p.m. Technical program
The menu choices are listed in the article above.
To make a reservation, call or
Radbill, (818) 353-8077, and indicate your choice of entree, by
Sunday before the dinner meeting.
There is no charge or reservation required to attend the program. Parking is free!
For membership information, contact Lee Schmidt, (805) 393-6224 or follow this link.
Other Affiliated groups
SIGAda SIGCHI SIGGRAPH SIGPLAN TACNUM
LA ACM TACNUM
For information contact John Radbill at (818) 354-3873 (or radbill@1stNetUSA.com).
Return to "More"
Return to "More"
For further details contact the SIGPHONE at (310) 288-1148 or at Los_Angeles_Chapter@siggraph.org, or www.siggraph.org/chapters/los_angeles
Return to "More"
November 1999 meeting* October 1999 meeting* September 1999 meeting* July 1999 meeting*
June 1999 meeting* May 1999 meeting* April 1999 meeting*March 1999 meeting* February 1999 meeting* January 1999 meeting
December 1998 meeting*November 1998 meeting October 1998 meeting September 1998 meetingJune (and prior) 1998 meetings
List of 1995-1996 meetings
Los Angeles ACM home page National ACM home page
* includes meeting summary
Last revision: 1999 1209 [ls]