Computably universal spaces
ONLINE
One of the central challenges of today's theory of computation is the lack of a systematic theoretical framework behind on-line algorithms. One usually studies only "off-line" algorithms with a fixed input. However, many modern computational tasks need to be performed upon a constantly updated and potentially unbounded input. For example, any algorithm dealing with a huge constantly changing database cannot have knowledge of the whole of the database before acting.
The proposed project contributes to a new and rapidly developing theory that aims to unite, explain, and ultimately advance the sparse results on on-line computation. More specifically, Kalimullin, Melnikov and Ng (2017) proposed a general framework for on-line computation for algebraic and combinatorial structures that relies on Dedekind's "primitive" recursion and advanced priority constructions. There is nothing primitive about this sort of recursion, as every polynomial-time algorithm is in fact primitive recursive.
The specific problems that we propose to attack during the workshop are motivated by the well-known results from computable algebra. These problems deal with the computational content of the theory of metric spaces, and the results will be applicable in the field of computable analysis (this is a fruitful area of the modern computability theory).
The proposed project contributes to a new and rapidly developing theory that aims to unite, explain, and ultimately advance the sparse results on on-line computation. More specifically, Kalimullin, Melnikov and Ng (2017) proposed a general framework for on-line computation for algebraic and combinatorial structures that relies on Dedekind's "primitive" recursion and advanced priority constructions. There is nothing primitive about this sort of recursion, as every polynomial-time algorithm is in fact primitive recursive.
The specific problems that we propose to attack during the workshop are motivated by the well-known results from computable algebra. These problems deal with the computational content of the theory of metric spaces, and the results will be applicable in the field of computable analysis (this is a fruitful area of the modern computability theory).
Brief description
Project team
Participants' expertise requirements:
1. English language proficiency: sufficient for reading scientific articles and understanding mathematical lectures.
2. Knowing the basics of computability theory (the notions of Turing machine, partial computable function, arithmetical hierarchy, computable algebraic structure, polynomial-time algorithm).
3. Knowing the basics of topology (the notions of topological space, separable metric space, compact space).
2. Knowing the basics of computability theory (the notions of Turing machine, partial computable function, arithmetical hierarchy, computable algebraic structure, polynomial-time algorithm).
3. Knowing the basics of topology (the notions of topological space, separable metric space, compact space).
You must necessarily possess:
Alexander Melnikov
End–user
PhD, Associate Professor, School of Natural and Computational Sciences, Massey University, New Zeland; Senior Researcher, Mathematical Center in Akademgorodok
Nikolay Bazhenov
End–user assistant
Candidate of Science, Senior Researcher, Mathematical Center in Akademgorodok
Ruslan Kornev
Tutor
Junior Researcher, Mathematical Center in Akademgorodok
Iskander Kalimullin
Lecturer
Doctor of Science, Associate Professor, Chief Researcher, N.I. Lobachevsky Institute of Mathematics and Mechanics, Kazan Federal University
Keng Meng Ng
Lecturer
PhD, Associate Professor, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
Victor Selivanov
Lecturer
Doctor of Science, Chief Researcher, A.P. Ershov Institute of Informatics Systems; Senior Researcher, Mathematical Center in Akademgorodok
The Workshop is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2019-1675 with the Ministry of Science and Higher Education of the Russian Federation.
Contacts