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

The homogeneity conjecture.

R A Shore1

  • 1Department of Mathematics, Cornell University, Ithaca, New York 14853.

Proceedings of the National Academy of Sciences of the United States of America
|September 1, 1979
PubMed
Summary
This summary is machine-generated.

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

Variability in the distribution of weak acid leachable cadmium, chromium, copper, iron, nickel, lead, and zinc in the sediments of the Georges Bank/Gulf of Maine region [USA].

Environmental science & technology·2012
Same author

An Epidemiological Study of Diphtheria in a remote New Zealand Community.

The Journal of hygiene·2010
Same author

Unwanted photon and neutron radiation resulting from collimated photon beams interacting with the body of radiotherapy patients.

Medical physics·1982
Same author

Unwanted radiation produced by leakage neutrons from medical electron accelerators.

Medical physics·1982

This study disproves a long-standing conjecture in computability theory. It demonstrates that the hierarchy of computable function degrees is not isomorphic to the hierarchy of degrees of functions computable from a given function f.

Area of Science:

  • Computability Theory
  • Theoretical Computer Science
  • Logic

Background:

  • The study of computable functions and their degrees is central to computability theory.
  • A well-known conjecture by H. Rogers, Jr. proposed an isomorphism between certain degree orderings.

Purpose of the Study:

  • To investigate the structural properties of Turing degrees.
  • To determine if the ordering of Turing degrees is isomorphic to the ordering of degrees of functions computable from a given function f, where Kleene's O is computable.

Main Methods:

  • The research involves theoretical analysis within computability theory.
  • It utilizes concepts related to Kleene's O and the hierarchy of computable functions.

Main Results:

Related Experiment Videos

  • The study proves that for any function f with computable Kleene's O, the ordering of Turing degrees is not isomorphic to the ordering of degrees of functions from which f is computable.
  • This finding directly refutes a significant conjecture in the field.

Conclusions:

  • The established isomorphism conjecture by H. Rogers, Jr. is disproven.
  • The structural relationship between Turing degrees and degrees of computability from a function f is more complex than previously hypothesized.