Grant: Discovery Grants Program - Individual
University of Waterloo
$15,000.00
Computability Theory and its Applications
EF 2016-17
Résumé
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 find out interesting phenomena about the area of mathematics being studied, often leading to further insight.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
312501-2013
Name nom
Csima, Barbara
Department département
Pure Mathematics
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2013
Award amount
15000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2912
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Logic
Research subject fr
Logique
Partie
4
Nb partie
5
Application title
Computability Theory and its Applications
Keyword
NSERC
Application summary
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 find out interesting phenomena about the area of mathematics being studied, often leading to further insight.