اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDiagonally non-computable functions and fireworks
204
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A set C of reals is said to be negligible if there is no probabilistic algorithm which generates a member of C with positive probability. Various classes have been proven to be negligible, for example the Turing upper-cone of a non-computable real, the class of coherent completions of Peano Arithmetic or the class of reals of minimal degrees. One class of particular interest in the study of negligibility is the class of diagonally non-computable (DNC) functions, proven by Kucera to be non-negligible in a strong sense: every Martin-Lof random real computes a DNC function. Ambos-Spies et al. showed that the converse does not hold: there are DNC functions which compute no Martin-Lof random real. In this paper, we show that such the set of such DNC functions is in fact non-negligible. More precisely, we prove that for every sufficiently fast-growing computable~$h$, every 2-random real computes an $h$-bounded DNC function which computes no Martin-Lof random real. Further, we show that the same holds for the set of reals which compute a DNC function but no bounded DNC function. The proofs of these results use a combination of a technique due to Kautz (which, following a metaphor of Shen, we like to call a `fireworks argument) and bushy tree forcing, which is the canonical forcing notion used in the study of DNC functions.
قيم البحث
اقرأ أيضاً
We investigate computable metrizability of Polish spaces up to homeomorphism. In this paper we focus on Stone spaces. We use Stone duality to construct the first known example of a computable topological Polish space not homeomorphic to any computabl
y metrized space. In fact, in our proof we construct a right-c.e. metrized Stone space which is not homeomorphic to any computably metrized space. Then we introduce a new notion of effective categoricity for effectively compact spaces and prove that effectively categorical Stone spaces are exactly the duals of computably categorical Boolean algebras. Finally, we prove that, for a Stone space $X$, the Banach space $C(X;mathbb{R})$ has a computable presentation if, and only if, $X$ is homeomorphic to a computably metrized space. This gives an unexpected positive partial answer to a question recently posed by McNicholl.
In this paper, we investigate connections between structures present in every generic extension of the universe $V$ and computability theory. We introduce the notion of {em generic Muchnik reducibility} that can be used to to compare the complexity o
f uncountable structures; we establish basic properties of this reducibility, and study it in the context of {em generic presentability}, the existence of a copy of the structure in every extension by a given forcing. We show that every forcing notion making $omega_2$ countable generically presents some countable structure with no copy in the ground model; and that every structure generically presentble by a forcing notion that does not make $omega_2$ countable has a copy in the ground model. We also show that any countable structure $mathcal{A}$ that is generically presentable by a forcing notion not collapsing $omega_1$ has a countable copy in $V$, as does any structure $mathcal{B}$ generically Muchnik reducible to a structure $mathcal{A}$ of cardinality $aleph_1$. The former positive result yields a new proof of Harringtons result that counterexamples to Vaughts conjecture have models of power $aleph_1$ with Scott rank arbitrarily high below $omega_2$. Finally, we show that a rigid structure with copies in all generic extensions by a given forcing has a copy already in the ground model.
We obtain a computable structure of Scott rank omega_1^{CK} (call this ock), and give a general coding procedure that transforms any hyperarithmetical structure A into a computable structure A such that the rank of A is ock, ock+1, or < ock iff the same is true of A.
We continue the study of computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree
structure. Our main result shows that although ${omega cdot 2, omega^star cdot 2}$ is computably embeddable in ${omega^2, {(omega^2)}^star}$, the class ${omega cdot k,omega^star cdot k}$ is emph{not} computably embeddable in ${omega^2, {(omega^2)}^star}$ for any natural number $k geq 3$.
We study computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree structure. Our m
ain result shows that ${omega cdot k,omega^star cdot k}$ is computably embeddable in ${omega cdot t, omega^star cdot t}$ iff $k$ divides $t$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
