Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$34,000.00

Computability Theory and its Applications

EF 2024-25

Résumé
Until 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 became 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, the work of Alan Turing and others culminated in an acceptable notion of computability. Since the 1930s, computability theory has developed far beyond simply 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 my ongoing research program, 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. Through the involvement of undergraduate and graduate students, as well as postdoctoral fellows, in the research program, I will also provide training and mentorship to the next generation. Some of these trainees will go on to careers in academia, while others will use the problem solving, communication, and time management skills learned in other careers.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2024-04021
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
2024
Competition year année de concours
2024
Award amount
34000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
2900
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Pure mathematics
Research subject fr
Mathématiques pures
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Computability Theory and its Applications
Keywords
computability theory; recursion theory; computable model theory; computable structure theory; reverse mathematics
Application summary
Until 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 became 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, the work of Alan Turing and others culminated in an acceptable notion of computability. Since the 1930s, computability theory has developed far beyond simply 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 my ongoing research program, 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. Through the involvement of undergraduate and graduate students, as well as postdoctoral fellows, in the research program, I will also provide training and mentorship to the next generation. Some of these trainees will go on to careers in academia, while others will use the problem solving, communication, and time management skills learned in other careers.