Цифровизация математических моделей и интеллектуальные системы обработки данных

Теория вычислимости является одной из центральных тем в математической логике и информатике. Исследования вычислимых по Тьюрингу алгоритмов во многом предопределили развитие современных компьютеров. Общая теория вычислимости и теория алгоритмов позволяют классифицировать сложность алгоритмических проблем с помощью различных сводимостей и иерархий. 

В исследовательском проекте методы современной теории вычислимости применяются для того, чтобы методологически объединить и развить ряд областей современной математики и информатики. Предлагается единый подход к этим областям, основанный на утончениях и обобщениях общепринятого теоретического понятия вычислимости. Основными направлениями исследований являются: 

• Проблемы классификации в математике и теоретической информатике. 
• Новая теория онлайн вычислений. 
• Математические методы, основанные на теории определимости и приоритетных конструкциях.

Основные результаты научной группы

1. Доказано, что три популярных (в литературе по компьютерной алгебре) представления упорядоченного поля вещественных алгебраических чисел полиномиально эквивалентны между собой.     
    
2. Установлена собственность тонкой иерархии арифметических $k$-разбиений натурального ряда.     
    
3. Для достаточно широкого класса упорядоченных полей получен примитивно рекурсивный аналог классической теоремы о конструктивизируемости вещественного замыкания конструктивного упорядоченного поля; этот аналог имеет интересные следствия для примитивной рекурсивности некоторых алгоритмов в линейной алгебре и в анализе.     
    
4. Получен новый критерий предельной распознаваемости (learnability in the limit) для счётных семейств вычислимых алгебраических структур.     
    
5. Доказано, что для произвольного стоуновского пространства $X$ соответствующее банахово пространство $C(X,R)$ имеет вычислимое представление в том и только том случае, когда $X$ гомеоморфно вычислимо-метризуемому пространству.     
    
6. Установлены новые свойства структуры степеней позитивных предпорядков относительно вычислимой сводимости: в частности, показано, что теория этой структуры рекурсивно изоморфна арифметике первого порядка.     
    
7. Построен пример допустимого множества $A$, в котором существует позитивная вычислимая $A$-нумерация семейства всех $A$-вычислимо перечислимых множеств, в то время как негативные вычислимые $A$-нумерации отсутствуют.    
    
8. В рамках reverse mathematics изучены логические свойства теоремы Райвала–Сэндса о цепях в бесконечных частичных порядках.     
    
9. Установлены новые свойства темпоральных аппроксимационных пространств над интервальными расширениями плотных линейных порядков (эти расширения рассматриваются как математические модели семантики глаголов в естественных языках); в частности, получено эффективное описание интервалов, соответствующих различным временам английского глагола.    
    

Список публикаций научной группы

