We provide an explicit characterization of the properties of primitive recursive functions that are decidable or semi-decidable, given a primitive recursive index for the function. The result is much more general as it applies to any c.e. class of to
tal computable functions. This is an analog of Rice and Rice-Shapiro theorem, for restricted classes of total computable functions.
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.
We study the computational content of the Radon-Nokodym theorem from measure theory in the framework of the representation approach to computable analysis. We define computable measurable spaces and canonical representations of the measures and the i
ntegrable functions on such spaces. For functions f,g on represented sets, f is W-reducible to g if f can be computed by applying the function g at most once. Let RN be the Radon-Nikodym operator on the space under consideration and let EC be the non-computable operator mapping every enumeration of a set of natural numbers to its characteristic function. We prove that for every computable measurable space, RN is W-reducible to EC, and we construct a computable measurable space for which EC is W-reducible to RN.
Let mu be a computable ergodic shift-invariant measure over the Cantor space. Providing a constructive proof of Shannon-McMillan-Breiman theorem, Vyugin proved that if a sequence x is Martin-Lof random w.r.t. mu then the strong effective dimension Di
m(x) of x equals the entropy of mu. Whether its effective dimension dim(x) also equals the entropy was left as an problem question. In this paper we settle this problem, providing a positive answer. A key step in the proof consists in extending recent results on Birkhoffs ergodic theorem for Martin-Lof random sequences.
The paper considers quantitati
We survey an area of recent development, relating dynamics to theoretical computer science. We discuss the theoretical limits of simulation and computation of interesting quantities in dynamical systems. We will focus on central objects of the theory
of dynamics, as invariant measures and invariant sets, showing that even if they can be computed with arbitrary precision in many interesting cases, there exists some cases in which they can not. We also explain how it is possible to compute the speed of convergence of ergodic averages (when the system is known exactly) and how this entails the computation of arbitrarily good approximations of points of the space having typical statistical behaviour (a sort of constructive version of the pointwise ergodic theorem).
We extend the notion of randomness (in the version introduced by Schnorr) to computable Probability Spaces and compare it to a dynamical notion of randomness: typicality. Roughly, a point is typical for some dynamic, if it follows the statistical beh
avior of the system (Birkhoffs pointwise ergodic theorem). We prove that a point is Schnorr random if and only if it is typical for every 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.
In this paper we investigate algorithmic randomness on more general spaces than the Cantor space, namely computable metric spaces. To do this, we first develop a unified framework allowing computations with probability measures. We show that any comp
utable metric space with a computable probability measure is isomorphic to the Cantor space in a computable and measure-theoretic sense. We show that any computable metric space admits a universal uniform randomness test (without further assumption).
