مرتضی منیری

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

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

در ابتدا برخی موضوع های بحث برانگیز در حوزه منطق ریاضی را بررسی می کنیم. این ها موضوع هایی هستند که معمولاً غیرمتخصصان را به دردسر و گاهی اشتباه می اندازند. موضوع های عمده ای که در این راستا به آن ها خواهیم پرداخت عبارتند از: تعریف صدق تارسکی، قضیه تعریف ناپذیری صدق تارسکی، قضیه تمامیت گودل و قضیه های ناتمامیت گودل، منطق مرتبه اول و مرتبه دوم. در ادامه، به معرفی برخی منطق های غیرکلاسیک و جایگاه آن ها در منطق فلسفی و همچنین منطق در علوم کامپیوتر می پردازیم. افزون بر آن، برخی موضوع های فلسفی مرتبط به منطق را به بحث می گذاریم. از زمره این موضوع ها، پرسش از چیستی منطق، تفاوت منطق و دستگاه منطقی و چالش یگانه گرایی در مقابل کثرت گرایی در انتخاب منطق است. با تفکیک منطق از دستگاه منطقی، از این دیدگاه دفاع خواهیم کرد که منطق ریاضی به عنوان بخشی از ریاضیات، تنها می بایست متعهد به رعایت استانداردهای خود ریاضیات باشد. در این راستا، هر یک از دستگاه های منطق غیرکلاسیک که این استانداردها را رعایت کند، مشروعیت خواهد داشت.