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

چکیده

In this article, we study the relationship between notions of depth for sequences, namely, Bennett’s notions of strong and weak depth, and deep $Π^0_1$ classes, introduced by the authors and motivated by previous work of Levin. For the first main result of the study, we show that every member of a $Π^0_1$ class is order-deep, a property that implies strong depth. From this result, we obtain new examples of strongly deep sequences based on properties studied in computability theory and algorithmic randomness. We further show that not every strongly deep sequence is a member of a deep $Π^0_1$ class. For the second main result, we show that the collection of strongly deep sequences is negligible, which is equivalent to the statement that the probability of computing a strongly deep sequence with some random oracle is 0, a property also shared by every deep $Π^0_1$ class. Finally, we show that variants of strong depth, given in terms of a priori complexity and monotone complexity, are equivalent to weak depth.

چکیده به فارسی (ترجمه ماشینی)

در این مقاله ، ما رابطه بین مفاهیم عمق توالی ها ، یعنی مفاهیم بنت از عمق قوی و ضعیف و کلاسهای عمیق π^0_1 $ را که توسط نویسندگان معرفی شده و با انگیزه کار قبلی لوین ، مطالعه می کنیم.برای اولین نتیجه اصلی مطالعه ، ما نشان می دهیم که هر یک از اعضای کلاس $ π^0_1 $ سفارش عمیق است ، اموالی که دلالت بر عمق قوی دارد.از این نتیجه ، ما نمونه های جدیدی از توالی های به شدت عمیق را بر اساس خواص مورد مطالعه در تئوری محاسبه و تصادفی الگوریتمی بدست می آوریم.ما همچنین نشان می دهیم که هر دنباله ای به شدت عمیق عضو کلاس $ π^0_1 $ نیست.برای دومین نتیجه اصلی ، ما نشان می دهیم که مجموعه توالی های بسیار عمیق ناچیز است ، که معادل این جمله است که احتمال محاسبه یک دنباله به شدت عمیق با برخی از اوراکل تصادفی 0 است ، یک خاصیت همچنین توسط هر $ $ read read به اشتراک گذاشته شده است.کلاس 0_1 $.سرانجام ، ما نشان می دهیم که انواع عمق قوی ، از نظر پیچیدگی پیشینی و پیچیدگی یکنواخت ، معادل عمق ضعیف است.