Topological aspects of numberings

We investigate connections between the syntactic and semantic distance of programs on an abstract, recursion theoretic level. For a certain rather restrictive notion of interdependency of the two kinds of distances, there remain only few and “unnatural” numberings allowing such close relationship. Weakening the requirements leads to the discovery of universal metrics such that for an arbitrary recursively enumerable family of functions a numbering compatible with such a metric can uniformly be constructed. We conclude our considerations with some implications on learning theory.     

Strong reducibility of partial numberings

A strong reducibility relation between partial numberings is introduced which is such that the reduction function transfers exactly the numbers which are indices under the numbering to be reduced into corresponding indices of the other numbering. The degrees of partial numberings of a given set with respect to this relation form an upper semilattice.In addition, Ershovs completion construction for total numberings is extended to the partial case: every partially numbered set can be embedded in a set which results from the given set by adding one point and which is enumerated by a total and complete numbering. As is shown, the degrees of complete numberings of the extended set also form an upper semilattice. Moreover, both semilattices are isomorphic.This is not so in the case of the usual, weaker reducibility relation for partial numberings which allows the reduction function to transfer arbitrary numbers into indices.This research has partially been supported by INTAS under grant 00-499 Computability in Hierarchies and Topological Spaces.Mathematics Subject Classification (2000): 03D45     

A note on partial numberings

The different behaviour of total and partial numberings with respect to the reducibility preorder is investigated. Partial numberings appear quite naturally in computability studies for topological spaces. The degrees of partial numberings form a distributive lattice which in the case of an infinite numbered set is neither complete nor contains a least element. Friedberg numberings are no longer minimal in this situation. Indeed, there is an infinite descending chain of non‐equivalent Friedberg numberings below every given numbering, as well as an uncountable antichain. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Distributive lattices of numberings

We study into a semilattice of numberings generated by a given fixed numbering via operations of completion and taking least upper bounds. It is proved that, except for the trivial cases, this semilattice is an infinite distributive lattice every principal ideal in which is finite. The least upper and the greatest lower bounds in the semilattice are invariant under extensions in the semilattice of all numberings. Isomorphism types for the semilattices in question are in one-to-one correspondence with pairs of cardinals the first component of which is equal to the cardinality of a set of non-special elements, and the second — to the cardinality of a set of special elements, of the initial numbering. Supported by INTAS grant No. 00-429. __________ Translated from Algebra i Logika, Vol. 46, No. 1, pp. 83–102, January–February, 2007.     

On a semilattice of numberings

We study some properties of a $ \mathfrak{c} $ \mathfrak{c} -universal semilattice $ \mathfrak{A} $ \mathfrak{A} with the cardinality of the continuum, i.e., of an upper semilattice of m-degrees. In particular, it is shown that the quotient semilattice of such a semilattice modulo any countable ideal will be also $ \mathfrak{c} $ \mathfrak{c} -universal. In addition, there exists an isomorphism $ \mathfrak{A} $ \mathfrak{A} such that $ {\mathfrak{A} \mathord{\left/ {\vphantom {\mathfrak{A} {\iota \left( \mathfrak{A} \right)}}} \right. \kern-\nulldelimiterspace} {\iota \left( \mathfrak{A} \right)}} $ {\mathfrak{A} \mathord{\left/ {\vphantom {\mathfrak{A} {\iota \left( \mathfrak{A} \right)}}} \right. \kern-\nulldelimiterspace} {\iota \left( \mathfrak{A} \right)}} will be also $ \mathfrak{c} $ \mathfrak{c} -universal. Furthermore, a property of the group of its automorphisms is obtained. To study properties of this semilattice, the technique and methods of admissible sets are used. More exactly, it is shown that the semilattice of mΣ-degrees $ L_{m\Sigma }^{\mathbb{H}\mathbb{F}\left( S \right)} $ L_{m\Sigma }^{\mathbb{H}\mathbb{F}\left( S \right)} on the hereditarily finite superstructure $ \mathbb{H}\mathbb{F} $ \mathbb{H}\mathbb{F} (S) over a countable set S will be a $ \mathfrak{c} $ \mathfrak{c} -universal semilattice with the cardinality of the continuum.     

Reductions between types of numberings

This paper considers reductions between types of numberings; these reductions preserve the Rogers Semilattice of the numberings reduced and also preserve the number of minimal and positive degrees in their semilattice. It is shown how to use these reductions to simplify some constructions of specific semilattices. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the k-r.e. numberings to the $(k+1)$-r.e. numberings; all further reductions are obtained by concatenating these reductions.     

Fixed point theorems for precomplete numberings

In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in this context.     

Some remarks on completion of numberings

We present some examples and constructions in the theory of complete numberings and completions of numberings that partially answer a few questions of [1].     

Some applications of computable one-one numberings

