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]

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]

We study the octahedron relation (also known as the A∞T-system), obeyed in particular by the partition function for dimer coverings of the Aztec Diamond graph. For a suitable class of doubly periodic initial conditions, we find exact solutions with a particularly simple factorized form. For these, we show that the density function that measures the average dimer occupation of a face of the Aztec graph, obeys a system of linear recursion relations with periodic coefficients. This allows us to explore the thermodynamic limit of the corresponding dimer models and to derive exact ‘arctic’ curves separating the various phases of the system. [ABSTRACT FROM AUTHOR]