کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875797 | 1441987 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Lowness and logical depth
ترجمه فارسی عنوان
عمق چابک و منطقی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Bennett's concept of logic depth [3] seeks to capture the idea that a language has a lot of useful information. Thus we would expect that neither sufficiently random nor sufficiently computationally trivial sequences are deep. A question of Moser and Stephan [11] explores the boundary of this assertion, asking if there is a low computably enumerable (Bennett) deep language. We answer this question affirmatively by constructing a superlow computably enumerable Bennett deep language.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 702, 30 November 2017, Pages 23-33
Journal: Theoretical Computer Science - Volume 702, 30 November 2017, Pages 23-33
نویسندگان
Rod Downey, Michael McInerney, Keng Meng Ng,