Post's program and incomplete recursively enumerable sets.
AUTOR(ES)
Harrington, L
RESUMO
A set A of nonnegative integers is recursively enumerable (r.e.) if A can be computably listed. It is shown that there is a first-order property, Q(X), definable in E, the lattice of r.e. sets under inclusion, such that (i) if A is any r.e. set satisfying Q(A) then A is nonrecursive and Turing incomplete and (ii) there exists an r.e. set A satisfying Q(A). This resolves a long open question stemming from Post's program of 1944, and it sheds light on the fundamental problem of the relationship between the algebraic structure of an r.e. set A and the (Turing) degree of information that A encodes.
ACESSO AO ARTIGO
http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=52904Documentos Relacionados
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
- LSD therapy in Dutch psychiatry: changing socio-political settings and medical sets.
- det1, cop1, and cop9 mutations cause inappropriate expression of several gene sets.
- Segregation patterns of endogenous mouse mammary tumor viruses in five recombinant inbred strain sets.
- Directional mutation pressure and transfer RNA in choice of the third nucleotide of synonymous two-codon sets.