Mathematical Sciences: Model Theory and Universal Algebra

9403187 McKenzie首席研究员最近证明，确定有限代数系统是否具有有限方程基的问题在算法上是不可解的，他正试图将这一结果推广到拟方程。证明某些自然问题在算法上无法解决的结果，如哥德尔1931年的证明，是非常基本的，因为它们揭示了实际计算和理论计算的内在局限性。塔斯基有限方程基问题的不可解性是一个坚实但不足为奇的证据，证明有限代数可以表现出在经典代数中没有发现的那种复杂性，即在有限群、环或半群中。“算法”的意思是解决问题或执行计算的一般程序。哥德尔的证明实质上证明了不可能存在一种算法来决定自然数的所有真正的算术性质。他的证明中隐含的思想被其他人发展成现代数学算法理论（递归函数，图灵机），通过艾伦·图灵和约翰·冯·诺伊曼的工作，也导致了后来存储程序计算机的发展。代数是算法的丰富来源，其中许多算法很容易超过现代计算机的能力。事实上，现代数学的一些最深刻的成果集中在代数中的算法问题上，这仍然是一个活跃的研究领域。实际计算的重大突破可能最终源于这一理论工作，这并非不合逻辑，尽管今天没有人能详细预见到这将如何实现。＊＊＊

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