Computability Theory and Logic

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

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.