کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875797 1441987 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Lowness and logical depth
ترجمه فارسی عنوان
عمق چابک و منطقی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , ,