پل زدن مفاهیم محاسباتی عمق: در اینجا دلیل ناچیز بودن عمق قوی است

جدول پیوندها

چکیده و 1 مقدمه

2 پس زمینه

3 در مورد قانون رشد آهسته

4 عضو کلاس Deep Π0 1

5 عمق قوی ناچیز است

6 نوع از عمق قوی

مراجع

پیوست A. اثبات لم 3

5. عمق قوی ناچیز است

قضیه 25. کلاس سکانس های به شدت عمیق ناچیز است.

اثبات به خاطر تناقض، فرض کنید که یک تابعی وجود دارد به طوری که

واضح است که q قابل محاسبه است جابجایی، q یک نیمه اندازه گیری گسسته است، زیرا

از سوی دیگر، تقریبا برای همه n:

در مقابل، توجه داشته باشید که مجموعه سکانس‌های با عمق ضعیف قابل چشم پوشی نیست. در واقع، همانطور که توسط Muchnik و همکاران نشان داده شده است. [MSU98]، هیچ دنباله 1-عمومی با توجه به یک اندازه گیری قابل محاسبه تصادفی مارتین-L نیست و بنابراین هر 1-عمومی ضعیف است. علاوه بر این، همانطور که توسط Kautz نشان داده شده است [Kau91]، هر دنباله 2 تصادفی یک 1 ژنریک را محاسبه می کند و از این رو مجموعه 1 ژنریک قابل چشم پوشی نیست.