Decider (Turing machine)
کمپیوٹیبلٹی تھیوری میں، فیصلہ کن ایک ٹورنگ مشین ہے جو ہر ان پٹ کے لیے رکتی ہے۔ فیصلہ کن کو کل ٹورنگ مشین بھی کہا جاتا ہے کیونکہ یہ کل فنکشن کی نمائندگی کرتا ہے۔ چونکہ یہ ہمیشہ رکتا ہے، اس طرح کی مشین یہ فیصلہ کرنے کے قابل ہوتی ہے کہ آیا دی گئی سٹرنگ کسی رسمی زبان کا رکن ہے یا نہیں۔ زبانوں کی وہ کلاس جس کا فیصلہ اس طرح کی مشینوں کے ذریعے کیا جا سکتا ہے وہ تکراری زبانوں کا مجموعہ ہے۔ ایک من مانی ٹورنگ مشین کو دیکھتے ہوئے، اس بات کا تعین کرنا کہ آیا یہ فیصلہ کن ہے، ایک ناقابل فیصلہ مسئلہ ہے۔ یہ رکنے کے مسئلے کا ایک متغیر ہے، جو یہ پوچھتا ہے کہ آیا ٹورنگ مشین کسی مخصوص ان پٹ پر رکتی ہے۔ کل ٹورنگ مشینوں کے حساب سے قابل حساب افعال عملی طور پر، دلچسپی کے بہت سے افعال ان مشینوں کے ذریعے قابل حساب ہوتے ہیں جو ہمیشہ رکتی ہیں۔ ایک ایسی مشین جو کسی خاص ان پٹ پر صرف محدود میموری کا استعمال کرتی ہے اسے اس کے بہاؤ پر قابو پانے کی صلاحیتوں کو محدود کرکے ہر ان پٹ کے لیے روکنے پر مجبور کیا جا سکتا ہے تاکہ کوئی بھی ان پٹ مشین کو کبھی بھی لامحدود لوپ میں داخل نہ کرے۔ ایک معمولی مثال کے طور پر، ایک حتمی فیصلہ ٹری کو لاگو کرنے والی مشین ہمیشہ رک جائے گی۔ یہ ضروری نہیں ہے کہ مشین لوپنگ کی صلاحیتوں سے مکمل طور پر پاک ہو، تاہم، رکنے کی ضمانت کے لیے۔ اگر ہم لوپس کو متوقع طور پر محدود سائز کے ہونے تک محدود رکھتے ہیں (جیسے بیسک میں ایف او آر لوپ)، تو ہم تمام ابتدائی تکراری افعال کا اظہار کر سکتے ہیں (میئر اور رچی، 1967)۔ اس طرح کی مشین کی ایک مثال برینارڈ اور لینڈویبر (1974) کی کھلونا پروگرامنگ زبان پی ایل-{جی او ٹی او} نے فراہم کی ہے۔ ہم ایک پروگرامنگ زبان کی مزید وضاحت کر سکتے ہیں جس میں ہم اس بات کو یقینی بنا سکتے ہیں کہ اس سے بھی زیادہ نفیس افعال ہمیشہ رک جائیں۔ مثال کے طور پر، ایکر مین فنکشن، جو کہ ابتدائی تکراری نہیں ہے، اس کے باوجود ایک کل کمپیوٹیبل فنکشن ہے جس کا حساب ایک اصطلاح دوبارہ لکھنے کے نظام کے ذریعے کیا جا سکتا ہے جس کے دلائل میں کمی کی ترتیب ہوتی ہے (اوہلیبش، 2002، پی پی 67)۔ پروگرامنگ زبانوں کی مذکورہ بالا مثالوں کے باوجود جو پروگراموں کے خاتمے کی ضمانت دیتی ہیں، ایسی کوئی پروگرامنگ زبان موجود نہیں ہے جو بالکل کل تکراری افعال پر قبضہ کرتی ہو، یعنی۔ وہ افعال جن کا حساب ٹورنگ مشین کے ذریعے لگایا جا سکتا ہے جو ہمیشہ رکتی ہے۔ اس کی وجہ یہ ہے کہ اس طرح کی پروگرامنگ زبان کا وجود اس مسئلے کی غیر نیم فیصلہ سازی سے متصادم ہوگا کہ آیا ٹورنگ مشین ہر ان پٹ پر رکتی ہے یا نہیں۔ جزوی ٹورنگ مشینوں سے تعلق ایک عام ٹورنگ مشین جزوی فنکشن کا حساب لگائے گی۔ جزوی ٹورنگ مشینوں اور کل ٹورنگ مشینوں کے درمیان تعلق کے بارے میں دو سوالات پوچھے جا سکتے ہیں: کیا جزوی ٹورنگ مشین کے ذریعے کمپیوٹیبل ہر جزوی فنکشن کو بڑھایا جا سکتا ہے (یعنی اس کا ڈومین بڑھایا جا سکتا ہے) تاکہ کل کمپیوٹیبل فنکشن بن جائے؟ کیا ٹورنگ مشین کی تعریف کو تبدیل کرنا ممکن ہے تاکہ کل ٹورنگ مشینوں کی ایک مخصوص کلاس، تمام کل کمپیوٹیبل افعال کا حساب لگانا، مل سکے؟ ان میں سے ہر ایک سوال کا جواب نہیں ہے۔ مندرجہ ذیل تھیوریم سے پتہ چلتا ہے کہ مشینوں کے ذریعہ کمپیوٹیبل افعال جو ہمیشہ رکتے ہیں ان میں تمام جزوی کمپیوٹیبل افعال کی توسیع شامل نہیں ہوتی ہے، جس کا مطلب ہے کہ اوپر دیے گئے پہلے سوال کا جواب منفی ہے۔ یہ حقیقت رکنے کے مسئلے کی الگورتھمک حل پذیری سے قریب سے متعلق ہے۔ درحقیقت، اگر g ایک کل کمپیوٹیبل فنکشن ہوتا جو f تک پھیلا ہوا ہوتا تو g کسی ٹورنگ مشین کے ذریعے کمپیوٹیبل ہوتا۔ اس طرح کی مشین کے انڈیکس کے طور پر e کو فکس کریں۔ کلین کے ریکرشن تھیوریم کا استعمال کرتے ہوئے ایک ٹورنگ مشین ایم بنائیں، جو ان پٹ پر مشین کو انڈیکس ای کے ساتھ ایم کے لیے انڈیکس این ایم پر چلتی ہے (اس طرح مشین ایم خود ایک انڈیکس تیار کر سکتی ہے ؛ یہ ریکرشن تھیوریم کا کردار ہے)۔ مفروضے کے مطابق، یہ تخروپن بالآخر جواب دے گا۔ تاکہ اگر g (nM) = m تو M کی واپسی کی قیمت ہے۔ اس طرح f (nM)، ان پٹ پر M کی حقیقی واپسی کی قیمت، g (nM) کے برابر نہیں ہوگی۔ لہذا g f کی توسیع نہیں کرتا ہے۔ دوسرا سوال بنیادی طور پر پوچھتا ہے کہ کیا کمپیوٹیشن کا کوئی اور معقول ماڈل ہے جو صرف کل افعال کا حساب لگاتا ہے اور تمام کل کمپیوٹیبل افعال کا حساب لگاتا ہے۔ غیر رسمی طور پر، اگر ایسا ماڈل موجود ہوتا تو اس کے ہر کمپیوٹر کو ٹورنگ مشین کے ذریعے سیمولیٹ کیا جا سکتا تھا۔ اس طرح اگر کمپیوٹیشن کا یہ نیا ماڈل مشینوں کی ترتیب پر مشتمل ہوتا، تو ٹورنگ مشینوں کا ایک بار بار شمار ہونے والا تسلسل ہوتا جو کل افعال کا حساب لگاتا ہے اور تاکہ ہر کل کمپیوٹیبل فنکشن مشینوں میں سے کسی ایک کے ذریعہ قابل حساب ہو۔ یہ ناممکن ہے، کیونکہ ایک مشین اس طرح بنائی جا سکتی ہے کہ ان پٹ i پر مشین T واپس آ جائے۔ یہ مشین فہرست میں موجود کسی بھی مشین کے مساوی نہیں ہو سکتی: فرض کریں کہ یہ انڈیکس جے کی فہرست میں تھی۔ پھر، جو انٹیجر کا نتیجہ نہیں دیتا ہے۔ لہذا، یہ کل نہیں ہو سکتا، لیکن تعمیر کے لحاظ سے فنکشن کل ہونا چاہیے (اگر کل فنکشن بار بار شمار کیے جا سکتے ہیں، تو یہ فنکشن تعمیر کیا جا سکتا ہے)، جو کہ ایک تضاد ہے۔ اس سے ظاہر ہوتا ہے کہ دوسرے سوال کا جواب منفی ہے۔ کل ٹورنگ مشینوں کے اشاریہ جات کا مجموعہ یہ فیصلہ کرنے کا مسئلہ کہ آیا انڈیکس ای والی ٹورنگ مشین ہر ان پٹ پر رک جائے گی، فیصلہ کن نہیں ہے۔ درحقیقت یہ مسئلہ ریاضیاتی درجہ بندی کی سطح پر ہے۔ اس طرح یہ مسئلہ ہالٹنگ کے مسئلے سے سختی سے زیادہ مشکل ہے، جو پوچھتا ہے کہ کیا انڈیکس ای والی مشین ان پٹ 0 پر رکتی ہے۔ بدیہی طور پر، غیر حل پذیری میں یہ فرق اس لیے ہے کیونکہ "کل مشین" کے مسئلے کی ہر مثال رکنے کے مسئلے کی لامحدود مثالوں کی نمائندگی کرتی ہے۔ امکان کسی کو نہ صرف اس بات میں دلچسپی ہو سکتی ہے کہ آیا ٹورنگ مشین کل ہے، بلکہ اس میں بھی دلچسپی ہو سکتی ہے کہ آیا اسے کسی خاص منطقی نظام میں ثابت کیا جا سکتا ہے، جیسے کہ فرسٹ آرڈر پیانو ریاضی۔ ساؤنڈ پروف سسٹم میں، ہر ممکنہ طور پر کل ٹورنگ مشین درحقیقت کل ہوتی ہے، لیکن اس کے برعکس سچ نہیں ہے: غیر رسمی طور پر، ہر فرسٹ آرڈر پروف سسٹم کے لیے جو کافی مضبوط ہے (بشمول پیانو ریاضی)، ٹورنگ مشینیں ایسی ہیں جو کل سمجھی جاتی ہیں، لیکن اس طرح ثابت نہیں کی جا سکتی، جب تک کہ نظام متضاد نہ ہو (ایسی صورت میں کوئی بھی کچھ ثابت کر سکتا ہے)۔ ان کی مجموعی حیثیت کا ثبوت یا تو کچھ مفروضوں پر منحصر ہوتا ہے یا کسی اور ثبوت کے نظام کی ضرورت ہوتی ہے۔ اس طرح، جیسا کہ کوئی بھی پروف سسٹم میں تمام ثبوتوں کی گنتی کر سکتا ہے، کوئی بھی ان پٹ n پر ٹورنگ مشین بنا سکتا ہے جو پہلے n ثبوتوں سے گزرتا ہے اور تضاد تلاش کرتا ہے۔ اگر اسے ایک مل جاتا ہے، تو یہ ایک لامحدود لوپ میں چلا جاتا ہے اور کبھی نہیں رکتا ؛ بصورت دیگر، یہ رک جاتا ہے۔ اگر نظام مستقل ہے، تو ٹورنگ مشین ہر ان پٹ پر رک جائے گی، لیکن گوڈل کے نامکمل نظریات کی وجہ سے کوئی بھی اسے کافی مضبوط پروف سسٹم میں ثابت نہیں کر سکتا۔ کوئی بھی ایک ٹورنگ مشین بھی بنا سکتا ہے جو صرف اس صورت میں رکے گی جب پروف سسٹم متضاد ہو، اور اس طرح ایک مستقل نظام کے لیے غیر مجموعی ہو لیکن اس طرح ثابت نہیں کیا جا سکتا: یہ ایک ٹورنگ مشین ہے جو، ان پٹ سے قطع نظر، تمام ثبوتوں کی گنتی کرتی ہے اور ایک تضاد پر رکتی ہے۔ ایک ٹورنگ مشین جو گڈسٹین کے سلسلے سے گزرتی ہے اور صفر پر رکتی ہے کل ہوتی ہے لیکن اسے پیانو ریاضی میں اس طرح ثابت نہیں کیا جا سکتا۔ بلوپ اور فلوپ ٹوٹل فنکشنل پروگرامنگ ٹرمینیشن تجزیہ حوالہ جات برینارڈ، ڈبلیو ایس، لینڈ ویبر، ایل ایچ بھی دیکھیں۔ (1974)، تھیوری آف کمپیوٹیشن، ولی۔ میئر، اے آر، رچی، ڈی ایم۔ (1967)، لوپ پروگراموں کی پیچیدگی، پروک۔ اے سی ایم کے قومی اجلاس، 465۔ سیپسر، ایم۔ (2006)، انٹروڈکشن ٹو دی تھیوری آف کمپیوٹیشن، پی ڈبلیو ایس پبلشنگ کمپنی کوزن، ڈی سی۔ (1997)، آٹومیٹا اینڈ کمپیوٹیبلٹی، سپرنگر۔ اوہلیبش، ای۔ (2002)، ایڈوانسڈ ٹاپکس ان ٹرم ری رائٹنگ، سپرنگر۔ ٹورنگ مشین