جدول پیوندها
چکیده و 1 مقدمه
2 پس زمینه
3 در مورد قانون رشد آهسته
4 عضو کلاس Deep Π0 1
5 عمق قوی ناچیز است
6 نوع از عمق قوی
مراجع
پیوست A. اثبات لم 3
6. انواع عمق قوی
اثبات. فرض کنید X ضعیف نیست. سپس مقداری اندازه گیری قابل محاسبه μ وجود دارد که X به صورت تصادفی μ-Martin-Lof باشد. توسط قضیه لوین-شنور برای پیچیدگی پیشینی با توجه به اندازهگیری μ (ضمنی در [Lev73]) برخی از c وجود دارد که
KA(X↾n) ≥ – log μ(X↾n) – c
برای همه n ∈ ω. به همین ترتیب، داریم
از آنجایی که هر اندازه گیری قابل محاسبه یک نیمه اندازه گیری قابل محاسبه است، نتیجه به شرح زیر است.
برای جهت دیگر، فرض کنید که مقداری نیمه اندازه گیری پیوسته و قابل محاسبه و مقداری c∈ ω وجود دارد به طوری که برای همه n ∈ ω،
بنابراین از قضیه لوین-شنور برای پیچیدگی پیشینی نتیجه می شود که X μ-مارتین-لوف تصادفی است و بنابراین عمق ضعیفی ندارد.
ما یک دنباله برای بودن تعریف می کنیم KA-عمیق اگر
(به مدرک مراجعه کنید [BDM23, Lemma 2.6] برای نیمه اندازه گیری های گسسته که مستقیماً به حالت نیمه اندازه گیری های پیوسته ترجمه می شود). بنابراین می توانیم نتیجه بگیریم:
6.2. عمق و پیچیدگی یکنواخت. ما می توانیم توصیف مشابهی از عمق ضعیف از نظر پیچیدگی یکنواخت بدست آوریم. اگر دنباله ای را به عمق کیلومتر تعریف کنید
این مفهوم توسط Schnorr و…