Search

This paper shows some of the differences and similarities between computation and hypercomputation, the similarities relating to the complexity of propositional computation and the differences being the propositions that can be decided computationally or hypercomputationally. The methods used are ordinal Turing machines with infinitely long programs and diagonalization out of computing complexity classes. The main results are the characterization of inequalities of run time complexities of serial, indeterministic serial and parallel computers and hypercomputers and the specification of a hierarchy of hypercomputers that can hypercompute the truths of all propositions in the standard class model of set theory, the von Neumann hierarchy of pure sets. [ABSTRACT FROM AUTHOR]

We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore–Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on the Martin Conjecture on the degree preserving Borel functions between Polish spaces. Additionally we prove results about the transfinite version as well as the computable version of the Decomposability Conjecture. [ABSTRACT FROM AUTHOR]

Highlights • We present an algorithm that transforms context-free grammars into a single set of supercombinators. • We evaluate our algorithm with the use of 62,008 grammar samples obtained from Groningen Meaning Bank. • We have found the limit of supercombinator set, which in case of our sample set is a sequence of Catalan numbers. • We show the way how to identify the most common structures of input grammars. Abstract We present an algorithm that transforms context-free grammars into a non-redundant set of supercombinators. This set contains interconnected lambda calculus' supercombinators that are enriched by grammar operations. The resulting set is scalable and it can be extended with new supercombinators created from grammars. We describe this algorithm in detail and then we apply it on 62,008 grammar samples in order to find out the properties and limits of acquired supercombinator set. We show that this set has a maximum theoretical limit of possible supercombinators. That limit is the sequence of Catalan numbers. We show that in some cases we are able to reach that limit if we use large enough input data source and we limit the size of supercombinators permitted into the final set. We also describe another benefit of our algorithm, which is the identification of most reoccurring structures in the input set. [ABSTRACT FROM AUTHOR]

We show that the only polynomial sets with a generating function of the form F ( x t − R ( t ) ) and satisfying a three-term recursion relation are the monomial set and the rescaled ultraspherical, Hermite, and Chebyshev polynomials of the first kind. [ABSTRACT FROM AUTHOR]

We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct constructions using martingales. At the same time, we introduce the concept of i.o. subuniformity and relate this concept to recursive measure theory. We prove that there are classes closed downwards under Turing reducibility that have recursive measure zero and that are not i.o. subuniform. This shows that there are examples of classes that cannot be covered with methods other than probabilistic ones. It is easily seen that every set of hyperimmune degree can cover the recursive sets. We prove that there are both examples of hyperimmune-free degree that can and that cannot compute such a cover. [ABSTRACT FROM AUTHOR]

In this article, three types of joins are introduced for subspaces of a vector space. Decompositions of the Graßmannian into joins are discussed. This framework admits a generalization of large set recursion methods for block designs to subspace designs. We construct a 2- ( 6 , 3 , 78 ) 5 design by computer, which corresponds to a halving LS 5 [ 2 ] ( 2 , 3 , 6 ) . The application of the new recursion method to this halving and an already known LS 3 [ 2 ] ( 2 , 3 , 6 ) yields two infinite two-parameter series of halvings LS 3 [ 2 ] ( 2 , k , v ) and LS 5 [ 2 ] ( 2 , k , v ) with integers v ≥ 6 , v ≡ 2 ( mod 4 ) and 3 ≤ k ≤ v − 3 , k ≡ 3 ( mod 4 ) . Thus in particular, two new infinite series of nontrivial subspace designs with t = 2 are constructed. Furthermore as a corollary, we get the existence of infinitely many nontrivial large sets of subspace designs with t = 2 . [ABSTRACT FROM AUTHOR]

Hjorth and Nies proposed notions of randomness corresponding to the higher recursion setting. In particular, they defined the notion of Π 1 1 -Martin-Löf randomness. In this article we present examples of Π 1 1 -Martin-Löf random reals which are obtained as measures of Π 1 1 open sets. [ABSTRACT FROM AUTHOR]

