History of the Church–Turing thesis
چرچ ٹورنگ تھیسس ("مقالہ") کی تاریخ میں افعال کی نوعیت کے مطالعہ کی ترقی کی تاریخ شامل ہے جن کی اقدار مؤثر طریقے سے قابل حساب ہیں۔ یا، زیادہ جدید اصطلاحات میں، وہ افعال جن کی اقدار الگورتھم کے لحاظ سے قابل حساب ہیں۔ یہ جدید ریاضیاتی نظریہ اور کمپیوٹر سائنس میں ایک اہم موضوع ہے، خاص طور پر الونزو چرچ اور ایلن ٹورنگ کے کام سے وابستہ ہے۔ "کمپیوٹیشن" اور "ریکرشن" کے معنی پر بحث اور دریافت طویل اور متنازعہ رہی ہے۔ یہ مضمون "محوری" کے معنی کی حالیہ بحث کے ذریعے 1889 میں پیانو کے محوریوں سے اس بحث اور دریافت کی تفصیل فراہم کرتا ہے۔ پیانو کے ریاضی کے نو محوریات 1889 میں، جیوسیپی پیانو نے ڈیڈیکنڈ کے کام پر مبنی ایک نئے طریقہ کار کے ذریعے پیش کردہ ریاضی کے اصول پیش کیے۔ سوارے تجویز کرتے ہیں کہ "ابتدائی تکرار" کی ابتدا باضابطہ طور پر پیانو کے محوریوں سے شروع ہوئی، حالانکہ "انیسویں صدی سے بہت پہلے ریاضی دانوں نے انڈکشن کے ذریعے فنکشن کی وضاحت کے اصول کا استعمال کیا تھا۔ ڈیڈیکنڈ 1888 نے قبول شدہ محوریات کا استعمال کرتے ہوئے ثابت کیا کہ اس طرح کی تعریف ایک منفرد فنکشن کی وضاحت کرتی ہے، اور اس نے اسے افعال m + n، m x n، اور mn کی تعریف پر لاگو کیا۔ ڈیڈیکنڈ کے اس کام کی بنیاد پر، پیانو 1889 اور 1891 نے مثبت انٹیجرز کے لیے واقف پانچ [sic] محور لکھے۔ اپنے پانچویں [sic] محوری، ریاضیاتی انڈکشن کے ساتھی کے طور پر، پیانو نے انڈکشن کے ذریعے تعریف کا استعمال کیا، جسے ابتدائی ریکرشن کہا جاتا ہے (پیٹر 1934 اور کلین 1936 کے بعد سے)۔ "۔ مشاہدہ کریں کہ حقیقت میں پیانو کے محوریات تعداد میں 9 ہیں اور محوریہ 9 تکرار/انضمام محوریہ ہے۔ "اس کے بعد 9 کو گھٹا کر 5 کر دیا گیا کیونکہ" محوریہ 2، 3، 4 اور 5 جو شناخت سے متعلق ہیں، بنیادی منطق سے تعلق رکھتے ہیں۔ اس سے وہ پانچ محوریات باقی رہ جاتے ہیں جو عالمی سطح پر "پیانو محوریات" کے نام سے مشہور ہو گئے ہیں۔ پیانو تسلیم کرتا ہے (1891b، p. 93) کہ اس کے محوریات ڈیڈیکنڈ سے آتے ہیں۔ "۔ ہلبرٹ اور پیرس میں 1900 میں ریاضی دانوں کی بین الاقوامی کانگریس (آئی سی ایم) میں مشہور ریاضی دان ڈیوڈ ہلبرٹ نے مسائل کا ایک مجموعہ پیش کیا-جسے اب ہلبرٹ کے مسائل کے نام سے جانا جاتا ہے-ان کی روشنی بیسویں صدی کے ریاضی دانوں کے لیے راہ روشن کرتی ہے۔ ہلبرٹ کے دوسرے اور دسویں مسائل نے ("فیصلہ کا مسئلہ") متعارف کرایا۔ اپنے دوسرے مسئلے میں اس نے اس بات کا ثبوت مانگا کہ "ریاضی" "مستقل" ہے۔ کرٹ گوڈل نے 1931 میں ثابت کیا کہ، جس کے اندر وہ "P" کہتے ہیں (جسے آج کل پیانو ریاضی کہا جاتا ہے)، "ناقابل فیصلہ جملے [تجاویز] موجود ہیں"۔ اس کی وجہ سے، "P کی مستقل مزاجی P میں ناقابل ثابت ہے، بشرطیکہ P مستقل ہو"۔ اگرچہ گوڈل کا ثبوت الونزو چرچ اور ایلن ٹورنگ کے حل کرنے کے لیے ضروری آلات کو ظاہر کرے گا، لیکن وہ خود اس کا جواب نہیں دے گا۔ یہ ہلبرٹ کے 10 ویں مسئلے کے اندر ہے جہاں اصل میں ایک کا سوال ظاہر ہوتا ہے۔ مادے کا مرکز مندرجہ ذیل سوال تھا: "ہمارا کیا مطلب ہے جب ہم کہتے ہیں کہ کوئی فنکشن 'مؤثر طریقے سے حساب کرنے کے قابل' ہے؟" اس کا جواب اس اثر کے لیے کچھ ہوگا: "جب فنکشن کا حساب میکانی طریقہ کار (عمل، طریقہ) کے ذریعے کیا جاتا ہے۔" اگرچہ آج کل آسانی سے بیان کیا گیا ہے، لیکن سوال (اور جواب) تقریبا 30 سال تک جاری رہے گا اس سے پہلے کہ اسے درست طریقے سے تیار کیا جائے۔ ہلبرٹ کی مسئلہ 10 کی اصل وضاحت اس طرح شروع ہوتی ہے: "10. ڈیوفنٹائن مساوات کی حل پذیری کا تعین۔ نامعلوم مقداروں کی کسی بھی تعداد کے ساتھ اور عقلی انٹیگرل کوفشنٹس کے ساتھ ایک ڈیوفنٹائن مساوات کو دیکھتے ہوئے: ایک ایسا عمل وضع کرنا جس کے مطابق اس کا تعین محدود تعداد میں کارروائیوں میں کیا جا سکے کہ آیا مساوات عقلی عددوں میں حل کرنے کے قابل ہے۔ 1922 تک، ڈیوفنٹائن مساوات پر لاگو ایک مخصوص سوال کسی بھی ریاضیاتی فارمولے کے لیے "فیصلہ کرنے کے طریقہ" کے بارے میں زیادہ عام سوال میں تبدیل ہو گیا تھا۔ مارٹن ڈیوس اس کی وضاحت اس طرح کرتے ہیں: فرض کریں کہ ہمیں ایک "حساب کتاب کا طریقہ کار" دیا گیا ہے جو (1) محوریوں کا ایک مجموعہ اور (2) فرسٹ آرڈر منطق میں لکھا گیا ایک منطقی نتیجہ پر مشتمل ہے، یعنی اس میں لکھا گیا ہے جسے ڈیوس "فریج کے کٹوتی کے اصول" (یا بولین منطق کے جدید مساوی) کہتے ہیں۔ گوڈل کے ڈاکٹریٹ کے مقالے نے ثابت کیا کہ فریج کے اصول مکمل تھے۔ "اس معنی میں کہ ہر درست فارمولا قابل تصدیق ہے۔" اس حوصلہ افزا حقیقت کو دیکھتے ہوئے، کیا کوئی عمومی "حساب کتاب کا طریقہ کار" ہو سکتا ہے جو ہمیں بتائے کہ کیا اس کے احاطے سے کوئی نتیجہ اخذ کیا جا سکتا ہے؟ ڈیوس اس طرح کے حساب کتاب کے طریقہ کار کو "الگورتھم" کہتے ہیں۔ یہ بھی ایک الگورتھم ہوگا۔ "اصولی طور پر، [دی] کے لیے ایک الگورتھم تمام انسانی تخفیف استدلال کو وحشیانہ حساب تک کم کر دیتا۔" دوسرے لفظوں میں: کیا کوئی "الگورتھم" ہے جو ہمیں بتا سکتا ہے کہ آیا کوئی فارمولا "سچ" ہے (یعنی۔ ایک الگورتھم جو ہمیشہ صحیح طریقے سے فیصلہ "سچ" یا "جھوٹ" دیتا ہے؟) "۔ ہلبرٹ کو یہ واضح لگ رہا تھا کہ اس مسئلے کے حل کے ساتھ، اینٹشیڈنگس پروبلم، کہ تمام ریاضیاتی سوالات کو خالصتا میکانی انداز میں حل کرنا اصولی طور پر ممکن ہونا چاہیے۔ لہذا، ناقابل حل مسائل کو بالکل بھی دیکھتے ہوئے، اگر ہلبرٹ درست تھا، تو خود اینٹشیڈنگس پروبلم ناقابل حل ہونا چاہیے۔ " درحقیقت: خود ہمارے الگورتھم کا کیا ہوگا؟ کیا یہ محدود تعداد میں مراحل میں اس بات کا تعین کر سکتا ہے کہ آیا یہ خود "کامیاب" اور "سچا" ہے (یعنی یہ ایک لامتناہی "دائرے" یا "لوپ" میں بند نہیں ہوتا ہے، اور یہ اپنے رویے اور نتائج کے بارے میں "سچ" یا "جھوٹ" کا درست فیصلہ کرتا ہے)؟ ہلبرٹ کے دوسرے اور دسویں مسائل سے تین مسائل 1928 کی کانگریس میں [بولوگنا، اٹلی میں] ہلبرٹ نے سوال کو بہت احتیاط سے تین حصوں میں بہتر بنایا۔ اسٹیفن ہاکنگ کا خلاصہ درج ذیل ہے: "1. یہ ثابت کرنے کے لیے کہ تمام حقیقی ریاضیاتی بیانات کو ثابت کیا جا سکتا ہے، یعنی ریاضی کی تکمیل۔ "2. یہ ثابت کرنے کے لیے کہ صرف حقیقی ریاضیاتی بیانات ثابت کیے جا سکتے ہیں، یعنی ریاضی کی مستقل مزاجی۔ ریاضی کی فیصلہ سازی کو ثابت کرنے کے لیے، یعنی کسی بھی ریاضیاتی تجویز کی سچائی یا جھوٹ کا فیصلہ کرنے کے لیے فیصلہ کرنے کے طریقہ کار کا وجود۔ " سادہ ریاضی کے افعال جو ابتدائی تکرار کے لیے ناقابل تلافی ہیں گیبریل سوڈان (1927) اور ولہیم ایکرمین (1928) تکرار کے افعال کو ظاہر کرتے ہیں جو ابتدائی تکرار نہیں ہیں: "کیا ایسی تکرار ہیں جو ابتدائی تکرار کے لیے قابل تخفیف نہیں ہیں ؛ اور خاص طور پر تکرار کو کسی ایسے فنکشن کی وضاحت کے لیے استعمال کیا جا سکتا ہے جو ابتدائی تکرار نہیں ہے؟ "یہ سوال 1926 میں ہلبرٹ کے تسلسل کے مسئلے پر ایک قیاس سے پیدا ہوا، اور اس کا جواب ایکر مین 1928 نے دیا تھا [ہاں: ایسی تکرار ہیں جو ابتدائی تکرار نہیں ہیں]۔" بعد کے سالوں میں کلین نے مشاہدہ کیا کہ روزسا پیٹر (1935) نے ایکرمن کی مثال کو آسان بنایا ("cf. ہلبرٹ برنیز 1934 ") اور رافیل رابنسن (1948) بھی۔ پیٹر نے ایک اور مثال (1935) کی نمائش کی جس میں کینٹر کی اخترن دلیل کو استعمال کیا گیا۔ پیٹر (1950) اور ایکر مین (1940) نے بھی "ٹرانسفائنٹ ریکرشنز" کا مظاہرہ کیا، اور اس نے کلین کو یہ سوچنے پر مجبور کیا: "... کیا ہم کسی بھی" ریکرشن "کے تصور، یا تمام" ریکرسو افعال "کی کلاس کو کسی بھی طرح سے نمایاں کر سکتے ہیں۔ کلین نے یہ نتیجہ اخذ کیا کہ تمام "تکرار" میں (i) ابتدائی تکرار افعال کے اپنے §54 رسمی حسابات میں پیش کردہ رسمی تجزیہ اور (ii) ریاضیاتی انڈکشن کا استعمال شامل ہے۔ وہ فوری طور پر یہ کہتے ہوئے آگے بڑھتے ہیں کہ درحقیقت گوڈل-ہربرانڈ کی تعریف درحقیقت "تمام تکراری افعال کی خصوصیت" رکھتی ہے-نیچے 1934 کا اقتباس دیکھیں۔ گوڈل کا ثبوت 1930 میں، ریاضی دان ہلبرٹ کے لیے ریاضی کی میٹنگ اور ریٹائرمنٹ ایونٹ کے لیے جمع ہوئے۔ جیسا کہ قسمت کے پاس ہوگا، "اسی ملاقات میں، ایک نوجوان چیک ریاضی دان، کرٹ گوڈل نے نتائج کا اعلان کیا جس نے اس سے نمٹا [ہلبرٹ کی رائے کہ تینوں جوابات ہاں تھے] ایک سنگین دھچکا۔" انہوں نے اعلان کیا کہ ہلبرٹ کے 1928 کے تین سوالوں میں سے پہلے دو کا جواب نہیں تھا۔ اس کے بعد 1931 میں گوڈل نے اپنا مشہور مقالہ آن فارمللی انڈیسیڈبل پروپوزیشنز آف پرنسپیا میتھمیٹکا اینڈ ریلیٹڈ شائع کیا اس مقالے کے پیش لفظ میں مارٹن ڈیوس ایک انتباہ دیتے ہیں: "قارئین کو خبردار کیا جانا چاہیے کہ [اس خاص مقالے میں] جسے گوڈل ریکرسو افعال کہتا ہے اب اسے ابتدائی ریکرسو افعال کہا جاتا ہے۔ (نظر ثانی شدہ اصطلاحات کلین نے متعارف کرائی تھیں) "۔ "موثر حساب کتاب" کی گوڈل توسیع کلین (1952) کا حوالہ دیتے ہوئے، "تمام" ریکرسو افعال "کی خصوصیت کو گوڈل 1934 کے ذریعہ 'جنرل ریکرسو فنکشن' کی تعریف میں پورا کیا گیا تھا، جس نے ہر برانڈ کی تجویز پر بنایا تھا" (کلین 1952:274)۔ گوڈل نے انسٹی ٹیوٹ فار ایڈوانسڈ اسٹڈی (آئی اے ایس)، پرنسٹن این جے میں لیکچرز کا ایک سلسلہ پیش کیا۔ مارٹن ڈیوس ڈیوس کے لکھے ہوئے ایک پیش لفظ میں مشاہدہ کیا گیا ہے کہ "ڈاکٹر گوڈل نے ایک خط میں کہا ہے کہ وہ ان لیکچرز کے وقت بالکل بھی اس بات پر قائل نہیں تھے کہ ان کے ریکرشن کے تصور میں تمام ممکنہ ریکرشن شامل ہیں۔" ڈاسن کا کہنا ہے کہ ان لیکچرز کا مقصد ان خدشات کو واضح کرنا تھا کہ "نامکمل تھیوریمز کسی نہ کسی طرح رسمی شکل کی خصوصیات پر منحصر تھے": "گوڈل نے اپنے 1934 کے مقالے کے آخری حصے میں ایکرمن کی مثال کا ذکر کیا،" جنرل ریکرسو فنکشن "کے تصور کو تحریک دینے کے ایک طریقے کے طور پر جس کی انہوں نے وہاں وضاحت کی تھی ؛ لیکن اس سے پہلے فوٹ نوٹ 3 میں، انہوں نے پہلے ہی قیاس آرائی کر لی تھی (" ایک ہیورسٹک اصول "کے طور پر) کہ تمام حتمی کمپیوٹیبل افعال حاصل کیے جا سکتے ہیں۔ "اس قیاس آرائی کے بعد سے بہت سارے تبصرے سامنے آئے ہیں۔ خاص طور پر، جب مارٹن ڈیوس نے گوڈل کے 1934 کے لیکچرز [ڈیوس 1965:41 ff میں] شائع کرنے کا کام شروع کیا تو اس نے اسے چرچ کے تھیسس کی ایک قسم کے طور پر لیا۔ لیکن ڈیوس کو لکھے گئے ایک خط میں۔ گوڈل نے زور دے کر کہا کہ یہ "سچ نہیں" تھا کیونکہ ان لیکچرز کے وقت وہ "بالکل بھی قائل نہیں" تھے کہ ان کے ریکرشن کے تصور میں "تمام ممکنہ ریکرشنز" شامل ہیں۔ بلکہ، انہوں نے کہا، "وہاں بیان کردہ قیاس صرف 'محدود (حساب کتاب) طریقہ کار' اور 'تکراری طریقہ کار' کے مساوات کی طرف اشارہ کرتا ہے۔" اس مسئلے کو واضح کرنے کے لیے گوڈل نے لیکچرز میں ایک پوسٹ اسکرپٹ شامل کیا، جس میں انہوں نے اشارہ کیا کہ جس چیز نے آخر کار انہیں اس بات پر قائل کیا کہ بدیہی طور پر کمپیوٹیبل افعال ان کے ساتھ موافق تھے جو عام طور پر تکراری تھے وہ ایلن ٹورنگ کا کام تھا۔ "عام تکرار یا λ-تعریف کو موثر کمپیوٹیبلٹی کے غیر رسمی تصور کی مناسب خصوصیت کے طور پر سمجھنے میں گوڈل کی ہچکچاہٹ کا کئی مصنفین نے تفصیل سے جائزہ لیا ہے [فوٹ نوٹ 248:" "خاص طور پر ڈیوس 1982 ؛ گانڈی 1980 اور 1988 ؛ سیگ 1994 دیکھیں" "]۔" اس بات پر اتفاق ہے کہ درحقیقت، ایلن ٹورنگ کے تجزیے کی طرح نہ تو گوڈل اور نہ ہی چرچ کی رسمی کارروائیاں اتنی واضح یا اندرونی طور پر قائل کرنے والی تھیں، اور ولفریڈ سیگ نے استدلال کیا ہے کہ چرچ کے مقالے کے حق میں "مختلف تصورات کے سنگم" کے ذریعہ فراہم کردہ ثبوت (حقیقت یہ ہے کہ چرچ، گوڈل، پوسٹ اور ایلن ٹورنگ کے ذریعہ تجویز کردہ نظام ایک ہی توسیع کے حامل نکلے ہیں) عام طور پر تصور کیے جانے سے کم مجبور کرنے والے ہیں۔ لہذا، گوڈل کی فطری احتیاط کے علاوہ اس کے شکوک و شبہات کی اچھی وجوہات تھیں۔ لیکن پھر، وہ اپنے عمومی تکرار کے تصور کے ذریعے کیا حاصل کرنے کی کوشش کر رہا تھا؟ "بلکہ، گوڈل نے ہربرانڈ کے نظریات میں ترمیم کے ذریعے [عمومی تکراری افعال کی کلاس کی] تعریف حاصل کی۔ اور ولفریڈ سیگ نے استدلال کیا ہے کہ 1934 کے مقالے کے آخری حصے میں [لیکچر نوٹ] ان کا اصل مقصد" "[ہربرانڈ کے] علمی طور پر محدود ثبوت کے تصور سے تکراری افعال کو الگ کرنا" "تھا جس میں" "مساوات حاصل کرنے کے مکینیکل قوانین" "کی وضاحت کی گئی تھی۔" سیگ تجویز کرتے ہیں کہ گوڈل کے "عمومی" تکرار کے تصور کے بارے میں جو چیز زیادہ عام تھی وہ یہ تھی کہ ہربرانڈ کا ارادہ صرف ان افعال کی خصوصیت کرنا تھا جو حتمی ذرائع [250] کے ذریعے تکرار ثابت ہو سکتے ہیں۔ " پرنسٹن کلین اور روسر میں گوڈل کے لیکچرز نے پرنسٹن میں گوڈل کے 1934 کے لیکچرز کو نقل کیا۔ اپنے مقالے میں جنرل ریکرسو فنکشنز آف نیچرل نمبرز کلین کا کہنا ہے کہ: "قدرتی اعداد کی عمومی ریکرسو فنکشن کی تعریف ہربرانڈ نے گوڈل کو تجویز کی تھی، اور اسے گوڈل نے 1934 میں پرنسٹن میں لیکچرز کے سلسلے میں ایک اہم ترمیم کے ساتھ استعمال کیا تھا۔" گوڈل کے معنی میں ایک ریکرسو فنکشن (رشتہ)۔ اب اسے ایک ابتدائی ریکرسو فنکشن (رشتہ) کہا جائے گا۔ چرچ کے مقالے این انسولویبل پروبلم آف ایلیمنٹری نمبر تھیوری (1936) نے ثابت کیا کہ اینٹشیڈنگس پروبلم λ-کیلکولس اور گوڈل-ہربرانڈ کے عمومی تکرار کے اندر ناقابل فیصلہ تھا۔ اس کے علاوہ چرچ نے کلین کے دو نظریات کا حوالہ دیا جس سے ثابت ہوا کہ λ-کیلکولس میں بیان کردہ افعال عام تکرار کے ذریعے بیان کردہ افعال سے ملتے جلتے ہیں: "تھیوریم XVI۔ مثبت انٹیجرز کا ہر ریکرسو فنکشن λ-definable.16 "تھیوریم XVII ہے۔ مثبت انٹیجرز کا ہر λ-متعین فنکشن recursive.17 "16 ہے۔ یہاں کی شکل میں یہ سب سے پہلے کلین نے حاصل کیا تھا۔ 17 یہ نتیجہ موجودہ مصنف اور ایس سی کلین نے تقریبا ایک ہی وقت میں آزادانہ طور پر حاصل کیا تھا۔ کاغذ ایک بہت لمبے فوٹ نوٹ کے ساتھ کھلتا ہے، 3. ایک اور فوٹ نوٹ، 9، بھی دلچسپ ہے۔ مارٹن ڈیوس کا کہنا ہے کہ "یہ مقالہ بنیادی طور پر اس کے واضح بیان کے لیے اہم ہے (جسے چرچ کے مقالے کے نام سے جانا جاتا ہے) کہ جن افعال کو ایک محدود الگورتھم کے ذریعے شمار کیا جا سکتا ہے وہ قطعی طور پر تکراری افعال ہیں، اور اس کے نتیجے میں ایک واضح ناقابل حل مسئلہ دیا جا سکتا ہے": "3 جیسا کہ ظاہر ہوگا، موثر حساب کی یہ تعریف دو مساوی شکلوں میں سے کسی ایک میں بیان کی جا سکتی ہے، (1). λ-قابل تعریف. 2). تکراری۔ λ-تعریف کا تصور مشترکہ طور پر موجودہ مصنف اور ایس سی کلین کی وجہ سے ہے، اس کی طرف مسلسل اقدامات موجودہ مصنف نے اینلز آف میتھمیٹکس، جلد میں اٹھائے ہیں۔ 34 (1933)، صفحہ 863، اور کلین ان دی امریکن جرنل آف میتھمیٹکس، جلد۔ 57 (1935)، صفحہ 219۔ ذیل میں §4 کے معنی میں تکرار کا تصور مشترکہ طور پر جیکس ہربرانڈ اور کرٹ گوڈل کی وجہ سے ہے، جیسا کہ وہاں بیان کیا گیا ہے۔ اور دونوں تصورات کی مساوات کا ثبوت بنیادی طور پر کلین کا ہے، بلکہ جزوی طور پر موجودہ مصنف اور جے کا بھی ہے۔ بی۔ روزسر۔ ان تصورات کو موثر حساب کے بدیہی تصور کے ساتھ شناخت کرنے کی تجویز سب سے پہلے موجودہ مقالے میں کی گئی ہے (لیکن نیچے §7 کا پہلا فوٹ نوٹ دیکھیں)۔ کلین (امریکن جرنل آف میتھمیٹکس، 1935) کے طریقوں کی مدد سے، موجودہ مقالے کے تحفظات کو، نسبتا معمولی ترمیم کے ساتھ، مکمل طور پر λ-تعریف کے لحاظ سے، تکرار کے تصور کو استعمال کیے بغیر انجام دیا جا سکتا ہے۔ دوسری طرف، چونکہ موجودہ مقالے کے نتائج حاصل کیے گئے تھے، اس لیے کلین کی طرف سے یہ دکھایا گیا ہے (ان کا آنے والا مقالہ دیکھیں، "قدرتی اعداد کے عمومی تکراری افعال") کہ مماثل نتائج مکمل طور پر تکراری کے لحاظ سے حاصل کیے جا سکتے ہیں، بغیر λ-تعریف کا استعمال کیے۔ تاہم، یہ حقیقت کہ موثر حساب کی دو ایسی وسیع پیمانے پر مختلف اور (مصنف کی رائے میں) یکساں طور پر فطری تعریفیں مساوی ثابت ہوتی ہیں، اس یقین کے لیے ذیل میں پیش کردہ وجوہات کی طاقت میں اضافہ کرتی ہیں کہ وہ اس تصور کی عمومی خصوصیت کے طور پر تشکیل دیتی ہیں جو اس کی معمول کی بدیہی تفہیم سے مطابقت رکھتی ہے۔ فوٹ نوٹ 9 سیکشن § 4 ریکرسو افعال میں ہے: "9 یہ تعریف [" ریکرسو "کی] ریکرسو افعال کی ایک تعریف سے قریب سے متعلق ہے، اور اس کی تجویز پیش کی گئی تھی، جسے کرٹ گوڈل نے پرنسٹن، این جے، 1934 کے لیکچرز میں تجویز کیا تھا، اور اس کا سہرا جزوی طور پر جیکس ہربرانڈ کی ایک غیر شائع شدہ تجویز کو دیا گیا تھا۔ بنیادی خصوصیات جن میں تکرار کی موجودہ تعریف گوڈل سے مختلف ہے وہ ایس سی کلین کی وجہ سے ہیں۔ کلین کے ایک آنے والے مقالے میں جس کا عنوان "قدرتی اعداد کے عمومی تکراری افعال" ہے، اس کے مطابق ہے کہ موجودہ معنوں میں ہر تکراری فعل گوڈل (1934) کے معنی میں بھی تکراری ہے اور اس کے برعکس۔ چرچ کے مقالے این انسولویبل پروبلم آف ایلیمنٹری نمبر تھیوری (1936) سے کچھ وقت پہلے گوڈل اور چرچ کے درمیان ایک مکالمہ ہوا کہ آیا "الگورتھم" اور "موثر حساب کاری" کے تصور کی تعریف کے لیے λ-تعریف کافی تھی یا نہیں۔ چرچ (1936) میں ہم دیکھتے ہیں، باب §7 کے تحت موثر حساب کتاب کا تصور، ایک فوٹ نوٹ 18 جس میں درج ذیل بیان کیا گیا ہے: "18 موثر حساب کتاب اور تکرار کے درمیان تعلق کا سوال (جس کا جواب یہاں دو تصورات کی شناخت کے ذریعے دینے کی تجویز کی گئی ہے) مصنف کے ساتھ گفتگو میں گوڈل نے اٹھایا تھا۔ موثر حساب کتاب اور λ-تعریف کے درمیان تعلق کا متعلقہ سوال پہلے مصنف کی طرف سے آزادانہ طور پر پیش کیا گیا تھا۔ چرچ کی "شناخت" کرنے کا مطلب ہے-"شناخت قائم کرنا" نہیں-بلکہ "یکساں ہونے یا بننے کا سبب بننا"، "متحد ہونے کا تصور کرنا" (جیسا کہ روح، نقطہ نظر یا اصول میں) (vt شکل)، اور (vi شکل) جیسا کہ "ایک جیسا ہونا یا بننا"۔ پوسٹ اور "ایفیکٹو کیلکولیبلٹی" بطور "نیچرل لا" پوسٹ کے شکوک و شبہات کہ آیا ریکرشن "ایفیکٹو کیلکولیبلٹی" کی مناسب تعریف تھی یا نہیں، نیز چرچ کے مقالے کی اشاعت نے انہیں 1936 کے موسم خزاں میں "نفسیاتی وفاداری" کے ساتھ "فارمولیشن" کی تجویز کرنے کی ترغیب دی: ایک کارکن ہر خانے میں کاغذ کی ایک شیٹ پر مشین کی طرح "ابتدائی اعمال" انجام دیتے ہوئے "خالی جگہوں یا خانوں کی ایک ترتیب" سے گزرتا ہے۔ کارکن "سمتوں کے ایک مقررہ غیر متغیر سیٹ" سے لیس ہوتا ہے۔ ہر ہدایت تین یا چار علامتوں پر مشتمل ہوتی ہے: (1) ایک شناخت کرنے والا لیبل/نمبر، (2) ایک آپریشن، (3) اگلی ہدایت جی ؛ تاہم، اگر ہدایت قسم (ای) کی ہے اور عزم "ہاں" ہے تو پھر ہدایت جی "ورنہ" اگر یہ "نہیں" ہدایت جی ہے۔ "ابتدائی اعمال" 5 میں سے صرف 1 قسم کے ہوتے ہیں: (اے) کاغذ کو اس باکس میں نشان زد کریں جس میں وہ ہے (یا پہلے سے موجود نشان کو زیادہ نشان زد کریں)، (بی) نشان کو مٹا دیں (یا زیادہ مٹا دیں)، (سی) ایک کمرے کو دائیں طرف منتقل کریں، (ڈی) ایک کمرے کو بائیں طرف منتقل کریں، (ای) اس بات کا تعین کریں کہ کاغذ نشان زدہ ہے یا خالی۔ کارکن ابتدائی کمرے میں مرحلہ 1 سے شروع کرتا ہے، اور وہی کرتا ہے جو ہدایات انہیں کرنے کی ہدایت کرتی ہیں۔ (پوسٹ ٹورنگ مشین پر مزید دیکھیں۔) "بدیہی نظریات" کے بارے میں تعارف میں مذکور اس معاملے نے پوسٹ کو چرچ پر ایک طاقتور دھکا لگانے پر مجبور کیا: "مصنف کو توقع ہے کہ موجودہ تشکیل گوڈل چرچ کے معنی میں منطقی طور پر تکرار کے مساوی ثابت ہوگی۔ تاہم، اس کا مقصد نہ صرف ایک خاص منطقی طاقت کا نظام پیش کرنا ہے بلکہ اس کے محدود میدان میں، نفسیاتی وفاداری بھی ہے۔ مؤخر الذکر معنوں میں وسیع تر اور وسیع تر فارمولیشن پر غور کیا جاتا ہے۔ دوسری طرف، ہمارا مقصد یہ ظاہر کرنا ہوگا کہ اس طرح کے تمام فارمولیشن 1 کے لیے منطقی طور پر قابل تخفیف ہیں۔ ہم اس نتیجے کو موجودہ وقت میں ایک عملی مفروضے کے طور پر پیش کرتے ہیں۔ اور ہمارے ذہن میں ایسا ہے کہ چرچ کی مؤثر حساب کی شناخت recursiveness.8 "(اصل میں ترچھے حروف) 7 [وہ ثبوت کے لیے ایک نقطہ نظر کا خاکہ بناتا ہے] 8" Cf. چرچ، لاک۔ cit، pp. 346، 356-358۔ درحقیقت چرچ اور دیگر کے ذریعے پہلے سے کیا گیا کام اس شناخت کو عملی مفروضے کے مرحلے سے کافی آگے لے جاتا ہے۔ لیکن ایک تعریف کے تحت اس شناخت کو چھپانا اس حقیقت کو چھپاتا ہے کہ ہومو سیپینز کی ریاضی کی طاقت کی حدود میں ایک بنیادی دریافت کی گئی ہے اور ہمیں اس کی مسلسل تصدیق کی ضرورت سے اندھا کر دیتی ہے۔ " دوسرے لفظوں میں پوسٹ کہہ رہا ہے کہ "صرف اس وجہ سے کہ آپ نے اس کی وضاحت کی ہے اس لیے یہ واقعی ایسا نہیں ہے ؛ آپ کی تعریف ایک وجدان سے زیادہ کچھ نہیں ہے"۔ پوسٹ ایک تعریف سے زیادہ تلاش کر رہا تھا: "مندرجہ بالا پروگرام کی کامیابی، ہمارے لیے، اس مفروضے کو اتنی تعریف یا محوری میں نہیں بلکہ قدرتی قانون میں تبدیل کر دے گی۔ مصنف کو ایسا ہی لگتا ہے کہ گوڈل کے نظریہ اور چرچ کے نتائج کو تمام علامتی منطقوں اور حل کے تمام طریقوں سے متعلق نتائج میں تبدیل کیا جا سکتا ہے۔ " اس متنازعہ موقف کو ایلن ٹورنگ 1939 میں ناگوار اظہار ملتا ہے، اور یہ گوڈل، گانڈی اور سیگ کے ساتھ دوبارہ ظاہر ہوگا۔ ٹورنگ اینڈ کمپیوٹیبلٹی اے ایم ٹورنگ کا مقالہ آن کمپیوٹیبل نمبرز، ود این ایپلیکیشن ٹو دی اینٹشیڈنگس پروبلم نومبر 1936 میں لندن میتھمیٹیکل سوسائٹی کو پہنچایا گیا۔ ایک بار پھر قارئین کو ایک احتیاط کو ذہن میں رکھنا چاہیے: جیسا کہ ٹورنگ نے استعمال کیا ہے، لفظ "کمپیوٹر" ایک انسان ہے، اور "کمپیوٹر" کا عمل جسے وہ "کمپیوٹنگ" کہتے ہیں ؛ مثال کے طور پر، وہ کہتا ہے کہ "کمپیوٹنگ عام طور پر کاغذ پر کچھ علامتیں لکھ کر کی جاتی ہے" (صفحہ 135)۔ لیکن وہ اپنی مشین کی تعریف کے تناظر میں لفظ "کمپیوٹیشن" استعمال کرتا ہے، اور "کمپیوٹیبل" نمبروں کی اس کی تعریف اس طرح ہے: "" کمپیوٹیبل "نمبروں کو مختصر طور پر حقیقی اعداد کے طور پر بیان کیا جا سکتا ہے جن کے اظہار اعشاریہ کے طور پر محدود ذرائع سے قابل حساب ہوتے ہیں۔ میری تعریف کے مطابق، ایک عدد قابل حساب ہے اگر اس کے اعشاریہ کو مشین کے ذریعے لکھا جا سکے۔" ٹورنگ کی "مشین" کی تعریف کیا ہے؟ ٹورنگ دو تعریفیں دیتا ہے، پہلا خلاصہ §1 کمپیوٹنگ مشینوں میں اور دوسرا §9 میں بہت ملتا جلتا ہے۔ I انسانی "کمپیوٹر" کے اعمال کے اس کے مزید تفصیلی تجزیے سے اخذ کیا گیا ہے۔ اپنی تعریف §1 کے حوالے سے وہ کہتے ہیں کہ "جواز اس حقیقت میں مضمر ہے کہ انسانی یادداشت لازمی طور پر محدود ہے"، اور وہ لفظ "تمام" کے استعمال کے ساتھ اپنی مجوزہ مشین کے گنجے دعوے کے ساتھ §1 کا اختتام کرتے ہیں "یہ میری دلیل ہے کہ یہ کارروائیاں [ٹیپ مربع پر علامت لکھیں، علامت کو مٹا دیں، ایک مربع کو بائیں طرف منتقل کریں، ایک مربع کو دائیں طرف منتقل کریں، علامت کے لیے مربع کو اسکین کریں اور ایک اسکین شدہ علامت کے نتیجے میں مشین کی تشکیل کو تبدیل کریں] میں وہ سب شامل ہیں جو کسی نمبر کے حساب میں استعمال ہوتے ہیں۔" مندرجہ بالا بریکٹ میں لفظ ایک کا زور جان بوجھ کر دیا گیا ہے۔ §9. I کے حوالے سے وہ مشین کو مزید مربعوں کی جانچ کرنے کی اجازت دیتا ہے۔ یہ زیادہ مربع قسم کا طرز عمل ہے جس کے بارے میں اس کا دعوی ہے کہ یہ کمپیوٹر (شخص) کے اعمال کی نشاندہی کرتا ہے: "مشین کمپیوٹر کے مشاہدہ کردہ B مربعوں کے مطابق B مربعوں کو اسکین کرتی ہے۔ کسی بھی حرکت میں مشین اسکین شدہ مربع پر کسی علامت کو تبدیل کر سکتی ہے یا اسکین شدہ مربعوں میں سے کسی ایک کو دوسرے مربع میں تبدیل کر سکتی ہے جو دوسرے اسکین شدہ مربعوں میں سے کسی ایک سے ایل مربع سے زیادہ دور نہیں ہے۔ جو مشینیں ابھی بیان کی گئی ہیں وہ بنیادی طور پر کمپیوٹنگ مشینوں سے بہت مختلف نہیں ہیں جیسا کہ §2 [sic] میں بیان کیا گیا ہے، اور اس قسم کی کسی بھی مشین کے مطابق ایک کمپیوٹنگ مشین کو اسی ترتیب کا حساب لگانے کے لیے بنایا جا سکتا ہے، یعنی کمپیوٹر کے ذریعے مرتب کردہ ترتیب۔ ٹورنگ §2 میں "کمپیوٹنگ مشین" کی وضاحت کرتے ہیں (i) "اے مشین" ("خودکار مشین") جیسا کہ §1 میں اضافی پابندی کے ساتھ بیان کیا گیا ہے (ii): (ii) یہ دو قسم کی علامتیں پرنٹ کرتا ہے-اعداد و شمار 0 اور 1-اور دیگر علامتیں۔ اعداد و شمار 0 اور 1 "مشین کے ذریعہ شمار کردہ ترتیب" کی نمائندگی کریں گے۔ مزید برآں، اس بات کی وضاحت کرنے کے لیے کہ آیا نمبر کو "کمپیوٹیبل" سمجھا جانا ہے، مشین کو 0 اور 1 کی لامحدود تعداد پرنٹ کرنی چاہیے ؛ اگر نہیں تو اسے "سرکلر" سمجھا جاتا ہے ؛ بصورت دیگر اسے "سرکل فری" سمجھا جاتا ہے: "ایک نمبر کمپیوٹیبل ہے اگر یہ سرکل فری مشین کے ذریعے مرتب کردہ نمبر سے انٹیجر سے مختلف ہو۔" اگرچہ وہ اسے اپنا "مقالہ" نہیں کہتے، ٹورنگ اس بات کا ثبوت پیش کرتے ہیں کہ ان کی "کمپیوٹیبلٹی" چرچ کی "موثر حساب کاری" کے مساوی ہے: "ایک حالیہ مقالے میں الونزو چرچ نے" موثر حساب کاری "کا ایک خیال متعارف کرایا ہے، جو میری" کمپیوٹیبلٹی "کے مساوی ہے، لیکن اس کی وضاحت بہت مختلف ہے۔ "کمپیوٹیبلٹی" اور "ایفیکٹو کیلکولیبلٹی" کے درمیان مساوات کا ثبوت موجودہ کاغذ کے ضمیمہ میں بیان کیا گیا ہے۔ ضمیمہ: کمپیوٹیبلٹی اور موثر حساب کتاب مندرجہ ذیل طریقے سے شروع ہوتا ہے ؛ مشاہدہ کریں کہ وہ یہاں تکرار کا ذکر نہیں کرتا ہے، اور درحقیقت اس کے پروف اسکیچ میں اس کی مشین λ-کیلکولس میں علامتوں کے تاروں کو منچ کرتی ہے اور کیلکولس اس کی مشین کی "مکمل ترتیبات" کو منچ کرتا ہے، اور کہیں بھی تکرار کا ذکر نہیں ہے۔ مشین-کمپیوٹیبلٹی اور ریکرشن کی مساوات کا ثبوت کلین 1943 اور 1952 کا انتظار کرنا چاہیے: "یہ نظریہ کہ تمام مؤثر طریقے سے قابل حساب (λ-ڈیفینیبل) ترتیبات قابل حساب ہیں اور اس کے برعکس خاکہ میں ذیل میں ثابت کیے گئے ہیں۔" ایسا لگتا ہے کہ گانڈی (1960) اس جرات مندانہ پروف اسکیچ کو چرچ کے تھیسس کے ساتھ الجھاتا ہے۔ نیچے 1960 اور 1995 دیکھیں۔ مزید برآں ٹورنگ کی تعریفوں کو احتیاط سے پڑھنے سے قاری یہ مشاہدہ کرنے پر مجبور ہوتا ہے کہ ٹورنگ اس بات پر زور دے رہا تھا کہ §1 میں اس کی مجوزہ مشین کے "آپریشنز" کسی بھی قابل حساب نمبر کا حساب لگانے کے لیے کافی ہیں، اور وہ مشین جو انسانی "کمپیوٹر" کے عمل کی نقل کرتی ہے جیسا کہ §9 میں پیش کیا گیا ہے۔ I اس مجوزہ مشین کی ایک قسم ہے۔ اس نکتے کا اعادہ ٹورنگ 1939 میں کریں گے۔ ٹورنگ مشین کے حساب کے ساتھ موثر حساب کی نشاندہی کرتا ہے ایلن ٹورنگ کا بڑے پیمانے پر پرنسٹن پی ایچ ڈی مقالہ (الونزو چرچ کے تحت) آرڈینلز پر مبنی منطق کے نظام کے طور پر ظاہر ہوتا ہے۔ اس میں وہ "مؤثر طریقے سے قابل حساب" کی تعریف کی تلاش کا خلاصہ پیش کرتا ہے۔ وہ ایک تعریف تجویز کرتا ہے جیسا کہ بولڈ فیس کی قسم میں دکھایا گیا ہے جو خاص طور پر "مشین کمپیوٹیشن" اور "مؤثر طریقے سے حساب کتاب" کے تصورات کی شناخت کرتا ہے (یکساں پیش کرتا ہے)۔ "کسی فنکشن کو" مؤثر طریقے سے قابل حساب "کہا جاتا ہے اگر اس کی اقدار کو کسی خالص میکانی عمل کے ذریعے پایا جا سکے۔ اگرچہ اس خیال کی بدیہی گرفت حاصل کرنا کافی آسان ہے، اس کے باوجود کچھ اور قطعی، ریاضیاتی طور پر قابل اظہار تعریف رکھنا مطلوب ہے۔ اس طرح کی تعریف سب سے پہلے 1934 میں پرنسٹن میں گوڈل نے دی تھی۔ ان افعال کو گوڈل نے "جنرل ریکرسو" کے طور پر بیان کیا ہے۔ مؤثر حساب کی ایک اور تعریف چرچ کی طرف سے دی گئی ہے۔ جو اسے λ-تعریف کے ساتھ شناخت کرتا ہے۔ مصنف نے حال ہی میں بدیہی خیال سے زیادہ قریب سے متعلق ایک تعریف تجویز کی ہے (ٹورنگ [1]، پوسٹ کا [1] بھی دیکھیں)۔ یہ اوپر بیان کیا گیا تھا کہ "کسی فنکشن کا مؤثر طریقے سے حساب لگایا جا سکتا ہے اگر اس کی اقدار کو کسی خالص میکانی عمل کے ذریعے پایا جا سکے"۔ ہم اس بیان کو لفظی طور پر ایک خالص میکانی عمل کے ذریعے سمجھ سکتے ہیں جسے مشین کے ذریعے انجام دیا جا سکتا ہے۔ ان مشینوں کے ڈھانچوں کی ایک مخصوص عام شکل میں ریاضیاتی وضاحت دینا ممکن ہے۔ ان خیالات کی ترقی مصنف کی کمپیوٹیبل فنکشن کی تعریف کی طرف لے جاتی ہے، اور موثر حساب کے ساتھ کمپیوٹیبلٹی کی شناخت کی طرف لے جاتی ہے۔ یہ ثابت کرنا مشکل نہیں ہے، اگرچہ کچھ مشکل ہے، کہ یہ تینوں تعریفیں مساوی ہیں۔ "κ ہم" کمپیوٹیبل فنکشن "کے اظہار کو کسی مشین کے ذریعے قابل حساب فنکشن کے معنی کے لیے استعمال کریں گے، اور ہم" مؤثر طریقے سے قابل حساب "کو ان تعریفوں میں سے کسی ایک کے ساتھ خاص شناخت کے بغیر بدیہی خیال کا حوالہ دیتے ہیں۔ ہم کمپیوٹیبل فنکشن کی طرف سے لی گئی اقدار کو قدرتی اعداد تک محدود نہیں کرتے ہیں ؛ مثال کے طور پر ہمارے پاس کمپیوٹیبل پروپوزیشنل افعال ہو سکتے ہیں۔ یہ ایک طاقتور اظہار ہے۔ کیونکہ "مماثلت" دراصل ضروری اور کافی شرائط کا ایک غیر واضح بیان ہے، دوسرے الفاظ میں شناخت کے لیے کوئی دوسری ہنگامی صورتحال نہیں ہے سوائے اس کے کہ الفاظ "فنکشن"، "مشین"، "کمپیوٹیبل"، اور "مؤثر طریقے سے قابل حساب" کی کیا تشریح کی گئی ہے: تمام افعال کے لیے: اگر "یہ فنکشن مشین کے ذریعے قابل حساب ہے" تب "یہ فنکشن مؤثر طریقے سے قابل حساب ہے" اور اگر "یہ فنکشن مؤثر طریقے سے قابل حساب ہے" تب "یہ فنکشن مشین کے ذریعے قابل حساب ہے۔ روسر: ریکرشن، λ-کیلکولس، اور ٹورنگ مشین کمپیوٹیشن آئیڈینٹی J۔ بی۔ روزسر کا مقالہ این انفارمل ایکسپوزیشن آف پروفز آف گوڈل تھیوریم اینڈ چرچز تھیوریم مندرجہ ذیل بیان کرتا ہے: "" مؤثر طریقہ "یہاں ایک طریقہ کے بجائے خاص معنوں میں استعمال کیا جاتا ہے جس کا ہر مرحلہ قطعی طور پر پہلے سے طے شدہ ہوتا ہے اور جس کا جواب محدود تعداد میں مراحل میں پیش کرنا یقینی ہوتا ہے۔ اس خاص معنی کے ساتھ، تاریخ 5 کی تین مختلف قطعی تعریفیں دی گئی ہیں۔ ان میں سے سب سے آسان بیان (پوسٹ اور ٹورنگ کی وجہ سے) بنیادی طور پر یہ کہتا ہے کہ مسائل کے ایک مخصوص سیٹ کو حل کرنے کا ایک موثر طریقہ موجود ہے اگر کوئی ایسی مشین بنا سکے جو سوال داخل کرنے اور (بعد میں) جواب کو پڑھنے کے علاوہ سیٹ کے کسی بھی مسئلے کو بغیر کسی انسانی مداخلت کے حل کرے۔ تینوں تعریفیں مساوی ہیں، اس لیے اس سے کوئی فرق نہیں پڑتا کہ کون سی تعریف استعمال کی گئی ہے۔ مزید برآں، یہ حقیقت کہ تینوں مساوی ہیں، کسی ایک کی درستگی کے لیے ایک بہت مضبوط دلیل ہے۔ 5 ایک تعریف چرچ کی طرف سے I میں دی گئی ہے [یعنی۔ چرچ 1936 ابتدائی نمبر تھیوری کا ایک ناقابل حل مسئلہ]۔ ایک اور تعریف جیکس ہربرانڈ اور کرٹ گوڈل کی وجہ سے ہے۔ یہ I، فوٹ نوٹ 3، صفحہ 346 میں بیان کیا گیا ہے۔ تیسری تعریف آزادانہ طور پر دو قدرے مختلف شکلوں میں ای ایل پوسٹ اور اے ایم ٹورنگ نے دی تھی۔ پہلی دو تعریفیں I میں مساوی ثابت ہوتی ہیں۔ تیسرا اے ایم ٹورنگ، کمپیوٹیبلٹی اینڈ λ-ڈیفینیبلٹی [جرنل آف سمبولک لاجک، جلد] کے ذریعہ پہلے دو کے مساوی ثابت ہوا ہے۔ 2 (1937)، پی۔ 153-163] "۔ کلین اور تھیسس I کلین نے اپنے مقالے ریکرسو پریڈیکیٹس اینڈ کوانٹیفائرز میں "جنرل ریکرسو" فنکشنز اور "پارشل ریکرسو فنکشنز" کی وضاحت کی ہے۔ نمائندگی کرنے والا فنکشن، میو آپریٹر، وغیرہ اپنی ظاہری شکل بناتے ہیں۔ وہ §12 الگورتھم کے نظریات میں اپنے مشہور مقالہ اول کو بیان کرتے ہوئے آگے بڑھتے ہیں، جسے وہ 1952 میں چرچ کا مقالہ کہتے ہیں: "یہ تحقیقی حقیقت، نیز علامتی الگورتھم کے عمل کی نوعیت پر کچھ عکاسی، چرچ کو مندرجہ ذیل مقالہ 22 بیان کرنے پر مجبور کرتی ہے۔ یہی مقالہ ٹورنگ کی کمپیوٹنگ مشینوں کی تفصیل میں مضمر ہے۔ "تھیسس I. ہر مؤثر طریقے سے قابل حساب فنکشن (مؤثر طریقے سے فیصلہ کن پیشن گوئی) عام تکرار ہے۔ "چونکہ مؤثر طریقے سے قابل حساب (مؤثر طریقے سے فیصلہ کن) اصطلاح کی ایک درست ریاضیاتی تعریف درکار ہے، اس لیے ہم اس مقالے کو اس اصول کے ساتھ مل کر لے سکتے ہیں جو پہلے ہی قبول کیا جا چکا ہے جس سے یہ متصادم ہے، اس کی تعریف کے طور پر۔ مقالے میں ایک مفروضے کی خصوصیت ہے-ایک نقطہ جس پر پوسٹ اور چرچ 24 نے زور دیا ہے۔ 22 چرچ [1] [ابتدائی نمبر تھیوری کا ایک ناقابل حل مسئلہ] 23 ٹورنگ [1] [کمپیوٹیبل نمبروں پر، اینٹشیڈنگس پروبلم (1936) پر درخواست کے ساتھ] 24 پوسٹ [1، صفحہ 105]، اور چرچ [2] کلین کا چرچ، ٹورنگ، اور چرچ-ٹورنگ تھیسس اپنے باب § 60 میں، کلین نے "چرچ کے مقالے" کی وضاحت اس طرح کی ہے: ". تحقیقی شواہد اور دیگر تحفظات نے چرچ 1936 کو مندرجہ ذیل مقالہ پیش کرنے پر مجبور کیا۔ "تھیسس I. ہر مؤثر طریقے سے قابل حساب فنکشن (مؤثر طریقے سے فیصلہ کن پیشن گوئی) عام تکرار ہے۔ "یہ مقالہ ٹورنگ 1936-7 اور پوسٹ 1936 کے ذریعہ وضع کردہ کمپیوٹنگ مشین کے تصور میں بھی مضمر ہے۔" صفحہ 317 پر وہ واضح طور پر مندرجہ بالا مقالے کو "چرچ کا مقالہ" کہتے ہیں: "§ 62۔ چرچ کا مقالہ۔ اس اور اگلے باب کے اہم مقاصد میں سے ایک چرچ کے مقالے (تھیسس I § 60) کے لیے ثبوت پیش کرنا ہے۔ ٹورنگ کی "تشکیل" کے بارے میں، کلین کہتے ہیں: "اس لیے ٹورنگ کی تشکیل چرچ کے مقالے (مساوی اصطلاحات میں) کا ایک آزاد بیان تشکیل دیتی ہے۔ 1936 کے بعد بھی اسی طرح کی تشکیل دی گئی۔ " کلین نے تجویز پیش کی کہ جو ٹورنگ نے دکھایا: "ٹورنگ کے کمپیوٹیبل افعال (1936-1937) وہ ہیں جن کا حساب ایک قسم کی مشین کے ذریعے کیا جا سکتا ہے جو ان کے تجزیے کے مطابق، ہر طرح کے آپریشنز کو دوبارہ پیش کرنے کے لیے ڈیزائن کیا گیا ہے جو ایک انسانی کمپیوٹر پہلے سے مقرر کردہ ہدایات کے مطابق کام کر سکتا ہے۔" کلین نے ٹورنگ کے مقالے کی وضاحت اس طرح کی ہے: "§70۔ ٹورنگ کا مقالہ۔ ٹورنگ کا مقالہ ہے کہ ہر فنکشن جسے اس کی تعریف کے تحت قدرتی طور پر کمپیوٹیبل سمجھا جائے گا، یعنی۔ ان کی مشینوں میں سے ایک، نظریہ XXX کے چرچ کے مقالے کے مساوی ہے۔ درحقیقت اس بیان سے فورا پہلے، کلین نظریہ XXX بیان کرتا ہے: "نظریہ XXX (= نظریہ XXVIII + XXIX)۔ جزوی افعال کی درج ذیل کلاسیں مربوط ہیں، یعنی۔ ایک ہی اراکین ہوتے ہیں: (a) جزوی تکراری افعال، (b) کمپیوٹیبل افعال، (c) 1/1 کمپیوٹیبل افعال۔ اسی طرح l [لور کیس L] کے ساتھ مکمل طور پر بیان کردہ فرض شدہ فنکشنز۔ گوڈل، ٹورنگ مشینیں، اور مؤثر طریقے سے حساب کتاب اپنے 1931 کے مقالے آن فارمللی انڈیسیڈیبل پروپوزیشنز میں، گوڈل نے 28 اگست 1963 کو ایک نوٹ شامل کیا جو "ایک رسمی نظام" کی متبادل شکلوں/اظہار کے بارے میں ان کی رائے کو واضح کرتا ہے۔ انہوں نے 1964 میں اپنی رائے کو اور بھی واضح طور پر دہرایا (نیچے دیکھیں): "نوٹ 28 اگست 1963 کو شامل کیا گیا۔ بعد کی پیشرفتوں کے نتیجے میں، خاص طور پر اس حقیقت کی وجہ سے کہ اے ایم ٹورنگ کے کام 69 کی وجہ سے اب رسمی نظام 70 کے عمومی تصور کی ایک درست اور بلا شبہ مناسب تعریف دی جا سکتی ہے، نظریہ VI اور XI کا مکمل طور پر عمومی ورژن اب ممکن ہے۔ یعنی، یہ سختی سے ثابت کیا جا سکتا ہے کہ ہر مستقل رسمی نظام میں جس میں ایک خاص مقدار میں فائنٹری نمبر تھیوری ہوتی ہے، ناقابل فیصلہ ریاضی کی تجاویز موجود ہوتی ہیں اور اس کے علاوہ، اس طرح کے کسی بھی نظام کی مستقل مزاجی کو نظام میں ثابت نہیں کیا جا سکتا۔ "69 دیکھیں، صفحہ 249۔ "70 میری رائے میں" رسمی نظام "یا" رسمی نظام "کی اصطلاح اس تصور کے علاوہ کسی اور چیز کے لیے کبھی استعمال نہیں کی جانی چاہیے۔ پرنسٹن میں ایک لیکچر میں (پرنسٹن یونیورسٹی 1946 میں مذکور، صفحہ 11۔ [ڈیوس 1965، صفحہ 11 دیکھیں۔ 84-88 [یعنی۔ ڈیوس پی۔ 84-88])، میں نے رسمی طریقوں کی کچھ ٹرانسفائنٹ جنرلائزیشنز تجویز کیں، لیکن یہ اصطلاح کے مناسب معنوں میں رسمی نظاموں سے یکسر مختلف ہیں، جن کی خصوصیت یہ ہے کہ ان میں استدلال، اصولی طور پر، مکینیکل آلات سے مکمل طور پر تبدیل کیا جا سکتا ہے۔ گوڈل 1964-گوڈل کے پوسٹ اسکرپٹم میں پرنسٹن میں آئی اے ایس میں 1934 کے اپنے لیکچر کے نوٹوں میں، وہ دہراتے ہیں، لیکن اس سے بھی زیادہ جرات مندانہ الفاظ میں، کمپیوٹیبلٹی کی افادیت کے بارے میں ان کی کم چمکتی ہوئی رائے کا اعادہ کرتے ہیں جیسا کہ چرچ کی λ-تعریف اور تکرار سے بیان کیا گیا ہے (ہمیں یہ اندازہ لگانا ہوگا کہ مندرجہ ذیل میں جمع "تعریفوں" کے استعمال کی وجہ سے دونوں کی توہین کی گئی ہے)۔ یہ مارٹن ڈیوس کو لکھے گئے ایک خط میں تھا (غالبا اس وقت جب وہ غیر فیصلہ کن کو جمع کر رہے تھے)۔ کچھ فقروں کا اعادہ حیرت انگیز ہے: "بعد کی پیشرفتوں کے نتیجے میں، خاص طور پر اس حقیقت کے نتیجے میں، کہ، اے ایم ٹورنگ کے کام کی وجہ سے، رسمی نظام کے عمومی تصور کی ایک درست اور بلا شبہ مناسب تعریف اب دی جا سکتی ہے، ناقابل فیصلہ ریاضی کی تجاویز کا وجود اور اسی نظام میں کسی نظام کی مستقل مزاجی کی عدم استحکام کو اب ہر مستقل رسمی نظام کے لیے سختی سے ثابت کیا جا سکتا ہے جس میں ایک خاص مقدار میں حتمی نمبر تھیوری ہوتی ہے۔ "ٹورنگ کا کام" مکینیکل طریقہ کار "(عرف" الگورتھم "یا" کمپیوٹیشن طریقہ کار "یا" محدود مشترکہ طریقہ کار ") کے تصور کا تجزیہ دیتا ہے۔ یہ تصور "ٹورنگ مشین" کے مساوی دکھایا گیا ہے۔ ایک رسمی نظام کو محض فارمولے تیار کرنے کے لیے کسی بھی مکینیکل طریقہ کار کے طور پر بیان کیا جا سکتا ہے، جسے قابل ثبوت فارمولے کہا جاتا ہے۔ رسمی نظام کا تصور، جس کا جوہر یہ ہے کہ استدلال کو فارمولوں پر مکینیکل کارروائیوں سے مکمل طور پر تبدیل کر دیا جاتا ہے۔ (نوٹ کریں کہ یہ سوال کہ آیا کوئی محدود غیر مکینیکل طریقہ کار موجود ہے۔ جو کسی الگورتھم کے مساوی نہیں ہے، کا "رسمی نظام" اور "مکینیکل طریقہ کار" کی تعریف کی اہلیت سے کوئی تعلق نہیں ہے۔ "اگر" محدود طریقہ کار "کا مطلب" مکینیکل طریقہ کار "سمجھا جاتا ہے، تو فوٹ نوٹ 3 میں اٹھائے گئے سوال کا جواب §9 میں بیان کردہ تکرار کے لیے مثبت طور پر دیا جا سکتا ہے، جو کہ آج کی تعریف کے مطابق عمومی تکرار کے مساوی ہے (دیکھیں ایس سی کلین (1936)۔)" * دیکھیں۔ اور ای ایل پوسٹ (1936) کا تقریبا بیک وقت کاغذ۔ جہاں تک کمپیوٹیبلٹی کی پچھلی مساوی تعریفوں کا تعلق ہے، جو تاہم ہمارے مقصد کے لیے بہت کم موزوں ہیں، اے دیکھیں۔ چرچ 1936۔ فوٹ نوٹ 3 1934 کے لیکچر نوٹ کے مرکزی حصے میں ہے: "3 اس کے برعکس درست معلوم ہوتا ہے، اگر اسکیم کے مطابق تکرار کے علاوہ (2) دیگر شکلوں کی تکرار (مثال کے طور پر، بیک وقت دو متغیرات کے حوالے سے) کو قبول کیا جائے۔ یہ ثابت نہیں کیا جا سکتا، کیونکہ محدود حساب کے تصور کی وضاحت نہیں کی گئی ہے، لیکن یہ ایک تحقیقی اصول کے طور پر کام کرتا ہے۔ ڈیوس کا مشاہدہ ہے کہ "درحقیقت اس کی [گوڈل کی] تعریف [تکرار کی] اور کلین کی [1936] کے درمیان مساوات بالکل معمولی نہیں ہے۔ لہذا، اس کے برعکس ظاہر ہونے کے باوجود، ان لیکچرز کا فوٹ نوٹ 3 چرچ کے مقالے کا بیان نہیں ہے۔ " گانڈی: "مشین کمپیوٹیشن"، مجرد، تعیناتی، اور روشنی کی رفتار کے ذریعہ "مقامی وجہ" تک محدود رابن گانڈی کا بااثر مقالہ جس کا عنوان چرچ کا تھیسس اور میکانزم کے اصول بار وائز ایٹ ال میں ظاہر ہوتا ہے۔ گانڈی چرچ کے مقالے کے غیر متوقع اظہار کے ساتھ شروع ہوتا ہے، جو اس طرح تیار کیا گیا ہے: "1. تعارف "اس پورے مقالے میں ہم کچھ بدیہی طور پر دیئے گئے تصور کا حوالہ دینے کے لیے" کیلکولیبل "اور" کمپیوٹیبل "کا استعمال کریں گے جس کا مطلب ہے" ٹورنگ مشین کے ذریعے کمپیوٹیبل "؛ یقینا" کمپیوٹیبل "کی بہت سی مساوی تعریفیں اب دستیاب ہیں۔ "چرچ کا مقالہ۔ جو مؤثر طریقے سے قابل حساب ہے وہ قابل حساب ہے۔ " ۔ چرچ اور ٹورنگ دونوں کے ذہن میں کچھ مکینیکل آلات (جیسے کاغذ اور پنسل) کا استعمال کرتے ہوئے ایک تجریدی انسان کا حساب تھا "رابرٹ سوئر (1995، نیچے دیکھیں) کو اس فریمنگ کے ساتھ مسائل تھے، چرچ کے مقالے (1936) پر غور کرتے ہوئے جو ٹورنگ کے" اپینڈکس پروف "(1937) سے پہلے شائع ہوا تھا۔ گانڈی "مکینیکل عمل کا تجزیہ کرنے اور اس طرح مندرجہ ذیل کے لیے دلائل فراہم کرنے کی کوشش کرتا ہے:" تھیسس ایم۔ مشین کے ذریعے جس چیز کا حساب لگایا جا سکتا ہے وہ قابل حساب ہے۔ " گانڈی "غور کرنے والے آلات سے خارج کرتے ہیں جو بنیادی طور پر ینالاگ مشینیں ہیں۔ مکینیکل آلات کے بارے میں صرف جسمانی مفروضے (نیچے Cf اصول IV) یہ ہیں کہ آلہ کے ہر جوہری حصے کے لکیری طول و عرض پر ایک نچلی حد ہوتی ہے اور یہ کہ تبدیلی کے پھیلاؤ کی رفتار پر ایک اوپری حد (روشنی کی رفتار) ہوتی ہے۔" لیکن پھر وہ اپنی مشینوں کو اور بھی محدود کر دیتا ہے: "(2) دوسرا ہم فرض کرتے ہیں کہ مکینیکل ڈیوائس کے ذریعے حساب کی پیش رفت کو الگ الگ اصطلاحات میں بیان کیا جا سکتا ہے، تاکہ جن آلات پر غور کیا جائے وہ ڈھیلے معنوں میں ڈیجیٹل کمپیوٹر ہوں۔ (3) آخر میں ہم یہ سمجھتے ہیں کہ آلہ متعین ہے: یعنی اس کی ابتدائی حالت کی مکمل وضاحت دیے جانے کے بعد آلہ کے بعد کے رویے کا منفرد طور پر تعین کیا جاتا ہے۔ درحقیقت وہ اس "تھیسس ایم" کے لیے ایک دلیل پیش کرتا ہے کہ وہ اسے "نظریہ" کہتا ہے، جس کا سب سے اہم "اصول" "اصول IV: مقامی وجہ کا اصول" ہے: "اب ہم اپنے سب سے اہم اصولوں پر آتے ہیں۔ ٹورنگ کے تجزیے میں یہ ضرورت کہ عمل صرف ریکارڈ کے ایک محدود حصے پر منحصر ہو، انسانی حد پر مبنی تھی۔ ہم اس کی جگہ ایک جسمانی حد لگاتے ہیں جسے ہم مقامی وجہ کا اصول کہتے ہیں۔ اس کا جواز اثرات اور اشاروں کے پھیلاؤ کی محدود رفتار میں مضمر ہے: عصری طبیعیات فاصلے پر فوری عمل کے امکان کو مسترد کرتی ہے۔ 1985 میں "تھیسس ایم" کو کوانٹم ٹورنگ مشین کے لیے ڈھال لیا گیا، جس کے نتیجے میں چرچ-ٹورنگ-ڈوئچ اصول وجود میں آیا۔ سوارے سوارے کا کمپیوٹیبلٹی اور ریکرشن کا مکمل جائزہ ظاہر ہوتا ہے۔ انہوں نے کمپیوٹیبلٹی کی "بہت کم موزوں" تعریف کے حوالے سے گوڈل کی 1964 کی رائے (اوپر) کا حوالہ دیا، اور مزید کہا: "کلین نے لکھا [1981b، p. 49]،" ٹورنگ کی کمپیوٹیبلٹی اندرونی طور پر قائل کرنے والی ہے "لیکن" λ-تعریف اندرونی طور پر قائل نہیں ہے "اور" عام تکرار شاید ہی ہو (اس کے مصنف گوڈل اس وقت بالکل قائل نہیں تھے)۔ آج کل زیادہ تر لوگ ٹورنگ کے مقالے کو قبول کرتے ہیں "سوارے کا فوٹ نوٹ 7 (1995) بھی گانڈی کی" الجھن "کو پکڑتا ہے، لیکن بظاہر یہ گانڈی (1988) میں بھی جاری ہے۔ یہ الجھن تحقیق اور/یا فکر کی ایک سنگین غلطی کی نمائندگی کرتی ہے اور اس کے پورے پروگرام پر ایک بادل چھایا ہوا ہے: "7 گینڈی نے اصل میں چرچ کا مقالہ لکھا" نہ کہ "ٹورنگ کا مقالہ" جیسا کہ یہاں لکھا گیا ہے، لیکن یقینی طور پر گانڈی کا مطلب مؤخر الذکر تھا، کم از کم ارادے سے، کیونکہ ٹورنگ نے 1936 میں یا کہیں اور عمومی تکراری افعال کے بارے میں کچھ ثابت نہیں کیا تھا۔ " بریجر اور ٹیسیٹ محوروں کا مسئلہ ایک مسئلے کی طرف اشارہ کرتا ہے جب کوئی "محوری طور پر" کسی تصور تک پہنچ رہا ہوتا ہے، یعنی، ایک "محوری نظام" اس میں ایک یا زیادہ محوری محوروں کو شامل کر سکتا ہے جو محوری سیٹ پیش کیے جانے پر غیر واضح ہوتے ہیں۔ مثال کے طور پر، علم (اور صلاحیت) کے ساتھ ایک فعال ایجنٹ کسی بھی محوری نظام میں ایک (ممکنہ) بنیادی محوریہ ہو سکتا ہے: "انسان کی جانکاری ضروری ہے-ایک ایسی جانکاری جو محوریوں میں باقاعدہ نہیں ہے۔ Â. علامتوں کے خالص رسمی نظام کے طور پر ریاضی بغیر کسی انسان کے علامتوں کی جانکاری کے ناممکن ہے۔ "انہوں نے ہلبرٹ کا حوالہ دیتے ہوئے کہا:" 1905 میں دیے گئے ایک یونیورسٹی کے لیکچر میں، ہلبرٹ نے منطق میں محوریات بیان کرنے سے پہلے "فکر کا محوری" یا "ذہانت کے وجود کا محوری" ہونا "بالکل ضروری" سمجھا۔ اسکرپٹ کے حاشیے میں، ہلبرٹ نے بعد میں مزید کہا: "فلسفیوں کی ترجیح"۔ انہوں نے اس محوری اصول کو اس طرح وضع کیا: "میرے پاس اشیاء کے بارے میں سوچنے کی صلاحیت ہے، اور انہیں a، b،.., x، y، جیسی سادہ علامتوں کے ذریعے ظاہر کرنے کی صلاحیت ہے، تاکہ انہیں غیر واضح طور پر پہچانا جا سکے۔ میری سوچ ان اشیاء کے ساتھ کچھ اصولوں کے مطابق ایک خاص طریقے سے کام کرتی ہے، اور میری سوچ خود کے مشاہدے سے ان اصولوں کا پتہ لگانے کے قابل ہے، اور ان اصولوں کو مکمل طور پر بیان کرنے کے قابل ہے "[(ہلبرٹ 1905,219) ؛ یہ بھی دیکھیں (پیکاؤس 1990، 62 ایف اور 227)]۔ بریگر جیوسیپی ویرونیز (1891) اور ہرمن ویل (1930-1) کی مثالوں کے ساتھ اپنی دلیل کی مزید حمایت کرتا ہے۔ وہ اس کے بعد ایک مخصوص زبان میں ایک محوری سیٹ کے اظہار کے مسئلے پر بحث کرتا ہے: یعنی۔ ایجنٹ کے ذریعہ جانی جانے والی زبان، مثال کے طور پر جرمن۔ الگورتھم کی خصوصیات میں اس کے بارے میں مزید دیکھیں، خاص طور پر سیرل کی رائے ہے کہ کسی بھی حساب سے باہر ایک مبصر ہونا چاہیے جو استعمال شدہ علامتوں کو معنی دیتا ہے۔ سیگ اور محوری تعریفیں "فیفر فیسٹ" میں-سولومن فیفرمین کی 70 ویں سالگرہ-ولفریڈ سیگ نے پہلی بار دو سال قبل لکھا گیا ایک مقالہ پیش کیا جس کا عنوان تھا "کیلکولیشنز بائی مین اینڈ مشین: کانسیپچوئل اینالیسس"، جو (سیگ اور دیگر) میں دوبارہ شائع ہوا۔ 2002:390-409)۔ اس سے قبل سیگ نے "مکینیکل پروسیجرز اینڈ میتھمیٹیکل ایکسپیرئنس" (جارج 1994، صفحہ 71 ایف ایف میں) شائع کیا جس میں "حساب کاری" کی تاریخ پیش کی گئی جس کا آغاز رچرڈ ڈیڈیکنڈ سے ہوا اور 1950 کی دہائی میں ایلن ٹورنگ اور اسٹیفن کول کلین کے بعد کے مقالے کے ساتھ اختتام پذیر ہوا۔ فیفر فیسٹ کا مقالہ سابقہ مقالے کو اس کے اہم نکات پر ڈسٹل کرتا ہے اور بنیادی طور پر رابن گانڈی کے 1980 کے مقالے پر رہتا ہے۔ سیگ ٹورنگ کی "سٹرنگ مشین کے ذریعے کمپیوٹیبلٹی" (انسانی "کمپیوٹر") کو گانڈی کی متوازی مشینوں تک "لیٹر مشین کے ذریعے کمپیوٹیبلٹی" میکانزم تک کم کر دیتا ہے۔ سیگ مزید حالیہ کام کا حوالہ دیتے ہیں جن میں "کولموگوروف اور یوسپنسکی کا الگورتھم پر کام" اور (ڈی پیساپیا 2000)، خاص طور پر، کے یو-پوائنٹر مشین ماڈل)، اور مصنوعی عصبی نیٹ ورکس شامل ہیں اور دعوی کرتے ہیں: "غیر رسمی تصوراتی تجزیہ اور ریاضیاتی مساوات کے ثبوت کی علیحدگی اس بات کو تسلیم کرنے کے لیے ضروری ہے کہ ٹورنگ کے مقالے (عام طور پر لیا گیا) کی درستگی دو ستونوں پر منحصر ہے ؛ یعنی کمپیوٹرز کے لیے حدود اور مقامی حالات کی درستگی، اور متعلقہ مرکزی مقالے کی درستگی پر۔ مؤخر الذکر واضح طور پر اس بات پر زور دیتا ہے کہ کمپیوٹر کے حسابات کو براہ راست کسی خاص قسم کی مشین کے ذریعے نقل کیا جا سکتا ہے۔ اگرچہ کسی کو تجزیاتی دلیل کی یہ لکیر تسلی بخش لگے، لیکن اس میں دو کمزوریاں ہیں: پابندیوں کی نرمی (علامتی ترتیبات کیا ہیں؟) مکینیکل آپریشنز میں کون سی تبدیلیاں اثر انداز ہو سکتی ہیں؟) اور مرکزی مقالے کی متعلقہ مبہمیت۔ ہم، اس بات سے قطع نظر کہ ہم اپنے آپ کو کس طرح موڑتے ہیں، ایک ایسی پوزیشن میں ہیں جو طریقہ کار کے لحاظ سے اب بھی غیر تسلی بخش ہے۔ "۔ وہ دعوی کرتا ہے کہ "زیادہ تسلی بخش موقف کی طرف قدم بڑھانا۔ مخصوص قسم کی ترتیبات اور کارروائیوں سے مزید دور خلاصہ کرنا۔" یہ اکثر دعوی کیا گیا ہے کہ ٹورنگ نے مشینوں کے حسابات کا تجزیہ کیا۔ یہ تاریخی اور منظم طور پر غلط ہے، کیونکہ میری وضاحت بالکل واضح ہونی چاہیے تھی۔ صرف 1980 میں ٹورنگ کے طالب علم رابن گانڈی نے مشین کے حسابات کی خصوصیت پیش کی۔ مذکورہ بالا بیان درست ہے یا نہیں، اس پر غور کرنے کا کام قارئین پر چھوڑ دیا گیا ہے۔ سیگ گانڈی کے تجزیے کو بیان کرتا ہے (اوپر 1980 دیکھیں)۔ ایسا کرتے ہوئے وہ اسے باضابطہ بنانے کی کوشش کرتا ہے جسے وہ "گانڈی مشینیں" کہتا ہے (ایک ضمیمہ میں تفصیلی تجزیہ کے ساتھ)۔ گانڈی مشینوں کے بارے میں: "۔ گانڈی مشین کی تعریف ایک" تجریدی "ریاضیاتی تعریف ہے جو متوازی حسابات کی خصوصیات کو ظاہر کرتی ہے۔ دوسرا، گانڈی مشینیں گروپوں اور ٹپوولوجیکل خالی جگہوں کے ساتھ تجریدی محوری تعریفوں کی عمومی خصوصیت کا اشتراک کرتی ہیں، یعنی کہ وہ مختلف تشریحات کی وسیع اقسام کو تسلیم کرتی ہیں۔ تیسرا، کسی بھی گانڈی مشین کے حسابات کو لیٹر مشین کے ذریعے نقل کیا جا سکتا ہے، [اور] محوری تصور کے لیے نمائندگی تھیوریم کے طور پر بہتر طور پر سمجھا جاتا ہے۔ [بولڈ فیس شامل کیا گیا] "محوری نقطہ نظر کمپیوٹیشن کے عمل کی ضروری نوعیت کو تجریدی انداز میں ظاہر کرتا ہے۔ میں جن دو قسم کے کیلکولیٹرز کی وضاحت کر رہا ہوں ان کے درمیان فرق اس حقیقت تک کم ہو گیا ہے کہ ٹورنگ کمپیوٹرز کسی ریاست کے ایک باؤنڈڈ حصے میں ترمیم کرتے ہیں، جبکہ گانڈی مشینیں من مانی طور پر بہت سے باؤنڈڈ حصوں پر متوازی طور پر کام کرتی ہیں۔ نمائندگی کے نظریات اس بات کی ضمانت دیتے ہیں کہ محوریات کے ماڈل ان کے حرف کی قسم میں کمپیوٹیشنل طور پر ٹورنگ مشینوں کے مساوی ہیں۔ بار وائز، جون، ایچ جے کیسلر، اور کے کونین، ایڈیٹرز، 1980، دی کلین سمپوزیم، 426 صفحات، نارتھ ہالینڈ پبلشنگ کمپنی، ایمسٹرڈیم، چرچ، اے، 1936 اے، (ڈیوس 1965:88 ایف ایف)، "این انسولویبل پروبلم آف ایلیمنٹری نمبر تھیوری" چرچ، اے، 1936 بی، ان (ڈیوس 1965:108 ایف ایف)، "اے نوٹ آن دی اینٹشیڈنگس پروبلم" چرچ، اے، 1938، دی کنسٹرکٹو سیکنڈ نمبر کلاس، بل۔ آمیر۔ ریاضی۔ ایس او سی۔ وال۔ 44، نمبر 4، 1938، پی پی۔ ڈیوس، مارٹن ایڈیٹر، 1965، دی انڈیسیڈبل، بیسک پیپرز آن انڈیسیڈبل پروپوزیشنز، ان سولویبل پروبلمز اینڈ کمپیوٹیبل فنکشنز، ریوین پریس، نیویارک۔ تمام اصل مقالے یہاں موجود ہیں جن میں گوڈل، چرچ، ٹورنگ، روسر، کلین اور پوسٹ کے مقالے شامل ہیں جن کا ذکر اس مضمون میں کیا گیا ہے۔ ڈیوس کی قیمتی کمنٹری زیادہ تر کاغذات سے پہلے ہوتی ہے۔ ڈیوس، مارٹن، 2001، انجنز آف لاجک: ریاضی دان اور کمپیوٹر کی ابتدا، ڈبلیو ڈبلیو نارٹن اینڈ کمپنی، نیویارک، پی بی کے۔ ڈاسن، جان ولیم، جونیئر، 1997، منطقی الجھن: کرٹ گوڈل کی زندگی اور کام، 361 صفحات، اے کے پیٹرز، ویلسلی، ایم اے، QA29.058D39۔ ڈاسن، جان ولیم اور جان ولیم ڈاسن، جونیئر، 2005، منطقی الجھن: کرٹ گوڈل کی زندگی اور کام، 362 صفحات، اے کے پیٹرز، ویلسلی، ایم اے، ڈی پیساپیا، این، 2000، گانڈی مشینیں: ٹورنگ مشینوں، گیم آف لائف، اور مصنوعی عصبی نیٹ ورکس کے لیے متوازی حساب کا ایک تجریدی ماڈل، ایم ایس۔ تھیسس، کارنیگی میلن یونیورسٹی، پٹسبرگ۔ ڈرشوٹز، ناچوم اور گوریویچ، یوری، 2007، چرچ کے تھیسس کی ایک قدرتی محوریت، http://research.microsoft.com ~ گوریویچ/اوپیرا/188. پی ڈی ایف گانڈی، رابن، 1978، چرچ کے تھیسس اور میکانزم کے اصول، (بار وائز ایٹ ال۔ 1980:123-148) جارج، الیگزینڈر (+ ایڈیشن۔ )، 1994، ریاضی اور ذہن، 216 صفحات، نیویارک، آکسفورڈ یونیورسٹی پریس، گوڈل، کے۔، 1930، میں (وین ہیجینورٹ 1967:592 ff)، مکمل اور مستقل مزاجی پر کچھ میٹا میتھیمیٹیکل نتائج گوڈل، کے۔، 1931a، میں (ڈیوس 1965:4-38)، پرنسپیا میتھمیٹکا اور متعلقہ سسٹمز کی رسمی طور پر ناقابل فیصلہ تجاویز پر۔ I. Gödel, K., 1931b, in (van Heijenoort 1976:616 ff) مکمل اور مستقل مزاجی پر Gödel, K., 1934, in (Davis 1965:39-74), آن انڈیسیڈیبل پروپوزیشنز آف فارمل میتھمیٹیکل سسٹمز Gödel, K., 1936, in (Davis 1965:82 ff), آن دی لینتھ آف پروفز، ایڈیٹر کی طرف سے ترجمہ کردہ اصل مضمون سے Ergenbnisse eines mathematishen Kolloquiums, Heft 7 (1936) pp. 23-24 "۔ کلیین (1952) نے ارجبنس آئنز ریاضی میں "über die Lāange von Beweisen" کے طور پر حوالہ دیا۔ کول، وغیرہ۔ گوڈل، کے۔، 1964، میں (ڈیوس 1965:71 ایف ایف)، پوسٹ اسکرپٹم گروشوز، ایملی اور بریگر، ہربرٹ، 2000، ریاضیاتی علم کی ترقی، 416 صفحات، کلوور اکیڈمک پبلشرز، ڈورڈریکٹ، نیدرلینڈز،۔ ہاکنگ، اسٹیفن، 2005، گاڈ کریئٹڈ دی انٹیجرز: دی میتھمیٹیکل بریک تھروز جس نے تاریخ کو تبدیل کیا، ایڈیٹڈ، اسٹیفن ہاکنگ کی کمنٹری کے ساتھ، رننگ پریس، فلاڈیلفیا، ہجز، اینڈریو، 1983، ایلن ٹورنگ: دی انیگما، پہلا ایڈیشن، سائمن اینڈ شسٹر، نیویارک، کلین، ایس سی، 1935، (ڈیوس 1965:236 ff) جنرل ریکرسو فنکشنز آف نیچرل نمبرز کلین، ایس سی، 1971، 1952 (10 واں تاثر 1991) انٹروڈکشن ٹو میٹامیتھمیٹکس، 550 صفحات، نارتھ ہالینڈ پبلشنگ کمپنی (والٹرز-نورڈہوف پبلشنگ) میریئم-ویبسٹر انکارپوریٹڈ، 1983 1، نہیں۔ 3 (ستمبر، 1936)، پی پی۔ 103-105۔ روسر۔ جے۔ بی۔، 1939، گوڈل کے نظریہ اور چرچ کے نظریہ کے ثبوتوں کی غیر رسمی نمائش، جرنل آف علامتی منطق۔ جلد۔ 4. (1939)، پی۔ 53-60 اور (ڈیوس 1967:223-230) میں دوبارہ چھاپا گیا۔ سیگ، ولفریڈ، رچرڈ سومر، اور کیرولن ٹیلکوٹ (ایڈز۔ )، 2002، ریفلیکشنز آن دی فاؤنڈیشنز آف میتھمیٹکس: ایسسز ان آنر آف سولومن فیفرمین، لیکچر نوٹس ان لاجک 15، 444 صفحات، اے کے پیٹرز لمیٹڈ، سوارے، رابرٹ، 1996، کمپیوٹیبلٹی اینڈ ریکرشن، "بلیٹن آف سمبولک لاجک 2"، جلد 2، نمبر 3، ستمبر 1996، پی پی۔ اور (یہ بھی دیکھیں: ڈیوس 1965:115 ff) ٹورنگ، A.، 1939، (ڈیوس 1965:154 ff)، سسٹمز آف لاجک بیسڈ آن آرڈینلز وین ہیجینورٹ، جین، 1976، فرام فریج ٹو گوڈل: اے سورس بک ان میتھمیٹیکل لاجک، 116 صفحات، 1879-1931، تھرڈ پرنٹنگ، اوریجنل پرنٹنگ 1967، ہارورڈ یونیورسٹی پریس، کیمبرج میساچوسٹس، (pbk.)۔ بیرونی روابط علامتی منطق کے بلیٹن میں آن لائن کاغذات کے ساتھ تمام جلدوں کے لنکس ہیں۔ الونزو چرچ، 1938، دی کنسٹرکٹو سیکنڈ نمبر کلاس "29 دسمبر 1937 کو سوسائٹی کے انڈیاناپولیس اجلاس میں پروگرام کمیٹی کی دعوت پر دیا گیا خطاب۔" کرٹ گوڈل، 1931، پرنسپیا میتھمیٹکا اور متعلقہ سسٹمز I کی باضابطہ طور پر ناقابل فیصلہ تجاویز پر۔ ترجمہ مارٹن ہرزل نے کیا، 27 نومبر 2000۔ ایمل ایل پوسٹ، 1946، اے ویرینٹ آف اے ریکورسیلی ان سولویبل پروبلم، ول فرائیڈ سیگ، 2005، چرچ ود آؤٹ ڈوگما: محوریات برائے کمپیوٹیبلٹی، کارنیگی میلن یونیورسٹی ول فرائیڈ سیگ، 2000، کیلکولیشنز بائی مین اینڈ مشین: تصوراتی تجزیہ، کارنیگی میلن یونیورسٹی رابرٹ آئی۔ سوئر، 1995، کمپیوٹیبلٹی اینڈ ریکرشن رابرٹ آئی۔ سوئر، 1996، کمپیوٹیبلٹی اینڈ ریکرشن جیسا کہ یہ دی بلیٹن آف سمبولک لاجک، جلد 2، جلد 2، نمبر 3، ستمبر 1996 میں شائع ہوا۔ ماساکو تاکاہاشی، 2004، عمومی تکراری افعال پر، انٹرنیشنل کرسچن یونیورسٹی خاص طور پر، حوالہ جات دیکھیں۔ اے۔ ایم۔ ٹورنگ، 1936، آن کمپیوٹیبل نمبرز، ود این ایپلیکیشن ٹو دی اینٹشیڈنگز پروبلم چرچ-ٹورنگ تھیسس کمپیوٹیبلٹی تھیوری ایلن ٹورنگ تھیوری آف کمپیوٹیشن