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 Computable analysis provides ways of representing points in a topological space, and therefore of defining a notion of computable points of the space. In this article, we investigate when two topologies on the same space induce different sets of computable points. We first study a purely topological version of the problem, which is to understand when two topologies are not $\sigma $ -homeomorphic. We obtain a characterization leading to an effective version, and we prove that two topologies satisfying this condition induce different sets of computable points. Along the way, we propose an effective version of the Baire category theorem which captures the construction technique, and enables one to build points satisfying properties that are co-meager with respect to a topology, and are computable with respect to another topology. Finally, we generalize the result to three topologies and give an application to prove that certain sets do not have computable type, which means that they have a homeomorphic copy that is semicomputable but not computable.

This article is a study of descriptive complexity of subsets of represented spaces. Two competing measures of descriptive complexity are available. The first one is topological and measures how complex it is to obtain a set from open sets using boolean operations. The second one measures how complex it is to test membership in the set, and we call it symbolic complexity because it measures the complexity of the symbolic representation of the set. While topological and symbolic complexity are equivalent on countably-based spaces, they differ on more general spaces. Our investigation is aimed at explaining this difference and highly suggests that it is related to the well-known mismatch between topological and sequential aspects of topological spaces.

Represented spaces are the spaces on which computations can be performed. We investigate the descriptive complexity of sets in represented spaces. We prove that the standard representation of a countably-based space preserves the effective descriptive complexity of sets. We prove that some results from descriptive set theory on Polish spaces extend to arbitrary countably-based spaces. We study the larger class of coPolish spaces, showing that their representation does not always preserve the complexity of sets, and we relate this mismatch with the sequential aspects of the space. We study in particular the space of polynomials.

Many variations of synchronization of finite automata have been studied in the previous decades. Here, we suggest studying the question if synchronizing words exist that belong to some fixed constraint language, given by some partial finite automaton called constraint automaton. We show that this synchronization problem becomes PSPACE-complete even for some constraint automata with two states and a ternary alphabet. In addition, we characterize constraint automata with arbitrarily many states for which the constrained synchronization problem is polynomial-time solvable. We classify the complexity of the constrained synchronization problem for constraint automata with two states and two or three letters completely and lift those results to larger classes of finite automata.

Computability and semicomputability of compact subsets of the Euclidean spaces are important notions, that have been investigated for many classes of sets including fractals (Julia sets, Mandelbrot set) and objects with geometrical or topological constraints (embedding of a sphere). In this paper we investigate one of the simplest classes, namely the filled triangles in the plane. We study the properties of the parameters of semicomputable triangles, such as the coordinates of their vertices. This problem is surprisingly rich. We introduce and develop a notion of semicomputability of points of the plane which is a generalization in dimension 2 of the left-c.e. and right-c.e. numbers. We relate this notion to Solovay reducibility. We show that semicomputable triangles admit no finite parametrization, for some notion of parametrization.

We investigate interrelationships among different notions from mathematical analysis, effective topology, and classical computability theory. Our main object of study is the class of computable functions defined over an interval with the boundary being a left-c.e. real number. We investigate necessary and sufficient conditions under which such functions can be computably extended. It turns out that this depends on the behavior of the function near the boundary as well as on the class of left-c.e. real numbers to which the boundary belongs, that is, how it can be constructed. Of particular interest a class of functions is investigated: sawtooth functions constructed from computable enumerations of c.e. sets.

What can be decided or semidecided about a primitive recursive function, given a definition of that function by primitive recursion? What about subrecursive classes other than primitive recursive functions? We provide a complete and explicit characterization of the decidable and semidecidable properties. This characterization uses a variant of Kolmogorov complexity where only programs in a subrecursive programming language are allowed. More precisely, we prove that all the decidable and semidecidable properties can be obtained as combinations of two classes of basic decidable properties: (i) the function takes some particular values on a finite set of inputs, and (ii) every finite part of the function can be compressed to some extent.

