We investigate completions of partial combinatory algebras (pcas), in particular of Kleene's second model $\mathcal{K}_2$ and generalizations thereof. We consider weak and strong notions of embeddability and completion that have been studied before in the literature. It is known that every countable pca can be weakly embedded into $\mathcal{K}_2$, and we generalize this to arbitrary cardinalities by considering generalizations of $\mathcal{K}_2$ for larger cardinals. This emphasizes the central role of $\mathcal{K}_2$ in the study of pcas. We also show that $\mathcal{K}_2$ and its generalizations have strong completions.

Abstract We discuss the complexity of completions of partial combinatory algebras, in particular, of Kleene’s first model. Various completions of this model exist in the literature, but all of them have high complexity. We show that although there are no computable completions, there exist completions of low Turing degree. We use this construction to relate completions of Kleene’s first model to complete extensions of $\mathrm{PA}$ . We also discuss the complexity of pcas defined from nonstandard models of $\mathrm{PA}$ .

\n Contains fulltext :\n 239187.pdf (Publisher’s version ) (Open Access)\n

Generalized numberings are an extension of Ershov's notion of numbering, based on partial combinatory algebra (pca) instead of the natural numbers. We study various algebraic properties of generalized numberings, relating properties of the numbering to properties of the pca. As in the lambda calculus, extensionality is a key notion here.

Abstract For every partial combinatory algebra (pca), we define a hierarchy of extensionality relations using ordinals. We investigate the closure ordinals of pca’s, i.e., the smallest ordinals where these relations become equal. We show that the closure ordinal of Kleene’s first model is ${\omega _1^{\textit {CK}}}$ and that the closure ordinal of Kleene’s second model is $\omega _1$ . We calculate the exact complexities of the extensionality relations in Kleene’s first model, showing that they exhaust the hyperarithmetical hierarchy. We also discuss embeddings of pca’s.

Abstract We consider two generalizations of the recursion theorem, namely Visser’s ADN theorem and Arslanov’s completeness criterion, and we prove a joint generalization of these theorems.

Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of the file involved, using a real-world compression program. This practical application is called `normalized compression distance' and it is trivially computable. It is a parameter-free similarity measure based on compression, and is used in pattern recognition, data mining, phylogeny, clustering, and classification. The complexity properties of its theoretical precursor, the NID, have been open. We show that the NID is neither upper semicomputable nor lower semicomputable up to any reasonable precision.

We study statistical sum-tests and independence tests, in particular for computably enumerable semimeasures on a discrete domain. Among other things, we prove that for universal semimeasures every $\Sigma ^{0}_{1}$ -sum-test is bounded, but unbounded $\Pi ^{0}_{1}$ -sum-tests exist, and we study to what extent the latter can be universal. For universal semimeasures, in the unary case of sum-test we leave open whether universal $\Pi ^{0}_{1}$ -sum-tests exist, whereas in the binary case of independence tests we prove that they do not exist.

Abstract We investigate the structure of the Medvedev lattice as a partial order. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size . the size of the lattice itself. We also prove that it is consistent with ZFC that the lattice has chains of size . and in fact that these big chains occur in every infinite interval. We also study embeddings of lattices and algebras. We show that large Boolean algebras can be embedded into the Medvedev lattice as upper semilattices, but that a Boolean algebra can be embedded as a lattice only if it is countable. Finally we discuss which of these results hold for the closely related Muchnik lattice.

Abstract We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅(n − 1). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ ∣x∣ − c. The ‘only if’ direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove some results on lowness. Among other things, we characterize the 2-random sets as those l-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω. sets coincide with the r.e. K-trivial ones. Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees.

We give a probabilistic interpretation of first-order formulas based on Valiants model of pac-learning. We study the resulting notion of probabilistic or approximate truth and take some first steps in developing its model theory. In particular we show that every fixed error parameter determining the precision of universal quantification gives rise to a different class of tautologies. Finally we study the inductive inference of first-order formulas from atomic truths.

Abstract We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0′. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.

We investigate the model recBC of learning of r.e.sets, where changes in hypotheses only count when there is an extensional difference.We study the learnability of collections that are uniformly r.e.We prove that, in contrast with the case of uniformly recursive collections, identifiability does not imply recursive BC-identifiability.This answers a question of D. de Jongh.In contrast to the model of recursive identifiability, we prove that the BCmodel separates the notions of finite thickness and finite elasticity.

Abstract A positive answer to a question of M. van Lambalgen and D. Zambella whether there exist nonrecursive sets that are low for the class of random sets is obtained. Here a set A is low for the class RAND of random sets if RAND = RANDA.