اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدBad oracles in higher computability and randomness
112
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Many constructions in computability theory rely on time tricks. In the higher setting, relativising to some oracles shows the necessity of these. We construct an oracle~$A$ and a set~$X$, higher Turing reducible to~$X$, but for which $Psi(A) e X$ for any higher functional~$Psi$ which is consistent on all oracles. We construct an oracle~$A$ relative to which there is no universal higher ML-test. On the other hand, we show that badness has its limits: there are no higher self-PA oracles, and for no~$A$ can we construct a higher $A$-c.e. set which is also higher $A$-ML-random. We study various classes of bad oracles and differentiate between them using other familiar classes. For example, bad oracles for consistent reductions can be higher ML-random, whereas bad oracles for universal tests cannot.
قيم البحث
اقرأ أيضاً
Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to image distribution if and only if it has a
random preimage. This result (for computable distributions and mappings, and Martin-Lof randomness) was known for a long time (folklore); in this paper we prove its natural generalization for layerwise computable mappings, and discuss the related quantitative results.
We investigate the role of continuous reductions and continuous relativisation in the context of higher randomness. We define a higher analogue of Turing reducibility and show that it interacts well with higher randomness, for example with respect to
van-Lambalgens theorem and the Miller-Yu / Levin theorem. We study lowness for continuous relativization of randomness, and show the equivalence of the higher analogues of the different characterisations of lowness for Martin-Lof randomness. We also characterise computing higher $K$-trivial sets by higher random sequences. We give a separation between higher notions of randomness, in particular between higher weak-2-randomness and $Pi^1_1$-randomness. To do so we investigate classes of functions computable from Kleenes~$O$ based on strong forms of the higher limit lemma.
Randomness plays a central rol in the quantum mechanical description of our interactions. We review the relationship between the violation of Bell inequalities, non signaling and randomness. We discuss the challenge in defining a random string, and s
how that algorithmic information theory provides a necessary condition for randomness using Borel normality. We close with a view on incomputablity and its implications in physics.
We investigate the effectivizations of several equivalent definitions of quasi-Polish spaces and study which characterizations hold effectively. Being a computable effectively open image of the Baire space is a robust notion that admits several chara
cterizations. We show that some natural effectivizations of quasi-metric spaces are strictly stronger.
We study the computational content of the Radon-Nokodym theorem from measure theory in the framework of the representation approach to computable analysis. We define computable measurable spaces and canonical representations of the measures and the i
ntegrable functions on such spaces. For functions f,g on represented sets, f is W-reducible to g if f can be computed by applying the function g at most once. Let RN be the Radon-Nikodym operator on the space under consideration and let EC be the non-computable operator mapping every enumeration of a set of natural numbers to its characteristic function. We prove that for every computable measurable space, RN is W-reducible to EC, and we construct a computable measurable space for which EC is W-reducible to RN.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
