Zobrazeno 1 - 10
of 33
pro vyhledávání: '"BARBARA F. CSIMA"'
Publikováno v:
The Journal of Symbolic Logic. :1-25
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0229f616d00c22b9515100baa516f7e0
https://doi.org/10.1017/jsl.2023.26
https://doi.org/10.1017/jsl.2023.26
Autor:
Barbara F. Csima, Keng Meng Ng
Publikováno v:
Journal of Mathematical Logic. 22
A strong degree of categoricity is a Turing degree [Formula: see text] such that there is a computable structure [Formula: see text] that is [Formula: see text]-computably categorical (there is a [Formula: see text]-computable isomorphism between any
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7f7e7f4f37b28b42c34e8c2fa610264e
https://doi.org/10.1142/s0219061322500222
https://doi.org/10.1142/s0219061322500222
Publikováno v:
Computability. 9:127-137
A computable structure $\mathcal{A}$ has degree of categoricity $\mathbf{d}$ if $\mathbf{d}$ is exactly the degree of difficulty of computing isomorphisms between isomorphic computable copies of $\mathcal{A}$. Fokina, Kalimullin, and Miller showed th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c9faf8ce17870d57905c294d30d9b7ef
https://doi.org/10.3233/com-190254
https://doi.org/10.3233/com-190254
Publikováno v:
The Journal of Symbolic Logic
The Journal of Symbolic Logic, Association for Symbolic Logic, 2021, pp.1-20. ⟨10.1017/jsl.2021.58⟩
The Journal of Symbolic Logic, Association for Symbolic Logic, 2021, pp.1-20. ⟨10.1017/jsl.2021.58⟩
The $\Omega $ numbers—the halting probabilities of universal prefix-free machines—are known to be exactly the Martin-Löf random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-Löf random left-c.e. real $\alpha $ , a un
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2b961baf1b147d91e7d66512e916e11a
http://arxiv.org/abs/2111.01472
http://arxiv.org/abs/2111.01472
Autor:
Barbara F. Csima, Damir D. Dzhafarov, Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Reed Solomon, Linda Brown Westrick
Publikováno v:
Computability. 8:253-263
Hindman's Theorem (HT) states that for every coloring of $\mathbb N$ with finitely many colors, there is an infinite set $H \subseteq \mathbb N$ such that all nonempty sums of distinct elements of $H$ have the same color. The investigation of restric
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4ae21f00d861ee0575faf36339721904
https://doi.org/10.3233/com-180094
https://doi.org/10.3233/com-180094
Autor:
Jonathan Stephenson, Barbara F. Csima
Publikováno v:
Annals of Pure and Applied Logic. 170:58-94
We first give an example of a rigid structure of computable dimension 2 such that the unique isomorphism between two non-computably isomorphic computable copies has Turing degree strictly below 0 ″ , and not above 0 ′ . This gives a first example
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0a34b83b01489705cc8d1f565f1ff0c5
https://doi.org/10.1016/j.apal.2018.08.012
https://doi.org/10.1016/j.apal.2018.08.012
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030800482
CiE
CiE
We study reductions well suited to compare structures and classes of structures with respect to properties based on enumeration reducibility. We introduce the notion of a positive enumerable functor and study the relationship with established reducti
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3a60de8eb82ca1157971db586329ac45
https://doi.org/10.1007/978-3-030-80049-9_38
https://doi.org/10.1007/978-3-030-80049-9_38
Publikováno v:
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society, American Mathematical Society, 2020, 373, pp.1983-2006. ⟨10.1090/tran/7972⟩
Transactions of the American Mathematical Society, American Mathematical Society, 2020, 373, pp.1983-2006. ⟨10.1090/tran/7972⟩
The rate of randomness (or dimension) of a string $\sigma$ is the ratio $C(\sigma)/|\sigma|$ where $C(\sigma)$ is the Kolmogorov complexity of $\sigma$. While it is known that a single computable transformation cannot increase the rate of randomness
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8f995dc05f558e34da974b238fb10bad
https://hal.archives-ouvertes.fr/hal-02392727
https://hal.archives-ouvertes.fr/hal-02392727
Publikováno v:
Archive for Mathematical Logic. 56:507-521
Anderson and Csima (Notre Dame J Form Log 55(2):245–264, 2014) defined a jump operator, the bounded jump, with respect to bounded Turing (or weak truth table) reducibility. They showed that the bounded jump is closely related to the Ershov hierarch
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e8cf7456abd8468e3d12423e3f2bbad1
https://doi.org/10.1007/s00153-017-0537-8
https://doi.org/10.1007/s00153-017-0537-8
Publikováno v:
The Journal of Symbolic Logic. 82:325-346
We investigate the complexity of isomorphisms of computable structures on cones in the Turing degrees. We show that, on a cone, every structure has a strong degree of categoricity, and that degree of categoricity is${\rm{\Delta }}_\alpha ^0 $-complet
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::431b6e0ffe52e41ab4f1a5f789c98cdb
https://doi.org/10.1017/jsl.2016.43
https://doi.org/10.1017/jsl.2016.43