Jove
Visualize
Contact Us
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

Related Experiment Videos

Algebraic aspects of the computably enumerable degrees.

T A Slaman1, R I Soare

  • 1Department of Mathematics, University of Chicago, Chicago, IL 60637, USA.

Proceedings of the National Academy of Sciences of the United States of America
|January 17, 1995
PubMed
Summary

This study introduces new methods to solve the extension of embedding problem for computably enumerable (c.e.) degrees. The research concludes that the full extension of embedding problem is decidable, advancing computability theory.

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

Post's program and incomplete recursively enumerable sets.

Proceedings of the National Academy of Sciences of the United States of America·1991
See all related articles

Area of Science:

  • Computability Theory
  • Set Theory
  • Mathematical Logic

Background:

  • Computably enumerable (c.e.) sets are fundamental in computability theory.
  • Turing degrees classify the complexity of c.e. sets.
  • The extension of embedding problem investigates structural properties of c.e. degrees.

Purpose of the Study:

  • To extend and unify existing results on embedding problems in c.e. degrees.
  • To develop complete criteria for analyzing extension and nonextension instances.
  • To determine the decidability of the full extension of embedding problem.

Main Methods:

  • Development of novel criteria and techniques for analyzing embeddings.
  • Unification of proofs for extension and nonextension theorems.

Related Experiment Videos

  • Algorithmic analysis of partially ordered sets within c.e. degrees.

    • Main Results:

    • Complete and complementary criteria for extension and nonextension are established.
    • A unified approach to a significant class of theorems in the field is presented.
    • The full extension of embedding problem for c.e. degrees is proven to be decidable.

    Conclusions:

    • The decidability of the full extension of embedding problem offers a significant advancement.
    • The developed techniques provide a comprehensive framework for studying c.e. degrees.
    • This research enhances algebraic insights into the structure of computability.