کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436065 689967 2007 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Random reals à la Chaitin with or without prefix-freeness
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Random reals à la Chaitin with or without prefix-freeness
چکیده انگلیسی

We give a general theorem that provides examples of n-random reals à la Chaitin, for every n≥1; these are halting probabilities of partial computable functions that are universal by adjunction for the class of all partial computable functions, The same result holds for the class functions of partial computable functions with prefix-free domain. Thus, the usual technical requirement of prefix-freeness on domains is an option which we show to be non-critical when dealing with universality by adjunction. We also prove that the condition of universality by adjunction (which, though particular, is a very natural case of optimality) is essential in our theorem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 385, Issues 1–3, 15 October 2007, Pages 193-201