In computability theory and computable analysis, finite programs can compute infinite objects. Presenting a computable object via any program for it, provides at least as much information as presenting the object itself, written on an infinite tape. What additional information do programs provide? We characterize this additional information to be any upper bound on the Kolmogorov complexity of the object. Hence we identify the exact relationship between Markov-computability and Type-2-computability. We then use this relationship to obtain several results characterizing the computational and topological structure of Markov-semidecidable sets.

The strong relationship between topology and computations has played a central role in the development of several branches of theoretical computer science: foundations of functional programming, computational geometry, computability theory, computable analysis. Often it happens that a given function is not computable simply because it is not continuous. In many cases, the function can moreover be proved to be non-computable in the stronger sense that it does not preserve computability: it maps a computable input to a non-computable output. To date, there is no connection between topology and this kind of non-computability, apart from Pour-El and Richards "First Main Theorem", applicable to linear operators on Banach spaces only. In the present paper, we establish such a connection. We identify the discontinuity notion, for the inverse of a computable function, that implies non-preservation of computability. Our result is applicable to a wide range of functions, it unifies many existing ad hoc constructions explaining at the same time what makes these constructions possible in particular contexts, sheds light on the relationship between topology and computability and most importantly allows us to solve open problems. In particular it enables us to answer the following open question in the negative: if the sum of two shift-invariant ergodic measures is computable, must these measures be computable as well? We also investigate how generic a point with computable image can be. To this end we introduce a notion of genericity of a point w.r.t. a function, which enables us to unify several finite injury constructions from computability theory.

Recently Kawamura and Cook developed a framework to define the computational complexity of operators arising in analysis. Our goal is to understand the effects of complexity restrictions on the analytical properties of the operator. We focus on the case of norms over C[0,1] and introduce the notion of dependence of a norm on a point and relate it to the query complexity of the norm. We show that the dependence of almost every point is of the order of the query complexity of the norm. A norm with small complexity depends on a few points but, as compensation, highly depends on them. We characterize the functionals that are computable using one oracle call only and discuss the uniformity of that characterization.

Let m be a computable ergodic shift-invariant measure over the set of infinite binary sequences. Providing a constructive proof of Shannon-McMillan-Breiman theorem, V'yugin proved that if x is a Martin-Löf random binary sequence w.r.t. m then its strong effective dimension Dim(x) equals the entropy of m. Whether its effective dimension dim(x) also equals the entropy was left as an open problem. In this paper we settle this problem, providing a positive answer. A key step in the proof consists in extending recent results on Birkhoff's ergodic theorem for Martin-Löf random sequences. At the same time, we present extensions of some previous results. As pointed out by a referee the main result can also be derived from results by Hochman [Upcrossing inequalities for stationary sequences and applications. The Annals of Probability, 37(6):2135--2149, 2009], using rather different considerations.

A pseudorandom point in an ergodic dynamical system over a computable metric space is a point which is computable but its dynamics has the same statistical behavior as a typical point of the system. It was proved in [Avigad et al. 2010, Local stability of ergodic averages] that in a system whose dynamics is computable the ergodic averages of computable observables converge effectively. We give an alternative, simpler proof of this result. This implies that if also the invariant measure is computable then the pseudorandom points are a set which is dense (hence nonempty) on the support of the invariant measure.

We extend the notion of randomness (in the version introduced by Schnorr) to computable Probability Spaces and compare it to a \emph{dynamical} notion of randomness: typicality. Roughly, a point is \emph{typical} for some dynamic, if it follows the statistical behavior of the system (Birkhoff's pointwise ergodic theorem). We prove that a point is Schnorr random if and only if it is typical for every \emph{mixing} computable dynamics. To prove the result we develop some tools for the theory of computable probability spaces (for example, morphisms) that are expected to have other applications.

Computers are used extensively to simulate continuous dynamical systems. However, different conceptual and mathematical structures underlie discrete machines and continuous dynamics, so the question arises as to the ability of the computer to simulate or, more generally, to check the properties of a continuous system. We discuss and compare two notions of stability for a continuous dynamical system,viz.shadowing and robustness, and relate them to both the practical and theoretical computability of the system. We first discuss what we can learn from the stability of a system, using a finite-precision machine. We then show, following the work in Collins (2005), that shadowing fails but robustness succeeds in ensuring the checkability of a reachability property.