Many Faces of Transfinite Hierarchies

超限层次结构的多面性

• 批准号: 2154173
• 负责人: Linda Westrick
• 金额: $ 15万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-08-01 至 2026-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2154173&HistoricalAwards=false
• 关键词: Many; Faces; Transfinite; Hierarchies

Strictly speaking, an algorithm is a procedure which can be carried out on a computer, but computability theory also includes more expansive notions of algorithm. A generalized algorithm runs for transfinitely many steps, and even a single step is too hard for an ordinary computer, but this kind of algorithmic thinking gives a useful perspective on mathematics. This project will use the algorithmic perspective of computability theory to analyze various hierarchies from classical analysis, topological dynamics, and descriptive set theory. Sometimes a hierarchy-derived tool, such as the measurability of a Borel set, is less powerful than a full hierarchy analysis, but still strong enough for many purposes. The research will explore this distinction, among other questions. The project will also support the training of graduate students. Theorems about Borel sets are sometimes proved by recursing along the structure of the Borel sets, but more often they are proved via measure or category. When the usual measure and category approaches do not pan out, reverse mathematics provides one framework for formalizing the question of whether any measure or category approach could succeed. This framework will be applied to analyze various theorems about Borel sets, in particular theorems from descriptive combinatorics. Second, the PI will address a number of questions about computability-theoretic properties of hierarchies in classical analysis, such as the Bourgain rank or the hierarchy of Denjoy integrable functions. Finally, shifts of finite type (SFTs) are certain topological dynamical systems which are simply described but exhibit complex behavior, because their dynamics can simulate Turing computations. It is not well understood which properties of the resulting dynamical system can be controlled by these computations. The project aims to develop usable meta-theorems describing classes of algorithms that can be implemented in SFTs.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

严格地说，算法是可以在计算机上执行的过程，但可计算性理论还包括更广泛的算法概念。 一个广义的算法要运行很多步骤，即使是一个简单的步骤对普通计算机来说也太难了，但是这种算法思维给了我们一个有用的数学视角。 本专题将使用可计算性理论的算法观点来分析来自古典分析、拓扑动力学和描述集合论的各种层次。 有时，一个层次衍生的工具，如博雷尔集的可测性，不如一个完整的层次分析强大，但仍然足够强大的许多用途。 这项研究将探讨这一区别以及其他问题。 该项目还将支持研究生的培训。关于Borel集的定理有时候是通过沿着Borel集的结构递归来证明的，但更多的时候是通过测度或范畴来证明的。当通常的测量和分类方法不成功时，逆向数学提供了一个框架，用于形式化任何测量或分类方法是否可以成功的问题。 这个框架将被应用于分析各种定理的博雷尔集，特别是定理从描述组合学。 第二，PI将解决一些关于经典分析中层次的可计算性理论性质的问题，例如Bourgain秩或Denjoy可积函数的层次。 最后，有限型移位（SFTs）是一类描述简单但行为复杂的拓扑动力系统，因为它们的动力学可以模拟图灵计算。 目前还不清楚所得到的动力系统的哪些属性可以通过这些计算来控制。 该项目旨在开发可用的元定理，描述可以在SFTs中实现的算法类。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。