The foundation scheme in set theory asserts that every nonempty class has an $$\in $$ -minimal element. In this paper, we investigate the logical strength of the foundation principle in basic set theory and $$\alpha $$ -recursion theory. We take KP set theory without foundation (called KP $$^-$$ ) as the base theory. We show that KP $$^-$$ + $$\Pi _1$$ -Foundation + $$V=L$$ is enough to carry out finite injury arguments in $$\alpha $$ -recursion theory, proving both the Friedberg-Muchnik theorem and the Sacks splitting theorem in this theory. In addition, we compare the strengths of some fragments of KP. [ABSTRACT FROM AUTHOR]

We introduce the concept of a generic relation for algorithmic problems, which preserves the property of being decidable for a problem for almost all inputs and possesses the transitive property. As distinct from the classical m-reducibility relation, the generic relation under consideration does not possess the reflexive property: we construct an example of a recursively enumerable set that is generically incomparable with itself. We also give an example of a set that is complete with respect to the generic relation in the class of recursively enumerable sets. [ABSTRACT FROM AUTHOR]

A recurring theme in nested recursions research has been the search for recursion families. By a recursion family we mean a collection of recursions with a common or at least highly similar structure, and where, with appropriate (but usually different) initial conditions for each recursion, their respective solutions behave similarly in key respects. Our key result is a general method for generating a family of recursions with slow solutions from any nested recursion of the form either R(n) = R(n-s1 -R(n-a1))+R(n-s2 -R(n-a2)) (a two-term generalized Conolly recursion) or R(n) = R(n-s1 -R(n-a1))+R(-t1 +R(n-b1)) (a generalized Conway recursion) so long as the recursion with which we start, together with its initial conditions, has a known slow solution. We apply this method to discover new families of recursions with slow solutions based on the well-known Hofstadter V and Conway recursions, respectively. [ABSTRACT FROM AUTHOR]

We investigate the reverse mathematics strength of Martin's pointed tree theorem (MPT) and one of its variants, weak Martin's pointed tree theorem (wMPT). [ABSTRACT FROM AUTHOR]

Jockusch and Lewis (J Symb Logic 78:977-988, ) proved that every DNC function computes a bi-immune set. They asked whether every DNC function computes an effectively bi-immune set. We construct a DNC function that computes no effectively bi-immune set, thereby answering their question in the negative. [ABSTRACT FROM AUTHOR]

We elaborate a recursion-theoretic method to define real numbers which are random to any jump of the halting problem. This is obtained by generalizing a result of V. Becher and G. Chaitin dealing with the class of cofinite sets. As in the work of V. Becher and S. Grigorieff (but this time in the context of open sets in Cantor space) appeal to completeness phenomena replaces machine arguments. [ABSTRACT FROM AUTHOR]

Using dimension-like invariant base dimension I of a space by a normal base, the inductive dimensions of the product of compacta in Filippov's example are computed. [ABSTRACT FROM AUTHOR]

Abstract: The main topic of the present work is the relation that a set X is strongly hyperimmune-free relative to Y. Here X is strongly hyperimmune-free relative to Y if and only if for every partial X-recursive function p there is a partial Y-recursive function q such that every a in the domain of p is also in the domain of q and satisfies , that is, p is majorised by q. For X being hyperimmune-free relative to Y, one also says that X is pmaj-reducible to Y . It is shown that between degrees not above the Halting problem the pmaj-reducibility coincides with the Turing reducibility and that therefore only recursive sets have a strongly hyperimmune-free Turing degree while those sets Turing above the Halting problem bound uncountably many sets with respect to the pmaj-relation. So pmaj-reduction is identical with Turing reduction on a class of sets of measure 1. Moreover, every pmaj-degree coincides with the corresponding Turing degree. The pmaj-degree of the Halting problem is definable with the pmaj-relation. [Copyright &y& Elsevier]

