کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426752 686259 2014 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Things that can be made into themselves
ترجمه فارسی عنوان
چیزهایی که می توانند در خود ساخته شوند
کلمات کلیدی
شماره گیری، خود ارجاع، حداقل سمت چپ مجموعه ها، حداکثر سمت چپ مجموعه ها، مجموعه های تصادفی مارتین لوف
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

One says that a property P   of sets of natural numbers can be made into itself iff there is a numbering α0,α1,…α0,α1,… of all left-r.e. sets such that the index set {e:αe satisfies P}{e:αe satisfies P} has the property P as well. For example, the property of being Martin-Löf random can be made into itself. Herein we characterize those singleton properties which can be made into themselves. A second direction of the present work is the investigation of the structure of left-r.e. sets under inclusion modulo a finite set. In contrast to the corresponding structure for r.e. sets, which has only maximal but no minimal members, both minimal and maximal left-r.e. sets exist. Moreover, our construction of minimal and maximal left-r.e. sets greatly differs from Friedberg's classical construction of maximal r.e. sets. Finally, we investigate whether the properties of minimal and maximal left-r.e. sets can be made into themselves.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 237, October 2014, Pages 174–186
نویسندگان
, ,