9403187 McKenzie The principal investigator recently proved that the problem of determining whether a finite algebraic system has a finite equational basis is algorithmically unsolvable, and he is attempting to extend this result to quasi-equations. Results showing that some natural problem is algorithmically unsolvable, as in Godel's proof 1931 , are very fundamental, because they reveal inherent limitations both to practical and to theoretical computation. The unsolvability of Tarski's finite equational basis problem is solid but unsurprising evidence that finite algebras can exhibit complexity of a kind that is not found in the classical algebras, i.e. in finite groups, rings or semigroups. The name "algorithm" means a general procedure for solving a problem or performing a calculation. Godel's proof was essentially a demonstration that there can be no algorithm to determine all true arithmetic properties of the natural numbers. Ideas implicit in his proof were developed by others into the modern mathematical theory of algorithms (recursive functions, Turing machines), which led as well, through the work of Alan Turing and John von Neumann, to the later development of the stored program computer. Algebra is a rich source of algorithms, many of which easily exceed the capabilities of modern computers. In fact, some of the deepest results of modern mathematics are centered on algorithmic problems in algebra, and this continues to be a lively area of research. It is not illogical to suggest that important breakthroughs in practical computation may eventually derive from this theoretical work, although nobody today can foresee in detail how this would come about. ***

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Application #
9403187
Program Officer
Ralph M. Krause
Project Start
Project End
Budget Start
1994-07-01
Budget End
1995-06-30
Support Year
Fiscal Year
1994
Total Cost
$52,100
Indirect Cost
Name
University of California Berkeley
Department
Type
DUNS #
City
Berkeley
State
CA
Country
United States
Zip Code
94704