THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY.
The article discusses the computational content of intrinsic density and proves that sets with intrinsic density 0 exist either high Turing degrees or compute a diagonally non-computable function. It proves that sets with intrinsic lower density 0 exist in every noncomputable Turing degree and sets...
| Publicado en: | Journal of Symbolic Logic Vol. 83; no. 2; pp. 817 - 829 |
|---|---|
| Autor principal: | |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Jun2018
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| Sumario: | The article discusses the computational content of intrinsic density and proves that sets with intrinsic density 0 exist either high Turing degrees or compute a diagonally non-computable function. It proves that sets with intrinsic lower density 0 exist in every noncomputable Turing degree and sets with intrinsic desnity 0 have more computational content.It uses reverse mathematics to demonstrate existence of set with intrinsic 0. |
|---|