کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429161 687066 2008 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Turing degrees of reals of positive effective packing dimension
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Turing degrees of reals of positive effective packing dimension
چکیده انگلیسی

A relatively longstanding question in algorithmic randomness is Jan Reimann's question whether there is a Turing cone of broken dimension. That is, is there a real A such that contains no 1-random real, yet contains elements of nonzero effective Hausdorff dimension? We show that the answer is affirmative if Hausdorff dimension is replaced by its inner analogue packing dimension. We construct a minimal degree of effective packing dimension 1.This leads us to examine the Turing degrees of reals with positive effective packing dimension. Unlike effective Hausdorff dimension, this is a notion of complexity which is shared by both random and sufficiently generic reals. We provide a characterization of the c.e. array noncomputable degrees in terms of effective packing dimension.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 108, Issue 5, 15 November 2008, Pages 298-303