Computability Theory and its Applications

可计算性理论及其应用

• 批准号: 312501-2013
• 负责人: Csima, Barbara
• 金额: $ 1.09万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=526546
• 关键词: 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.

直到19世纪中期左右，数学主要是算法。存在的证明通常是通过给出物体的实际构造来完成的。随着数学变得越来越抽象，人们开始研究算法和可计算性的概念。第一个障碍是对算法或可计算的定义。当面对一种算法时，人们会同意它是一种算法，但人们如何证明某些东西不能被计算出来，或者不能被算法解决呢？到了20世纪30年代，图灵和其他人的工作在可计算性的概念上达到了顶峰。