We present a simple proof of a Theorem of Khutoretskij on the number of incomparable one-one numberings of an r.e. family of r.e. sets. The proof directly generalizes to effective domains. In the second part, applying a Theorem of Goncharov, we show that for anyk there exist total recursive functions having exactlyk recursive isomorphism classes. Using a Theorem of Selivanov, it is shown that a certain notion of computability via gödelization is different from Lacombe's notion ofV-recursiveness. Finally, we discuss the complexity (w.r.t.T-degrees) of translating a Gödelnumbering into a direct sum of Friedbergnumberings.     

A semilattice of numberings. II

\mathfrakc \mathfrak{c} -Universal semilattices \mathfrakA \mathfrak{A} of the power of the continuum (of an upper semilattice of m-degrees ) on admissible sets are studied. Moreover, it is shown that a semilattice of \mathbbH\mathbbF( \mathfrakM ) \mathbb{H}\mathbb{F}\left( \mathfrak{M} \right) -numberings of a finite set is \mathfrakc \mathfrak{c} -universal if \mathfrakM \mathfrak{M} is a countable model of a c-simple theory.     

Positive undecidable numberings in the Ershov hierarchy

A sufficient condition is given under which an infinite computable family of Σ^-1 _a -sets has computable positive but undecidable numberings, where a is a notation for a nonzero computable ordinal. This extends a theorem proved for finite levels of the Ershov hierarchy in [1]. As a consequence, it is stated that the family of all Σ^-1 _a -sets has a computable positive undecidable numbering. In addition, for every ordinal notation a > 1, an infinite family of Σ^-1 _a -sets is constructed which possesses a computable positive numbering but has no computable Friedberg numberings. This answers the question of whether such families exist at any—finite or infinite—level of the Ershov hierarchy, which was originally raised by Badaev and Goncharov only for the finite levels bigger than 1.     

Completely unimodal numberings of a simple polytope

A completely unimodal numbering of the m vertices of a simple d-dimensional polytope is a numbering 0, 1, …,m−1 of the vertices such that on every k-dimensional face (2≤k≤d) there is exactly one local minimum (a vertex with no lower-numbered neighbors on that face). Such numberings are abstract objective functions in the sense of Adler and Saigal [1]. It is shown that a completely unimodal numbering of the vertices of a simple polytope induces a shelling of the facets of the dual simplicial polytope. The h-vector of the dual simplicial polytope is interpreted in terms of the numbering (with respect to using a local-improvement algorithm to locate the vertex numbered 0). In the case that the polytope is combinatorially equivalent to a d-dimensional cube, a ‘successor-tuple’ for each vertex is defined which carries the crucial information of the numbering for local-improvement algorithms. Combinatorial properties of these d-tuples are studied. Finally the running time of one particular local-improvement algorithm, the Random Algorithm, is studied for completely unimodal numberings of the d-cube. It is shown that for a certain class of numberings (which includes the example of Klee and Minty [8] showing that the simplex algorithm is not polynomial and all Hamiltonian saddle-free injective pseudo-Boolean functions [6]) this algorithm has expected running time that is at worst quadratic in the dimension d.     

Subfamilies of special elements of complete numberings

Any subfamily of a given at most countable non-empty family can be converted into a set of all special elements of a suitable numbering. __________ Translated from Algebra i Logika, Vol. 45, No. 6, pp. 758–764, November–December, 2006.     

On centain decompositions of Gödel numberings

Summary We define certain decompositions of the functions that describe Gödel numberings of the partial recursive functions (Section 2). These decompositions reflect the way in which concrete Gödel numberings may be obtained from the known computability formalisms. We show that such decompositions exist for all partial recursive functions (Section 3). It turns out that there is an intimate connection between these decompositions and Blum's step counting functions which yields a suggestive interpretation of Blum's notion (Section 4). In terms of these decompositions we, finally, give an exact formulation for a basic problem in the theory of computability formalisms, which, on an intuitive level, would read as follows: Find conditions on the expressive power of one step in a given computability formalism such that all partial recursive functions can be represented within that formalism. We derive two theorems which may be regarded as a first step in a thorough study of this problem.     

Directeds-t numberings,Rubber bands,and testing digraphk-vertex connectivity

LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k–1)-dimensional spaceR ^k–1,fVR ^k–1, such that no hyperplane containsk points of {f(v)|vV}, and for eachvV–X, f(v) is in the convex hull of {f(w)| (v, w)E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in Rubber bands, convex embeddings and graph connectivity,Combinatorica 8 (1988), 91–102.Using this characterization, a directed graph can be tested fork-vertex connectivity by a Monte Carlo algorithm in timeO((M(n)+nM(k)) · (logn)) with error probability<1/n, and by a Las Vegas algorithm in expected timeO((M(n)+nM(k)) ·k), whereM(n) denotes the number of arithmetic steps for multiplying twon×n matrices (M(n)=O(n ^2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities fork>n ^0.19; e.g., for , the factor of improvement is >n ^0.62. Both algorithms have processor efficient parallel versions that run inO((logn)²) time on the EREW PRAM model of computation, using a number of processors equal to logn times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at leastn ²/(logn)³ while having the same running time.Generalizing the notion ofs-t numberings, we give a combinatorial construction of a directeds-t numbering for any 2-vertex connected directed graph.