Recursively enumerable sets and degrees (Q4184825)

scientific article; zbMATH DE number 3621704

Language	Label	Description	Also known as
English	Recursively enumerable sets and degrees	scientific article; zbMATH DE number 3621704

Statements

instance of

scholarly article

0 references

title

Recursively enumerable sets and degrees (English)

0 references

author

Robert I. Soare

0 references

published in

Bulletin of the American Mathematical Society

0 references

publication date

1978

0 references

zbMATH Keywords

Recursively Enumerable Sets and Degrees

0 references

Relative Recursiveness

0 references

Inclusion Lattice

0 references

Upper Semilattice

0 references

Degrees of Unsolvability

0 references

Jump Operation

0 references

Survey

0 references

Simple Set

0 references

Incompleteness

0 references

Maximal Set

0 references

Infinite Injury Priority Method

0 references

Embedding Conjecture

0 references

Undecidability

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Some lowness properties and computational complexity sequences

0 references

Q4753364

0 references

Q5532570

0 references

On complexity properties of recursively enumerable sets

0 references

Q5825667

0 references

The word problem

0 references

Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups

0 references

A lattice property of Post's simple set

0 references

An Unsolvable Problem of Elementary Number Theory

0 references

Minimal Upper Bounds for Sequences of Recursively Enumerable Degrees

0 references

Degrees of unsolvability complementary between recursively enumerable degrees, Part 1

0 references

Jump equivalence of the Δ20 hyperimmune sets

0 references

Minimal pairs and high recursively enumerable degrees

0 references

Q3247126

0 references

Hilbert's Tenth Problem is Unsolvable

0 references

Hypersimple sets with retraceable complements

0 references

Two Notes on Recursively Enumerable Sets

0 references

A Theorem on Hypersimple Sets

0 references

Productive Sets

0 references

Some Theorems on Classes of Recursively Enumerable Sets

0 references

Retraceable Sets

0 references

Q5596792

0 references

Q4436303

0 references

Degrees of unsolvability associated with classes of formalized theories

0 references

TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)

0 references

A criterion for completeness of degrees of unsolvability

0 references

Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication

0 references

Reducibility and Completeness for Sets of Integers

0 references

On subcreative sets and S-reducibility

0 references

The class of recursively enumerable subsets of a recursively enumerabl e set

0 references

The Halting Problem Relativized to Complements

0 references

The degrees of hyperhyperimmune sets

0 references

Relationships Between Reducibilities

0 references

Degrees in Which the Recursive Sets are Uniformly Recursive

0 references

Π10 classes and Boolean combinations of recursively enumerable sets

0 references

A minimal pair of Π10 classes

0 references

Degrees of members of $\Pi_ 1^ 0$ classes

0 references

∏ 0 1 Classes and Degrees of Theories

0 references

Post's problem and his hypersimple set

0 references

Constructive Analogues of the Group of Permutations of the Natural Numbers

0 references

A Theory of Positive Integers in Formal Logic. Part I

0 references

General recursive functions of natural numbers

0 references

Q5812175

0 references

The upper semi-lattice of degrees of recursive unsolvability

0 references

Some Notions of Reducibility and Productiveness

0 references

On a Problem of G. E. Sacks

0 references

A note on universal sets

0 references

The impossibility of finding relative complements for recursively enumerable degrees

0 references

Lower Bounds for Pairs of Recursively Enumerable Degrees

0 references

The Priority Method I

0 references

Complete Recursively Enumerable Sets

0 references

On the Lattice of Recursively Enumerable Sets

0 references

The elementary theory of recursively enumerable sets

0 references

Distributive Initial Segments of the Degrees of Unsolvability

0 references

Degrees of recursively enumerable sets which have no maximal supersets

0 references

On some games which are relevant to the theory of recursively enumerable sets

0 references

Recursively enumerable many-one degrees

0 references

A recursively enumerable degree which will not split over all lesser ones

0 references

Uniform enumeration operations

0 references

w tt-Complete Sets are not Necessarily tt-Complete

0 references

Bounding minimal pairs

