Recursive events in random sequences

Let ω be a Kolmogorov–Chaitin random sequence with ω_{1: n} denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω_{1: n} )} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any such P and α finds an n such that P holds within the first n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of the result fail. Received: 1 December 1998 / Published online: 3 October 2001     

The $\mu$-measure as a tool for classifying computational complexity

Two simply typed term systems and are considered, both for representing algorithms computing primitive recursive functions. is based on primitive recursion, on recursion on notation. A purely syntactical method of determining the computational complexity of algorithms in , called $\mu$ -measure, is employed to uniformly integrate traditional results in subrecursion theory with resource-free characterisations of sub-elementary complexity classes. Extending the Schwichtenberg and Müller characterisation of the Grzegorczyk classes for , it is shown $\mathcal{E}_{n+1} = \mathcal{R}^n_1n\ge 1\mathcal{R}^n_i$ denotes the \emph{th modified Heinermann class} based on . The proof does not refer to any machine-based computation model, unlike the Schwichtenberg and Müller proofs. This is due to the notion of modified recursion lying on top of each other provided by . By Ritchie's result, characterises the linear-space computable functions. Using the same method, a short and straightforward proof is presented, showing that characterises the polynomial time computable functions. Furthermore, the classes and coincide at and above level 2. Received: 22 September 1997 / Revised version: 12 May 1999     

Density results in the Δ20 e-degrees

We show that the Δ⁰ ₂ enumeration degrees are dense. We also show that for every nonzero n-c. e. e-degree a, with n≥ 3, one can always find a nonzero 3-c. e. e-degree b such that b < a on the other hand there is a nonzero ωc. e. e-degree which bounds no nonzero n-c. e. e-degree. Received: 13 June 2000 / Published online: 3 October 2001     

<Emphasis Type="Italic">P</Emphasis>≠<Emphasis Type="Italic">NP</Emphasis> for Infinite Time Turing Machines

We state different versions of the P=?NP problem for infinite time Turing machines. It is observed that PNP collapses to the fact that there are analytic sets which are not Borel.The author thanks J. D. Hamkins, R. Schipperus, and P. Welch for comments on earlier versions of this paper. He thanks Sanders Seliverstov for pointing out an inaccuracy in the first version of the proof of Theorem 2.10.Received April 19, 2002; in revised form June 10, 2002 Published online May 16, 2003     

On one-sided versus two-sided classification

One-sided classifiers are computable devices which read the characteristic function of a set and output a sequence of guesses which converges to 1 iff the set on the input belongs to the gven class. Such a classifier istwo-sided if the sequence of its output in addition converges to 0 on setsnot belonging to the class. The present work obtains the below mentionedresults for one-sided classes (= Σ⁰ ₂ classes) with respect to four areas: Turing complexity, 1-reductions, index sets and measure. There are one-sided classes which are not two-sided. This can have two reasons: (1) the class has only high Turing complexity. Then there are some oracles which allow to construct noncomputale two-sided classifiers. (2) The class is difficult because of some topological constraints and then there are also no nonrecursive two-sided classifiers. For case (1), several results are obtainedto localize the Turing complexity of certain types of one-sided classes. The concepts of 1-reduction, 1-completeness and simple sets is transferred to one-sided classes: There are 1-complete classes and simple classes, but no class is at the same time 1-complete nd simple. The one-sided classes have a natural numbering. Most of the common index sets relative to this numbering have the high complexity Π¹ ₁: the index set of the class {0,1}^∞, the index set of the equality problem and the index set of all two-sided classes. On the other side the index set of the empty class has complexity Π⁰ ₂; Π⁰ ₂ and Σ⁰ ₂ are the least complexities any nontrivial index set can have. Lusin showed that any one-sided class is measurable. Concerning the effectiveness of this measure, it is shown that a one-sided class has recursive measure 0 if it has measure 0, but that thre are one-sided classes having measure 1 without having measure 1 effectively. The measure of a two-sided class can be computed in the limit. Received: 2 December 1999 / Revised version: 28 February 2000 / Published online: 15 June 2001     

Every incomplete computably enumerable truth-table degree is branching

If r is a reducibility between sets of numbers, a natural question to ask about the structure ? _r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by showing that every tt-incomplete computably enumerable truth-table degree a is branching in ? _tt . The fact that every Turing-incomplete computably enumerable truth-table degree is branching has been known for some time. This fact can be shown using a technique of Ambos-Spies and, as noticed by Nies, also follows from a relativization of a result of Degtev. We give a proof here using the Ambos-Spies technique because it has not yet appeared in the literature. The proof uses an infinite injury argument. Our main result is the proof when a is Turing-complete but tt-incomplete. Here we are able to exploit the Turing-completeness of a in a novel way to give a finite injury proof. Received: 22 January 1999 / Revised version: 12 July 1999 / Published online: 21 December 2000     

A restricted computation model on Scott domains and its partial primitive recursive functionals

The paper builds on both a simply typed term system and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions and PTWP are studied that are closed under scvr. The twist are certain type 1 G?del recursors for simultaneous partial primitive recursion. Formally, denotes a function , however, is modelled such that is finite, or in other words, a partial sequence. As for PTWP, the concept of type writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP-computable functionals coincide with those definable in plus a constant for sequential minimisation. In particular, the functionals definable in denoted can be characterised by a subclass of PTWP-computable functionals denoted . Moreover, hierarchies of strictly increasing classes in the style of Heinermann and complexity classes are introduced such that . These results extend those for and PTWP [Nig94]. Finally, scvr is employed to define for each type the enumeration functional of all finite elements of . Received January 30, 1996     

