کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875870 1441989 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Enumerations including laconic enumerators
ترجمه فارسی عنوان
شمارش شامل شمارنده های لاکونیک
کلمات کلیدی
فهرست تقارنها، برنامه های حداقل پیچیدگی کلموگروف، شماره های کلموگروف، نظریه رقیب،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that it is possible, for every machine universal for Kolmogorov complexity, to enumerate the lexicographically least description of a length n string in O(n) attempts. In contrast to this positive result for strings, we find that, in any Kolmogorov numbering, no enumerator of nontrivial size can generate a list containing the minimal index of a given partial-computable function. One cannot even achieve a laconic enumerator for nearly-minimal indices of partial-computable functions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 700, 14 November 2017, Pages 89-95
نویسندگان
, ,