The minimum degree of recursively representable choice functions
Mathematical Social SciencesPublished 1 October 1985
Alain A. Lewis
Citations29
SJR quartileQ1
SJR score0.58
SNIP0.77
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The minimum degree of Turing complexity of a recursively representable choice function is O, the degree of a complete ∑ 2 set in the Kleene-Mostowski hierarchy, which is bounded strictly above the degrees of R.E. subsets on N.
Abstract
We show that the minimum degree of Turing complexity of a recursively representable choice function is Õ″, the degree of a complete ∑2 set in the Kleene-Mostowski hierarchy. A consequence of this result is that the complexity of such choice functions in this sense is bounded strictly above the degrees of R.E. subsets on N.
Keywords
Computer ScienceMathematics
Bulletin of the American Mathematical SocietyRecursively enumerable sets of positive integers and their decision problems
885 Citations1944Emil L. Post
Transactions of the American Mathematical SocietyRecursive predicates and quantifiers
341 Citations1943S. C. Kleene
Annals of MathematicsThe Upper Semi-Lattice of Degrees of Recursive Unsolvability
275 Citations1954S. C. Kleene, Emil L. Post
The concept 'degree of recursive unsolvability' was introduced briefly in Post [16], and in his abstract [17] the concept was formulated precisely via an extension of [15], and a resulting partial scale of degrees of recursiveUnsolvability was applied to strengthen Theorem II of Kleene [8].
Mathematical Social SciencesOn effectively computable realizations of choice functions
99 Citations1985Alain A. Lewis
Journal of Mathematical EconomicsUtility theory based on rational probabilities
24 Citations1980J. C. Shepherdson
Theoretical Computer ScienceThe Turing degree of the inherent ambiguity problem for context-free languages
8 Citations1975Ann Reedy, Walter J. Savitch
The inherent ambiguity question for context-free languages is shown to be in the Turing degree of unsolvability O’, which is equivalent to the finiteness question for r.e. sets which is in degree O”.