جدول پیوندها
چکیده و 1 مقدمه
2 پس زمینه
3 در مورد قانون رشد آهسته
4 عضو کلاس Deep Π0 1
5 عمق قوی ناچیز است
6 نوع از عمق قوی
مراجع
پیوست A. اثبات لم 3
1. مقدمه
بنت چندین حقایق اساسی را در مورد توالی های به شدت عمیق ثابت کرد، یعنی اینکه مجموعه توقف K به شدت عمیق است، هیچ دنباله قابل محاسبه و هیچ دنباله تصادفی Martin-L به شدت عمیق نیست، و این عمق قوی تحت تقلیل پذیری جدول حقیقت به سمت بالا بسته می شود. نتیجه ای که او از آن به عنوان قانون رشد آهسته یاد کرد). بنت بیشتر مفهوم عمق ضعیف را معرفی کرد، که در آن یک دنباله ضعیف است اگر جدول صدق قابل تقلیل به یک دنباله تصادفی نباشد.
یکی از نکاتی که قصد داریم در این مطالعه بر آن تاکید کنیم، اهمیت قانون رشد آهسته برای مطالعه عمق، شبیه به نقش حفظ تصادفی در مطالعه تصادفی بودن الگوریتمی است. طبق دومی، هر دنبالهای که جدول صدق قابل تقلیل به دنبالهای است که نسبت به اندازهگیری قابل محاسبه تصادفی است، خود با توجه به اندازهگیری قابل محاسبه تصادفی است، که دقیقاً دوگانه قانون رشد آهسته برای دنبالههای عمیق است. ما پیش بینی می کنیم که قانون رشد آهسته همچنان ابزار مفیدی در مطالعه مفاهیم عمق باشد.
نویسندگان:
(1) Laurent Bienvenu;
(2)…