Abstract A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of compact Polish spaces. We show that there exists a bold 0 prime $\mathbf {0}'$ 0 ' -computable low Subscript 3 $_3$ 3 compact Polish space which is not homeomorphic to a computable one, and that, for any natural number n greater than or equals 2 $n\geq 2$ n ≥ 2 , there exists a Polish space upper X Subscript n $X_n$ X n such that exactly the high Subscript n $_{n}$ n -degrees are required to present the homeomorphism type of upper X Subscript n $X_n$ X n . Along the way we investigate the computable aspects of Čech homology groups. We also show that no compact Polish space has a least presentation with respect to Turing reducibility.

Abstract The Wadge hierarchy was originally defined and studied only in the Baire space (and some other zero-dimensional spaces). Here we extend the Wadge hierarchy of Borel sets to arbitrary topological spaces by providing a set-theoretic definition of all its levels. We show that our extension behaves well in second countable spaces and especially in quasi-Polish spaces. In particular, all levels are preserved by continuous open surjections between second countable spaces which implies e.g., several Hausdorff–Kuratowski (HK)-type theorems in quasi-Polish spaces. In fact, many results hold not only for the Wadge hierarchy of sets but also for its extension to Borel functions from a space to a countable better quasiorder Q.

We discuss possibilities of application of Numerical Analysis methods to proving computability, in the sense of the TTE approach, of solution operators of boundary-value problems for systems of PDEs. We prove computability of the solution operator for a symmetric hyperbolic system with computable real coefficients and dissipative boundary conditions, and of the Cauchy problem for the same system (we also prove computable dependence on the coefficients) in a cube $Q\subseteq\mathbb R^m$. Such systems describe a wide variety of physical processes (e.g. elasticity, acoustics, Maxwell equations). Moreover, many boundary-value problems for the wave equation also can be reduced to this case, thus we partially answer a question raised in Weihrauch and Zhong (2002). Compared with most of other existing methods of proving computability for PDEs, this method does not require existence of explicit solution formulas and is thus applicable to a broader class of (systems of) equations. Comment: 31 pages

The paper tries to extend some results of the classical Descriptive Set Theory to as many countably basedT0-spaces (cb0-spaces) as possible. Along with extending some central facts about Borel, Luzin and Hausdorff hierarchies of sets we also consider the more general case ofk-partitions. In particular, we investigate the difference hierarchy ofk-partitions and the fine hierarchy closely related to the Wadge hierarchy.

This special issue of Mathematical Structures in Computer Science is composed mainly of papers submitted by participants of the Dagstuhl Seminar on Computing with Infinite Data: Topological and Logical Foundations. The workshop took place in the Schloss Dagstuhl - Leibniz Center for Informatics in the first half of October 2011.

The structure of the Wadge degrees on zero-dimensional spaces is very simple (almost well ordered), but for many other natural nonzero-dimensional spaces (including the space of reals) this structure is much more complicated. We consider weaker notions of reducibility, including the so-called Δ0α-reductions, and try to find for various natural topological spaces X the least ordinal αX such that for every αX ⩽ β < ω1 the degree-structure induced on X by the Δ0β-reductions is simple (i.e. similar to the Wadge hierarchy on the Baire space). We show that αX ⩽ ω for every quasi-Polish space X, that αX ⩽ 3 for quasi-Polish spaces of dimension ≠ ∞, and that this last bound is in fact optimal for many (quasi-)Polish spaces, including the real line and its powers.

We define and study hierarchies of topological spaces induced by the classical Borel and Luzin hierarchies of sets. Our hierarchies are divided into two classes: hierarchies of countably based spaces induced by their embeddings into Pω, and hierarchies of spaces (not necessarily countably based) induced by their admissible representations. We concentrate on the non-collapse property of the hierarchies and on the relationships between hierarchies in the two classes.

We show that many of the so called discrete weak semilattices considered earlier in a series of author's publications have hereditary undecidable first-order theories. Since such structures appear naturally in some parts of computation theory, we obtain several new undecidability results. This applies e.g. to the structures of complete numberings, of m-degrees of index sets and of the Wadge degrees of k-partitions in the Baire space and ω-algebraic domains. Whenever possible, we try to determine also the exact degrees of undecidability of the theories under discussion.

The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results: - The classes of the Boolean hierarchy over level $Sigma_1$ of the dot-depth hierarchy are decidable in $NL$ (previously only the decidability was known). The same remains true if predicates mod $d$ for fixed $d$ are allowed. - If modular predicates for arbitrary $d$ are allowed, then the classes of the Boolean hierarchy over level $Sigma_1$ are decidable. - For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level $Sigma_2$ of the Straubing-Th{'\e}rien hierarchy are decidable in $NL$. This is the first decidability result for this hierarchy. - The membership problems for all mentioned Boolean-hierarchy classes are logspace many-one hard for $NL$. - The membership problems for quasi-aperiodic languages and for $d$-quasi-aperiodic languages are logspace many-one complete for $PSPACE$.

We prove that the homomorphic quasiorder of finite k-labelled forests has a hereditary undecidable first-order theory for k ≥ 3, in contrast to the known decidability result for k = 2. We establish also hereditary undecidability (again for every k ≥ 3) of first-order theories of two other relevant structures: the homomorphic quasiorder of finite k-labelled trees, and of finite k-labelled trees with a fixed label of the root element. Finally, all three first-order theories are shown to be computably isomorphic to the first-order arithmetic.

Abstract We consider fine hierarchies in recursion theory, descriptive set theory, logic and complexity theory. The main results state that the sets of values of different Boolean terms coincide with the levels of suitable fine hierarchies. This gives new short descriptions of these hierarchies and shows that collections of sets of values of Boolean terms are almost well ordered by inclusion. For the sake of completeness we mention also some earlier results demonstrating the usefulness of fine hierarchies.