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