ابوالفضل علم؛ مرتضی منیری
چکیده
نظریة مدل محدود را می‌توان بخشی از نظریة مدل دانست که هدف آن بررسی مفاهیم و نتایج نظریة مدل در یک زبان شامل یک رابطة ترتیبی است در حالتی که سورهای مورد بحث همگی از نوع محدود هستند. از نظریة مدل محدود می‌توان برای مطالعة مسائل مربوط به نظریة حساب محدود استفاده کرد. حساب محدود را می‌توان زیرنظریه‌ای از حساب مرتبة اول پئانو در زبانی ...
بیشتر
نظریة مدل محدود را می‌توان بخشی از نظریة مدل دانست که هدف آن بررسی مفاهیم و نتایج نظریة مدل در یک زبان شامل یک رابطة ترتیبی است در حالتی که سورهای مورد بحث همگی از نوع محدود هستند. از نظریة مدل محدود می‌توان برای مطالعة مسائل مربوط به نظریة حساب محدود استفاده کرد. حساب محدود را می‌توان زیرنظریه‌ای از حساب مرتبة اول پئانو در زبانی گسترشیافته دانست. خود حساب محدود، کاربردهای فراوانی در نظریة پیچیدگی محاسبات دارد. با تعریف و مطالعة مفاهیم پایهای نظریة مدل در حالت محدود مانند حذف سور محدود و مدل کامل محدود، نتایج جالبی در نظریة مدل با کاربردهایی در نظریۀ پیچیدگی محاسبه و حساب محدود به دست آمده است. در این مقاله، ضمن مروری بر نتایج موجود در این زمینه، برخی مفاهیم و نتایج جدید را در این راستا ارائه میکنیم و ارتباطهای آنها را با برخی مسائل بنیادی در نظریة پیچیدگی محاسبه مطالعه میکنیم.
