Recursively enumerable sets of positive integers and their decision problems
From MaRDI portal
Publication:5845382
DOI10.1090/S0002-9904-1944-08111-1zbMath0063.06328OpenAlexW2045033949WikidataQ55881466 ScholiaQ55881466MaRDI QIDQ5845382
Publication date: 1944
Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1090/s0002-9904-1944-08111-1
recursively enumerable setsmany-one reducibilityGödel's theoremcreative setssimhyper-simple setscomplete set \(K\)counter-example for unbounded truth-tablesnon-reducibility of creative sets to hyper-simple sets by truth-tables unrestrictednon-reducibility of creative sets to simple sets by bounded truth-tablesone-one reducibility to \(K\)Recursive sets
Recursively (computably) enumerable sets and degrees (03D25) Recursive equivalence types of sets and structures, isols (03D50)
Related Items (only showing first 100 items - show all)
On speedable and levelable vector spaces ⋮ Reductions among polynomial isomorphism types ⋮ A class of hypersimple incomplete sets ⋮ Nonhemimaximal degrees and the high/low hierarchy ⋮ Model checking mobile ambients ⋮ Uncertainty, predictability and decidability in chaotic dynamical systems ⋮ Completeness of the hyperarithmetic isomorphism equivalence relation ⋮ Almost every set in exponential time is P-bi-immune ⋮ On simple and creative sets in NP ⋮ Unsolvable algorithmic problems for semigroups, groups and rings ⋮ On the classification of recursive languages ⋮ There is no fat orbit ⋮ Formalism and intuition in computability ⋮ On the Hardness of Almost–Sure Termination ⋮ Representation theorems for recursively enumerable sets and a conjecture related to Poonen's large subring of \(\mathbb Q\) ⋮ Expository notes on computability and complexity in (arithmetical) games ⋮ Computational processes, observers and Turing incompleteness ⋮ Mass problems and density ⋮ Structure of the upper semilattice of recursively enumerable m-degrees and related questions. I ⋮ Not every finite lattice is embeddable in the recursively enumerable degrees ⋮ Turing degrees of hypersimple relations on computable structures ⋮ Hyperhypersimple sets and Q1 -reducibility ⋮ Closed left-r.e. sets ⋮ Complexity of graph embeddability problems ⋮ Extending and interpreting Post's programme ⋮ On \(n\)-tardy sets ⋮ Syntactic structures and recursive devices: a legacy of imprecision ⋮ On the mathematical foundations of \textit{Syntactic structures} ⋮ Recursion-theoretic ranking and compression ⋮ Some observations on NP real numbers and P-selective sets ⋮ Immunity and pseudorandomness of context-free languages ⋮ A personal account of Turing's imprint on the development of computer science ⋮ Some undecidable determined games ⋮ Undecidability and incompleteness in classical mechanics ⋮ The modal argument for hypercomputing minds ⋮ On the hardness of analyzing probabilistic programs ⋮ On Lachlan's major sub-degree problem ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ Myhill's work in recursion theory ⋮ Bi-immunity over different size alphabets ⋮ On the structures inside truth-table degrees ⋮ Automorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degrees ⋮ Incomparable prime ideals of recursively enumerable degrees ⋮ The distribution of the generic recursively enumerable degrees ⋮ Direct product primality testing of graphs is GI-hard ⋮ Things that can be made into themselves ⋮ An explicit solution to Post's problem over the reals ⋮ Computably enumerable sets and related issues ⋮ Gödel's reception of Turing's model of computability: the shift of perception in 1934 ⋮ Hypothesis spaces for learning ⋮ Small \(\Pi^{0}_{1}\) classes ⋮ Survey of polynomial transformations between NP-complete problems ⋮ A comparison of polynomial time reducibilities ⋮ Polynomial and abstract subrecursive classes ⋮ Weakly useful sequences ⋮ Isomorphic implication ⋮ tt- and m-degrees ⋮ Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets ⋮ Strong and weak reducibility of algorithmic problems1 ⋮ \(r\)-maximal major subsets ⋮ Constructive dimension and Turing degrees ⋮ One class of partial sets ⋮ Lattice nonembeddings and intervals of the recursively enumerable degrees ⋮ The origins of the halting problem ⋮ A hierarchy below the halting problem for additive machines ⋮ Prescribed learning of r.e. classes ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ Investigations Concerning the Structure of Complete Sets ⋮ On \(1\)-degrees inside \(m\)-degrees ⋮ An answer to a question by P. R. Young ⋮ Initial segments of the degrees of size \(\aleph _ 1\) ⋮ Effectively hyperimmune sets and majorants ⋮ Computable permutations and word problems ⋮ On the reducibility of \(\Pi_ 1^ 1\) sets ⋮ Classes of recursively enumerable sets and Q-reducibility ⋮ Hyperhypersimple sets and \(\Delta _ 2\) systems ⋮ Turing oracle machines, online computing, and three displacements in computability theory ⋮ The use of lists in the study of undecidable problems in automata theory ⋮ The factorial function for isols ⋮ Call-by-value lambda calculus as a model of computation in Coq ⋮ Computing degrees of unsolvability ⋮ Recursive digraphs, splinters and cylinders ⋮ Emergence as a computability-theoretic phenomenon ⋮ Uncomputability and undecidability in economic theory ⋮ On effectively hypersimple sets ⋮ Representation of one-one degrees by decision problems for system functions ⋮ The density of the nonbranching degrees ⋮ Resource bounded immunity and simplicity ⋮ Undecidability of Model Checking in Brane Logic ⋮ Cappable recursively enumerable degrees and Post's program ⋮ The relative power of logspace and polynomial time reductions ⋮ On trees without hyperimmune branches ⋮ Model-theoretic and algorithmic questions in group theory ⋮ Splitting theorems in recursion theory ⋮ Graphs realised by r.e. equivalence relations ⋮ A reducibility related to being hyperimmune-free ⋮ TAMING THE INCOMPUTABLE, RECONSTRUCTING THE NONCONSTRUCTIVE AND DECIDING THE UNDECIDABLE IN MATHEMATICAL ECONOMICS ⋮ \(Q\)-reducibility and \(m\)-reducibility on computably enumerable sets ⋮ The minimum degree of recursively representable choice functions ⋮ Degree structures of conjunctive reducibility
This page was built for publication: Recursively enumerable sets of positive integers and their decision problems
