SCHEDULE FOR OBERWOLFACH SEMINAR IN COMPUTABILITY 2018: (abstracts can be found at the end) MONDAY: 08:00-09:00 BREAKFAST 09:00-09:15 Housekeeping/Information for Participants 09:15-10:00 Ludovic Patey: Pigeons do not jump high 10:30-10:50 Klaus Ambos-Spies: Uniformly multiply permitting c.e. sets and lattice embeddings into the c.e. degrees 11:00-11:20 Alberto Marcone: Computability and incomputability of projection functions in Euclidean space 12:30-13:30 LUNCH 14:30-16:00 COFFEE AND CAKE 16:00-16:20 Klaus Weihrauch: Computable planar curves intersect in a computable point 16:30-16:50 Arno Pauly: Almost-total degrees, graph-cototal degrees and a theorem by Sierpinski 18:30-19:30 DINNER TUESDAY: 08:00-09:00 BREAKFAST 09:15-10:00 Joe Miller: Characterizing the continuous degrees 10:30-10:50 Veronica Becher: Randomness as uniform distribution modulo one 11:00-11:20 Sergey Goncharov: Rogers semilattices of generalized computable numberings 12:30-13:30 LUNCH 14:30-16:00 COFFEE AND CAKE 16:00-16:20 Jack Lutz: Who asked us? How the theory of computing answers Questions that weren’t about computing 16:30-16:50 Uri Andrews: On building models of Solovay theories 18:30-19:30 DINNER 20:00-21:00 Open problem session WEDNESDAY: 08:00-09:00 BREAKFAST 09:15-10:00 Takayuki Kihara: Topologizing the degree theory 10:30-10:50 Keng Meng (Selwyn) Ng: A degree characterisation of strong jump traceability 11:00-11:20 Matthew Harrison-Trainor: When is a property expressed in infinitary logic also pseudo-elementary? 11:30-11:50 Noam Greenberg: Cardinal characteristics, highness classes, Weihrauch reducibility, and forcing 12:30-13:30 LUNCH FREE AFTERNOON 18:30-19:30 DINNER THURSDAY: 08:00-09:00 BREAKFAST 09:15-10:00 Russell Miller: Effective classification and measure for countable structures 10:30-10:50 Ted Slaman: Exponents of irrationality and transcendence and effective Hausdorff dimension 11:00-11:20 Mariya Soskova: Randomness relative to an enumeration oracle 12:30-13:30 LUNCH 14:30-16:00 COFFEE AND CAKE 16:00-16:20 Laurent Bienvenu: On low for speed sets 16:30-16:50 Reed Solomon: Partial results on the complexity of roots of polynomials over Hahn fields and Puiseux fields 18:30-19:30 DINNER 20:00-20:20 Elvira Mayordomo: A point-to-set principle for separable metric spaces 20:30-20:50 George Barmpalias: Algorithmic learning of probability distributions from random data in the limit 21:00-21:20 Steffen Lempp: Finite final segments of the d.c.e. degrees 21:30-21:50 Satyadev Nandakumar: Martingales and restricted ratio betting FRIDAY: 08:00-09:00 BREAKFAST 09:15-10:00 Linda Brown Westrick: Determined Borel codes in reverse math 10:30-10:50 Sasha Shlapentokh: All things diophantine: stability, definability and undecidability 11:00-11:20 Adam Day: Algorithmic randomness and amenable groups 11:30-11:50 Bakhadyr Khoussainov: On finitely presented expansions of semigroups, groups, and algebras 12:30-13:30 LUNCH 14:00-14:20 Damir Dzhafarov: Existence of fixed points for monotone operators 14:30-16:00 COFFEE AND CAKE 18:30-19:30 DINNER SATURDAY: 08:00-09:00 BREAKFAST ABSTRACTS: Ludovic Patey: Pigeons do not jump high Abstract: The infinite pigeonhole principle asserts that every set of integers admits an infinite subset in it or its complement. This seemingly trivial principle surprisingly admits highly non-trivial computability-theoretic features, when considering non-computable instances. In particular, one may wonder whether there is an instance of the pigeonhole principle whose solutions are all high. The answer to this question will be given during this talk, although the careful reader might find a subtle clue in the title. This is joint work with Benoit Monin. Klaus Ambos-Spies: Uniformly multiply permitting c.e. sets and lattice embeddings into the c.e. degrees Abstract: We introduce a new permitting property of c.e. sets called uniform multiple permitting. This notion is wtt-invariant and the c.e. wtt-degrees which do not contain any sets with this property form an ideal. The Turing degrees of the sets with the uniform multiple property are the c.e. not totally $\omega$-c.e. degrees. So this new property gives an alternative characterization of the permitting power of those degrees. We apply our permitting notion in order to obtain some new results on the c.e. not totally $\omega$-c.e. degrees. For instance we show that there are some finite lattices such that a c.e. degree bounds an embedding of such a lattice in the c.e. degrees if and only if the degree is not totally $\omega$-c.e. An example of such a lattice is the 7-element lattice $S_7$ which is meet-semidistributive but not join- semidistributive. (Joint work with Nadine Losert) Alberto Marcone: Computability and incomputability of projection functions in Euclidean space Abstract: Projecting a point over a non-empty closed subset of the Euclidean space is deeply grounded in our geometrical intuition of the spatial continuum and has many important applications in several areas of mathematics. We study the complexity of this projection operator (and of a natural approximate version of it) in the Weihrauch lattice. The answer does depend on the way the closed set is given and, in some cases, on the dimension of the Euclidean space. Klaus Weihrauch: Computable planar curves intersect in a computable point Abstract: Consider continuous mappings f,g (paths) from the closed unit interval to the closed unit square such that f(0) = (0, 0), f(1) = (1, 1), g(0) = (0, 1) and g(1) = (1, 0) . We prove that there is a computable point of intersection if the paths are computable. Arno Pauly: Almost-total degrees, graph-cototal degrees and a theorem by Sierpinski Abstract: I will showcase the close connection between substructures of the enumeration degrees and properties of second-countable topological spaces by an open question: Is every almost-total enumeration degree a graph-cototal enumeration degree? Translating this question into the language of topological spaces yields an extension of Sierpinski's theorem regarding non-existence of countable closed partitions of connected compact metric spaces. Joe Miller: Characterizing the continuous degrees Abstract: The continuous degrees measure the computability-theoretic content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are all very close to total: joining a continuous degree with a total degree that is not below it always results in a total degree. We call this curious property almost totality. We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of enumeration degrees (Cai, Ganchev, Lempp, Miller, Soskova), we see that the continuous degrees are also definable. Applying earlier work on the continuous degrees, this shows that the relation “PA above” on the total degrees is definable in the enumeration degrees. In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly. Like them, we identify our almost total degree as the degree of a point in a computably regular space with a computable dense sequence, and then we apply the effective version of Urysohn's metrization theorem (Schroeder) to reveal our space as a computable metric space. This is joint work with Uri Andrews, Greg Igusa, and Mariya Soskova. Veronica Becher: Randomness as uniform distribution modulo one Abstract: How is the notion of randomness of algorithmic information theory related to the notion of uniform distribution? In this talk we study Martin-Löf randomness for real numbers in terms of uniform distribution of sequences. We present a necessary condition for a real number to be Martin-Löf random, and a strengthening of that condition which is sufficient for Martin-Löf randomness. For this strengthening, we define a notion of uniform distribution relative to the computably enumerable open subsets of the unit interval. We call the notion Sigma^0_1-uniform distribution. This is joint work with Serge Grigorieff. Sergey Goncharov: Rogers semilattices of generalized computable numberings Abstract: A comprehensive and extensive study of generalized computable numberings was initiated at the end of the past century, through a unifying approach towards a notion of a computable numbering for a family of sets of constructive objects, suggested in the paper of S. Goncharov and A. Sorbi [1]. A program of such a study was outlined in the authors' paper [2]. The study of the Ershov hierarchy was started by S. Goncharov and S. Lempp [3] and for the analytical hierarchy by Owings [4]. One of the interesting questions in the analytical hierarchy is connected with computable Friedberg numberings. Owings [4] proved that the family of all Sigma^1_1-sets has no Sigma^1_1-computable Friedberg numbering but M. Dorzhieva (in print) proved the Owings result without metarecursion and proved that the family of all Sigma^1_2-sets has no Sigma^1_2$-computable Friedberg numbering. Nevertheless, the questions for n>2 are open. The question for the Rogers semilatticas R^0_n of the arithmetical Sigma^0_n-computable sets and Sigma^0_n-computable numberings was solved in [5] and [6], but it is open whether R^0_n and R^0_{n+1} are isomorphic if n>2. There are interesting questions about computable numberings relative to classes of Ershov Hierarchy. Together with A. Sorbi and S. Badaev, the following result was proved: Theorem: There exist an infinite family S of Sigma^{-1}_n-sets (for n>2) with Rogers semilattices R^{-1}_n(S) of all Sigma^{-1}_n-numberings of the family S with exactly two different elements alpha and beta such that the Sigma^{-1}_n-computable numbering alpha is a Friedberg numbering and for any Sigma^{-1}_n-computable numbering gamma of this family, if alpha is not equivalent to gamma then beta <= gamma. Open question about finite families with these properties remain. Bibliography: [1] S. S. Goncharov, A. Sorbi. Generalized computable numberings and nontrivial Rogers semilattices. Algebra and Logic, 1997, vol. 36, no. 6, pp. 359–369. [2] S. A. Badaev, S. S. Goncharov. Theory of numberings: Open problems. In: Computability Theory and its Applications, P. Cholak, S. Lempp, M. Lerman and R. Shore eds., Contemporary Mathematics, American Mathematical Society, 2000, vol. 257, pp. 23-38, Providence, RI. [3] S. S. Goncharov, S. Lempp, D. R. Solomon. Friedberg numberings of families of n-computably enumerable sets. Algebra and Logic, 2002, vol. 41, no. 2, pp. 81–86. [4] James C. Owings, Jr. The meta-r.e. sets, but not the Pi^1_1-sets, can be enumerated without repetition, The Journal of Symbolic Logic, Volume 35, Number 2, June 1970. [5] S. A. Badaev, S. S. Goncharov, A. Sorbi. Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy. Algebra and Logic, 2006, vol. 45, no. 6. pp. 361–370. [6] S. Yu. Podzorov, Numbered distributive semilattices, Siberian Adv. Math. 17 (2007), no. 3, 171-185. Jack Lutz: Who asked us? How the theory of computing answers questions that weren’t about computing Abstract: It is rare for the theory of computing to be used to answer open mathematical questions whose statements do not involve computation or related aspects of logic. This talk discusses recent developments that do exactly this. After a brief review of algorithmic information and dimension, we describe the point-to-set principle (with N. Lutz) and its application to two new results in geometric measure theory. These are (1) N. Lutz and D. Stull's strengthened lower bounds on the Hausdorff dimensions of generalized Furstenberg sets, and (2) N. Lutz's extension of the fractal intersection formulas for Hausdorff and packing dimensions in Euclidean spaces from Borel sets to arbitrary sets. Uri Andrews: On building models of Solovay theories Abstract: If M is a recursive structure, then the E_n-fragment of the theory of M is uniformly Sigma^0_n. In general, we call a theory with this property a Solovay theory. Knight (with some shared credit to Solovay) gave a characterization of precisely the degrees that compute some model of every Solovay theory. It is the same as the degrees that compute a nonstandard model of true arithmetic. One can ask how hard it is to compute every model of a Solovay theory. Of course, no degree does this for every Solovay theory, as some Solovay theories have continuum many models (true arithmetic for example). When we restrict to a nice class C of theories which do not have continuum many countable models, this question becomes meaningful and important again. I think of this as asking what understanding we need to have of a theory in C, beyond the obvious, to know how to build its models. I'll discuss results giving the answer for the class of countably categorical theories (due to Knight '94 improving a result of Lerman and Schmerl '79) and recent results about the class of strongly minimal theories. Takayuki Kihara: Topologizing the degree theory Abstract: I will survey my recent works with collaborators on the topological generalization of the degree theory. My first motivation for topologizing the Turing degree theory came from my attempt to solve the generalized Jayne-Rogers conjecture, one of the most attractive open problems in descriptive set theory. After a few years of work, the topologized Turing degree theory has turned out to have many other applications. This theory has clarified the relationship between the Turing degree theory and infinite dimensional topology (joint with Arno Pauly). This theory has enabled us to utilize nonmetrizable topology to explore the structure of the enumeration degrees (joint with Steffen Lempp, Keng Meng Ng, and Arno Pauly). In the latter part of this talk, I will focus on a generalization of the truth-table degrees in computable metric spaces, which is recently introduced by McNicholl-Rute. We apply the Jayne-Rogers theorem to characterize the notion of the generalized tt-degree in the context of the first-level Borel isomorphism. This characterization is the guidepost which indicates the right way to go. First-level Borel isomorphisms have appeared in several literatures in topological dimension theory. Thus the theory of effective topological dimension naturally emerges. For instance, by the topological method called "condensation of singularities," we show that, for any positive integer n, every weakly 1-generic Turing degree contains a tt-degree which is (n+1)-dimensional, but not n-dimensional. Keng Meng (Selwyn) Ng: A degree characterisation of strong jump Traceability Abstract: We discuss recent work which explores the unexpected relationship between strong jump traceability and ideals originating in the study of c.e. degrees. Given a downwards closed class L, the ideal Pres(L) is the class of all Delta2 degrees a such that a+b is in L for every b in L. We investigate this for certain lowness classes L. Matthew Harrison-Trainor: When is a property expressed in infinitary logic also pseudo-elementary? Abstract: Some non-elementary properties, such as reachability in a graph, are expressible both in infinitary logic and in a pseudo- elementary (or co-pseudo-elementary) way. On the other hand, some properties, such as well-foundedness, are expressible in only one of these ways. We will give an explanation of what kinds of infinitary sentences can be expressed in a pseudo-elementary way. This is joint work in progress with Barbara Csima and Nancy Day. Noam Greenberg: Cardinal characteristics, highness classes, Weihrauch reducibility, and forcing Abstract: Vojtas showed that many cardinal characteristics of the continuum, including all those appearing in the Cichon diagram, arise from binary relations considered as problems, with the cardinal being the smallest size of a set which includes solutions for all instances. ZFC- provable cardinal inequalities arise from morphisms between these binary relations. In his thesis, Rupprecht introduced highness classes in computability which correspond to these cardinals by considering the very same binary relations (see also Brendle, Brooke-Taylor, Nies and Ng). He showed that computable morphisms prove implications between these highness classes. The morphisms are (not necessarily uniform) strong Weihrauch reductions. Some implications in both set theory and computability require not only morphisms but manipulations of problems, operations which have been studies in both the Weihrauch lattice and in set theory. We discuss this correspondence, how it relates to several results in algorithmic randomness, and how to calibrate computational strength by working over ideals. Russell Miller: Effective classification and measure for countable structures Abstract: Model theorists and descriptive set theorists have considered the class of all atomic diagrams of structures with domain omega belonging to a given class $C$ of structures, and have used it in attempts to classify the countable models of C up to isomorphism. We continue these efforts from the perspective of computable structure theory. For classes C for which the isomorphism problem is not too difficult, it is sometimes possible to give an effective classification of the countable structures in C, up to isomorphism. More commonly, it becomes possible to do so once one adds certain well-chosen definable predicates to the language, thus taking a (partial) Morleyization. We will give several specific examples of this process, including the class of algebraic fields of characteristic 0, the class of finite- branching infinite trees, the class of archimedean real closed fields, and the class of torsion-free abelian groups of rank n. In some cases, classification can be accomplished by a computable homeomorphism onto Cantor space or Baire space. In these cases, it then becomes possible to put a measure on the class, which can be used to define randomness notions and also to consider the prevalence of properties such as relative computable categoricity. In other cases, effective classification can be done if one allows an equivalence elation on Cantor space or Baire space as part of the description. Portions of this work are joint with Johanna Franklin and with Fokina, S. Friedman, Rossegger, and San Mauro. Ted Slaman: Exponents of irrationality and transcendence and effective Hausdorff dimension Abstract: We will discuss the similarities between measuring the describability of a real number in terms of Diophantine Approximation or by measuring it in terms of Kolmogorov Complexity. This is joint work with Veronica Becher and Jan Reimann. Mariya Soskova: Randomness relative to an enumeration oracle Abstract: We initiate the study of algorithmic randomness relative to an enumeration oracle. The enumeration degrees can be viewed as an extension of the Turing degrees: the substructure of the total enumeration degrees is an isomorphic copy of the Turing degrees within the wider context of the enumeration degrees. In this sense, the notion of randomness for total enumeration oracles can be inferred from the corresponding notion for Turing oracles. There are two distinct approaches to extending this notion to non-total enumeration degrees. The first one is to define randomness relative to a non-total enumeration oracle in terms of the total enumeration oracles that are comparable with it. On the other hand, most of the notions in algorithmic randomness, and all of those most closely related to Martin-L\" of randomness, can be expressed in terms of c.e. sets. So when we relativize these notions to an oracle X, we are usually interested in the X-c.e. sets. The second approach to generalizing from Turing degrees to enumeration degrees is straightforward: to relativize a randomness notion to the enumeration degree of a set A we simply replace X-c.e. with c.e. in every enumeration of A (i.e., enumeration reducible to A). The resulting definitions are easily seen to be unchanged for the total degrees, demonstrating that this notion of randomness does lead to an extension of the original one. We show that there are oracles for which this notion does not coincide with the notions obtained via our first approach. Thus moving to the context of the enumeration degrees gives rise to a notion of relative randomness that does not reduce to one expressible in the Turing world by relativizing to sets of oracles. For non-total degrees, we find that some familiar theorems are preserved, perhaps with more subtle proofs, while other theorems may fail. For example, there need not be a universal Martin-Loef test relative to the enumeration degree of A, and there are continuum many enumeration degrees that are low for randomness. This is joint work with Joe Miller. Laurent Bienvenu: On low for speed sets Abstract: Relativizing computations of Turing machines to an oracle is a central concept in the theory of computation, both in complexity theory and in computability theory(!). Inspired by lowness notions from computability theory, Allender introduced the concept of “low for speed” oracles. An oracle A is low for speed if relativizing to A has essentially no effect on computational complexity, meaning that if a decidable language can be decided in time f(n$ with access to oracle A, then it can be decided in time poly(f(n)) without any oracle. The existence of non-computable such A's was later proven by Bayer and Slaman, who even constructed a computably enumerable one, and exhibited a number of properties of these oracles as well as interesting connections with computability theory. We pursue this line of research, answering the questions left by Bayer and Slaman and give further evidence that the structure of the class of low for speed oracles is a very rich one. This is joint work with Rod Downey. Reed Solomon: Partial results on the complexity of roots of polynomials over Hahn fields and Puiseux fields Abstract: Let K be an algebraically closed field of characteristic zero and G be a divisible ordered abelian group. The associated Hahn field and the field of Puiseux series are both algebraically closed. We will give preliminary partial results on the complexity of finding roots in these fields. This work is joint with Julia Knight and Karen Lange. Elvira Mayordomo: A point-to-set principle for separable metric spaces J. Lutz and N. Lutz (2017) have recently proven a point-to-set principle for Euclidean and Cantor spaces. This result is a characterization of classical Hausdorff dimension in terms of relativized effective dimension. This implies that geometric measure results regarding Hausdorff dimension can be shown using solely effective methods. Several interesting classical results have already been proven using this principle (please refer to Jack Lutz's presentation on Tuesday for details on these). In this talk a point-to-set principle for any separable metric space will be presented. We will first present an effectivization of dimension in terms of Kolmogorov complexity that is valid for any separable space, and then show that the classical Hausdorff dimension of any set is the minimum on all oracles of the relativized effective dimension. We expect that better Hausdorff dimension bounds will be proven as consequences of this theorem. George Barmpalias: Algorithmic learning of probability distributions from random data in the limit Abstract: We study the problem of identifying a probability distribution for some given randomly sampled data in the limit, in the context of algorithmic learning theory as proposed recently by Vinanyi and Chater. We show that there exists a computable partial learner for the computable probability measures, while by Bienvenu, Monin and Shen, it is known that there is no computable learner for the computable probability measures. Our main result is the characterization of the oracles that compute explanatory learners for the computable (continuous) probability measures as the high oracles. This provides an analogue of a well-known result of Adleman and Blum in the context of learning computable probability distributions. We also discuss related learning notions such as behaviorally correct learning and other variations of explanatory learning, in the context of learning probability distributions from data. This is joint work with Frank Stephan. Steffen Lempp: Finite final segments of the d.c.e. degrees Abstract: Ever since the existence of a maximal incomplete d.c.e. degree was established, the question of exactly which finite final segments exist in the d.c.e. degrees has been an interesting open question. In this talk, I will report on progress toward establishing that all finite distributive lattices are final segments; some partial results exist, challenges lie ahead, and there is a larger class, the so-called finite interval dismantlable lattices, which may be realized using the same techniques. This is joint work with Yiqun Liu, Yong Liu, Selwyn Ng, Cheng Peng, Guohua Wu and Yue Yang, all from Singapore. Satyadev Nandakumar: Martingales and restricted ratio betting Abstract: Let A and B be two finite sets of computable real numbers which denote the allowable wagers that martingales can make. Following the terminology in Chalcraft et. al., an A-martingale is a martingale whose wagers are limited to elements in A, and a B-martingale has wagers limited to elements in B. In Chalcraft et al., the authors establish necessary and sufficient conditions for some A-martingale to succeed betting on sequences that B-martingales can succeed betting on. In this paper, we investigate the analogous question of comparative betting power of martingales when the ratios of bets are restricted to a finite set which excludes 1. This contrasts with the setting of simple martingales and almost simple martingales as investigated by Ambos- Spies and Mayordomo. Without loss of generality, we will restrict the ratios to rational numbers, and the general case of finite sets of computable real ratios is similar. We derive necessary and sufficient conditions for deciding when a set of ratios allows greater power in betting as compared to another. (Joint work with Sumedh Masulkar and Keng Men Ng.) Linda Brown Westrick: Determined Borel codes in reverse math Abstract: The standard definition of a Borel code in reverse math doesn't require the model to believe that each real is either in the coded set or in its complement. In fact, the statement "for every Borel coded set, either it or its complement is non-empty" already implies ATR. We define a determined Borel code to be a Borel code with the property that every real is contained either in the coded set or in its complement. While the statement "every Borel set has the property of Baire" is equivalent to ATR due to the above-mentioned technicality, the statement "every determined Borel set has the property of Baire" is not. We discuss the location of this statement relative to ATR, theories of hyperarithmetic analysis, and the existence of hyperarithmetic generics. This is joint work with Astor, Dzhafarov, Montalbán and Solomon. Sasha Shlapentokh: All things diophantine: stability, definability and Undecidability We discuss the cur rent state of affairs with respect to using elliptic curves (and abelian varieties in general) to show first-order and Diophantine definability of Z over subrings of algebraic extensions of Q, Proving that the first-order or existential theory of these rings is undecidable. Adam Day: Algorithmic randomness and amenable groups Abstract: The main space studied in algorithmic randomness is the space of all infinite binary strings. It is possible to transfer the study of algorithmic randomness to the set of functions from G to {0,1} where G is a countable group. In the case that G is amenable, different notions of complexity such as entropy and effective dimension can be translated to the new space as well. We give an effective version of the Shannon- McMillian-Breiman theorem in this setting. We also extend a result of Simpson equating topological entropy and Hausdorff dimension. This proof makes use of work of an interesting lemma of Ornstein and Weiss which we also outline. Bakhadyr Khoussainov: On finitely presented expansions of semigroups, groups, and algebras Abstract: Finitely presented structures, such as groups and semigroups, are of foundational interest in algebra and computation. Finitely presented structures necessarily have c.e. word equality and these systems are finitely generated. Not all c.e. and finitely generated structures are finitely presented. This work is concerned with finding finitely presented expansions of finitely generated structures. Expansions of structures, such as turning groups into rings or distinguishing subsets in the underlying structures, is an important method used in algebra, model theory, and various areas of computer science. Bergstra and Tucker [1] [2] proved that all c.e. algebraic systems with decidable word problem have finitely presented expansions. Then they [1] [2] and, independently, Goncharov [3] asked if every finitely generated c.e. algebraic system has a finitely presented expansion. We build examples of finitely generated c.e. semigroups, algebras (rings that are vectors spaces over fields), and groups that fail to possess finitely presented expansions. We also construct examples of a residually finite and immune group, answering the question of Miasnikov and Osin from [4]. Our proofs are based on the interplay between key constructions, concepts, and results from computability theory (simple set constructions), universal algebra (residually finite structures), and classical algebra (Golod- Shafaverevich theorem [7]). The work is joint with D. Hirschfeldt, and independently with A. Miyasnikov. [1] J.A. Bergstra, J.V.Tucker. Initial and Final Algebra Semantics for Data Type Specifications: Two characterization Theorems, SIAM J. Comput. 12, 1983. [2] J.A.Bergstra, J.V.Tucker, Algebraic Specifications of Computable and Semicomputable DataTypes, Theoretical Comp. science, 50, 1987. [3] Logic Notebook (Open questions in Logic), Novosibirsk University Press, editors Yu.Ershov and S. Goncharov, 1989. [4] A. Miasnikov, D. Osin. Algorithmically finite groups. Journal of Pure and Applied Algebra, Volume 215, Issue 11, November 2011, pp. 2789-2796. [5] B. Khoussainov, D. Hirschfeldt. On finitely presented expansions of semigroups. Algebra and Logic, 51, 435-445, 2012. [6] B. Khoussainov, A. Miasanikov. Finitely presented expansions of semigroups, groups, and algebras, TAMS, 2015. [7] E.S. Golod, I.R. Shafarevich. On the class field tower, Izv. Akad. Nauk SSSR 28: 261-272 (in Russian), 1964. Damir Dzhafarov: Existence of fixed points for monotone operators Abstract: I will discuss work in progress with Sean Walsh concerning the logical strength of the existence of fixed points for monotone operators. It is easy to see that repeatedly applying such an operator to the empty set must result in a fixed point, and in fact, this will be the least fixed point under inclusion. The strength of the existence of least fixed points was analyzed already by Cenzer and Remmel, but the situation for arbitrary fixed points, as opposed to least, is quite different from theirs. For example, Cenzer and Remmel showed that the existence of least fixed points for computable monotone operators is equivalent to ACA_0, while we show that the existence of general fixed points is equivalent to WKL_0. I will mention partial results concerning the existence of fixed points for various other classes of operators. Part of our motivation is understanding the strength of constructions of formal theories of truth in the style of Kripke; we present a proof of Kripke’s fixed point theorem in Pi^1_1-CA_0.