This paper gives the additivity and reduction formulas for mixed multiplicities of multi-graded modules M and mixed multiplicities of arbitrary ideals, and establishes the recursion formulas for the sum of all the mixed multiplicities of M. As an application of these formulas we get the recursion formulas for the multiplicity of multi-graded Rees modules. [ABSTRACT FROM AUTHOR]

Abstract: We study the strength of , Rainbow Ramsey Theorem for colorings of triples, and prove that implies neither nor . To this end, we establish some recursion theoretic properties of cohesive sets and rainbows for colorings of pairs. We show that every sequence (2-bounded coloring of pairs) admits a cohesive set (infinite rainbow) of non-PA Turing degree; and that every -recursive sequence (2-bounded coloring of pairs) admits a cohesive set (infinite rainbow). [Copyright &y& Elsevier]

The solutions to certain nested recursions, such as Conolly’s C( n) =  C( n− C( n−1)) +  C( n−1− C( n−2)), with initial conditions C(1) = 1, C(2) = 2, have a well-established combinatorial interpretation in terms of counting leaves in an infinite binary tree. This tree-based interpretation, and its generalization to a similar k-term nested recursion, only apply to homogeneous recursions and only solve each recursion for one set of initial conditions determined by the tree. In this paper, we extend the tree-based interpretation to solve a non-homogeneous version of the k-term recursion that includes a constant term. To do so we introduce a tree-grafting methodology that inserts copies of a finite tree into the infinite k-ary tree associated with the solution of the corresponding homogeneous k-term recursion. This technique also solves the given non-homogeneous recursion with various sets of initial conditions. [ABSTRACT FROM AUTHOR]

Abstract: Franek et al. recently described four constructions for large sets of -intersecting Steiner triple systems of order (STS ) [F. Franek, M.J. Grannell, T.S. Griggs, A. Rosa, On the large sets of -intersecting Steiner triple systems of order , Des. Codes Cryptogr. 26 (2002) 243–256]. In this study we focus on large sets of -intersecting STS . Some recursive constructions are presented that involve three-wise balanced designs. By applying these constructions we obtain some new infinite classes of such large sets, and the large sets of -intersecting KTS are used to produce some new large sets of Kirkman triple systems. [Copyright &y& Elsevier]

Abstract: Based on four sets of Lenard recursion sequences and zero-curvature equation, we derive the full positive flows of the Manakov hierarchy associated with a matrix spectral problem, from which some new nonlinear evolution equations are proposed. With the help of the Darboux transformation, soliton solutions of two new nonlinear evolution equations in the Manakov hierarchy are constructed. As two special reductions, the full positive flows of the coupled modified Korteweg–de Vries hierarchy and the Sasa–Satsuma hierarchy are deduced, in which some new nonlinear evolution equations are included. And then, we construct the Hamiltonian structures of the Manakov hierarchy and infinite conservation laws of several nonlinear evolution equations. [Copyright &y& Elsevier]

We consider clopen game formulae , analogous to the open game formulae widely studied in admissible recursion theory. This leads to characterizing the locally countable Σ 1 1 -reflecting ordinals α as those for which, over L α , the clopen-game–definable relations are not precisely those which are both open-game and closed-game definable. [ABSTRACT FROM AUTHOR]

Abstract: This article introduces the notions of prolongations and prolongational limit sets of control systems. It is shown how the prolongational limit sets play in studying recursive and dispersive concepts of control systems. [Copyright &y& Elsevier]

Abstract: An () over a -set is a collection of pairwise disjoint resolvable (almost resolvable) Mendelsohn triple systems of order . In this paper several direct construction methods for OLRMTSs and OLARMTSs are presented and then applied to produce some new orders; the smallest unknown for , the smallest unknown for , and some other small designs are displayed; a few new existence families are also obtained by known recursive constructions. [Copyright &y& Elsevier]

Abstract: We use discrete Morse theory to determine the Möbius function of generalized factor order. Ordinary factor order on the Kleene closure of a set is the partial order defined by letting if contains as a subsequence of consecutive letters. Generalized factor order takes into account a partial order on the alphabet , that is, whenever contains a subsequence such that for each , in . Using Babson and Hersh’s application of Robin Forman’s discrete Morse theory to poset order complexes, we are able to give a recursive formula for the Möbius function in the case where each element of covers a unique letter in . [Copyright &y& Elsevier]

