Recent zbMATH articles in MSC 03Dhttps://www.zbmath.org/atom/cc/03D2021-03-30T15:24:00+00:00WerkzeugEnumeration 1-genericity in the local enumeration degrees.https://www.zbmath.org/1455.030542021-03-30T15:24:00+00:00"Badillo, Liliana"https://www.zbmath.org/authors/?q=ai:badillo.liliana"Harris, Charles M."https://www.zbmath.org/authors/?q=ai:harris.charles-m"Soskova, Mariya I."https://www.zbmath.org/authors/?q=ai:soskova.mariya-ivanovaSummary: We discuss a notion of forcing that characterizes enumeration 1-genericity, and we investigate the immunity, lowness, and quasiminimality properties of enumeration 1-generic sets and their degrees. We construct an enumeration operator \(\Delta\) such that, for any \(A\), the set \(\Delta^A\) is enumeration 1-generic and has the same jump complexity as \(A\). We deduce from this and other recent results from the literature that not only does every degree \(a\) bound an enumeration 1-generic degree \(b\) such that \(a'=b'\), but also that, if \(a\) is nonzero, then we can find such \(b\) satisfying \(0_e< b< a\). We conclude by proving the existence of both a nonzero low and a properly \(\Sigma_2^0\) nonsplittable enumeration 1-generic degree, hence proving that the class of 1-generic degrees is properly subsumed by the class of enumeration 1-generic degrees.Projection operators in the Weihrauch lattice.https://www.zbmath.org/1455.030572021-03-30T15:24:00+00:00"Gherardi, Guido"https://www.zbmath.org/authors/?q=ai:gherardi.guido"Marcone, Alberto"https://www.zbmath.org/authors/?q=ai:marcone.alberto"Pauly, Arno"https://www.zbmath.org/authors/?q=ai:pauly.arno-mSummary: In this paper we study, for \( n \geqslant 1\), the projection operators over \( \mathbb{R}^n \), that is the multi-valued functions that associate to \(x \in \mathbb{R}^n \) and \( A \subseteq \mathbb{R}^n\) closed, the points of \(A\) which are closest to \(x\). We also deal with approximate projections, where we content ourselves with points of \(A\) which are almost the closest to \(x\). We use the tools of Weihrauch reducibility to classify these operators dependingon the representation of \(A\) and the dimension \(n\). It turns out that, depending on the representation of the closed sets and the dimension of the space, the projection and approximate projection operators characterize some of the most fundamental computational classes in the Weihrauch lattice.Short proofs for slow consistency.https://www.zbmath.org/1455.030782021-03-30T15:24:00+00:00"Freund, Anton"https://www.zbmath.org/authors/?q=ai:freund.anton"Pakhomov, Fedor"https://www.zbmath.org/authors/?q=ai:pakhomov.fedor-nFor a consistent, polynomial-time axiomatized theory \(T\) containing some arithmetic, let \(\mathrm{Con}_x(T)\) be a natural formalization of the statement that there is no proof of contradiction in \(T\) containing at most \(x\) symbols. [\textit{P. Pudlák}, Stud. Logic Found. Math. 120, 165--196 (1986; Zbl 0619.03037)] showed that for any standard natural number \(n\), a theory \(T\) as above can prove \(\mathrm{Con}_n(T)\) by a proof of size polynomial in \(n\). In contrast, Pudlák [loc. cit.] has also conjectured that \(T\) will no longer have polynomial-size proofs of \(\mathrm{Con}_n(T + \mathrm{Con}(T))\). The conjecture has important implications for computational complexity, propositional proof complexity, and related fields.
In this paper, the authors consider the problem whether PA has small proofs of \(\mathrm{Con}_n(\mathrm{PA} + \mathrm{Con}^*(\mathrm{PA}))\), where \(\mathrm{Con}^*(\mathrm{PA})\) is the ``slow consistency'' principle of [\textit{S.-D. Friedman} et al., Ann. Pure Appl. Logic 164, No. 3, 382--393 (2013; Zbl 1263.03055)]: ``for every \(x\) such that \(F_{\epsilon_0}(x)\) exists, \(\mathrm{Con}(\mathrm{I}\Sigma_x)\) holds''. Here, \(F_{\epsilon_0}\) is the \(\epsilon_0\)-th function in the Hardy hierarchy of fast-growing functions. \(\mathrm{PA}\) does not prove that \(F_{\epsilon_0}\) is a total function, and indeed \(\mathrm{PA} + \mathrm{Con}^*(\mathrm{PA})\) is strictly intermediate in strength between \(\mathrm{PA}\) and \(\mathrm{PA} + \mathrm{Con}(\mathrm{PA})\).
The main theorem of the paper is that \(\mathrm{PA}\) can prove \(\mathrm{Con}_n(\mathrm{PA} + \mathrm{Con}^*(\mathrm{PA}))\) by proofs of size polynomial in \(n\). Moreover, the result still holds if \(\mathrm{Con}^*(\mathrm{PA})\) is strengthened to a ``slow uniform \(\Pi_2\) reflection'' principle, \(\mathrm{RFN}^*_{\Pi_2}(\mathrm{PA})\), which says ``for every \(x\) such that \(F_{\epsilon_0}(x)\) exists, no false \(\Pi_2\) statement can be derived from \(\mathrm{PA}\) by a proof containing at most \(x\) symbols''.
The proof of the main theorem has two major ingredients. The first of these is showing that already \(\mathrm{I}\Sigma_1\) proves ``for every \(x\), if \(F_{\epsilon_0}(x)\) exists, then \(\mathrm{Con}_x(\mathrm{PA} + \mathrm{Con}^*(\mathrm{PA}))\) holds''. This is achieved by interpreting \(\mathrm{RFN}^*_{\Pi_2}(\mathrm{PA})\) as a sentence expressing the totality of a function that grows considerably slower than \(F_{\epsilon_0}\), and then analyzing that sentence in terms of an infinitary proof system due to \textit{W. Buchholz} and \textit{S. Wainer} [Contemp. Math. 65, 179--198 (1987; Zbl 0635.03056)]. Proving the main theorem then comes down to showing that for standard \(n\), \(\mathrm{PA}\) is able to prove the existence of the value \(F_{\epsilon_0}(n)\) by proofs of size polynomial in \(n\). Such proofs are obtained using the transfinite induction available in \(\mathrm{PA}\). Their construction is more or less as expected but with some technical wrinkles.
Interestingly, the statement ``for every \(x\), if \(F_{\epsilon_0}(x)\) exists, then \(\mathrm{Con}_x(\mathrm{PA} + \mathrm{Con}(\mathrm{PA}))\) holds'' is unprovable even in \(\mathrm{PA}\). This may suggest that the main theorem of the paper says more about the weakness of \(\mathrm{Con}^*(\mathrm{PA})\) compared to \(\mathrm{Con}(\mathrm{PA})\) than about Pudlák's conjecture [loc. cit.] as such.
Reviewer: Leszek Aleksander Kołodziejczyk (Warszawa)Coding and definability in computable structures.https://www.zbmath.org/1455.030562021-03-30T15:24:00+00:00"Montalbán, Antonio"https://www.zbmath.org/authors/?q=ai:montalban.antonioSummary: These are the lecture notes from a 10-hour course that the author gave at the University of Notre Dame in September 2010. The objective of the course was to introduce some basic concepts in computable structure theory and develop the background needed to understand the author's research on back-and-forth relations.On a metric generalization of the \(tt\)-degrees and effective dimension theory.https://www.zbmath.org/1455.030552021-03-30T15:24:00+00:00"Kihara, Takayuki"https://www.zbmath.org/authors/?q=ai:kihara.takayukiIn classical computability, tt-reducibility can be characterised as follows: \(A \leq_\text{tt} B\) iff there exists a total computable functional \(\Phi\colon 2^\omega \to 2^\omega\) such that \(\Phi(A) = B\). \textit{T. H. McNicholl} and \textit{J. Rute} [``A uniform reducibility in computably presented Polish spaces'', talk held at AMS sectional meeting AMS special session on ``effective mathematics in discrete and continuous worlds'', October 28--30, 2016] generalised this to a metric setting. For computable metric spaces \(\mathcal{X}\) and \(\mathcal{Y}\) and points \(x \in \mathcal{X}\), \(y \in \mathcal{Y}\), \(x \leq_\text{tt} y\) if there is a total computable functional \(\Phi\colon \omega^\omega \to \omega^\omega\) mapping every Cauchy name of \(x\) to one of \(y\).
The author further explores the metric \(\leq_\text{tt}\) relation and the associated degree structure. A first-level Borel function \(f\colon \mathcal{X} \to \mathcal{Y}\) is one for which the preimage of any F\(_\sigma\) set is F\(_\sigma\); the author shows that \(\omega \times \mathcal{X}\) and \(\omega \times \mathcal{Y}\) are first-level Borel isomorphic iff they have the same tt-degree structures relative to a common oracle.
In \S3, metric tt-degrees are used to connect (effective) topological dimension to the Schnorr packing dimension \(\operatorname{dim}^\text{Sch}_P\) of \textit{R. Downey} et al. [Math. Struct. Comput. Sci. 16, No. 5, 789--811 (2006; Zbl 1125.03033)]. The main result is that every point in an \(n\)-dimensional computable compact metric space is tt-equivalent to some \(y\) with \(\operatorname{dim}^\text{Sch}_P(y) \leq n\).
Reviewer: Jordan Mitchell Barrett (Wellington)Simplicity via provability for universal prefix-free Turing machines.https://www.zbmath.org/1455.030502021-03-30T15:24:00+00:00"Calude, Cristian S."https://www.zbmath.org/authors/?q=ai:calude.cristian-sSummary: Universality is one of the most important ideas in computability theory. There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This criterion is more complex than it may appear at a first glance. In this note we review recent results in Algorithmic Information Theory and propose three new criteria of simplicity for universal prefix-free Turing machines. These criteria refer to the possibility of proving various natural properties of such a machine (its universality, for example) in a formal theory, PA or ZFC. In all cases some, but not all, machines are simple.
For the entire collection see [Zbl 1392.68029].Weak completeness notions for exponential time.https://www.zbmath.org/1455.680682021-03-30T15:24:00+00:00"Ambos-Spies, Klaus"https://www.zbmath.org/authors/?q=ai:ambos-spies.klaus"Bakibayev, Timur"https://www.zbmath.org/authors/?q=ai:bakibayev.timurIn the present paper, the authors investigate reduction notions that can be employed in the context of linear exponential time (E).
It is well known that the complexity class E is not closed under polynomial many-to-one reductions (Lemma 1) through a padding argument.
Because of that, \textit{J. H. Lutz} [SIAM J. Comput. 24, No. 6, 1170--1189 (1995; Zbl 0845.68048)] formalised in a way a type of measure for that class.
The authors introduce two weak hardness notions for E, namely, (strong) E-nontriviality.
Intuitively, a subclass of E is negligible if it is contained in some \(\mathrm{E}_k= \mathrm{DTIME}(2^{kn})\) in the exponential-time hierarchy.
Arguing that ``E-nontriviality is the most general weak hardness notion for E'', the authors stress that it ``generalised E-hardness and implies intractability but that it also reflects the internal, hierarchical structure of E hence considers finite parts of the linear exponential time hierarchy to be negligible.''
The strong variant of this concept lies strictly between the weak notion and the ones of measure- and category-hardnesses.
The authors give a verbose overview of the sections in the introduction and motivate quite well.
Section 2 then handles the new central notions and Lemma 3 is an important result showing how meaningful their approach is.
Theorem 1 characterises the strong variant via \(\mathrm{E}_1\)-bi-immune sets (a set \(A\) is \(C\)-bi-immune for a class \(C\) if there is no infinite \(B\in C\) such that \(B\subseteq A\) or \(B\cap A=\emptyset\)).
Section 3 provides then some examples.
First, the existence of an E-trivial set in \(\mathrm{E}\setminus \mathrm{P}\) (Theorem 2), but also E-trivial sets in arbitrarily high levels \(\mathrm{E}\setminus \mathrm{E}_k\) of the E-hierarchy (Theorem 4).
Section 4 considers sparse and tally sets in this context.
The authors show the existence of an E-category-complete set which is sparse and that no such set is tally (Theorem 8).
Yet, there are tally sets which are strongly E-nontrivial (Theorem 9).
The authors show the context when tally sets are E-nontrivial (Theorem 10) and when even an E-nontrivial set is exptally (Corollary 2) which is also not strongly E-nontrivial (Corollary 3).
Theorem 13 then gives the context for a set \(A\) to be E-hard, E-measure-hard, E-category-hard, strongly E-nontrivial, E-nontrivial, and intractable (in this order).
Section 5 talks about information content. Can one, from splitting ``a weakly complete set \(A\) into two parts \(A_0\) and \(A_1\)'', deduce weak completeness for either of them?
The authors show that this is true for E-nontriviality but for the remainder of the weak completeness notions this is false.
Reviewer: Arne Meier (Hannover)Weaker variants of infinite time Turing machines.https://www.zbmath.org/1455.030492021-03-30T15:24:00+00:00"Bianchetti, Matteo"https://www.zbmath.org/authors/?q=ai:bianchetti.matteoThe paper is devoted to infinite time Turing machines (for short: ITTM). ITTM are Turing machines that can halt and provide a result after infinitely many steps. They are far more powerful than ordinary Turing machines. They were introduced by \textit{J. D. Hamkins} and \textit{A. Lewis} [J. Symb. Log. 65, No. 2, 567--604 (2000; Zbl 0963.03064)], In the paper under review, models of infinitary computation whose computational power lies strictly between that of Turing machines and ITTMs are investigated. Four types of weak infinite time Turing machines are defined and some results about their computational power are proved. Special attention is paid to so called weak infinite time Turing machines (wITTM). They are defined by replacing in tye definitione of ITTM the lim sup rule with an `eventually constant' rule: at each limit step, the value of each cell isdefined if and only if the content of that cell has stabilized before that limit step and is then equal to this constant value. The author studies different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. It is shown that some of these models are equivalent to each other concerning their computational strength and that wITTMs decide exactly the arithmetic relations on natural numbers.
Reviewer: Roman Murawski (Poznań)New substitution bases for complexity classes.https://www.zbmath.org/1455.030512021-03-30T15:24:00+00:00"Mazzanti, Stefano"https://www.zbmath.org/authors/?q=ai:mazzanti.stefanoIn this paper, the author improves earlier work by showing that well-known function complexity classes can be characterised as the substitution closure of finite sets of simple functions \(\mathbf{AC}^0(F)\). Intuitively, this work is about finding fitting substitution bases, that is, finite sets of functions that define a function class (projection functions and substitution is allowed). For instance, if \(F=\{\text{mult}\}\) then \(\mathbf{AC}^0(F)=\mathbf{TC}^0\). Furthermore, the author present in the concluding section a discussion on how the introduced function algebras may lead to a new, algebraic proof that \(\mathbf{AC}^0\neq\mathbf{TC}^0\). At the end of the preliminaries, the author gives already a short outlook on the results he is going to prove which gives a nice context. Some results (e.g., Lemma 3.8, Lemma 3.12) in the main part are not proven (``straightforward''). Unfortunately, there is little intertext between the lemmas which could guide a reader a bit more.
Section 5 presents new bases for \(\mathbf{TC}^0\), and, in the next Section 6, one gets a nice characterisation of the complexity classes \(\mathbf{NC}^1, \mathbf{L}, \mathbf{P},\) and \(\mathbf{PSPACE}\) in terms of function sets \(F\) such that they respectively coincide with \(\mathbf{AC}^0(F)\).
Reviewer: Arne Meier (Hannover)On the jumps of the degrees below a recursively enumerable degree.https://www.zbmath.org/1455.030522021-03-30T15:24:00+00:00"Belanger, David R."https://www.zbmath.org/authors/?q=ai:belanger.david-r"Shore, Richard A."https://www.zbmath.org/authors/?q=ai:shore.richard-aSummary: We consider the set of jumps below a Turing degree, given by \(\mathrm{JB}(\mathbf{a})=\{\mathbf{x}':\mathbf{x}\leq\mathbf{a}\}\), with a focus on the problem: Which recursively enumerable (r.e.) degrees \(\mathbf{a}\) are uniquely determined by \(\mathrm{JB}(\mathbf{a})\)? Initially, this is motivated as a strategy to solve the rigidity problem for the partial order \(\mathcal{R}\) of r.e. degrees. Namely, we show that if every high\({}_{2}\) r.e. degree \(\mathbf{a}\) is determined by \(\mathsf{JB}(\mathbf{a})\), then \(\mathcal{R}\) cannot have a nontrivial automorphism. We then defeat the strategy -- at least in the form presented -- by constructing pairs \(\mathbf{a}_{0}\), \(\mathbf{a}_{1}\) of distinct r.e. degrees such that \(\mathrm{JB}(\mathbf{a}_{0})=\mathrm{JB}(\mathbf{a}_{1})\) within any possible jump class \(\{\mathbf{x}:\mathbf{x}'=\mathbf{c}\}\). We give some extensions of the construction and suggest ways to salvage the attack on rigidity.Classifications of computable structures.https://www.zbmath.org/1455.030442021-03-30T15:24:00+00:00"Lange, Karen"https://www.zbmath.org/authors/?q=ai:lange.karen"Miller, Russell"https://www.zbmath.org/authors/?q=ai:miller.russell-g"Steiner, Rebecca M."https://www.zbmath.org/authors/?q=ai:steiner.rebecca-mSummary: Let \(\mathcal{K}\) be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from \(\mathcal{K}\) such that every structure in \(\mathcal{K}\) is isomorphic to exactly one structure on the list. Such a list is called a computable classification of \(\mathcal{K}\), up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a \(\mathbf{0'}\)-oracle, we can obtain similar classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no computable classification of the latter, nor of the family of computable torsion-free abelian groups of rank \(1\), even though these families are both closely allied with computable algebraic fields.Computable numberings of families of infinite sets.https://www.zbmath.org/1455.030532021-03-30T15:24:00+00:00"Dorzhieva, M. V."https://www.zbmath.org/authors/?q=ai:dorzhieva.marina-valerianovnaA Friedberg numbering of a set is an effective enumeration of the set's members without repetition. In [Bull. Acad. Pol. Sci., Sér. Sci. Math. Astron. Phys. 6, 1--5 (1958; Zbl 0084.24902)] \textit{R. M. Friedberg} gave such an enumeration of the c.e. sets. This paper shows by diagonal argument that there is no such enumeration for the infinite c.e. sets. Extending these arguments to the analytical hierarchy, there is neither a \(\pi^1_1\)-computable numbering for all infinite \(\pi^1_1\) sets, nor a \(\varepsilon^1_2\)-computable numbering for all infinite \(\varepsilon^1_2\) sets.
Moreover, that for \(k>2\) there is no \(\varepsilon^1_k\)-computable numbering of the infinite \(\varepsilon^1_k\) sets is a consequence of Gödel's axiom of constructibility, whence existence of such an ordering is unprovable in ZF. Whether or not its nonexistence is provable in ZF is an open question.
Reviewer: Joseph S. Ullian (Santa Barbara)On testing the existence of universal denominators for partial differential and difference equations.https://www.zbmath.org/1455.350532021-03-30T15:24:00+00:00"Paramonov, S. V."https://www.zbmath.org/authors/?q=ai:paramonov.serge-vSummary: We consider the problem of testing the existence of a universal denominator for partial differential or difference equations with polynomial coefficients and prove its algorithmic undecidability. This problem is closely related to finding rational function solutions in that the construction of a universal denominator is a part of the algorithms for finding solutions of such form for ordinary differential and difference equations.Computational processes and incompleteness.https://www.zbmath.org/1455.681152021-03-30T15:24:00+00:00"Sutner, Klaus"https://www.zbmath.org/authors/?q=ai:sutner.klausSummary: We introduce a formal definition of Wolfram's notion of computational process based on cellular automata, a physics-like model of computation. There is a natural classification of these processes into decidable, intermediate and complete. It is shown that in the context of standard finite injury priority arguments one cannot establish the existence of an intermediate computational process.
For the entire collection see [Zbl 1392.68029].A first-order theory of Ulm type.https://www.zbmath.org/1455.030432021-03-30T15:24:00+00:00"Harrison-Trainor, Matthew"https://www.zbmath.org/authors/?q=ai:harrison-trainor.matthewAuthor's abstract: The class of abelian \(p\)-groups are an example of some very interesting phenomena in computable structure theory. We will give an elementary first-order theory \(T_p\) whose models are each bi-interpretable with the disjoint union of an abelian \(p\)-group and a pure set (and so that every abelian \(p\)-group is bi-interpretable with a model of \(T_p\)) using computable infinitary formulas. This answers a question of Knight by giving an example of an elementary first-order theory of ``Ulm type'': Any two models, low for \(\omega_1^{CK}\), and with the same computable infinitary theory, are isomorphic. It also gives a new example of an elementary first-order theory whose isomorphism problem is \(\mathbf{\Sigma}_1^1\)-complete but not Borel complete.
Reviewer: Andrei S. Morozov (Novosibirsk)A general notion of useful information.https://www.zbmath.org/1455.680752021-03-30T15:24:00+00:00"Moser, Philippe"https://www.zbmath.org/authors/?q=ai:moser.philippeSummary: In this paper we introduce a general framework for defining the depth of a sequence with respect to a class of observers. We show that our general framework captures all depth notions introduced in complexity theory so far. We review most such notions, show how they are particular cases of our general depth framework, and review some classical results about the different depth notions.
For the entire collection see [Zbl 1392.68029].Algorithmic information theory and its statistical mechanical interpretation.https://www.zbmath.org/1455.680762021-03-30T15:24:00+00:00"Tadaki, Kohtaro"https://www.zbmath.org/authors/?q=ai:tadaki.kohtaroThe paper reviews similarities between statistical mechanics and algorithmic information theory (AIT). It includes a presentation of some elements of AIT, formulations in AIT terms of the partition function, free energy, energy and statistical mechanical entropy. A discussion of the interpretation of temperature as partial randomness is given. No new results in either statistical mechanics or in AIT are proved.
Reviewer: Cristian S. Calude (Auckland)Busy beavers gone wild.https://www.zbmath.org/1455.030792021-03-30T15:24:00+00:00"Lafitte, Grégory"https://www.zbmath.org/authors/?q=ai:lafitte.gregorySummary: We show some incompleteness results à la Chaitin using the busy beaver functions. Then, with the help of ordinal logics, we show how to obtain a theory in which the values of the busy beaver functions can be provably established and use this to reveal a structure on the provability of the values of these functions.
For the entire collection see [Zbl 1392.68029].Some considerations on universality.https://www.zbmath.org/1455.680552021-03-30T15:24:00+00:00"Kudlek, Manfred"https://www.zbmath.org/authors/?q=ai:kudlek.manfredSummary: The paper puts into discussion the concept of universality, in particular for structures not of the power of Turing computability. The question arises if for such structures a universal structure of the same kind exists or not. For that the construction of universal Turing machines and those with some constraints are presented in some detail.
For the entire collection see [Zbl 1392.68029].Small Turing universal signal machines.https://www.zbmath.org/1455.680542021-03-30T15:24:00+00:00"Durand-Lose, Jérôme"https://www.zbmath.org/authors/?q=ai:durand-lose.jerome-oSummary: This article aims at providing signal machines as small as possible able to perform any computation (in the classical understanding). After presenting signal machines, it is shown how to get universal ones from Turing machines, cellular-automata and cyclic tag systems. Finally a halting universal signal machine with 13 meta-signals and 21 collision rules is presented.
For the entire collection see [Zbl 1392.68029].On the boundaries of solvability and unsolvability in tag systems. Theoretical and experimental results.https://www.zbmath.org/1455.030482021-03-30T15:24:00+00:00"De Mol, Liesbeth"https://www.zbmath.org/authors/?q=ai:de-mol.liesbethSummary: Several older and more recent results on the boundaries of solvability and unsolvability in tag systems are surveyed. Emphasis will be put on the significance of computer experiments in research on very small tag systems.
For the entire collection see [Zbl 1392.68029].Computability at zero temperature.https://www.zbmath.org/1455.370322021-03-30T15:24:00+00:00"Burr, Michael"https://www.zbmath.org/authors/?q=ai:burr.michael-a"Wolf, Christian"https://www.zbmath.org/authors/?q=ai:wolf.christianThe authors give some answers concerning the computability of basic thermodynamic invariants at zero temperature. They investigate the computability of the residual entropy on the space of continuous potentials for subshifts of finite type (SFTs).
Let \(f : X\rightarrow X\) be a subshift of finite type over an alphabet with \(d\) elements and let \(\mathcal{M}\) be the set of \(f\)-invariant Borel probability measures on \(X\) endowed with the weak* topology. Define \(\mathcal{M}_{\max}(\phi) = \{\mu\in \mathcal{M}: \mu(\phi) = b_{\phi}\}\), where \(\phi:X\rightarrow \mathbb{R}\) is a continuous function. The residual entropy of the potential \(\phi\) is defined by \(h_{\infty,\phi}= \sup\{h_{\mu}(f): \mu\in \mathcal{M}_{\max}(\phi)\}\), where \(h_{\mu}(f)\) is the measure entropy of \(f\) with respect to the measure \(\mu\). The authors prove that the function \(\phi\rightarrow h_{\infty,\phi}\) is upper semi-computable, but not computable on \(C(X,\mathbb{R})\). Moreover, the map \(\phi\rightarrow h_{\infty,\phi}\) is continuous at \(\phi_0\) if and only if \(h_{\infty,\phi_0} = 0\). Therefore, they prove that the residual entropy is semi-computable, but not computable. Then they study locally constant potentials for which the zero-temperature measure is known to exist. Let LC\((X,\mathbb{R}) =\bigcup_{k\in \mathbb{N}}\)LC\(_{k}(X,\mathbb{R})\) denote the space of locally constant potentials, where LC\(_{k}(X,\mathbb{R})\) denotes the space of potentials that are constant on cylinders of length \(k\). The authors prove that if \(f : X\rightarrow X\) is a transitive SFT with positive topological entropy, then the set \(\mathcal{O}\) has no interior points in LC\((X,\mathbb{R})\), where \(\mathcal{O}\) is the set of locally constant potentials that are uniquely maximizing.
Reviewer: Hasan Akin (Gaziantep)Deep reinforcement learning with temporal logics.https://www.zbmath.org/1455.681902021-03-30T15:24:00+00:00"Hasanbeig, Mohammadhosein"https://www.zbmath.org/authors/?q=ai:hasanbeig.mohammadhosein"Kroening, Daniel"https://www.zbmath.org/authors/?q=ai:kroning.daniel"Abate, Alessandro"https://www.zbmath.org/authors/?q=ai:abate.alessandroSummary: The combination of data-driven learning methods with formal reasoning has seen a surge of interest, as either area has the potential to bolstering the other. For instance, formal methods promise to expand the use of state-of-the-art learning approaches in the direction of certification and sample efficiency. In this work, we propose a deep Reinforcement Learning (RL) method for policy synthesis in continuous-state/action unknown environments, under requirements expressed in Linear Temporal Logic (LTL). We show that this combination lifts the applicability of deep RL to complex temporal and memory-dependent policy synthesis goals. We express an LTL specification as a Limit Deterministic Büchi Automaton (LDBA) and synchronise it on-the-fly with the agent/environment. The LDBA in practice monitors the environment, acting as a modular reward machine for the agent: accordingly, a modular Deep Deterministic Policy Gradient (DDPG) architecture is proposed to generate a low-level control policy that maximises the probability of the given LTL formula. We evaluate our framework in a cart-pole example and in a Mars rover experiment, where we achieve near-perfect success rates, while baselines based on standard RL are shown to fail in practice.
For the entire collection see [Zbl 1455.68021].On the uniform computational content of the Baire category theorem.https://www.zbmath.org/1455.030802021-03-30T15:24:00+00:00"Brattka, Vasco"https://www.zbmath.org/authors/?q=ai:brattka.vasco"Hendtlass, Matthew"https://www.zbmath.org/authors/?q=ai:hendtlass.matthew"Kreuzer, Alexander P."https://www.zbmath.org/authors/?q=ai:kreuzer.alexander-pSummary: We study the uniform computational content of different versions of the Baire category theorem in the Weihrauch lattice. The Baire category theorem can be seen as a pigeonhole principle that states that a complete (i.e., ``large'') metric space cannot be decomposed into countably many nowhere dense (i.e., small) pieces. The Baire category theorem is an illuminating example of a theorem that can be used to demonstrate that one classical theorem can have several different computational interpretations. For one, we distinguish two different logical versions of the theorem, where one can be seen as the contrapositive form of the other one. The first version aims to find an uncovered point in the space, given a sequence of nowhere dense closed sets. The second version aims to find the index of a closed set that is somewhere dense, given a sequence of closed sets that cover the space. Even though the two statements behind these versions are equivalent to each other in classical logic, they are not equivalent in intuitionistic logic, and likewise, they exhibit different computational behavior in the Weihrauch lattice. Besides this logical distinction, we also consider different ways in which the sequence of closed sets is ``given.'' Essentially, we can distinguish between positive and negative information on closed sets. We discuss all four resulting versions of the Baire category theorem. Somewhat surprisingly, it turns out that the difference in providing the input information can also be expressed with the jump operation. Finally, we also relate the Baire category theorem to notions of genericity and computably comeager sets.