Computability, Reverse Mathematics, and Information Coding

可计算性、逆向数学和信息编码

• 批准号: 1600543
• 负责人: Denis Hirschfeldt
• 金额: $ 24万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-06-01 至 2024-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1600543&HistoricalAwards=false
• 关键词: Computability; Reverse; Mathematics; Information; Coding

In the first half of the last century, Turing and others developed a mathematically precise definition of the notion of algorithm, or computer program. Modern computability theory and theoretical computer science grew out of these efforts, and led in particular to an interest in studying the computational content of mathematics. At the same time, developments in the foundations of mathematics led to the investigation of the relative power of different formal systems for mathematical reasoning. These two areas of inquiry turn out to be closely related, and this project is concerned with questions at their intersection. It aims to further our understanding of how structure affects computability, and how computability interacts with other fundamental notions such as randomness, the power of formal systems, and the interactions between formal systems and the mathematical structures they describe.In particular, this project lies in two related areas: computable mathematics and reverse mathematics of combinatorial, model theoretic, and related principles; and notions of robust information coding, including their connections with algorithmic randomness. Reverse mathematics and computable mathematics are closely related and complementary approaches to calibrating the strength of theorems and constructions throughout mathematics, and revealing the fundamental structure behind them. The investigation of combinatorial and model-theoretic principles from this point of view has proved to be a particularly rich line of research, and this project will pursue it from several angles, for instance the study of first order consequences of second order principles and notions of computability theoretic reduction that provide a particularly fine-grained analysis of the comparative strength of mathematical statements. Several of the combinatorial principles that play a central role in this area concern the existence of particular kinds of subobjects, which leads to a natural connection with the investigation of notions of robust information coding, which are reducibilities capturing the idea of being able to obtain partial information about an object from partial information about another. This project will further the study of these notions, in particular versions of infinite information reducibility, which are particularly closely connected with the computability theoretic aspects of versions of Ramsey's Theorem, and versions of coarse reducibility, which have already been found to have significant connections with algorithmic randomness.

在上个世纪上半叶，图灵和其他人对算法或计算机程序的概念进行了精确的数学定义。现代可计算性理论和理论计算机科学从这些努力中发展出来，并特别引起了对研究数学计算内容的兴趣。与此同时，数学基础的发展导致了对数学推理的不同形式系统的相对力量的研究。这两个领域的研究被证明是密切相关的，这个项目关注的是它们交集的问题。它旨在进一步加深我们对结构如何影响可计算性的理解，以及可计算性如何与其他基本概念（如随机性、形式系统的力量、形式系统与它们所描述的数学结构之间的相互作用）相互作用。具体而言，该项目涉及两个相关领域：可计算数学和反向数学的组合、模型理论和相关原理；以及稳健信息编码的概念，包括它们与算法随机性的联系。逆向数学和可计算数学是密切相关和互补的方法，用于校准整个数学中的定理和结构的强度，并揭示它们背后的基本结构。从这个角度对组合和模型理论原理的研究已被证明是一个特别丰富的研究方向，本项目将从几个角度进行研究，例如对二阶原理的一阶结果的研究和可计算理论约简的概念，这些概念提供了对数学陈述的比较强度的特别细粒度的分析。在这一领域中发挥核心作用的几个组合原则涉及特定类型的子对象的存在，这导致了与鲁棒信息编码概念研究的自然联系，这些概念是可约性，能够从关于另一个对象的部分信息中获得关于一个对象的部分信息。这个项目将进一步研究这些概念，特别是无限信息可约性的版本，它与拉姆齐定理版本的可计算性理论方面密切相关，以及粗糙可约性的版本，它已经被发现与算法随机性有重要的联系。