Abstract: Mathematics shares with language an essential reliance on the human capacity for recursion, permitting the generation of an infinite range of embedded expressions from a finite set of symbols. We studied the role of syntax in arithmetic thinking, a neglected component of numerical cognition, by examining eye movement sequences during the calculation of arithmetic expressions. Specifically, we investigated whether, similar to language, an expression has to be scanned sequentially while the nested syntactic structure is being computed or, alternatively, whether this structure can be extracted quickly and in parallel. Our data provide evidence for the latter: fixations sequences were stereotypically organized in clusters that reflected a fast identification of syntactic embeddings. A syntactically relevant pattern of eye movement was observed even when syntax was defined by implicit procedural rules (precedence of multiplication over addition) rather than explicit parentheses. While the total number of fixations was determined by syntax, the duration of each fixation varied with the complexity of the arithmetic operation at each step. These findings provide strong evidence for a syntactic organization for arithmetic thinking, paving the way for further comparative analysis of differences and coincidences in the instantiation of recursion in language and mathematics. [Copyright &y& Elsevier]

A classical theme in recursion theory is the question whether for a set A and n given elements x1,...,xn, an oracle machine having access to an oracle B can determine which of the elements xi belong to A. And if yes, how many queries are necessary? Here, B = A is possible and leads to interesting special cases of the general question In the present paper we adapt classical notions in this area of bounded query computations to real number algorithms as formalized by Blum, Shub, and Smale and analyze them in the new framework. Among the results obtained we find: A real version of a non-speedup theorem based on real quantifier elimination, some basic properties about selective real sets, and a way to construct natural terse sets in ℝ by applying the implicit function theorem. The purpose of the paper is on presenting some interesting questions and basic results as an appertizer to intensify research into this direction. [ABSTRACT FROM AUTHOR]

Function classes closed with respect to substitution and concatenation recursion on notation are characterized as the substitution closure of finite function sets. Consequently, the sets of TC0, NC1 and L computable functions are characterized as the substitution closure of a finite function set. [ABSTRACT FROM AUTHOR]

Abstract: Let denote a graph formed from unlabelled graphs and a labelled graph replacing every vertex of by the graph and joining the vertices of with all the vertices of those of whenever . For unlabelled graphs , let stand for the class of all graphs taken over all possible orderings of . A prime inductive class of graphs, , is said to be a set of all graphs, which can be produced by recursive applying of where is a graph from a fixed set of prime graphs and are either graphs from the set of prime graphs or graphs obtained in the previous steps. Similar inductive definitions for cographs, -trees, series–parallel graphs, Halin graphs, bipartite cubic graphs or forbidden structures of some graph classes were considered in the literature (Batagelj (1994) Drgas-Burchardt et al. (2010) and Hajós (1961) ). This paper initiates a study of prime inductive classes of graphs giving a result, which characterizes, in their language, the substitution closed induced hereditary graph classes. Moreover, for an arbitrary induced hereditary graph class it presents a method for the construction of maximal induced hereditary graph classes contained in and substitution closed. The main contribution of this paper is to give a minimal forbidden graph characterization of induced hereditary prime inductive classes of graphs. As a consequence, the minimal forbidden graph characterization for some special induced hereditary prime inductive graph classes is given There is also offered an algebraic view on the class of all prime inductive classes of graphs of the type . [Copyright &y& Elsevier]

We consider probability measures on the real line or unit circle with Jacobi or Verblunsky coefficients satisfying an ℓ condition and a generalized bounded variation condition. This latter condition requires that a sequence can be expressed as a sum of sequences β, each of which has rotated bounded variation, i.e., for some $${\phi_l}$$ . This includes a large class of discrete Schrödinger operators with almost periodic potentials modulated by ℓ decay, i.e. linear combinations of $${\lambda_n {\rm cos}(2\pi\alpha n + \phi)}$$ with $${\lambda \in \ell^p}$$ of bounded variation and any α. In all cases, we prove absence of singular continuous spectrum, preservation of absolutely continuous spectrum from the corresponding free case, and that pure points embedded in the continuous spectrum can only occur in an explicit finite set. [ABSTRACT FROM AUTHOR]

