Mathematical Sciences: Model Theory and Universal Algebra

点击翻译按钮获取中文摘要

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. ***