Department of Mathematical Logic and Applications
English version Bulgarian version

Models of Computability

a project supported by the Bulgarian Science Fund, DN 02-16/19.12.2016

Project description

The research conducted in this project is concentrated on two mathematical models for the problems that arise in natural sciences, compared to their information content. The rigidity issue of the more adequate model of the enumeration degrees is one of the main tasks in computability theory. It would reveal which problems can only be approximated and how accurately this can be done. It would allow transforming in an algorithmic way solutions of given problems into solutions of other problems. Thus, the question that arises is to what extent the local structure, consisting of the problems that we could approximate well, determines the entire structure of the information content of the problems. The hypothesis is that the local structure determines fully the global structure. A confirmation of this hypothesis would have significant consequences for computability theory. The next step is to understand the objects at a higher level – the mathematical structures. To study the complexity of a structure, we associate with it a set of degrees that describes it: the spectrum of the structure. The task is to examine how the models of computability can be applied to the study of the effective properties of the classical mathematical objects. The complexity of the connections between the different presentations is also of interest, because it gives a more complete picture of the algorithmic properties. A natural development of the topic is the study of the functions on real numbers, which can be described by an algorithm, i.e. the computable analysis. The question here is how the restriction of the generality of computable processes reflects computable analysis, in other words, what is the relationship between computable analysis and complexity theory. The studies here aim at effective computability of real constants and functions with respect to low subrecursive classes. The Bulgarian project members form one of the strongest groups on computability theory in Europe. This project consolidates this positive trend by providing the opportunity to work closely with some of the most prominent international experts in the field, the foreign project members.

Participants

Bulgarian participants

Foreign participants

Editorial work

  1. The Incomputable: Journeys Beyond the Turing Barrier, S. B. Cooper and M. Soskova. Springer book (2017) (doi)

Published papers

  1. A Structural Dichotomy in the Enumearion Degrees, H. Ganchev, I. Kalimullin, J. Miller, M. Soskova. Journal of Symbolic Logic, vol. 87, issue 2 (2022) pp. 527-544 (doi) (preprint)
  2. Interpreting a field in its Heisenberg group, R. Alvir, W. Calvert, G. Goodman, V. Harizanov, J. Knight, A. Morozov, R. Miller, A. Soskova, R. Weisshaar. Journal of Symbolic Logic vol. 87, issue 2 (2022) pp. 1215-1230 (doi) (preprint)
  3. Computable embeddings for pairs of linear orders, N. Bazhenov, H. Ganchev, S. Vatev. Algebra and Logic, vol. 60, no. 3 (2021) pp. 163 - 187 (doi) (preprint)
  4. Computable Irrational Numbers with Representations of Surprising Complexity, I. Georgiev, L. Kristiansen, F. Stephan. Annals of Pure and Applied Logic, vol. 172 (2021), no. 2 (doi) (preprint)
  5. Coding in graphs and linear orderings, J. Knight, A. Soskova, S. Vatev. Journal of Symbolic Logic, vol. 85 (2020), no. 2, pp. 673-690, (doi) (preprint)
  6. On subrecursive complexity of integration, Ivan Georgiev. Annals of Pure and Applied Logic, vol. 171, issue 4 (2020) (doi) (preprint)
  7. A Note on Computable Embeddings for Ordinals and Their Reverses, N. Bazhenov, S. Vatev. Proceedings of CiE 2020 (doi) (preprint)
  8. Definability in the local theory of the ω-Turing degrees, H. Ganchev and A. Sariev. to appear in Mathematical Structures in Computer Science (doi) (preprint)
  9. Cohesive powers of linear orders, R. Dimitrov, V. Harizanov, A. Morozov, P. Shafer, A. Soskova and S. Vatev. Lecture Notes in Computer Science “Proceedings of CiE 2019”, vol. 11558 (2019), pp. 168 - 180 (doi) (preprint)
  10. Minimal ω-Turing degrees, Andrey Sariev. Proceedings of the 12-th Panhellenic Logic Symposium (2019), Anogeia, Greece (preprint)
  11. On cototatlity and the skip operator, U. Andrews, H. Ganchev, R. Kuyper, S. Lempp, J. Miller, A. Soskova and M. Soskova. Transactions of American Mathematical Society, vol. 372 (2019), pp. 1631 - 1670 (doi) (preprint)
  12. Definability issues in the ω-Turing degrees, H. Ganchev and A. Sariev. Annual of Sofia University, vol. 105 (2018), pp. 45-54 (preprint)
  13. The jump hierarchy in the enumeration degrees, H. Ganchev and M. Soskova. Computability, vol. 7 (2018), no. 2-3, pp. 179–188 (doi) (preprint)
  14. Strong jump inversion, W. Calvert, A. Frolov, V. Harizanov, J. Knight, C. McCoy, A. Soskova and S. Vatev. Journal of Logic and Computation, vol. 28, Issue 7 (2018), pp. 1499–1522 (doi) (preprint)
  15. On General Sum Approximations of Irrational Numbers, I. Georgiev, Lars Kristiansen and Frank Stefan. In: Manea F., Miller R., Nowotka D. (eds) Sailing Routes in the World of Computation. CiE 2018. Lecture Notes in Computer Science, Springer, vol. 10936 (2018), pp. 194–203 (doi) (preprint)
  16. Density of the cototal enumeration degrees, J. Miller and M. Soskova. Annals of Pure and Applied Logic, no. 5 (2018), pp. 450–462 (doi) (preprint)
  17. Fast Converging Sequence to Euler-Mascheroni Constant, I. Georgiev. Annuaire de l’Universite de Sofia “St. Kliment Ohridski” Faculte de Mathematiques et Informatique, vol. 104, (2017), pp. 185–191 (preprint)
  18. Definability of the jump operator in the ω-enumeration degrees, H. Ganchev and A. Sariev. Proceedings of the 11th Panhellenic Logic Symposium, Delphi, Greece, A. Soskova, A. Kakas, N. Papaspyrou eds. NTU, Athens, (2017), pp. 61–64 (preprint)
  19. За Димитър Скордев от неговите ученици, A. Soskova, L. Ivanov и I. Georgiev. СМБ, Математика и Математическо образование. Доклади на 46-тата пролетна конференция на СМБ, Borovets, (2017), pp. 52–62 (preprint)

