Computability Theory and its Applications

可计算性理论及其应用

基本信息

批准号：
RGPIN-2018-03982
负责人：
Csima, Barbara
金额：
$ 1.31万
依托单位：
University of Waterloo
依托单位国家：
加拿大
项目类别：
Discovery Grants Program - Individual
财政年份：
2020
资助国家：
加拿大
起止时间：
2020-01-01 至 2021-12-31
项目状态：
已结题

来源：
https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=712652
关键词：
Computability Theory its Applications

项目摘要

Up to the mid 19th century or so, mathematics was mostly algorithmic. Proofs of existence were usually done by giving an actual construction of the object. As mathematics began to become more abstract, people began to study the notions of algorithms and computability. The first stumbling block was on the definition of what it meant to be algorithmic or computable. When faced with an algorithm, people would agree that it was one, but how would one show that something could not be computed, or solved by an algorithm? By the 1930s, work of Turing and others culminated in an acceptable notion of computability. Since the 1930s, computability theory has developed far beyond just checking what is computable and what is not. We have notions of relative computability, where we say A is computed from B if there is some program that can compute A if it is allowed to refer (finitely often) to an infinite tape coding B. In this project, I propose to study various areas of mathematics, and use computability theory to examine the complexity of the proofs. This can help answer questions such as how difficult is it to prove one thing compared to another? Is the original proof the most efficient? How difficult is it to tell that similar objects are actually similar? By studying these properties, we can discover interesting phenomena about the area of mathematics being studied, often leading to further insight.

直到19世纪中叶左右，数学主要是算法。存在的证据通常是通过给物体的实际结构来完成的。随着数学开始变得越来越抽象，人们开始研究算法和计算性的概念。第一个绊脚石是关于算法或可计算的含义的定义。当面对算法时，人们会同意这是一种，但是如何表明无法通过算法来计算或解决某些问题？到1930年代，图灵（Turing）和其他工作的工作最终达到了可接受的可计算性概念。自1930年代以来，计算理论的发展远远不止是检查什么是可计算的，什么不是。我们有相对可计算性的概念，如果有一些程序可以计算A（如果允许经常）将其引用到无限磁带编码B（有限频繁）。在这个项目中，我建议研究数学的各个领域，并使用计算性理论来检查证明的复杂性。这可以帮助回答问题，例如与另一件事相比，证明一件事有多困难？原始证明是最有效的吗？说出类似对象实际上相似有多困难？通过研究这些特性，我们可以发现有关正在研究的数学领域的有趣现象，通常会导致进一步的见解。