Zobrazeno 1 - 10
of 253
pro vyhledávání: '"Hyperarithmetical theory"'
Autor:
Andrew Lewis-Pye
Publikováno v:
Computability. 7:189-235
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::454a7fa227eee09a7b90128b652dff86
https://doi.org/10.3233/com-170068
https://doi.org/10.3233/com-170068
Autor:
A. I. Stukachev
Publikováno v:
Algebra and Logic. 55:507-526
We consider the class of approximation spaces generated by admissible sets, in particular by hereditarily finite superstructures over structures. Generalized computability on approximation spaces is conceived of as effective definability in dynamic l
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9d4ea59b8a7e09aa12870ce56743a8bb
https://doi.org/10.1007/s10469-017-9421-1
https://doi.org/10.1007/s10469-017-9421-1
Autor:
Alberto Ciaffaglione
Publikováno v:
Science of Computer Programming. 126:31-51
We adopt corecursion and coinduction to formalize Turing Machines and their operational semantics in the Coq proof assistant. By combining the formal analysis of converging and diverging computations, via big-step and small-step predicates, our appro
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::906f09e2c6fc73912a2eb4b0ef174a19
https://doi.org/10.1016/j.scico.2016.02.004
https://doi.org/10.1016/j.scico.2016.02.004
Autor:
Barbara F. Csima, Carolyn Knoll
Publikováno v:
Annals of Pure and Applied Logic. 166:1365-1381
How do we compare the complexities of various classes of structures? The Turing ordinal of a class of structures, introduced by Jockusch and Soare, is defined in terms of the number of jumps required for coding to be possible. The back-and-forth ordi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::419ef3941ee34303021b1ec97443b74b
https://doi.org/10.1016/j.apal.2015.08.001
https://doi.org/10.1016/j.apal.2015.08.001
Autor:
Daniel Leivant
Publikováno v:
Turing-100
We use notions originating in Computational Complexity to provide insight into the analogies between computational complexity and Higher Recursion Theory. We consider alternating Turing machines, but with a modified, global, definition of acceptance.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f74ab335111072a1ba3a3c5cf101a9f3
https://doi.org/10.29007/t77g
https://doi.org/10.29007/t77g
Autor:
Paolo Cotogno
Publikováno v:
Acta Analytica. 30:275-282
The ‘Turing barrier’ is an evocative image for 0′, the degree of the unsolvability of the halting problem for Turing machines—equivalently, of the undecidability of Peano Arithmetic (PA). The ‘barrier’ metaphor conveys the idea that effec
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::798b0c0e8d456d5ad0d9bb9271cbdf38
https://doi.org/10.1007/s12136-014-0248-2
https://doi.org/10.1007/s12136-014-0248-2
Autor:
Richard A. Shore, Antonio Montalbán
Publikováno v:
Fundamenta Mathematicae. :1-20
We investigate the reverse mathematical strength of Turing determinacy up to 0 which is itself not provable in second order arithmetic.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c01d56992bd0528c60e9f5c1ba88eb8c
https://doi.org/10.4064/fm27-12-2015
https://doi.org/10.4064/fm27-12-2015
Autor:
Frank Stephan, Liang Yu
Publikováno v:
Annals of Pure and Applied Logic. 165:1291-1300
The main topic of the present work is the relation that a set X is strongly hyperimmune-free relative to Y . Here X is strongly hyperimmune-free relative to Y if and only if for every partial X -recursive function p there is a partial Y -recursive fu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::599f3e6f1f27b878fedf9eea61ad74bb
https://doi.org/10.1016/j.apal.2014.04.002
https://doi.org/10.1016/j.apal.2014.04.002
Publikováno v:
Journal of Mathematical Logic. Dec2016, Vol. 16 Issue 2, p-1. 10p.
Publikováno v:
Journal of Mathematical Logic. 16:1650006
Recall that [Formula: see text] is the lattice of Muchnik degrees of nonempty effectively compact sets in Euclidean space. We solve a long-standing open problem by proving that [Formula: see text] is dense, i.e. satisfies [Formula: see text]. Our pro
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::369772afa959d028c2c2f2d47d65e029
https://doi.org/10.1142/s0219061316500069
https://doi.org/10.1142/s0219061316500069