Many Faces of Transfinite Hierarchies

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

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.