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

数学科学：代数编码方法、可计算性理论和模型论

• 批准号: 9500983
• 负责人: Andre Nies
• 金额: $ 6万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-07-01 至 1998-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9500983&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Coding; Methods; Algebra

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

9500983 NIES NIES的研究涉及代数和逻辑领域，这些区域涉及结构和结构类别中的一阶特性编码。 他有兴趣证明由几个量词交替的句子组成的基本理论片段的不可证明性，特别是有限群体的理论，有限的分布晶格理论以及枚举集的晶格E理论。 对这种片段的兴趣来自其通常在数学实践中发生的一阶句子。 此外，他将致力于确定从结构复杂性理论和使用编码方法研究模型理论特性D的结构理论的复杂性。 E和D都是可计算理论中的中心结构。 他同样使用编码方法，旨在证明各种程度结构的非元素等效性，并打算引入对模型理论中属于各种结构的结构的同构类型的信息含量的度量。 在一个进一步的项目中，他计划分开确定性和非确定性线性时间概括的复杂性类别。 编码的一般思想是用另一种对象表示一种对象，并用固定的解码密钥用于从第二种对象中检索信息。 在这个项目中，对象是代数，计算理论和模型理论的某些结构。 解码密钥由一阶逻辑中的公式集成，一种正式语言可以被视为数学中自然语言主要部分的形式化。 结构A中的结构A的编码可以保证B至少与A. NIE一样复杂，NIES将通过比较其co mplexity对所有可能的无限结构的类别进行抽象顺序，并将对有限结构的类别应用类似的方法，近年来，它与计算机科学的联系一直是人们关注的焦点。 在该项目的第二部分中，编码方法将应用于可计算性理论，即在理想意义上处理计算性的数学逻辑的一部分。 不可确定的集合会因其计算复杂性而有所不同。 除了确定相关一阶理论的复杂性之外，这里的目标是找出结构的对称性，并找到对这些结构的简单表征。 这些问题对于加深对计算的理解很重要。 ***