Computability Theory and Logic

可计算性理论和逻辑

• 批准号: 0099556
• 负责人: Robert Soare
• 金额: $ 6万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-15 至 2003-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0099556&HistoricalAwards=false
• 关键词: Computability; Theory; Logic

IN this project the investigator will study computability theory and its relationship and applications to other areas of mathematics such as differential geometry and algebraic structures, as well as internal computability properties such as automorphisms of computably enumerable (c.e.) sets and the effective content of mathematics. The space Riem(M) of Riemannian metrics (modulo diffeomorphisms) on certain manifolds is of considerable interest to a wide variety of mathematicians and physicists. Topologists have proved for certain natural scale invariant functionals related to diameter on the space Riem(M), and for certain manifolds M of dimension 4 that for every c.e. set A there is a sequence of points x_n, n in N, the integers, such that if n in A then x_n determines a local minimum on Riem(M) whose depth is roughly equal to the halting time of the Turing machine computation that n in A. The investigator constructed an infinite sequence of sets A_i, i in N, of c.e. sets so that for all n the settling function (for stopping times of the associated Turing machine) of A_i dominates that of A_{i+1}, even when the latter is composed with an arbitrary computable function. The two results together give a "fractal" like behavior with extremely big basins, and very much smaller basins coming off them, and those containing still smaller basins, and so on, where the relative size of one set of basins to the next exceeds any computable function, what the topologists describe in their paper on fractals as "the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization.'' The investigator's work will also stress connections of computability to model theory and algebraic structures. With a junior colleague and a graduate student he will classify the degree spectrum of models which are prime or saturated but which have no computable isomorphic copy. Finally, he will continue his work on the automorphisms and structure of c.e. sets. He will put together these results to help obtain a classification of structure of c.e. sets and effective content of certain parts of mathematics.

在这个项目中，研究人员将研究可计算性理论及其在其他数学领域的关系和应用，如微分几何和代数结构，以及内部可计算性性质，如可计算可数(C.E.)的自同构。集合和数学的有效内容。黎曼度量(模微分同胚)在某些流形上的空间Riem(M)是许多数学家和物理学家非常感兴趣的问题。拓扑学家已经证明了对于Riem(M)空间上与直径有关的某些自然尺度不变泛函，以及对于某些4维流形M，对于每个C.E.集合A有一个点序列x_n，n在N中是整数，使得如果n在A中，则x_n确定Riem(M)上的一个局部极小值，它的深度大致等于图灵机计算在A中的停止时间。调查者构造了一个无穷序列集A_i，i in N，在C.E.集合使得对于所有n，A_i的稳定函数(用于相关图灵机的停止时间)支配A_{i+1}的稳定函数，即使后者由任意可计算函数组成。这两个结果一起给出了一个类似于“分形”的行为：非常大的盆地，从它们上面出来的非常小的盆地，以及那些包含更小的盆地，以此类推，其中一组盆地与另一组盆地的相对大小超过了任何可计算的函数，拓扑学家在他们的关于分形学的论文中将其描述为“在光滑流形上，黎曼度量空间的惊人丰富，直到重新参数化。”研究人员的工作还将强调可计算性与模型理论和代数结构的联系。与一名初级同事和一名研究生一起，他将对质数或饱和但没有可计算同构副本的模型的度谱进行分类。最后，他将继续研究C.E.的自同构和结构。布景。他将把这些结果结合起来，以帮助获得C.E.的结构分类。数学某些部分的集合和有效内容。