Jove
Visualize
Contact Us

Related Experiment Videos

Post's program and incomplete recursively enumerable sets.

L Harrington1, R I Soare

  • 1Department of Mathematics, University of California, Berkeley, CA 94720, USA.

Proceedings of the National Academy of Sciences of the United States of America
|November 15, 1991
PubMed
Summary

Researchers found a specific property for computably listable sets. Sets with this property are nonrecursive and Turing incomplete, answering a question from Post's 1944 program.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Listeria Meningitis, one of your five a day? A case report of Listeria Monocytogenes Meningitis in a fit and well 62-year-old woman.

Acute medicine·2023
Same author

Attitudes of women with gestational diabetes toward diet and exercise: a qualitative study.

The journal of maternal-fetal & neonatal medicine : the official journal of the European Association of Perinatal Medicine, the Federation of Asia and Oceania Perinatal Societies, the International Society of Perinatal Obstetricians·2023
Same author

Developing priorities for quality improvement in acute medicine using a modified Delphi method A consensus process hosted by the Society for Acute Medicine Quality Improvement Committee (SAM-QI).

Acute medicine·2022
Same author

A Qualitative Evaluation of a Simulation Training Initiative for Registrars Working in Acute Medicine.

Acute medicine·2022
Same author

AeDES: a next-generation monitoring and forecasting system for environmental suitability of Aedes-borne disease transmission.

Scientific reports·2020
Same author

Opioid analgesia and the somatosensory memory of neonatal surgical injury in the adult rat.

British journal of anaesthesia·2018
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Area of Science:

  • Computability Theory
  • Set Theory
  • Mathematical Logic

Background:

  • Recursively enumerable (r.e.) sets are fundamental in computability theory.
  • Post's program (1944) investigated the relationship between algebraic properties of r.e. sets and their computational complexity.
  • A long-standing question concerned the existence of r.e. sets with specific structural properties that imply computational limitations.

Purpose of the Study:

  • To determine if a first-order property exists within the lattice of r.e. sets that characterizes nonrecursive and Turing incomplete sets.
  • To resolve a key open problem originating from Post's foundational work.
  • To explore the connection between the algebraic structure of r.e. sets and the information they encode.

Main Methods:

  • Defined a first-order property, Q(X), within E, the lattice of r.e. sets ordered by inclusion.

Related Experiment Videos

  • Investigated the implications of satisfying property Q(X) for an r.e. set A.
  • Demonstrated the existence of at least one r.e. set satisfying Q(X).

    • Main Results:

    • Established the existence of a first-order property Q(X) in the lattice of r.e. sets.
    • Proved that any r.e. set A satisfying Q(A) must be nonrecursive.
    • Proved that any r.e. set A satisfying Q(A) must be Turing incomplete.
    • Confirmed the existence of such an r.e. set A satisfying Q(A).

    Conclusions:

    • The study confirms the existence of r.e. sets with specific structural properties that necessitate computational incompleteness.
    • This finding resolves a significant open question in computability theory dating back to Post's program.
    • The results provide new insights into how the algebraic structure of r.e. sets relates to the Turing degrees they represent.