
هدف:
۱- آشنایی با زبان های فرمال
۲- محدودیت های محاسبه با معرفی "مسائل تصمیم" و اثبات تصمیم ناپذیری.
۳-در نهایت معرفی تز چرچ تورینگ و بحث در مورد مسائل تصمیم ناپذیر.
کلید واژه ها: زبان فرمال، مسائل تصمیم، پیچیدگی الگوریتمی، تصمیم پذیری، محاسبه پذیری، ماشین تورینگ، حساب لمبدا، شیوه موثر، شبه تصمیم پذیر، به طور بازگشتی شمارش پذیر، ابرمحاسبه
یک مساله محاسباتی مساله ای است که با زبان های فرمال رابطه نزدیکی دارد برای ورود به بحث ابتدا یک زبان فرمال را تعریف می کنیم به طور کلی برای هر زبان یک الفبا داریم که یک مجموعه از نماد هاست مثلا نمادهای زبان انگلیسی که 26 حرف هستند وقتی این حرف ها را کنار هم قرار می دهیم "کلمه" (word) ساخته می شوند زبان فرمال به صورت مجموعه ای از کلمات تعریف می شود مثلا:

این زبان بر روی الفبای {A={a,b,c تعریف شده است همانطور که می بینید این نوع تعریف بسیار جامع است و کاری به ساختمند بودن (structure) یا قواعدِ زبان ندارد اما برای این که بتوان جلوتر رفت باید گرامری تعریف کرد که بنابر آن فقط بعضی از کلمات بتوانند وارد زبان شوند مثلا اگر x یک صفت باشد x-مند هم بتواند در مجموعه باشد مثلا :ثروتمند ،قدرتمند البته این روش در مورد زبان های طبیعی خیلی جواب نمی دهد چون بطور کل گرامر دقیق و همه جانبه ای ندارند و به همین خاطر فرمال نیستند.
اما مساله جالب این جاست که اکثر مسائل ریاضی را می توان به صورت یک الگوریتم در آورد و در قالب زبان فرمال نتایج را دید؛ در ساده ترین حالت می توان یک رشته را به الگوریتم داد و پرسید که آیا این رشته متعلق به "مجموعه جواب" (که همان کلمات داخل زبان است) هست یا نه. یعنی به این فکر کنیم که هر زبانی را با یک الگوریتم مشخص کنیم.

به چنین مسائلی "مسائل تصمیم" (Decision Problem) می گویند؛ مثلا یک عدد طبیعی را به الگوریتم داد و از آن پرسید که آیا اول هست یا خیر در این صورت مجموعه جواب( که طبق تعریف بالا یک زبان است) همان مجموعه اعداد اول است. به نظر چنین روشی برای همه ی الگوریتم ها جواب ندهد یعنی از هر الگوریتم به روش بالا یک زبان قابل استخراج نباشد، چون ما که همیشه جواب بله-خیر نمی خواهیم، مثلا اگر الگوریتم ضرب را در نظر بگیریم دو عدد a,b می دهیم و حاصلضرب آن را می خواهیم ؛ در عمل چنین حرفی درست است اما مساله ای مانند ضرب کلی تر از مسائل تصمیم نیست چون می توان مثلا (a,b,c) را به الگوریتم داد و پرسید که آیا c حاصلضرب a ,b هست یا خیر. آنچه مهم است "مجموعه جواب" و تصمیم پذیر بودن آن است که مثلا در مورد این مساله خاص c فقط یک جواب دارد و آن هم حاصلضرب a و b است و زبان را می توان به صورت سه تایی های (a,b,c) صحیح در نظر گرفت. مثلا (3,4,12) متعلق به این زبان است ولی (2,5,6) متعلق به این زبان نیست.
به این ترتیب هر الگوریتمی قابل تبدیل به یک مساله تصمیم است. در مورد الگوریتم ها باید بدانیم که برای یک مساله خاص (مثلا بررسی اول بودن یک عدد) الگوریتم های متعددی وجود دارد و برخی سریعتر از بقیه اند. برخی از مسائل به طور "ذاتی" نیاز به زمان زیادی برای حل کردن دارند و به اصطلاح پیچیدگی الگوریتمی (Algorithmic Complexity) بالایی دارند اما برخی ساده اند. اما فراتر از این مسائل سوالی که بسیار کلی تر و هستی شناختی تر است این است که آیا اصولا همواره می توان انتظار داشت برای هر زبانی یک الگوریتم وجود داشته باشد که با اتکا به آن بتوان تشخیص داد یک رشته جزء زبان هست یا نه؟ توجه کنید در این جا کاری با زمان محاسبه این الگوریتم نداریم الگوریتم می تواند بسیار بسیار کند باشد اما آیا می تواند ما را مطمئن کند که در نهایت جواب را می یابد؟ به عبارتی آیا هر زبانی تصمیم پذیر است؟ این مساله بسیار جالب است و ذهن اولین کسانی که به طور اصولی مبانی محاسبه و کامپیوتر را پایه ریزی کردند به خود مشغول کرد. آلن تورینگ اولین کسی بود که به این مساله فکر کرد و در نهایت آن را حل کرد. او به این نتیجه رسید مسائلی وجود دارند که تصمیم ناپذیرند. یا به عبارت بهتر زبانِ آن ها تصمیم ناپذیر است که به این معنی است که هیچ الگوریتمی وجود ندارد که بتواند برای هر ورودی تصمیم بگیرد که آیا جز زبان (مجموعه جواب مساله)هست یا خیر.
اثبات این نتیجه خیلی سخت نیست اما قبلش چند چیز را باید بدانیم اول اینکه هر برنامه ای(وکلا هر داده ای) روی کامپیوتر مجموعه ای از صفر ها و یک هاست (اعداد باینری) از این دید برنامه و داده فرقی ندارند! (البته منظور این است که نمایش متفاوتی ندارند). دومین نکته این است که اعداد باینری قابل شمارش هستند یعنی می توان یک شماره گذاری انجام داد و مثلا در آن گفت عدد باینری اول عدد باینری دوم و الخ. برای این که منظور از این حرف مشخص شود به دنباله ی زیر توجه کنید:

همانطور که می بینید با این روش توانسیم همه ی اعداد باینری را بشماریم اول تک بیتی ها، بعد ۲ بیتی ها ،۳ بیتی ها و الخ. اما می دانید که هر برنامه صرفا یک رشته از صفر ها و یک ها است. پس بالاخره در جایی از این دنباله به آن می رسیم به این ترتیب فضای برنامه ها "قابل شمارش" است!! این یعنی هر برنامه متناظر با یک عدد طبیعی در این دنباله است بنابراین این جمله معنی دارد که بگوییم ۱۰۲۳ امین برنامه. حتی برنامه مایکروسافت ورد یا برنامه پخش آهنگ روی گوشی اتان هم متناظر با یک عدد است!! همه برنامه هایی که درست شده اند یا خواهند شد یا هیچگاه بشر آن ها را نمی سازد یک شماره دارند!!
این همین قضیه در مورد رشته ها یعنی داده های ورودی برنامه ها هم صادق است چون هر کدام از صفر ها و یک های بالا یک رشته هستند.
حال به اثبات می پردازیم: از برهان خلف استفاده می کنیم به این معنا که فرض می کنیم توانسته ایم برای هر زبانی یک برنامه پیدا کنیم که در موردش تصمیم بگیرد به این ترتیب یک جدول بدست می آوریم که در ستون افقی برنامه ی i ام و در ستون عمودی رشته ی ورودی را داریم و هر خانه نشان می دهد که برنامه i ام رشته ی ورودی j را قبول می کند یا نه.

بنابراین مثلا برنامه ۲ ورودی شماره ۱ را می پذیرد ورودی شماره ۲ را می پذیرد ورودی های شماره ۳ و ۴ را نمی پذیرد و الی آخر. همانطور که قبلا هم گفتیم یک برنامه یا الگوریتم یک رویه تصمیم است که مشخص می کند کدام رشته ها (کلمات) جزء زبان اند وکدام ها نیستند. بنابراین هر برنامه (الگوریتم) یک زبان را مشخص می کند. و در این جا هر سطر از جدول یک زبان است: زبانی که نشان می دهد کدام رشته ها به آن تعلق دارند(1) و کدام ها ندارند(0).در این جا در صددیم یک رابطه یک به یک بین زبان ها و الگوریتم ها بیابیم.
1↔L1(01100…)
2↔L2(11001…)
3↔L3(10111…)
4↔L4(10001…)
….
که در آن Li زبان الگوریتم سطر i است. اما آیا این تمام زبان ها را پوشش می دهد؟ یعنی برعکس آن هم برقرار است؟ یعنی برای هر زبان یک الگوریتم یافت؟! و به این ترتیب رابطه ی یک به یک بین هر زبان و الگوریتمش برقرار کرد(بین مجموعه ی تمام زبان ها و مجموعه تمام الگوریتم ها)؟این کار غیر ممکن است! برای نشان دادن این موضوع بیایید زبانی بسازیم که در هیچ سطری ایجاد نشود برای این کار از استدلال قطری (Diagonal Argument) استفاده می کنیم. به اعضای روی قطر که علامت زده شده اند توجه می کنیم و یک زبان جدید می سازیم. فرآیند ساختن این زبان به این صورت است که اولین رشته در دنباله رشته ها را بپذیرد اگر این طور باشد پس این زبان متفاوت از زبان سطر یک است، همچنین زبان ما دومین رشته را نمی پذیرد پس زبان ما زبان سطر دوم هم نیست(دقت کنید فقط یک مورد تفاوت کافی است که بدانیم این زبان متفاوت از زبان مورد نظر ماست) همین استدلال را برای بقیه بکار می گیریم با این تعریف زبان قطری ما در هیچ سطری ظاهر نمی شود!! و بنابراین هیچ برنامه ای نمی تواند با آن متناظر باشد. این فکر را از ذهن دور بریزید که در بی نهایت بالاخره به آن زبان می رسیم اگر هنوز قانع نشده اید این استدلال را ببینید:
فرض کنید برنامه ای برای زبان قطری ما وجود دارد. فرض کنید این زبان در سطری مانند i است. حالا رشته i ام را در نظر بگیرید آیا این ورودی در زبان قطری ما هست:
اگر رشته ی i ام در زبان ما باشد پس برنامه آن را می پذیرد و در مکان آن یعنی(i,i) باید 1 قرار دهیم اما بنابر تعریفِ زبان ما، اگر یک در آن جا باشد(چون روی قطر است و مقدارش 1 است) نباید در زبان باشد.
اگر رشته در زبان نباشد برنامه آن را نمی پذیرد و باید در مکان آن (i,i) مقدار 0 قرار دهیم اما باز هم بنابر تعریفِ زبانِ عجیب ما این رشته در زبان است چون روی قطر است و مقدارش صفر است.
بنابراین نمی توان در مورد رشته ی i ام برای زبان تصمیم گرفت. این استدلال بسیار شبیه به پارادوکس دروغگو است. a درست است اگر و تنها اگر a غلط باشد!!!.
می توان این را به زبانی حتی راحتتر هم توضیح داد: دلیل اصلی آنکه برخی از زبان ها الگوریتمی ندارند این است که تعداد زبان ها خیلی بیشتر از الگوریتم هاست!!! این جمله در نظر اول بی معنی به نظر می رسد چطور می توان گفت تعداد زبان ها بیشتر از الگوریتم هاست در حالی که می دانیم بی نهایت زبان و بی نهایت الگوریتم داریم و بی نهایت ها قابل مقایسه نیستند.
خوب قسمت اول جمله بالا درست است ولی قسمت دوم نه ؛ منظور این است که بینهایت ها در کمال تعجب قابل مقایسه اند دو مجموعه بی نهایت عضوی "برابر"(بهتر است بگوییم "هم کاردینال"(cardinal)) اند اگر وتنها اگر بتوان یک رابطه یک به یک بین اعضای آن ها یافت مثلا دو مجموعه زیر هم کاردینال اند:
A={1,2,3,4,5,…}
B={2,4,6,8,10,…}
مجموعه B زیر مجموعه A است اما هر دو هم کاردینال اند چون بسادگی رابطه یک به یک f(n)=2n را می توان بین آن ها دید. جزء همیشه کوچکتر از کل نیست! (حداقل وقتی در مورد بی نهایت ها حرف میزنیم!) این در مورد هر دو زیر مجموعه بی نهایت از اعداد طبیعی صادق است (مثلا اعداد اول و اعداد زوج). هر مجموعه ای که هم کاردینال با اعداد طبیعی باشد "شمارش پذیر" می نامند چون رابطه یک به یک اجازه می دهد یکی یکی آن ها را بشماریم .حالا سراغ مجموعه های دیگر می رویم که به نظر می رسد بی نهایت بزرگ تری داشته باشند مثلا مجموعه اعداد گویا. اما باید گفت حتی این مجموعه هم قابل شمارش است استدلال آن ساده است اما آن را اینجا نمی آوریم. مجموعه بعدی که به نظر می رسد اعضای بیشتری داشته باشد مجموعه اعداد حقیقی است. بله مجموعه اعداد حقیقی شمارش ناپذیر است یعنی نمی توان یک رابطه یک به یک بین اعضای آن و اعداد طبیعی برقرار کرد. استدلال این واقعیت بسیار شبیه به استدلال قطری بالا است و اصلا استدلال قطری اولین بار در مورد اعداد حقیقی استفاده شد و نه زبان ها و الگوریتم ها. با همین استدلال متوجه می شویم کاردینال مجموعه ی زبان ها بزرگتر از مجموعه ی الگوریتم هاست بنابراین بعضی از زبان ها بدون الگوریتم می مانند!

در مقام مقایسه می توان مجموعه تمام زبان ها را شبیه به صفحه دارت در نظر گرفت در آن صورت تمام الگوریتم های جهان تنها یک نقطه از آن صفحه هستند!!