An explicit bound for uniform perfectness of the Julia sets of rational maps

A compact set C in the Riemann sphere is called uniformly perfect if there is a uniform upper bound on the moduli of annuli which separate C. Julia sets of rational maps of degree at least two are uniformly perfect. Proofs have been given independently by Ma né and da Rocha and by Hinkkanen, but no explicit bounds are given. In this note, we shall provide such an explicit bound and, as a result, give another proof of uniform perfectness of Julia sets of rational maps of degree at least two. As an application, we provide a lower estimate of the Hausdorff dimension of the Julia sets. We also give a concrete bound for the family of quadratic polynomials in terms of the parameter c. Received: 7 June 1999; in final form: 9 November 1999 / Published online: 17 May 2001     

A computably enumerable vector space with the strong antibasis property

Downey and Remmel have completely characterized the degrees of c.e. bases for c.e. vector spaces (and c.e. fields) in terms of weak truth table degrees. In this paper we obtain a structural result concerning the interaction between the c.e. Turing degrees and the c.e. weak truth table degrees, which by Downey and Remmel's classification, establishes the existence of c.e. vector spaces (and fields) with the strong antibasis property (a question which they raised). Namely, we construct c.e. sets such that the c.e. W-degrees below that of A are disjoint from the nonzero c.e. T-degrees below that of A and comparable to that of B. Received: 2 December 1998     

On the filter of computably enumerable supersets of an r-maximal set

We study the filter ℒ^*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ^*(A) is still Σ⁰ ₃-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ^*(A). Received: 6 November 1999 / Revised version: 10 March 2000 /?Published online: 18 May 2001     

Subrecursive functions on partial sequences

The paper studies a domain theoretical notion of primitive recursion over partial sequences in the context of Scott domains. Based on a non-monotone coding of partial sequences, this notion supports a rich concept of parallelism in the sense of Plotkin. The complexity of these functions is analysed by a hierarchy of classes similar to the Grzegorczyk classes. The functions considered are characterised by a function algebra generated by continuity preserving operations starting from computable initial functions. Its layers are related to those above by showing , thus generalising results of Schwichtenberg/Müller and Niggl. Received: 18 November 1996     

Explaining the Gentzen–Takeuti reduction steps: a second-order system

Using the concept of notations for infinitary derivations we give an explanation of Takeuti's reduction steps on finite derivations (used in his consistency proof for Π¹ ₁-CA) in terms of the more perspicious infinitary approach from [BS88]. Received: 27 April 1999 / Published online: 21 March 2001     

A version of the Jensen–Johnsbråten coding at arbitrary level n≥ 3

We generalize, on higher projective levels, a construction of “incompatible” generic Δ¹ ₃ real singletons given by Jensen and Johnsbr?ten. Received: 3 November 1998 / Revised version: 23 April 2000 / Published online: 3 October 2001     

Cut elimination for a calculus with context-dependent rules

Context-dependent rules are an obstacle to cut elimination. Turning to a generalised sequent style formulation using deep inferences is helpful, and for the calculus presented here it is essential. Cut elimination is shown for a substructural, multiplicative, pure propositional calculus. Moreover we consider the extra problems induced by non-logical axioms and extend the results to additive connectives and quantifiers. Received: 11 April 1998 / Published online: 25 January 2001     

The Karp complexity of unstable classes

A class K of structures is controlled if, for all cardinals λ, the relation of L _∞,λ-equivalence partitions K into a set of equivalence classes (as opposed to a proper class). We prove that the class of doubly transitive linear orders is controlled, while any pseudo-elementary class with the ω-independence property is not controlled. Received: 23 September 1998 / Revised version: 6 July 1999 / Published online: 21 December 2000     

On quasi-amorphous sets

A set is said to be amorphous if it is infinite, but cannot be written as the disjoint union of two infinite sets. The possible structures which an amorphous set can carry were discussed in [5]. Here we study an analogous notion at the next level up, that is to say replacing finite/infinite by countable/uncountable, saying that a set is quasi-amorphous if it is uncountable, but is not the disjoint union of two uncountable sets, and every infinite subset has a countably infinite subset. We use the Fraenkel–Mostowski method to give many examples showing the diverse structures which can arise as quasi-amorphous sets, for instance carrying a projective geometry, or a linear ordering, or both; reconstruction results in the style of [1] are harder to come by in this case. Received: 8 April 1999 / Published online: 3 October 2001     

Near coherence and filter games

We investigate a two-player game involving pairs of filters on ω. Our results generalize a result of Shelah ([7] Chapter VI) dealing with applications of game theory in the study of ultrafilters. Received: 28 September 1998 / Published online: 25 January 2001     

Positive polynomials on compact sets

The aim of this note is to give short algebraic proofs of theorems of Handelman, Pólya and Schmüdgen concerning the algebraic structure of polynomials being positive on certain subsets of ℝ ⁿ . The main ingredient of the proofs is the representation theorem of Kadison–Dubois. The proof of the latter is elementary and algebraic but tricky. Received: 6 February 1999 / Revised version: 28 August 2000