تصمیم ناپذیری منطق محمولات مرتبه اول و مسایل کلمه ای مقالة

مؤلف: حجتی، سید محمد ؛ مزگی نژاد، مرتضی ؛

شناخت بهار 1385 - شماره 49 التصنيف العلمية - البحثية (Ministry of Science/ISC (‎22 صفحة - من 161 إلی 182 )

الکلمات المفتاحية: منطق محمولات ماشین تورینگ توقف الگوریتمی تصمیم‌ناپذیری ماشین اثبات

خلاصة:

با شیوه های متعددی، تصمیم ناپذیری منطق محمولات اثبات شده که در هر کدام از این روش ها به نحوی از دیگر حوزه های علوم استفاده شده است. یکی از شیوه های نسبتا پیچیده، اثباتی است که مبتنی بر مفاهیم جبری مانند گروه ها، نیم گروه ها (semi groups) و مسایل کلمه ای (word problems) مرتبط با آن است. پس از بررسی این شیوه برخی مسایل تازه نمود پیدا می کند، مثلا به نظر می رسد تمامی اثبات های ارایه شده یک هسته مرکزی دارند که در همه آن مشترک است و متاثر از مساله توقف (halting problem) هیلبرت است. با مشخص شدن این موضوع به نظر می رسد تصمیم ناپذیری منطق محمولات امر تبعی است؛ یعنی منطق محمولات مانند زبان گسترده ای است که قابلیت بیان مسایل تصمیم ناپذیر را داراست.

ملخص الجهاز:

"یعنی به ازای هر فرمول خوش‌ساختی مانند: A ،الگوریتمی برای تصمیم‌گیری این که آیا آن فرمول قضیه‌ای از k ??* است: (به تصویر صفحه مراجعه شود) وجود دارد،پس اگر کلمه‌ w E??S A داده شده باشد،برای تصمیم‌گیری دربارهءاین که آیا w هم‌ارز h q? مسألهء توقف‌ Jenrym 2003 عبارت است از یافتن الگوریتمی که به ازای هر برنامه به عنوان ورودی، تشخیص دهد که آیا آن برنامه پس از طی تعداد مراحل متناهی،متوقف خواهد شد،یا نه؟ لم مسأله توقف مسألهء توقف برای ماشین تورینگ حل‌ناپذیراست؛یعنی الگوریتمی وجود ندارد که بتواند مشخص کند که آیا T با ورودی‌ a? همان‌گونه که در ابتدا مقاله بیان شد،با مشخص شدن مسألهء توقف به عنوان هسته‌ اصلی همه برهان‌ها،مسأله دیگری به وجود می‌آید:آیا تصمیم‌ناپذیری منطق محمولات امری‌ تبعی است،یعنی منطق محمولات مانند زبان گسترده‌ای است که قابلیت بیان هر مسأله‌ای را دارد و می‌توان مسأله تصمیم‌ناپذیری را با این منطقی فرموله کرد و تصمیم‌ناپذیری این‌ منطق به تبع این‌گونه مسایل است؟ تعریف تصمیم‌پذیری را با دقت بازنگری می‌کنیم. بنابراین مانند دیگر اثبات‌های ارائه شده برای تصمیم‌ناپذیری منطق محمولات،در این شیوه‌ نیز از اصول ماشین تورینگ و مسألهء توقف استفاده شده است. با مشخص شدن مسألهء توقف به منزلهء هستهء اصلی همه براهین،در پاسخ به این پرسش که آیا تصمیم‌ناپذیری منطق محمولات‌ امری تبعی است و منطق محمولات مانند زبان گسترده‌ای است که قابلیت بیان هر مسأله‌ای‌ را دارد،فرضیه دوم مطرح شده به‌طور کامل تأیید نمی‌شود؛زیرا هرچند منطق محمولات‌ یک سیستم است،اما یک سیستم منطقی علاوه بر زبان،داری دستگاه استنتاج است؛بنابراین‌ صرفا نمی‌توان گفت منطق محمولات یک زبان است که قابلیت بیان مسایل تصمیم‌ناپذیر را دارد؛اما بااین‌حال،این سیستم خصوصیات یک زبان پیشرفته برنامه‌نویسی را دارد."

استلام ملف الإرجاع :
(پژوهیار, , , )

تحميل
تحميل HTML

رابط قصير:

صفحة:

دخول / الاشتراک

تحتاج الدخول لعرض محتوى المقالة. إذا لم تكن عضوًا ، فتابع من الجزء الاشتراک.

دخول