Abstract: A -disjoint path cover of a graph is defined as a set of internally vertex-disjoint paths connecting given sources and sinks in such a way that every vertex of the graph is covered by a path in the set. In this paper, we analyze the -disjoint path cover of recursive circulant under the condition that at most faulty vertices and/or edges are removed. It is shown that when , has a -disjoint path cover (of one-to-one type) joining any pair of two distinct source and sink for arbitrary and subject to . In addition, it is proven that when , has a -disjoint path cover (of unpaired many-to-many type) joining any two disjoint sets of sources and sinks for arbitrary and satisfying , in which sources and sinks are freely matched. In particular, the mentioned bounds and of the two cases are shown to be optimal. [Copyright &y& Elsevier]

Abstract: An implicit characterization of the class is given, without using any minimization scheme. This is the first purely recursion-theoretic formulation of . [Copyright &y& Elsevier]

Bifurcation of limit cycles is discussed for three-dimensional Lotka-Volterra competitive systems. A recursion formula for computation of the singular point quantities is given for the corresponding Hopf bifurcation equation. Some new results are obtained for 6 classes 26-31 in Zeeman's classification, especially, an example with four limit cycles in class 29 is given for the first time. The algorithm applied here is effective for solving the above general cyclicity. [ABSTRACT FROM AUTHOR]

Abstract: Given a set of vertices of a connected graph , the metric representation of a vertex of with respect to is the vector , where , denotes the distance between and . is a resolving set for if for every pair of distinct vertices of , . The metric dimension of , , is the minimum cardinality of any resolving set for . Let and be two graphs of order and , respectively. The corona product is defined as the graph obtained from and by taking one copy of and copies of and joining by an edge each vertex from the th-copy of with the th-vertex of . For any integer , we define the graph recursively from as . We give several results on the metric dimension of . For instance, we show that given two connected graphs and of order and , respectively, if the diameter of is at most two, then . Moreover, if and the diameter of is greater than five or is a cycle graph, then . [Copyright &y& Elsevier]

Abstract: It has been previously observed that for many -learnable computable families of computably enumerable (c.e. for short) sets all their computable numberings are evidently -equivalent, i.e. are equivalent with respect to reductions computable in the halting problem. We show that this holds for all -learnable computable families of c.e. sets, and prove that, in general, the converse is not true. In fact there is a computable family of c.e. sets such that all computable numberings of are computably equivalent and is not -learnable. Moreover, we construct a computable family of c.e. sets which is not -learnable though all of its computable numberings are -equivalent. We also give a natural example of a computable -learnable family of c.e. sets which possesses non--equivalent computable numberings. So, for the computable families of c.e. sets, the properties of -learnability and -equivalence of all computable numberings are independent. [Copyright &y& Elsevier]

Abstract: This work initiates a systematic investigation into the matrix forms of the Pascal triangle as mathematical objects in their own right. The present paper is especially devoted to the so-called G-matrices, i.e. the set of the twelve triangular matrix forms that can be derived from the Pascal triangle expanded to the level . For , the G-matrix set reduces to a set of four distinct matrices. The twelve G-matrices are defined and the classic Pascal recursion is reformulated for each of the twelve G-matrices. Three sets of matrix transformations are then introduced to highlight different relations between the twelve G-matrices and for generating them from appropriately chosen subsets. [Copyright &y& Elsevier]