1. Алаев П. Е., Селиванов В. Л.    
   Поля алгебраических чисел, вычислимые за полиномиальное время. II // Алгебра и логика, 60:6 (2021), 533–548. https://doi.org/10.33048/alglog.2021.60.601    
   (Перевод: Alaev P. E. and Selivanov V. L.    
   Fields of algebraic numbers computable in polynomial time. II // Algebra and Logic, 60:6 (2022), 349–359.    
   https://doi.org/10.1007/s10469-022-09661-3)    
    
2. Бадаев С. А., Баженов Н. А., Калмурзаев Б. С.    
   О структуре позитивных предпорядков // Алгебра и логика, 59:3 (2020), 293–314.    
   https://doi.org/10.33048/alglog.2020.59.301    
   (Перевод: Badaev S. A., Bazhenov N. A., and Kalmurzaev B. S.    
   The structure of computably enumerable preorder relations // Algebra and Logic, 59:3 (2020), 201–215.    
   https://doi.org/10.1007/s10469-020-09592-x)    
    
3. Баженов Н. А., Мустафа М., Оспичев С. С.    
   Об универсальных парах в иерархии Ершова // Сибирский математический журнал, 62:1 (2021), 31–41.    
   https://doi.org/10.33048/smzh.2021.62.103    
   (Перевод: Bazhenov N. A., Mustafa M., and Ospichev S. S.    
   On universal pairs in the Ershov hierarchy // Siberian Mathematical Journal, 62:1 (2021), 23–31.    
   https://doi.org/10.1134/S0037446621010031)    
    
4. Бурнистов А. С., Стукачев А. И.    
   О внутренней конструктивизируемости функциональных структур // Алгебра и логика, 61:1 (2022), 23–41.    
   https://doi.org/10.33048/alglog.2022.61.102    
   (Перевод: Burnistov A. S. and Stukachev A. I.    
   Inner constructivizability of functional structures // Algebra and Logic, 61:1 (2022), 16–29.    
   https://doi.org/10.1007/s10469-022-09672-0)    
    
5. Гончаров С. С., Марчук М. И.    
   О степени разрешимой категоричности модели с бесконечными решениями для полных формул // Алгебра и логика, 60:3 (2021), 303–312.    
   https://doi.org/10.33048/alglog.2021.60.304    
   (Перевод: Goncharov S. S. and Marchuk M. I.    
   The degree of decidable categoricity of a model with infinite solutions for complete formulas // Algebra and Logic, 60:3 (2021), 200–206.    
   https://doi.org/10.1007/s10469-021-09642-y)    
    
6. Калимуллин И. Ш., Пузаренко В. Г., Файзрахманов М. Х.    
   Позитивные нумерации в допустимых множествах // Сибирский математический журнал, 61:3 (2020), 607–621.    
   https://doi.org/10.33048/smzh.2020.61.309    
   (Перевод: Kalimullin I. Sh., Puzarenko V. G., and Faizrahmanov M. Kh.    
   Positive numberings in admissible sets // Siberian Mathematical Journal, 61:3 (2020), 478–489.    
   https://doi.org/10.1134/S003744662003009X)    
    
7. Корнев Р. А.    
   Полурешетка степеней вычислимых метрик // Сибирский математический журнал, 62:5 (2021), 1013–1038.    
   https://doi.org/10.33048/smzh.2021.62.505    
   (Перевод: Kornev R. A.    
   A semilattice of degrees of computable metrics // Siberian Mathematical Journal, 62:5 (2021), 822–841.    
   https://doi.org/10.1134/S0037446621050050)    
    
8. Стукачев А. И.    
   Интервальные расширения порядков и темпоральные аппроксимационные пространства // Сибирский математический журнал, 62:4 (2021), 894–910.    
   https://doi.org/10.33048/smzh.2021.62.415    
   (Перевод: Stukachev A. I.    
   Interval extensions of orders and temporal approximation spaces // Siberian Mathematical Journal, 62:4 (2021), 730–741.    
   https://doi.org/10.1134/S0037446621040157)    
    
9. Хусаинов Б., Мельников А. Г.    
   Разложимость и вычислимость // Алгебра и логика, 61:2 (2022), 220–229.    
   https://doi.org/10.33048/alglog.2022.61.205    
   (Перевод: Khoussainov B. and Melnikov A. G.    
   Decomposability and computability // Algebra and Logic, 61:2 (2022), 153–159.    
   https://doi.org/10.1007/s10469-022-09683-x)    
    
10. Alaev P. and Selivanov V.    
    Complexity issues for the iterated $h$-preorders // Lecture Notes in Computer Science, vol. 13037, pp. 1–12. Springer, Cham, 2022.    
    https://doi.org/10.1007/978-3-030-93489-7_1    
     
11. Alaev P. E. and Selivanov V. L.    
    Searching for applicable versions of computable structures // Lecture Notes in Computer Science, vol. 12813, pp. 1–11. Springer, Cham, 2021.    
    https://doi.org/10.1007/978-3-030-80049-9_1    
     
12. Bazhenov N.    
    Definable subsets of polynomial-time algebraic structures // Lecture Notes in Computer Science, vol. 12159, pp. 142–154. Springer, Cham, 2020.    
    https://doi.org/10.1007/978-3-030-50026-9_10    
     
13. Bazhenov N., Cipriani V., and San Mauro L.    
    Learning algebraic structures with the help of Borel equivalence relations // Theoretical Computer Science, 951 (2023), article id 113762.    
    https://doi.org/10.1016/j.tcs.2023.113762    
     
14. Bazhenov N., Harrison-Trainor M., and Melnikov A.    
    Computable Stone spaces // Annals of Pure and Applied Logic, 174:9 (2023), article id 103304.    
    https://doi.org/10.1016/j.apal.2023.103304    
     
15. Bazhenov N., Kalmurzayev B., and Zubkov M.    
    A note on joins and meets for positive linear preorders // Сибирские электронные математические известия, 20:1 (2023), 1–16.    
    https://doi.org/10.33048/semi.2023.20.001    
     
16. Bazhenov N. and Kalocinski D.    
    Degree spectra, and relative acceptability of notations // Leibniz International Proceedings in Informatics, vol. 252 (2023), paper 11.    
    https://doi.org/10.4230/LIPIcs.CSL.2023.11    
     
17. Bazhenov N., Kalocinski D., and Wroclawski M.    
    Intrinsic complexity of recursive functions on natural numbers with standard order // Leibniz International Proceedings in Informatics, vol. 219 (2022), paper 8.    
    https://doi.org/10.4230/LIPIcs.STACS.2022.8    
     
18. Bazhenov N. and Marchuk M.    
    A note on decidable categoricity and index sets // Сибирские электронные математические известия, 17 (2020), 1013–1026.    
    https://doi.org/10.33048/semi.2020.17.076    
     
19. Bazhenov N., Mustafa M., and Nurakunov A.    
    On two types of concept lattices in the theory of numberings // Lecture Notes in Computer Science, vol. 13571, pp. 79-92. Springer, Cham, 2022.   
    https://doi.org/10.1007/978-3-031-20350-3_8    
     
20. Bazhenov N., Mustafa M., and Ospichev S.    
    Rogers semilattices of punctual numberings // Mathematical Structures in Computer Science, 32:2 (2022), 164–188.    
    https://doi.org/10.1017/S0960129522000093    
     
21. Bazhenov N., Ng K. M., San Mauro L., and Sorbi A.    
    Primitive recursive equivalence relations and their primitive recursive complexity // Computability, 11:3-4 (2022), 187–221.    
    https://doi.org/10.3233/COM-210375    
     
22. Bazhenov N. and San Mauro L.    
    On the Turing complexity of learning finite families of algebraic structures // Journal of Logic and Computation, 31:7 (2021), 1891–1900.    
    https://doi.org/10.1093/logcom/exab044    
     
23. Dorzhieva M. V., Issakhov A. A., Kalmurzayev B. S., Kornev R. A., and Kotov M. V.    
    Punctual dimension of algebraic structures in certain classes // Lobachevskii Journal of Mathematics, 42:4 (2021), 716–725.    
    https://doi.org/10.1134/S1995080221040089    
     
24. Fiori-Carones M., Marcone A., Shafer P., and Solda G.    
    (Extra)Ordinary equivalences with the ascending/descending sequence principle // Journal of Symbolic Logic, published online.    
    https://doi.org/10.1017/jsl.2022.92    
     
25. Koswara I., Pogudin G., Selivanova S., and Ziegler M.    
    Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations // Journal of Complexity, 76 (2023), article id 101727.    
    https://doi.org/10.1016/j.jco.2022.101727    
     
26. Novikov A., Novikov A., and Farkhshatov F.    
    Numerical solution of Kiefer-Weiss problems when sampling from continuous exponential families // Sequential Analysis, 42:2 (2023), 189–209.    
    https://doi.org/10.1080/07474946.2023.2193602    
     
27. Novikov A. and Zainullin R.    
    Phase shift and multi-controlled $Z$-type gates // Quantum Information Processing, 22:7 (2023), article 269.    
    https://doi.org/10.1007/s11128-023-04005-1    
     
28. Selivanov V.    
    Boole vs Wadge: Comparing two basic tools of descriptive set theory // Lecture Notes in Computer Science, vol. 13359, 287–298. Springer, Cham, 2022.    
    https://doi.org/10.1007/978-3-031-08740-0_24    
     
29. Selivanov V.    
    Desriptive complexity of $qcb_0$-spaces // Theoretical Computer Science, 945 (2023), article id 113666.    
    https://doi.org/10.1016/j.tcs.2022.12.016    
     
30. Selivanov V.    
    Non-collapse of the effective Wadge hierarchy // Lecture Notes in Computer Science, vol. 12813, pp. 407–416. Springer, Cham, 2021.    
    https://doi.org/10.1007/978-3-030-80049-9_40    
     
31. Selivanov V.    
    Non-collapse of the effective Wadge hierarchy // Computability, 11:3–4 (2022), 335–358.    
    https://doi.org/10.3233/COM-210376    
     
32. Selivanov V. and Selivanova S.    
    Primitive recursive ordered fields and some applications // Lecture Notes in Computer Science, vol. 12865, pp. 353–369. Springer, Cham, 2021.    
    https://doi.org/10.1007/978-3-030-85165-1_20    
     
33. Selivanov V. and Selivanova S.    
    Primitive recursive ordered fields and some applications // Computability, 12:1 (2023), 71–99.    
    https://doi.org/10.3233/COM-210386