Mathematical Sciences: Coding Methods in Algebra, Computability Theory and Model Theory

9500983 Nies Nies的研究涉及代数和逻辑领域，涉及结构和结构类中具有一阶属性的编码。他对证明由少量量词交替的句子组成的初等理论片段的不可判定感兴趣，特别是有限群的类理论、有限分配格的理论和可数集合的格E的理论。对这类片段的兴趣源于它们包含了通常在数学实践中出现的一阶句子。此外，他将致力于从结构复杂性理论确定度结构理论的复杂性，并利用编码方法研究可枚举图灵度结构D的模型理论性质。E和D都是可计算性理论中的中心结构。同样利用编码方法，他打算证明各种程度结构的非初等等价性，并打算从模型理论中引入属于各种结构类的结构的同构类型的信息内容的度量。在进一步的项目中，他计划分离确定性和非确定性线性时间泛化的复杂性类。编码的一般思想是用另一种类型的对象表示一种类型的对象，使用固定的解码密钥从第二类对象检索信息。在这个项目中，对象是来自代数、可计算理论和模型理论的某些结构。解码密钥由一阶逻辑中的一组公式组成，这是一种形式语言，可以看作是数学中自然语言的主要部分的形式化。在结构B中对结构A进行编码，保证B至少与A一样复杂。Nies将通过比较它们的共复杂度来研究所有可能无限结构类的抽象排序，并将类似的方法应用于有限结构类，这是近年来与计算机科学联系密切的一个领域。在这个项目的第二部分，编码方法将应用于可计算性理论，这是数学逻辑中处理理想意义上的可计算性的部分。不可判定集可以根据其计算复杂度而变化。除了确定相关一阶理论的复杂性之外，我们的目标是找出结构的对称性，并找到这些结构的简单表征。这些问题对于加深对计算的理解很重要。* * *

9500983 Nies Nies' research concerns areas of algebra and logic that involve coding with first-order properties in structures and in classes of structures. He is interested in proving undecidability of fragments of elementary theories consisting of sentences with few quantifier alternations, in particular, for theories of classes of finite groups, the theory of finite distributive lattices, and for the theory of the lattice E of enumerable sets. Interest in such fragments arises from their containing the first-order sentences that usually occur in mathematical practice. Moreover, he will work toward determining the complexity of theories of degree structures from structural complexity theory and toward using coding methods to investigate model-theoretic properties of the structure D of enumerable Turing degrees. Both E and D are central structures in computability theory. Also using coding methods, he intends to prove nonelementary equivalence of various degree structures and intends to introduce a measure of the informational content of isomorphism types of structures belonging to various classes of structures from model theory. In a further project, he plans to separate complexity classes that are generalizations of deterministic and nondeterministic linear time. The general idea of coding is to represent objects of one kind by objects of another kind, with a fixed decoding key used to retrieve the information from an object of the second kind. In this project, the objects are certain structures from algebra, computability theory, and model theory. The decoding key consists of a collection of formulas in first-order logic, a formal language which can be viewed as a formalization of a major part of natural language within mathematics. A coding of a structure A in a structure B guarantees that B is at least as complex as A. Nies will investigate the abstract ordering on classes of all possibly infinite structures by comparing their co mplexity and will apply similar methods to classes of finite structures, a field which has been the focus of interest in recent years for its connections with computer science. In a second part of this project, coding methods will be applied to computability theory, that part of mathematical logic which deals with computability in the ideal sense. Undecidable sets can vary with respect to their computational complexity. The goals here, beyond determining the complexity of the associated first-order theory, are to find out the symmetries of the structures and to find a simple characterization of these structures. These questions are important for deepening the understanding of computation. ***