Cantor's theory of cardinal numbers offers a way to generalize arithmetic from finite sets to infinite sets using the notion of one-to-one association between two sets. As is well known, all countable infinite sets have the same 'size' in this account, namely that of the cardinality of the natural numbers. However, throughout the history of reflections on infinity another powerful intuition has played a major role: if a collection A is properly included in a collection B then the 'size' of A should be less than the 'size' of B (part-whole principle). This second intuition was not developed mathematically in a satisfactory way until quite recently. In this article I begin by reviewing the contributions of some thinkers who argued in favor of the assignment of different sizes to infinite collections of natural numbers (Thabit ibn Qurra, Grosseteste, Maignan, Bolzano). Then, I review some recent mathematical developments that generalize the part-whole principle to infinite sets in a coherent fashion (Katz, Benci, Di Nasso, Forti). Finally, I show how these new developments are important for a proper evaluation of a number of positions in philosophy of mathematics which argue either for the inevitability of the Cantorian notion of infinite number (Gödel) or for the rational nature of the Cantorian generalization as opposed to that, based on the part-whole principle, envisaged by Bolzano (Kitcher). [ABSTRACT FROM AUTHOR]

This paper introduces theories for arithmetical quasi-inductive definitions (Burgess, 1986) as it has been done for first-order monotone and nonmonotone inductive ones. After displaying the basic axiomatic framework, we provide some initial result in the proof theoretic bounds line of research (the upper one being given in terms of a theory of sets extending Kripke-Platek set theory). [ABSTRACT FROM AUTHOR]

Abstract: A new axiomatic system OST of operational set theory is introduced in which the usual language of set theory is expanded to allow us to talk about (possibly partial) operations applicable both to sets and to operations. OST is equivalent in strength to admissible set theory, and a natural extension of OST is equivalent in strength to ZFC. The language of OST provides a framework in which to express “small” large cardinal notions—such as those of being an inaccessible cardinal, a Mahlo cardinal, and a weakly compact cardinal—in terms of operational closure conditions that specialize to the analogue notions on admissible sets. This illustrates a wider program whose aim is to provide a common framework for analogues of large cardinal notions that have appeared in admissible set theory, admissible recursion theory, constructive set theory, constructive type theory, explicit mathematics, and systems of recursive ordinal notations that have been used in proof theory. [Copyright &y& Elsevier]

The sets of five numbers picked in the North Carolina Cash- 5 Lottery game were identical on July 9th and 11th, 2007. This coincidence was the topic of a local television station news story on July 12 in which I played a minor role. This article documents the coincidence, my interactions with the television re- porter seeking to understand how likely, or unlikely, the coincidence was, and some afterthoughts, including an analysis of the likelihood of matching sets of numbers. [ABSTRACT FROM AUTHOR]

This paper presents a novel and mathematically rigorous Bayes' recursion for tracking a target that generates multiple measurements with state dependent sensor field of view and clutter. Our Bayesian formulation is mathematically well-founded due to our use of a consistent likelihood function derived from random finite set theory. It is established that under certain assumptions, the proposed Bayes' recursion reduces to the cardinalized probability hypothesis density (CPHD) recursion for a single target. A particle implementation of the proposed recursion is given. Under linear Gaussian and constant sensor field of view assumptions, an exact closed-form solution to the proposed recursion is derived, and efficient implementations are given. Extensions of the closed-form recursion to accommodate mild nonlinearities are also given using linearization and unscented transforms. [ABSTRACT FROM AUTHOR]

This paper presents a sound and complete category-theoretic notion of models for Linear Abadi & Plotkin Logic [Birkedal et al., 2006], a logic suitable for reasoning about parametricity in combination with recursion. A subclass of these called parametric LAPL structures can be seen as an axiomatization of domain theoretic models of parametric polymorphism, and we show how to solve general (nested) recursive domain equations in these. Parametric LAPL structures constitute a general notion of model of parametricity in a setting with recursion. In future papers we will demonstrate this by showing how many different models of parametricity and recursion give rise to parametric LAPL structures, including Simpson and Rosolini's set theoretic models [Rosolini and Simpson, 2004], a syntactic model based on Lily [Pitts, 2000, Bierman et al., 2000] and a model based on admissible pers over a reflexive domain [Birkedal et al., 2007]. [ABSTRACT FROM AUTHOR]

