scientific article
From MaRDI portal
Publication:3819052
zbMath0667.03030MaRDI QIDQ3819052
Publication date: 1987
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
oracler.e. setsr.e. degreeslattice of r.e. setsPost's problemfinite injury priority methoddegree of informationinfinite injury priority methodminimal pair method
History of mathematics in the 20th century (01A60) Development of contemporary mathematics (01A65) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) History of mathematical logic and foundations (03-03) Recursively (computably) enumerable sets and degrees (03D25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items
Effective presentability of Boolean algebras of Cantor-Bendixson rank 1, Index Sets for Finite Normal Predicate Logic Programs with Function Symbols, Turing degrees of nonabelian groups, On the problem of the critical bound, A join theorem for the computably enumerable degrees, The ∀∃-theory of ℛ(≤,∨,∧) is undecidable, Turing incomparability in Scott sets, Nonisomorphism of lattices of recursively enumerable sets, Degree spectra of prime models, Bounding prime models, Non-p-generic and strongly nonbranching degree, Non-p-generic and strongly nonbranching degree, Unnamed Item, Computation over algebraic structures and a classification of undecidable problems, Computable elements and functions in effectively enumerable topological spaces, 1-reducibility inside an m-degree with a maximal set, The complexity of decomposability of computable rings, Cupping computably enumerable degrees simultaneously, A local version of the Slaman-Wehner theorem and families closed under finite differences, On the embedding of the first nonconstructive ordinal in the Rogers semilattices, Isomorphism of lattices of recursively enumerable sets, Undecidability in diagonalizable algebras, Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices, Computability and Recursion, The complexity of recursion theoretic games, A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals, Two notes on subshifts, Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets, When series of computable functions with varying domains are computable, Why Turing’s Thesis Is Not a Thesis, Turing computable embeddings of equivalences other than isomorphism, Finitely presented expansions of groups, semigroups, and algebras, Invariants, Boolean algebras and ACA₀⁺, The computational complexity of torsion-freeness of finitely presented groups, The power of backtracking and the confinement of length, Computability Theory and Differential Geometry, The nonlow computably enumerable degrees are not invariant in $\mathcal {E}$, Weakly computable real numbers, Codable sets and orbits of computably enumerable sets, TURING DEGREE SPECTRA OF DIFFERENTIALLY CLOSED FIELDS, Π10 classes and strong degree spectra of relations, The settling-time reducibility ordering, Further Generalizations of Results on Structures of Continuous Functions, Reverse mathematics and fully ordered groups, Completeness, Compactness, Effective Dimensions, On the bounded quasi‐degrees of c.e. sets, A characterization of the 0-basis homogeneous bounding degrees, Recursively enumerable reals and Chaitin \(\Omega\) numbers, Computable analysis and Blaschke products, Hierarchies of probabilistic and team FIN-learning, Synthesizing learners tolerating computable noisy data, The canonical Ramsey theorem and computability theory, Extension theorems, orbits, and automorphisms of the computably enumerable sets, Learnability and positive equivalence relations, Every Low Boolean Algebra is Isomorphic to a Recursive One, On the hierarchies of Δ20-real numbers, Friedberg splittings in Σ30 quotient lattices of, A characterization of c. e. random reals, Permutations and Presentations, Undecidability and initial segments of the (r.e.) tt-degrees, FIRST-ORDER POSSIBILITY MODELS AND FINITARY COMPLETENESS PROOFS, The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable, ON THE COMPLEXITY OF CLASSIFYING LEBESGUE SPACES, Effectively dense Boolean algebras and their applications, Computability of Real Numbers, One note on positive A-computable numberings, There is no ordering on the classes in the generalized high/low hierarchies, Lowness for genericity, Orbits of maximal vector spaces, A note on the enumeration degrees of 1-generic sets, Reverse mathematics, well-quasi-orders, and Noetherian spaces, Computable dimension for ordered fields, On the computing power of fuzzy Turing machines, The complexity of finding SUBSEQ\((A)\), Completely mitotic r. e. degrees, Classification of degree classes associated with r.e. subspaces, Degrees that are not degrees of categoricity, Recursively enumerable \(m\)- and \(tt\)-degrees. II: The distribution of singular degrees, Diagonalizations over polynomial time computable sets, On the learnability of vector spaces, Collapsing degrees, Intervals containing exactly one c.e. degree, On the definable ideal generated by the plus cupping c.e. degrees, On the strength of the finite intersection principle, An improved zero-one law for algorithmically random sequences, Undecidability of the structure of the Solovay degrees of c.e. reals, Linear orderings of low degree, PAC learning, VC dimension, and the arithmetic hierarchy, Ramsey-type graph coloring and diagonal non-computability, Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility, Almost universal cupping and diamond embeddings, Computable fields and the bounded Turing reduction, Badness and jump inversion in the enumeration degrees, A superhigh diamond in the c.e. tt-degrees, Effectively approximating measurable sets by open sets, Taking the Pirahã seriously, Initial segments of computable linear orders with additional computable predicates, Extending and interpreting Post's programme, \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs, A measure-theoretic proof of Turing incomparability, \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures, The complexity of central series in nilpotent computable groups, An easy priority-free proof of a theorem of Friedberg, The Friedman embedding theorem., \(Q _{1}\)-degrees of c.e. sets, On arithmetical level of the class of superhigh sets, On degree-preserving homeomorphisms between trees in computable topology, Embedding \(\mathrm{FD}(\omega)\) into \({\mathcal{P}_s}\) densely, Effectively closed sets and enumerations, Definable relations in Turing degree structures, Inferring answers to queries, Index sets of classes of hyper-hypersimple sets, Domain theory in logical form, The density of the low\(_ 2\) \(n\)-r.e. degrees, Some effects of Ash-Nerode and other decidability conditions on degree spectra, Uncountable degree spectra, Branching in the \({\Sigma^0_2}\)-enumeration degrees: a new perspective, On a computable presentation of low linear orderings, A DNC function that computes no effectively bi-immune set, Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra, Computing planarity in computable planar graphs, Continuity of capping in \(\mathcal C_{\text{bT}}\), Automorphisms in the PTIME-Turing degrees of recursive sets, The strength of the Grätzer-Schmidt theorem, Fine hierarchies and m-reducibilities in theoretical computer science, The isomorphism problem for torsion-free abelian groups is analytic complete, Friedberg splittings of recursively enumerable sets, Structural properties of \(Q\)-degrees of n-c.e. sets, Random numbers as probabilities of machine behavior, Undecidability and 1-types in the recursively enumerable degrees, The distribution of the generic recursively enumerable degrees, Automata theory based on complete residuated lattice-valued logic: Turing machines, How powerful are integer-valued martingales?, Ramsey's theorem for trees: the polarized tree theorem and notions of stability, Strongly \(\eta \)-representable degrees and limitwise monotonic functions, Computing interpolating sequences, Numberings optimal for learning, The minimal e-degree problem in fragments of Peano arithmetic, Computability of simple games: a complete investigation of the sixty-four possibilities, Embedding and coding below a 1-generic degree, Index sets and universal numberings, Application of precomplete enumerations to tabular-type degrees and index sets, Completeness in the arithmetical hierarchy and fixed points, Complexity of the isomorphism problem for computable free projective planes of finite rank, Working below a \(low_ 2\) recursively enumerable degree, Goodness in the enumeration and singleton degrees, Constructive dimension and Turing degrees, Enumerations and completely decomposable torsion-free abelian groups, A theorem on strongly \(\eta \)-representable sets, Elementary differences among jump classes, Model-theoretic properties of Turing degrees in the Ershov difference hierarchy, The polarized Ramsey's theorem, Dimension extractors and optimal decompression, Classification of computably approximable real numbers, Some applications of computable one-one numberings, Cook reducibility is faster than Karp reducibility in NP, Determining and stationary sets for some classes of partial recursive functions, Empty intervals in the enumeration degrees, Mass problems associated with effectively closed sets, Post's problem for ordinal register machines: an explicit approach, A non-splitting theorem in the enumeration degrees, Martin's conjecture and strong ergodicity, Lattice-valued fuzzy Turing machines: computing power, universality and efficiency, Degrees of orderings not isomorphic to recursive linear orderings, Logic programming with infinite sets, Learning via finitely many queries, Learning Families of Closed Sets in Matroids, Orbits of Creative Subspaces, Splitting into degrees with low computational strength, Program Size Complexity of Correction Grammars in the Ershov Hierarchy, Automorphism Groups of Substructure Lattices of Vector Spaces in Computable Algebra, On the Lattices of Effectively Open Sets, Computable completely decomposable groups, Nonexistence of Minimal Pairs in $$L[{\mathbf d}$$], On the complexity of radicals in noncommutative rings, The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable, Infima of d.r.e. degrees, Degrees of categoricity of computable structures, LEARNING THEORY IN THE ARITHMETIC HIERARCHY, The jump is definable in the structure of the degrees of unsolvability, On initial segment complexity and degrees of randomness, choice classes, Hyperhypersimple sets and Q1 -reducibility, Localization of a theorem of Ambos-Spies and the strong anti-splitting property, Hierarchies of function classes defined by the first-value operator, Prescribed Learning of R.E. Classes, Complexity with Rod, Weakly Represented Families in Reverse Mathematics, On Constructive Nilpotent Groups, The Lattice of Computably Enumerable Vector Spaces, Injection Structures Specified by Finite State Transducers, There Are No Maximal d.c.e. wtt-degrees, Nondensity of Double Bubbles in the D.C.E. Degrees, On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets, On the Reals Which Cannot Be Random, Completeness of Hoare Logic Relative to the Standard Model, On a general method of constructing post reducibilities and the corresponding completeness criteria, Borel-Piecewise Continuous Reducibility for Uniformization Problems, On Turing degrees of points in computable topology, Singular coverings and non‐uniform notions of closed set computability, Effective packing dimension of $\Pi ^0_1$-classes, On a question of Slaman and Groszek, Degrees of Word Problem for Algebras Without Finitely Presented Expansions, Modulo computably enumerable degrees by cupping partners, Prime models of theories of computable linear orderings, Ideals in computable rings, Truth-table Schnorr randomness and truth-table reducible randomness, Closed Left-R.E. Sets, Recursive Linear Orders with Incomplete Successivities, On the structures inside truth-table degrees, Automorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degrees, Schnorr trivial sets and truth-table reducibility, An explicit solution to Post's problem over the reals, $\Sigma^0_1$ and $\Pi^0_1$ Equivalence Structures, Immunity for Closed Sets, Computable Exchangeable Sequences Have Computable de Finetti Measures, Spectra of Algebraic Fields and Subfields, 0″-Categorical Completely Decomposable Torsion-Free Abelian Groups, Computability of simple games: A characterization and application to the core, Joining up to the generalized high degrees, Depth zero Boolean algebras, A single minimal complement for the c.e. degrees, Definability as hypercomputational effect, Bounding computably enumerable degrees in the Ershov hierarchy, Computational power of infinite quantum parallelism, Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets, Is it harder to factor a polynomial or to find a root?, A computably stable structure with no Scott family of finitary formulas, On the orbits of computably enumerable sets, Boolean algebras, Tarski invariants, and index sets, \(\Pi^0_1\)-presentations of algebras, Function operators spanning the arithmetical and the polynomial hierarchy, Weakly precomplete computably enumerable equivalence relations, COMPUTABLE ABELIAN GROUPS, Chain conditions in computable rings, Decidability and Invariant Classes for Degree Structures, Classifying model-theoretic properties, The degree spectra of homogeneous models, Invariance in ℰ* and ℰ_{Π}, Difference randomness, T-Degrees, Jump Classes, and Strong Reducibilities, Effective Categoricity of Injection Structures, Cupping and Diamond Embeddings: A Unifying Approach, Adapting Rabin’s Theorem for Differential Fields, The atomic model theorem and type omitting, On Approximate Decidability of Minimal Programs, Incompleteness, Undecidability and Automated Proofs, Learning Finite Variants of Single Languages from Informant, Non-isolated quasi-degrees, Degree spectra and immunity properties, Hyperarithmetical Index Sets in Recursion Theory, Comparing theorems of hyperarithmetic analysis with the arithmetic Bolzano-Weierstrass theorem, Computability Results Used in Differential Geometry, Measure and cupping in the Turing degrees, A note on the join property, The isomorphism problem on classes of automatic structures with transitive relations, Reverse mathematics and infinite traceable graphs, On Σ1 1 equivalence relations over the natural numbers, Non-cupping and randomness, Hypersimplicity and semicomputability in the weak truth table degrees, 1-generic splittings of computably enumerable degrees, Computational classification of cellular automata, On the effective generation of set elements within specified ranges, Asymptotic invariants, complexity of groups and related problems, Congruence relations on lattices of recursively enumerable sets, On orbits, of prompt and low computably enumerable sets, Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees, Sufficient conditions for the existence of 0'-limitwise monotonic functions for computable \(\eta\)-like linear orders, Randomness and reducibility, Embeddability of the semilattice \(L_m^0\) in Rogers semilattices, Computational depth and reducibility, Semantic universality of theories over a superlist, Classification of the index sets of low \([n^ p\) and high \([n]^ p\)], Bounded recursively enumerable sets and degrees, On definable filters in computably enumerable degrees, The dimensions of individual strings and sequences, Counting extensional differences in BC-learning, Infimum properties differ in the weak truth-table degrees and the Turing degrees, Enumeration 1-genericity in the local enumeration degrees, Refining the taming of the reverse mathematics zoo, Computable linearizations of well-partial-orderings, Between Turing and Kleene, Interpreting true arithmetic in the theory of the r.e. truth table degrees, Undecidable fragments of elementary theories, Learning recursive functions from approximations, Infinite versions of some problems from finite complexity theory, Lattice embeddings below a nonlow\(_ 2\) recursively enumerable degree, Bounded low and high sets, Interpolating \(d\)-r.e. and REA degrees between r.e. degrees, Effective content of the calculus of variations. I: Semi-continuity and the chattering lemma, Learning-theoretic perspectives of acceptable numberings, Effective inseparability in a topological setting, Priority constructions, A representation of recursively enumerable sets through Horn formulas in higher recursion theory, A connection between the Cantor-Bendixson derivative and the well-founded semantics of finite logic programs, On mutual definability of operations on fields, Seas of squares with sizes from a \(\Pi_{1}^{0}\) set, Effective algebraicity, Finitely presented expansions of computably enumerable semigroups, Effective randomness of unions and intersections, Maximal pairs of computably enumerable sets in the computably Lipschitz degrees, Classifications of computable structures, Degrees of categoricity and the hyperarithmetic hierarchy, Classifying equivalence relations in the Ershov hierarchy, A blend of methods of recursion theory and topology., Complements for enumeration \(\Pi_1^0\)-degrees, Minimal equivalence relations in hyperarithmetical and analytical hierarchies, A note on \(\Delta_2^0\)-spectra of linear orderings and degree spectra of the successor relation, Isolated 2-computably enumerable \(Q\)-degrees, Strong noncuppability in low computably enumerable degrees, Simple structures with complex symmetry, Arrow's theorem, countably many agents, and more visible invisible dictators, Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures, A bounded jump for the bounded Turing degrees, Some reducibilities and splittings of recursively enumerable sets, The d.r.e. degrees are not dense, Automorphisms of the lattice of recursively enumerable sets: Orbits, Myhill's work in recursion theory, On co-simple isols and their intersection types, The complexity of primes in computable unique factorization domains, Nondiamond theorems for polynomial time reducibility, Algorithmic randomness and Fourier analysis, The \(n\)-rea enumeration degrees are dense, Bounds on the strength of ordinal definable determinacy in small admissible sets, A blend of methods of recursion theory and topology: a \(\Pi_1^0\) tree of shadow points, Combinatorial principles between \(\text{RRT}_2^2\) and \(\text{RT}_2^2\), Completely mitotic c.e. degrees and non-jump inversion, A Banach-Mazur computable but not Markov computable function on the computable real numbers, Isolation in the CEA hierarchy, Scattered linear orderings with no computable presentation, Limitwise monotonic functions relative to the Kleene's ordinal notation system, Codings on linear orders and algorithmic independence of natural relations, On computably enumerable structures, Outline of partial computability in computable topology, On higher effective descriptive set theory, Joining to high degrees via noncuppables, The limitations of cupping in the local structure of the enumeration degrees, On computational complexity and honest polynomial degrees, R.e. Prime powers and total rigidity, Bounded Turing reductions and data processing inequalities for sequences, Upper semilattice of recursively enumerable sQ-degrees, Analogues of Rice's theorem for semantic classes of propositions, Index sets of quotient objects of the Post numeration, Turing degrees of certain isomorphic images of computable relations, Approximation methods in inductive inference, Point-free topological spaces, functions and recursive points; filter foundation for recursive analysis. I, Splitting theorems and the jump operator, Learning via queries and oracles, Partial decidable presentations in hyperarithmetic, Discrete families of recursive functions and index sets, Recursive and nonextendible functions over the reals; filter foundation for recursive analysis. II, Unified characterizations of lowness properties via Kolmogorov complexity, Abelian \(p\)-groups and autostability relative to an oracle, Computability-theoretic properties of injection structures, \(\Sigma_{2}^{0}\)-initial segments of computable linear orders, Cappable recursively enumerable degrees and Post's program, Computational foundations of basic recursive function theory, Splitting theorems in recursion theory, Non-uniformity and generalised Sacks splitting, Gap-definable counting classes, Recursive versus recursively enumerable binary relations, Extremes in the degrees of inferability, \(Q\)-reducibility and \(m\)-reducibility on computably enumerable sets, Effectively closed sets and graphs of computable real functions., Presentations of computably enumerable reals., Inductive inference with additional information.
