پیچیدگی کولموگروف وثوابت مشخصه ی نظریه های صوری حساب
نام نخستين پديدآور
/سجاد غنی زاده زارع
وضعیت نشر و پخش و غیره
نام ناشر، پخش کننده و غيره
: علوم ریاضی
تاریخ نشرو بخش و غیره
، ۱۳۹۴
نام توليد کننده
، راشدی
یادداشتهای مربوط به نشر، بخش و غیره
متن يادداشت
چاپی
یادداشتهای مربوط به پایان نامه ها
جزئيات پايان نامه و نوع درجه آن
کارشناسی ارشد
نظم درجات
ریاضی محض
زمان اعطا مدرک
۱۳۹۴/۰۶/۲۱
کسي که مدرک را اعطا کرده
تبریز
یادداشتهای مربوط به خلاصه یا چکیده
متن يادداشت
فاقد چکیده فارسی
متن يادداشت
Two constants c T and r T , introduced by Chaitin and Raatikainen respectively and defined for each recursively axiomatizable consistent theory T and universal Turing machine, used to determine Kolmogorov complexity, are investigate this theory. Raatikainen argued that c T does not represent the complexity of T and found that for two theories S and T , one can always find a universal Turing machine such that c S = c T . In this thesis, it is shown that the following three conditions are equivalent: 1. There is a 1 -sentence which is provable in T but not in S , 2. c T = c S for some universal Turing machine, and 3. r T = r S for some universal Turing machine. Moreover it is shown that r T does not necessarily coincide with c T ; for two arith- metical theories T and S with a 1 -sentence provable in T but not in S , there is an enumeration of the Turing machines such that r S < r T and c S = c T
نام شخص به منزله سر شناسه - (مسئولیت معنوی درجه اول )