Preface of the special issue for the conference computability in Europe 2022

The articles in this special double issue of the journal Computability constitute a post-conference publication of the meeting Computability in Europe 2022: Revolutions and Revelations in Computability, held at Swansea University, UK, between July 11 and July 15, 2022. CiE 2022 was the eighteenth in the series of conferences organized by the Association for Computability in Europe. The main aim of the association is to promote the development, particularly in Europe, of computability-related science, ranging over mathematics, computer science and applications in various natural and engineering sciences such as physics and biology. Its aims include the promotion of the study of philosophy and history of computing as it relates to questions of computability.

The theme of CiE 2022 alludes to the revolutionary developments we have seen in computability theory, starting with Turing’s and Gödel’s discoveries to the advent of new computational paradigms. The conference addressed not only the more established lines of research of computability and complexity theory and the interplay between proofs and computation, but also novel views that rely on physical and biological processes and models to find new ways of tackling computations and improving their efficiency. As is usual in computer science, CiE 2022 had a regular pre-proceedings volume published in Lecture Notes in Computer Science [1].

As a follow-up to the conference, this special issue was edited with journal versions of talks and presentations at CiE 2022. It adheres to the CiE publications policy which does not allow double publication of the same research content: in order to be accepted for a post-proceedings special issue, a journal version must exhibit unpublished research content beyond the content printed in the LNCS volume.

The papers published were pre-selected by the Programme Committee of CiE 2022 and underwent a thorough and strict refereeing process. This was the work of many referees who put in a lot of effort to judge the quality of the articles for the special issue. Eight of the twelve papers are journal versions of papers published in the mentioned LNCS volume: the paper Maps for Learning Indexable Classes by Berger, Böther, Doskoc, Gadea Harder, Klodt, Kötzing, Lötzsch, Peters, Schiller, Seifert, Wells, and Wietheger, the paper Reifying dynamical algebra: maximal ideals in countable rings, constructively by Blechschmidt and Schuster, the paper Lower Bounds on β(α) and other properties of α-register machines by Carl, the paper Ideal presentations and numberings of some classes of effective quasi-Polish spaces by de Brecht, Kihara, and Selivanov, the paper Defining long words succinctly in FO and MSO by Hella and Vilander, the paper Complemented subsets and Boolean-valued, partial functions by Misselbeck-Wessel and Petrakis, the paper Hilbert’s Tenth Problem for Term Algebras with a Substitution Operator by Murwanashyaka, and the paper On the Weihrauch degree of the additive Ramsey theorem by Pauly, Pradic, and Soldà. Robert S. Lubarsky was an invited speaker of the special session on Constructive and reverse mathematics (organized by Samuele Maschio and Takako Nemoto) and the paper On the Necessity of Some Topological Spaces by Banakh and Lubarsky is an extended version of Lubarsky’s invited talk, of which an extended abstract was published in the mentioned LNCS volume. Noam Greenberg gave a tutorial at CiE 2022, but the paper Algorithmically random series by Downey, Greenberg, and Tanggara in this special issue is separate from his presentation in Swansea. Damir Dzhaforov gave a plenary talk at CiE 2022 and has contributed the paper On the first-order parts of problems in the Weihrauch degrees by Dzhafarov, Solomon, and Yokoyama. Finally, the paper Computing the Index of Non-isometric k-ary Words with Hamming and Lee Distance by Anselmo, Flores, and Madonia corresponds to an informal presentation given at CiE 2022.

We would like to thank all our referees for their help in producing this special issue, including the members of the CiE 2022 Programme Committee.

For the most current information about the conference series CiE-CS, we refer the reader to our webpage https://www.acie.eu/cie-conference-series/.