Computability Theory, Reverse Mathematics and Countable Algebraic Structures

可计算性理论、逆向数学和可数代数结构

• 批准号: 0400754
• 负责人: David Solomon
• 金额: $ 8.6万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-06-01 至 2007-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0400754&HistoricalAwards=false
• 关键词: Computability; Theory; Reverse; Mathematics; Countable

In computable algebra, one applies the methods of classical computability theory to study computational properties of algebraic structures. Solomon proposes to study several questions concerning the members ofthese and other classes of algebraic structures. Do the members of a given class display the most general forms of ineffectiveness found in computable algebra? Are instances of ineffectiveness caused by the coding methods (and hence can be removed by a reasonable coding) or by some inherent property of the underlying algebra (and are therefore unavoidable)? How does adding structure (such as an ordering) to the members of a class effect the computational properties? These questions aim toward a deeper understanding of the connection between computation and algebraic behavior in mathematics. Many theorems in mathematics state that given certain conditions, a particular mathematical object must exist. There are numerous ways to study the effectiveness of such a theorem. One method, called computable or recursive mathematics, uses an idealized model of a computer in which computations are allowed to run for arbitrarily long (but finite) amounts of time and to use arbitrarily large (but finite) amounts of memory. The fundamental question is whether such an idealized computer can construct the desired mathematical object from the theorem. If the answer to this question is no, then the theorem uses a method of construction that cannot be performed on an actual computer no matter how much technology increases computer speed and memory size. Because this question requires that mathematical objects be coded into the binary language of computers, the answer sometimes depends on the type of coding used. Solomon proposes to study a number of algebraic constructions from this point of view and in particular to study when ineffectiveness is caused by a poor choice of coding (and hence can be fixed by a better choice of coding) and when it is caused by inherent conflicts between mathematical structure and computation (and hence cannot be removed by clever coding). Solomon also proposes to use a second method, called reverse mathematics, to study the effectiveness of numerous mathematical theorems. In this approach, one isolates the mathematical axioms required to prove the theorem. Reverse mathematics and computable mathematics are closely related. If only simple axioms are required to prove a theorem, then it is likely that a computer can carry out the construction, while if complicated axioms are required, then a computer probably cannot perform the construction.

在可计算代数中，人们应用经典可计算性理论的方法来研究代数结构的计算性质。 所罗门提出研究几个问题的成员ofthese和其他类别的代数结构。 给定类的成员是否表现出可计算代数中最普遍的无效性形式？ 无效的例子是由编码方法引起的（因此可以通过合理的编码来消除）还是由底层代数的某些固有属性引起的（因此是不可避免的）？ 向类的成员添加结构（如排序）如何影响计算属性？ 这些问题旨在更深入地理解数学中计算和代数行为之间的联系。 数学中的许多定理指出，给定某些条件，特定的数学对象必须存在。 有许多方法可以研究这样一个定理的有效性。 一种方法，称为可计算或递归数学，使用计算机的理想化模型，其中允许计算运行任意长（但有限）的时间，并使用任意大（但有限）的内存量。 基本的问题是这样一个理想化的计算机是否能从定理中构造出所需的数学对象。 如果这个问题的答案是否定的，那么该定理使用的构造方法无法在实际计算机上执行，无论技术如何提高计算机速度和内存大小。 因为这个问题要求数学对象被编码成计算机的二进制语言，所以答案有时取决于所使用的编码类型。 所罗门提议从这个角度研究许多代数结构，特别是研究无效性何时是由糟糕的编码选择引起的（因此可以通过更好的编码选择来修复），以及何时是由数学结构和计算之间的固有冲突引起的（因此无法通过巧妙的编码来消除）。 所罗门还提议使用第二种方法，称为反向数学，来研究众多数学定理的有效性。 在这种方法中，人们隔离了证明定理所需的数学公理。 逆向数学与可计算数学密切相关。 如果只需要简单的公理来证明一个定理，那么很可能计算机可以进行构造，而如果需要复杂的公理，那么计算机可能无法进行构造。