کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4661711 1633452 2015 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cone avoidance and randomness preservation
ترجمه فارسی عنوان
اجتناب مخروطی و حفظ تصادفی
کلمات کلیدی
تصادف الگوریتمی؛ پیچیدگی کلموگروف؛ قضایای پایه؛ PA-کامل؛ K-triviality؛ تصادفی جزئی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

Let X be an infinite sequence of 0's and 1's. Let f be a computable function. Recall that X is strongly f-random if and only if the a priori Kolmogorov complexity of each finite initial segment τ of X   is bounded below by f(τ)f(τ) minus a constant. We study the problem of finding a PA-complete Turing oracle which preserves the strong f-randomness of X while avoiding a Turing cone. In the context of this problem, we prove that the cones which cannot always be avoided are precisely the K-trivial ones. We also prove: (1) If f is convex and X is strongly f-random and Y is Martin-Löf random relative to X, then X is strongly f-random relative to Y. (2) X is complex relative to some oracle if and only if X is random with respect to some continuous probability measure.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 166, Issue 6, June 2015, Pages 713–728
نویسندگان
, ,