کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875870 | 1441989 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Enumerations including laconic enumerators
ترجمه فارسی عنوان
شمارش شامل شمارنده های لاکونیک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
فهرست تقارنها، برنامه های حداقل پیچیدگی کلموگروف، شماره های کلموگروف، نظریه رقیب،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Theoretical Computer Science - Volume 700, 14 November 2017, Pages 89-95
نویسندگان
Sanjay Jain, Jason Teutsch,