کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437433 690140 2011 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Inductive inference and computable numberings
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Inductive inference and computable numberings
چکیده انگلیسی

It has been previously observed that for many TxtEx-learnable computable families of computably enumerable (c.e. for short) sets all their computable numberings are evidently -equivalent, i.e. are equivalent with respect to reductions computable in the halting problem. We show that this holds for all TxtEx-learnable computable families of c.e. sets, and prove that, in general, the converse is not true. In fact there is a computable family A of c.e. sets such that all computable numberings of A are computably equivalent and A is not TxtEx-learnable. Moreover, we construct a computable family of c.e. sets which is not TxtBC-learnable though all of its computable numberings are -equivalent. We also give a natural example of a computable TxtBC-learnable family of c.e. sets which possesses non--equivalent computable numberings. So, for the computable families of c.e. sets, the properties of TxtBC-learnability and -equivalence of all computable numberings are independent.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 18, 15 April 2011, Pages 1652-1668