تز چرچ-تورینگ به مفهوم روش کارآمد، سیستماتیک یا مکانیکی در منطق، ریاضیات و علوم کامپیوتر اشاره دارد. این به عنوان توصیفی از مفهوم شهودی محاسبه‌پذیری فرمول‌بندی می‌شود و در رابطه با توابع بازگشتی عمومی، اغلب تز چرچ نامیده می‌شود. همچنین به تئوری توابع قابل محاسبه کامپیوتری اشاره دارد. این تز در دهه 1930 ظاهر شد، زمانی که خود کامپیوترها هنوز وجود نداشتند. بعدها به نام ریاضیدان آمریکایی آلونسو چرچ و همکار بریتانیایی اش آلن تورینگ نامگذاری شد.
کارایی روش برای رسیدن به نتیجه
اولین وسیله ای که شبیه یک کامپیوتر مدرن بود، Bombie بود، ماشینی که توسط ریاضیدان انگلیسی آلن تورینگ ساخته شد. در طول جنگ جهانی دوم برای رمزگشایی پیام های آلمانی استفاده می شد. اما برای تز و رسمی کردن مفهوم الگوریتم از ماشین‌های انتزاعی استفاده کرد که بعدها ماشین‌های تورینگ نامیده شدند. پایان نامه ارائه می شودعلاقه هم برای ریاضیدانان و هم برای برنامه نویسان، زیرا این ایده الهام بخش سازندگان اولین کامپیوترها بود.
در نظریه محاسباتی، تز چرچ تورینگ به عنوان حدس در مورد ماهیت توابع قابل محاسبه نیز شناخته می شود. بیان می کند که برای هر تابع قابل محاسبه الگوریتمی روی اعداد طبیعی، یک ماشین تورینگ وجود دارد که قادر به محاسبه آن است. یا به عبارتی الگوریتم مناسبی برای آن وجود دارد. یک مثال معروف از اثربخشی این روش، آزمون جدول صدق برای آزمایش توتولوژی است.
راهی برای دستیابی به هر نتیجه دلخواه "موثر"، "سیستماتیک" یا "مکانیکی" نامیده می شود اگر:
- روش بر حسب تعداد محدودی از دستورالعمل‌های دقیق مشخص می‌شود، هر دستورالعمل با استفاده از تعداد محدودی از کاراکترها بیان می‌شود.
- بدون خطا اجرا می شود، نتیجه دلخواه را در تعداد معینی از مراحل ایجاد می کند.
- این روش را می توان توسط انسان بدون کمک با هر وسیله ای غیر از کاغذ و مداد انجام داد
- نیازی به درک، شهود یا نبوغ از سوی شخصی که این عمل را انجام می دهد ندارد
پیش از این در ریاضیات، اصطلاح غیررسمی "به طور موثر قابل محاسبه" برای اشاره به توابعی استفاده می شد که می توان آنها را با مداد و کاغذ محاسبه کرد. اما مفهوم محاسبات الگوریتمی بیشتر از هر چیزی مشخص بود. اکنون با یک تابع با یک آرگومان طبیعی مشخص می شود که یک الگوریتم محاسبه برای آن وجود دارد. یکی از دستاوردهای آلن تورینگ بودنمایش یک محمول به طور رسمی دقیق، که با کمک آن می توان در صورت استفاده از شرط کارایی روش، گزاره غیررسمی را جایگزین کرد. کلیسا همین کشف را انجام داد.
مفاهیم اساسی توابع بازگشتی
تغییر محمولات تورینگ، در نگاه اول، متفاوت از آنچه توسط همکارش پیشنهاد شده بود به نظر می رسید. اما در نتیجه، آنها معادل هستند، به این معنا که هر یک از آنها مجموعه یکسانی از توابع ریاضی را انتخاب می کنند. تز چرچ-تورینگ این ادعا است که این مجموعه شامل هر تابعی است که مقادیر آن را می توان با روشی به دست آورد که شرایط کارایی را برآورده کند. تفاوت دیگری بین این دو کشف وجود داشت. این بود که چرچ تنها نمونه هایی از اعداد صحیح مثبت را در نظر گرفت، در حالی که تورینگ کار خود را به عنوان پوشش توابع قابل محاسبه با یک متغیر انتگرال یا واقعی توصیف کرد.
توابع بازگشتی رایج
فرمول بندی اصلی کلیسا بیان می کند که محاسبه را می توان با استفاده از حساب λ انجام داد. این معادل استفاده از توابع بازگشتی عمومی است. تز چرچ-تورینگ بیشتر از آنچه در ابتدا تصور می شد، انواع محاسبات را پوشش می دهد. به عنوان مثال، مربوط به اتوماتای سلولی، کمبیناتورها، ماشین‌های ثبت و سیستم‌های جایگزین. در سال 1933، ریاضیدانان کرت گودل و ژاک هربراند یک تعریف رسمی از کلاسی به نام توابع بازگشتی عمومی ایجاد کردند. از توابعی استفاده می کند که در آن بیش از یک آرگومان ممکن است.
ایجاد روشλ-حساب
در سال 1936، آلونسو چرچ روشی برای تعیین به نام λ-calculus ایجاد کرد. او با اعداد طبیعی مرتبط بود. در حساب λ، دانشمند رمزگذاری آنها را تعیین کرد. در نتیجه، آنها را اعداد کلیسا می نامند. تابعی بر اساس اعداد طبیعی λ-computable نامیده می شد. تعریف دیگری هم داشت. تابع تز چرچ تحت دو شرط λ قابل محاسبه نامیده می شود. اولی اینگونه به نظر می رسید: اگر بر روی عناصر کلیسا محاسبه می شد، و شرط دوم امکان نمایش توسط یکی از اعضای حساب λ بود.
همچنین در سال 1936، تورینگ قبل از مطالعه کار همکارش، یک مدل نظری برای ماشین‌های انتزاعی ایجاد کرد که اکنون به نام او نامگذاری شده‌اند. آنها می توانستند با دستکاری کاراکترهای روی نوار محاسبات را انجام دهند. این همچنین در مورد سایر فعالیت های ریاضی موجود در علوم کامپیوتر نظری، مانند محاسبات احتمالات کوانتومی، صدق می کند. عملکرد تز چرچ تنها بعداً با استفاده از ماشین تورینگ اثبات شد. در ابتدا، آنها بر λ-حساب تکیه کردند.
قابلیت محاسبه تابع
وقتی اعداد طبیعی به‌طور مناسب به‌عنوان دنباله‌های کاراکتری کدگذاری می‌شوند، اگر ماشین انتزاعی الگوریتم مورد نیاز را پیدا کند و این تابع را روی نوار چاپ کند، گفته می‌شود که تابعی روی اعداد طبیعی قابل محاسبه تورینگ است. چنین دستگاهی که در دهه 1930 وجود نداشت، در آینده یک کامپیوتر در نظر گرفته می شود. ماشین تورینگ انتزاعی و تز چرچ منادی عصر توسعه بوددستگاه های محاسباتی ثابت شد که طبقات توابع به طور رسمی توسط هر دو دانشمند تعریف شده اند. بنابراین، در نتیجه، هر دو عبارت در یکی ترکیب شدند. توابع محاسباتی و تز چرچ نیز تأثیر زیادی بر مفهوم محاسبه پذیری داشتند. آنها همچنین ابزار مهمی برای منطق ریاضی و نظریه اثبات شدند.
توجیه و مشکلات روش
نظرات متناقضی در مورد این پایان نامه وجود دارد. شواهد متعددی برای "فرضیه کاری" ارائه شده توسط چرچ و تورینگ در سال 1936 جمع آوری شد. اما تمام روش ها یا عملیات شناخته شده برای کشف توابع جدید به طور موثر قابل محاسبه از توابع داده شده با روش های ساخت ماشین آلات مرتبط بود که در آن زمان وجود نداشت. برای اثبات تز چرچ-تورینگ، از این واقعیت شروع می شود که هر مدل واقعی محاسباتی معادل است.
به دلیل تنوع تحلیل‌های مختلف، این به طور کلی به عنوان شواهد قوی در نظر گرفته می‌شود. همه تلاش‌ها برای تعریف دقیق‌تر مفهوم شهودی یک تابع قابل محاسبه مؤثر، معادل بودند. هر تحلیلی که ارائه شده است ثابت کرده است که همان دسته از توابع را مشخص می کند، یعنی آنهایی که توسط ماشین های تورینگ قابل محاسبه هستند. اما برخی از مدل‌های محاسباتی از نظر زمان و استفاده از حافظه برای کارهای مختلف کارآمدتر بودند. بعداً اشاره شد که مفاهیم اساسی توابع بازگشتی و تز چرچ نسبتاً فرضی هستند.
پایان نامه M
مهم است که بین تز تورینگ و این ادعا تمایز قائل شویم که هر چیزی که توسط یک دستگاه محاسباتی قابل محاسبه باشد، توسط ماشین آن قابل محاسبه است. گزینه دوم تعریف خاص خود را دارد. گاندی جمله دوم را «پایان نامه ام» می نامد. به این صورت است: "هر چیزی که می تواند توسط یک دستگاه محاسبه شود، می تواند توسط یک ماشین تورینگ محاسبه شود." در معنای محدود این تز، این یک گزاره تجربی است که ارزش صدق آن ناشناخته است. تز تورینگ و «تز M» گاهی با هم اشتباه گرفته می شوند. نسخه دوم به طور کلی نادرست است. ماشین‌های شرطی مختلفی توصیف شده‌اند که می‌توانند توابعی را محاسبه کنند که قابل محاسبه تورینگ نیستند. ذکر این نکته ضروری است که تز اول متضمن دومی نیست، اما با نادرستی آن مطابقت دارد.
مفهوم معکوس پایان نامه
در نظریه محاسباتی، تز چرچ به عنوان توصیفی از مفهوم محاسبه پذیری توسط یک کلاس از توابع بازگشتی عمومی استفاده می شود. استفان کلین آمریکایی فرمول کلی تری ارائه کرد. او همه توابع جزئی قابل محاسبه با الگوریتم را جزئی بازگشتی نامید.
استلزام معکوس معمولاً به عنوان تز معکوس چرچ نامیده می شود. این در این واقعیت نهفته است که هر تابع بازگشتی از اعداد صحیح مثبت به طور کارآمد ارزیابی می شود. در معنای محدود، یک پایان نامه به سادگی چنین امکانی را نشان می دهد. و به معنای وسیع‌تر، از این سؤال که آیا این ماشین شرطی می‌تواند در آن وجود داشته باشد، انتزاع می‌کند.
کامپیوترهای کوانتومی
مفاهیم توابع قابل محاسبه و تز چرچ به کشف مهمی برای ریاضیات، نظریه ماشین و بسیاری از علوم دیگر تبدیل شد. اما تکنولوژی بسیار تغییر کرده و همچنان در حال پیشرفت است. فرض بر این است که کامپیوترهای کوانتومی می توانند بسیاری از وظایف رایج را با زمان کمتری نسبت به کامپیوترهای مدرن انجام دهند. اما سوالاتی مانند مشکل توقف باقی می ماند. یک کامپیوتر کوانتومی نمی تواند به آن پاسخ دهد. و طبق تز چرچ-تورینگ، هیچ وسیله محاسباتی دیگری نیز وجود ندارد.