This paper provides an axiomatic framework to compare the D-core (the set of undominated imputations) and the core of a cooperative game with transferable utility. Theorem 1 states that the D-core is the only solution satisfying projection consistency, reasonableness (from above), (*)-antimonotonicity, and modularity. Theorem 2 characterizes the core replacing (*)-antimonotonicity by antimonotonicity. Moreover, these axioms also characterize the core on the domain of convex games, totally balanced games, balanced games, and superadditive games. [ABSTRACT FROM AUTHOR]

Sacks [23] asks if the metarecursively enumerable degrees are elementarily equivalent to the r.e. degrees. In unpublished work, Slaman and Shore proved that they are not. This paper provides a simpler proof of that result and characterizes the degree of the theory as $\mathcal{O}^{(\omega)}$ or, equivalently, that of the truth set of $L_{\omega_{1}^{CK}}$.. [ABSTRACT FROM AUTHOR]

This paper is a companion to work of Feferman, Jäger, Glaß, and Strahm on the proof theory of the type two functionals μ and E1 in the context of Feferman-style applicative theories. In contrast to the previous work, we analyze these two functionals in the context of Schlüter's weakened applicative basis PRON which allows for an interpretation in the primitive recursive indices. The proof-theoretic strength of PRON augmented by μ and E1 is measured in terms of the two subsystems of second order arithmetic, Π10-CA and Π11-CA, respectively. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Abstract: The concept of recursive coalgebra of a functor was introduced in the 1970s by Osius in his work on categorical set theory to discuss the relationship between wellfounded induction and recursively specified functions. In this paper, we motivate the use of recursive coalgebras as a paradigm of structured recursion in programming semantics, list some basic facts about recursive coalgebras and, centrally, give new conditions for the recursiveness of a coalgebra based on comonads, comonad-coalgebras and distributive laws of functors over comonads. We also present an alternative construction using countable products instead of cofree comonads. [Copyright &y& Elsevier]

We develop the concepts of recursively nowhere dense sets and sets that are recursively of first category and study closed sets of points in light of Baire's Category Theorem. Our theorems are primarily concerned with exdomains (i. e. complements of domains) of recursive quantum functions and hence with avoidable points (i. e. points that can be forced into exdomains of recursive quantum functions). An avoidance function is a recursive function which can be used to expel avoidable points from domains of recursive quantum functions. We define an avoidable set of points to be an arbitrary subset of the avoidable points of a single avoidance function, and we study an effective union of such sets which we call a piecemeal avoidable set. We note that each of ‘the set of recursive points’ and ‘the set of avoidable points’ is of first category but not recursively of first category. We show an exdomain exists which is recursively nowhere dense, as well as one that is nowhere dense but not recursively nowhere dense. After establishing that every exdomain is recursively of first category, we prove that given any fixed exdomain, there is another exdomain, which while dense in the underlying space, is disjoint from the fixed exdomain. Finally, we show how to build a recursive sequence of recursive quantum functions that have mutually disjoint, dense exdomains. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

We establish a first step towards a “Rice theorem” for tilings: for non-trivial sets, it is undecidable to know whether two different tile sets produce the same tilings of the plane. Then, we study quasiperiodicity functions associated with tilings. This function is a way to measure the regularity of tilings. We prove that, not only almost all recursive functions can be obtained as quasiperiodicity functions, but also, a function which overgrows any recursive function. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

We prove the existence of a perfect Π01 set of reals such that the uniform join of any of its infinite subsets is above 0′. We explain a couple of ways in which this demonstrates the optimality of the Low Basis Theorem. [Copyright &y& Elsevier]

We investigate Turing cones as sets of reals, and look at the relationship between Turing cones, measures, Baire category and special sets of reals, using these methods to show that Martin's proof of Turing Determinacy (every determined Turing closed set contains a Turing cone or is disjoint from one) does not work when you replace “determined” with “Blackwell determined”. This answers a question of Tony Martin. [ABSTRACT FROM AUTHOR]