Recursively enumerable sets of positive integers and their decision problems

From MaRDI portal
Revision as of 05:42, 7 March 2024 by Import240305080351 (talk | contribs) (Created automatically from import240305080351)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Publication:5845382

DOI10.1090/S0002-9904-1944-08111-1zbMath0063.06328OpenAlexW2045033949WikidataQ55881466 ScholiaQ55881466MaRDI QIDQ5845382

E. L. Post

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




Related Items (only showing first 100 items - show all)

On speedable and levelable vector spacesReductions among polynomial isomorphism typesA class of hypersimple incomplete setsNonhemimaximal degrees and the high/low hierarchyModel checking mobile ambientsUncertainty, predictability and decidability in chaotic dynamical systemsCompleteness of the hyperarithmetic isomorphism equivalence relationAlmost every set in exponential time is P-bi-immuneOn simple and creative sets in NPUnsolvable algorithmic problems for semigroups, groups and ringsOn the classification of recursive languagesThere is no fat orbitFormalism and intuition in computabilityOn the Hardness of Almost–Sure TerminationRepresentation 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) gamesComputational processes, observers and Turing incompletenessMass problems and densityStructure of the upper semilattice of recursively enumerable m-degrees and related questions. INot every finite lattice is embeddable in the recursively enumerable degreesTuring degrees of hypersimple relations on computable structuresHyperhypersimple sets and Q1 -reducibilityClosed left-r.e. setsComplexity of graph embeddability problemsExtending and interpreting Post's programmeOn \(n\)-tardy setsSyntactic structures and recursive devices: a legacy of imprecisionOn the mathematical foundations of \textit{Syntactic structures}Recursion-theoretic ranking and compressionSome observations on NP real numbers and P-selective setsImmunity and pseudorandomness of context-free languagesA personal account of Turing's imprint on the development of computer scienceSome undecidable determined gamesUndecidability and incompleteness in classical mechanicsThe modal argument for hypercomputing mindsOn the hardness of analyzing probabilistic programsOn Lachlan's major sub-degree problemDoes truth-table of linear norm reduce the one-query tautologies to a random oracle?Myhill's work in recursion theoryBi-immunity over different size alphabetsOn the structures inside truth-table degreesAutomorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degreesIncomparable prime ideals of recursively enumerable degreesThe distribution of the generic recursively enumerable degreesDirect product primality testing of graphs is GI-hardThings that can be made into themselvesAn explicit solution to Post's problem over the realsComputably enumerable sets and related issuesGödel's reception of Turing's model of computability: the shift of perception in 1934Hypothesis spaces for learningSmall \(\Pi^{0}_{1}\) classesSurvey of polynomial transformations between NP-complete problemsA comparison of polynomial time reducibilitiesPolynomial and abstract subrecursive classesWeakly useful sequencesIsomorphic implicationtt- and m-degreesEffective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple setsStrong and weak reducibility of algorithmic problems1\(r\)-maximal major subsetsConstructive dimension and Turing degreesOne class of partial setsLattice nonembeddings and intervals of the recursively enumerable degreesThe origins of the halting problemA hierarchy below the halting problem for additive machinesPrescribed learning of r.e. classesCook reducibility is faster than Karp reducibility in NPInvestigations Concerning the Structure of Complete SetsOn \(1\)-degrees inside \(m\)-degreesAn answer to a question by P. R. YoungInitial segments of the degrees of size \(\aleph _ 1\)Effectively hyperimmune sets and majorantsComputable permutations and word problemsOn the reducibility of \(\Pi_ 1^ 1\) setsClasses of recursively enumerable sets and Q-reducibilityHyperhypersimple sets and \(\Delta _ 2\) systemsTuring oracle machines, online computing, and three displacements in computability theoryThe use of lists in the study of undecidable problems in automata theoryThe factorial function for isolsCall-by-value lambda calculus as a model of computation in CoqComputing degrees of unsolvabilityRecursive digraphs, splinters and cylindersEmergence as a computability-theoretic phenomenonUncomputability and undecidability in economic theoryOn effectively hypersimple setsRepresentation of one-one degrees by decision problems for system functionsThe density of the nonbranching degreesResource bounded immunity and simplicityUndecidability of Model Checking in Brane LogicCappable recursively enumerable degrees and Post's programThe relative power of logspace and polynomial time reductionsOn trees without hyperimmune branchesModel-theoretic and algorithmic questions in group theorySplitting theorems in recursion theoryGraphs realised by r.e. equivalence relationsA reducibility related to being hyperimmune-freeTAMING THE INCOMPUTABLE, RECONSTRUCTING THE NONCONSTRUCTIVE AND DECIDING THE UNDECIDABLE IN MATHEMATICAL ECONOMICS\(Q\)-reducibility and \(m\)-reducibility on computably enumerable setsThe minimum degree of recursively representable choice functionsDegree structures of conjunctive reducibility







This page was built for publication: Recursively enumerable sets of positive integers and their decision problems