Accepted papers

  1. Expanding the reals by continuous functions adds no computational power, U. Andrews, J. Knight, R. Kuyper, J. Miller and M. Soskova. accepted to Journal of Symbolic Logic (doi) (preprint)
  2. On cohesive powers of linear orders, R. Dimitrov, V. Harizanov, A. Morozov, P. Shafer, A. Soskova, S. Vatev. accepted to Journal of Symbolic Logic (doi) (preprint)

Talks at conferences

  1. Computable embeddings for classes of structures, Stefan Vatev. Workshop on Digitalization and Computable Models, Novosibirsk, Russia, December 2019 (slides)
  2. Uniform Limits of Conditionally Computable Real Functions, Ivan Georgiev. Higher-order Complexity Theory and its Applications, Japan, October 2019 (slides)
  3. On representations of irrational numbers in subrecursive context, Ivan Georgiev. Computability and Complexity in Analysis 2019, Zagreb, July 2019 (slides)
  4. Effective embeddings for pairs of structures, Stefan Vatev. Computability in Europe 2019, Durham, July 2019 (slides)
  5. Minimal ω-Turing degrees, Andrey Sariev. Proceedings of the 12-th Panhellenic Logic Symposium (2019), Anogeia, Greece (slides)
  6. Transfer of Properties from Uniform to Conditional Computability of Real Functions, Ivan Georgiev. 12th Panhellenic Logic Symposium, Anogeia, Crete, June 2019 (poster)
  7. On the complexity of irrational numbers under different representations, Ivan Georgiev. Scientific session dedicated to the 80th anniversary of Prof. Dimiter Vakarelov, Gyolechitsa, 12-14 May 2018 (slides)
  8. Randomness relative to an enumeration oracle, Mariya Soskova. Oberwolfach Workshop in Computability Theory. Oberwolfach. Invited speaker (slides)
  9. Бързо сходяща редица към константата на Ойлер-Маскерони, Иван Георгиев. Юбилейна научна конференция “100 години от рождението на проф. Ярослав Тагамлицки”, ФМИ, СУ (slides)
  10. Cototal enumeration degrees and skip operator, Alexandra Soskova. Aspects of Computation, 2017, Workshop on Classical Computability Theory, Singapore. Invited speaker (slides)
  11. Characterizing the continuous degrees, Mariya Soskova. Logic Colloquium 2017, Stockholm, August 2017. Invited speaker at the special session on computability (slides)
  12. Structural properties of the cototal enumeration degrees, Alexandra Soskova. Logic Colloquium 2017, Stockholm, August 2017 (slides)
  13. Complexity of some real numbers and functions with respect to the subrecursive class M2, Ivan Georgiev. Computability and Complexity in Analysis, Daejeon, Republic of Korea, July 2017 (slides)
  14. Definability of the Jump Operator in the ω-enumeration Degrees, Andrey Sariev. 11th Panhellenic Logic Symposium, Delphi, Greece, July 2017 (slides)
  15. Structural properties of spectra and ω-spectra, Alexandra Soskova. Computability in Europe 2017, Turku, June 2017 (slides)
  16. Generic Muchnik reducibility and expansions of the reals, Mariya Soskova. AMS Sectional Meeting, Hunter’s College, New York City, May 2017. Invited speaker (slides)
  17. Seven characterizations of the cototal enumeration degrees, Mariya Soskova. South Eastern Logic Symposium 2017, University of Florida, Gainesville, March 2017. Invited speaker at the special session on Computability Theory (slides)

Talks at seminars

  1. Effective embeddings for pairs of structures, Stefan Vatev. Computability Seminar, University of Notre Dame, March 2019
  2. Strong jump inversion, Alexandra Soskova. Logic Seminar at University of Leeds, August 2018 (slides)
  3. Properties of degree spectra, co-spectra and ω co-spectra, Alexandra Soskova. Logic Seminar at University of Notre Dame, May 2018 (slides)
  4. Jump Inversion of Structures, Stefan Vatev. Computability Seminar, University of Notre Dame, April 2018 (slides)
  5. Structural properties of spectra and omega-spectra, Alexandra Soskova. Logic Seminar at George Washington University, March 2018 (slides)
  6. The definability of the continuous degrees, Mariya Soskova. Mathematical Logic Seminar, FMI, Sofia University, January 2018 (slides)
  7. Characterizing the continuous degrees, Mariya Soskova. Southern Wisconsin Logic Colloquium, University of Wisconsin–Madison, November 2017 (slides)
  8. Subrecursive Computability in Analysis, Ivan Georgiev. Mathematical Logic Seminar, FMI, Sofia University, July 2017 (slides)
  9. Cototal enumeration degrees, Alexandra Soskova. Siena University Logic Seminar, June 2017 (slides)
  10. Logic and degrees, Mariya Soskova. Marquette University Mathematics Colloquium, Milwaukee. April 2017 (slides)

Last edition on 17 August 2023 at 17:07. This page is valid XHTML 1.0 Strict with valid CSS level 2.1.