0 references

A Completely Mitotic Nonrecursive R.E. Degree

0 references

Mitotic recursively enumerable sets

0 references

The weak truth table degrees of recursively enumerable sets

0 references

Recursive Functions Modulo Co-r-Maximal Sets

0 references

Turing degrees and many-one degrees of maximal sets

0 references

Some theorems on R-maximal sets and major subsets of recursively enumerable sets

0 references

Congruence relations, filters, ideals, and definability in lattices of α-recursively enumerable sets

0 references

Q4044555

0 references

On elementary theories of some lattices or α-recursively enumerable sets

0 references

A Decidable Fragment of the Elementary Theory of the Lattice of Recursively Enumerable Sets

0 references

d-simple sets, small sets, and degree classes

0 references

$r$-maximal major subsets

0 references

A theorem on hyperhypersimple sets

0 references

Completeness, the Recursion Theorem, and Effectively Simple Sets

0 references

Classes of Recursively Enumerable Sets and Degrees of Unsolvability

0 references

On a question of G. E. Sacks

0 references

The Degrees of Hyperimmune Sets

0 references

Axiomatizable theories with few axiomatizable extensions

0 references

On a Class of Complete Simple Sets

0 references

Recursively enumerable vector spaces

0 references

On Group-Theoretic Decision Problems and Their Classification. (AM-68)

0 references

Boolean algebras, splitting theorems, and $Δ^0_2$ sets

0 references

Creative sets

0 references

Recursion, metarecursion, and inclusion

0 references

Recursively enumerable sets of positive integers and their decision problems

0 references

Classes of Recursively Enumerable Sets and Their Decision Problems

0 references

On completely recursively enumerable classes and their key arrays

0 references

Two Theorems on Hyperhypersimple Sets

0 references

Simplicity of recursively enumerable sets

0 references

A Dichotomy of the Recursively Enumerable Sets

0 references

Interpolation and embedding in the recursively enumerable degrees

0 references

Jump restricted interpolation in the recursively enumerable degrees

0 references

Computing degrees of unsolvability

0 references

A minimal degree less than 0’

0 references

On the degrees less than 0'

0 references

Recursive Enumerability and the Jump Operator

0 references

A maximal set which is not complete

0 references

The recursively enumerable degrees are dense

0 references

A Simple Set Which is Not Effectively Simple

0 references

Degrees of Unsolvability. (AM-55)

0 references

On a Theorem of Lachlan and Martin

0 references

Deficiency Sets and Bounded Information Reducibilities

0 references

Quasicreative Sets

0 references

On degrees of unsolvability

0 references

Undecidable and creative theories

0 references

Q5586291

0 references

The decision problem for recursively enumerable degrees

0 references

Degrees of classes of RE sets

0 references

Nowhere simple sets and the lattice of recursively enumerable sets

0 references

Determining Automorphisms of the Recursively Enumerable Sets

0 references

Effectively Simple Sets

0 references

The Friedberg-Muchnik Theorem Re-Examined

0 references

Automorphisms of the lattice of recursively enumerable sets

0 references

Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets

0 references

The infinite injury priority method

0 references

Q4040892

0 references

Post's program and incomplete recursively enumerable sets.

0 references

Computational complexity, speedable and levelable sets

0 references

On degrees of recursive unsolvability

0 references

Q5596776

0 references

Sublattices of the Recursively Enumerable Degrees

0 references

On Computable Numbers, with an Application to the Entscheidungsproblem

0 references

[Russian Text Ignored]

0 references

Recursively Enumerable Sets and Retracing Functions

0 references

Three theorems on the degrees of recursively enumerable sets

0 references

A minimal pair of recursively enumerable degrees

0 references

On the Degrees of Index Sets

0 references

On the Degrees of Index Sets. II

0 references

Prioric games and minimal degrees below $0^{(1)}$

0 references

Banach–Mazur games, comeager sets and degrees of unsolvability

0 references

Identifiers

zbMATH Open document ID

0401.03018

0 references

DOI

10.1090/S0002-9904-1978-14552-2

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4184825