We extend the notion of immunity to closed sets and to $\Pi^0_1$ classes in particular in two ways: immunity meaning the corresponding tree has no infinite computable subset, and tree-immunity meaning it has no infinite computable subtree. We separate these notions from each other and that of being special, and show separating classes for computably inseparable c.e. sets are immune and perfect thin classes are tree-immune. We define the notion of prompt immunity and construct a positive-measure promptly immune $\Pi^0_1$ class. We show that no immune-free $\Pi^0_1$ class $P$ cups to the Medvedev complete class $\mathrm{DNC}$ of diagonally noncomputable sets, where $P$ cups to $Q$ in the Medvedev degrees of $\Pi^0_1$ classes if there is a class $R$ such that the product $P \otimes R \equiv_\textrm{M} Q$. We characterize the interaction between (tree-)immunity and Medvedev meet and join, showing the (tree-)immune degrees form prime ideals in the Medvedev lattice. We show that every random closed set is immune and not small, and every small special class is immune.
We model a selection process arising in certain storage problems. A sequence ( X 1 , · ··, X n ) of non-negative, independent and identically distributed random variables is given. F ( x ) denotes the common distribution of the X i ′ s. With F ( x ) given we seek a decision rule for selecting a maximum number of the X i ′ s subject to the following constraints: (1) the sum of the elements selected must not exceed a given constant c > 0, and (2) the X i ′ s must be inspected in strict sequence with the decision to accept or reject an element being final at the time it is inspected. We prove first that there exists such a rule of threshold type, i.e. the i th element inspected is accepted if and only if it is no larger than a threshold which depends only on i and the sum of the elements already accepted. Next, we prove that if F ( x ) ~ Ax α as x → 0 for some A, α > 0 , then for fixed c the expected number, E n ( c ), selected by an optimal threshold is characterized by Asymptotics as c → ∞ and n → ∞with c/n held fixed are derived, and connections with several closely related, well-known problems are brought out and discussed.
We examine the sequences A that are low for dimension, i.e. those for which the effective (Hausdorff) dimension relative to A is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Löf random sequence has effective dimension 1 relative to A, and lowishness for K, namely, that the limit of K A (n)/K(n) is 1. We show that there is a perfect [Formula: see text]-class of low for dimension sequences. Since there are only countably many low for random sequences, many more sequences are low for dimension. Finally, we prove that every low for dimension is jump-traceable in order n ε , for any ε > 0.
Abstract We prove that there exists a noncomputable c.e. real which is low for weak 2-randomness, a definition of randomness due to Kurtz, and that all reals which are low for weak 2-randomness are low for Martin-Löf randomness.
Abstract Let denote the collection of all Π 1 0 classes, ordered by inclusion. A collection of Turing degrees in is called invariant over if there is some collection of Π 1 0 classes representing exactly the degrees such that is invariant under automorphisms of . Herein we expand the known degree invariant classes of , previously including only { 0 } and the array noncomputable degrees, to include all high n and non-low n degrees for n > 2. This is a corollary to a very general definability result. The result is carried out in a substructure G of , within which the techniques used model those used by Cholak and Harrington [6] to obtain the same definability for the c.e. sets. We work back and forth between G and to show that this definability in G gives the desired degree invariance over .
We characterize the class of c.e. degrees that bound a critical triple (equivalently, a weak critical triple) as those degrees that compute a function that has no ω-c.e. approximation.
'/%3e%3cuse xlink:href='%23a' transform='rotate(72 0 0)'/%3e%3cuse xlink:href='%23a' transform='rotate(-72 0 0)'/%3e%3cuse xlink:href='%23a' transform='scale(-1 1) rotate(72)'/%3e%3c/g%3e%3c/defs%3e%3cpath fill='%23012169' d='M0 0h1200v600H0z'/%3e%3cpath stroke='%23FFF' stroke-width='60' d='m0 0 600 300M0 300 600 0' clip-path='url(%23b)'/%3e%3cpath stroke='%23C8102E' stroke-width='40' d='m0 0 600 300M0 300 600 0' clip-path='url(%23c)'/%3e%3cpath stroke='%23FFF' stroke-width='100' d='M300 0v300M0 150h600' clip-path='url(%23b)'/%3e%3cpath stroke='%23C8102E' stroke-width='60' d='M300 0v300M0 150h600' clip-path='url(%23b)'/%3e%3cuse xlink:href='%23d' fill='%23FFF' transform='matrix(45.4 0 0 45.4 900 120)'/%3e%3cuse xlink:href='%23d' fill='%23C8102E' transform='matrix(30 0 0 30 900 120)'/%3e%3cg transform='rotate(82 900 240)'%3e%3cuse xlink:href='%23d' fill='%23FFF' transform='rotate(-82 519.022 -457.666) scale(40.4)'/%3e%3cuse xlink:href='%23d' fill='%23C8102E' transform='rotate(-82 519.022 -457.666) scale(25)'/%3e%3c/g%3e%3cg transform='rotate(82 900 240)'%3e%3cuse xlink:href='%23d' fill='%23FFF' transform='rotate(-82 668.57 -327.666) scale(45.4)'/%3e%3cuse xlink:href='%23d' fill='%23C8102E' transform='rotate(-82 668.57 -327.666) scale(30)'/%3e%3c/g%3e%3cuse xlink:href='%23d' fill='%23FFF' transform='matrix(50.4 0 0 50.4 900 480)'/%3e%3cuse xlink:href='%23d' fill='%23C8102E' transform='matrix(35 0 0 35 900 480)'/%3e%3c/svg%3e)
'/%3e%3cuse xlink:href='%23a' transform='translate(288.889 -214.211)'/%3e%3cuse xlink:href='%23a' transform='translate(108 342.749)'/%3e%3cuse xlink:href='%23a' transform='translate(469.189 342.749)'/%3e%3c/svg%3e)
