تز چرچ-تورینگ

در نظریهٔ محاسبات، تز چرچ-تورینگ (Church–Turing thesis) پیرامون مفهوم یک روش مؤثر یا مکانیکی در منطق و ریاضیات شکل یافته‌است.
در اویل قرن ۲۰ تلاش‌های فراوانی برای فرمول سازی  محاسبات انجام شد.
 ریاضیدان آمریکایی آلونزو چرچAlonzo Church برای تعریف تابع روشی به نام جبر لانداLambda calculus ابداع کرد.
 ریاضیدان انگلیسی آلن تورینگ مدلی تئوری که حالا به نام ماشین جهانی تورینگUniversal Turing machine شناخته می‌شود ابداع کرد.
 چرچ همراه با یک ریاضیدانی به نام استفان کل کلینStephen Cole Kleene و منطقدانی به نام جان بارکلی روزرJ. Barkley Rosser تعریفی رسمی از گروهی از توابع که با کمک آنها می‌توان مقدارشان را به طور بازگشتی محاسبه کرد ارائه دادند.

هر سه روش محاسبات بالا هم ارز یکدیگرند و هر سه نگرش یک گروه از توابع را تعریف می‌کنند. همین باعث این شد که ریاضیدانان و محققین علم کامپیوتر به این  نتیجه برسند که   نظریه محاسبات به وسیله همین سه روش مشخص و تعریف می‌شود. به عبارتی تز چرچ-تورینگ بیان می‌کند اگر الگوریتمی برای انجام محاسبات وجود داشته باشد، آنگاه همان الگوریتم توسط ماشین تورینگ انجام می‌شود.
تز چرچ-تورینگ بیانکننده طبیعت محاسبات است و نمی‌توان آن را اثبات کرد. حتی اگر  هم اثبات شود سه روش فوق معادل یکدیگرند، اما یک اصل اساسی  است که آن حس مبهمی که این تز دارد بنابراین این تز همچنان به شکل فرضیه باقی می‌ماند.
علیرغم اینکه تز چرچ-تورینگ هنوز اثبات نشده‌است , ولی تقریباً به طور جهانی پذیرفته شده‌است.

 بیان رسمی 
سخرانی روزر در سال ۱۹۳۶ در مورد مفهوم شمارش پذیری مؤثر بدین صورت بود که: واضح است که وجود  CC و RC (اثبات  چرج و روزر) مستلزم تعریف دقیق از " مؤثر بودن " است.روش مؤثر بودنEffective method در اینجا در مفهوم نسبتاً خاصی از یک روش که در آن هر مرحله دقیقاً از پیش تعیین شده و مسلم است به تولید پاسخ در تعداد متناهی مرحله، استفاده می‌شود. بنابراین صفت و قید "مؤثر بودن "در اینجا به یک معنا است و آن," گرفتن یک تصمیم مطمئن یا اثر مطمئن است " و " توانایی رسیدن به نتیجه ".
همچنین در ادامه کلمه شمارش پذیری مؤثر به معنای "  به هر طریقی به طور مستقیم مؤثر تولید کردن " و محاسبه پذیری مؤثر به معنای " توسط ماشین تورینگ یا هر ماشین مکانیکی معادل تولید شدن " است. تعریف "تورینگ" در پاورقی رساله دکتری خود به نام " سیستم‌های منطقی برحسب ترتیب"Systems of Logic Based on Ordinals که زیر نظر چرچ در سال ۱۹۳۹تهیه کرده بود، تقریباًَ یکسان اند.
"ما باید از عبارت "توابع قابل محاسبه" به منظور تابعی که با ماشین محاسبه شده است استفاده کنیم، و عبارت "شمارش پذیر مؤثر" را برای اشاره به ایده‌هایحسی که با توجه به این تعاریف هیچ هویتی ندارند، استفاده کنیم."
همچین در این پایان‌نامه عبارت زیر وجود دارد که:
"تمام توابع شمارش پذیر مؤثر همان توابع قابل محاسبه‌اند.Gandy (Gandy 1980 in Barwise 1980:123) states it this way: What is effectively calculable is computable. He calls this "Church's Thesis", a peculiar choice of moniker."

 تاریخچه و اهمیت 
مسئله تصمیمEntscheidungsproblemداوید هیلبرت یکی از مسائل مهم منطق در سال‌های ۱۹۳۶ بود که بیان می‌کرد: یک روش مکانیکی برای جداسازی حقایق ریاضی از دروغ‌های ریاضی وجود دارد.
برای این کار لازم است که مفهوم "الگوریتم" و "شمارش پذیری" از هم جدا شوند. بنابراین قید و صفت مؤثر بودن در اینجا به یک معنا است که آن," تصمیم گرفتن یا اثر مورد دلخواه و توانایی تولید نتیجه" است.

تز چرچ-تورینگ را آلونزو چرچ در سال ۱۹۳۶ میلادی پیشنهاد نموده‌است. این تز بیان می‌دارد که هر محاسبهٔ مؤثرEffective computation صورت‌یافته، در هر سیستم الگوریتمی را می‌توانیم با استفاده از یک ماشین تورینگ به انجام برسانیم. چنانچه بخواهیم این تز بسیار اساسی در تئوری محاسبات را تنها به‌عنوان تعریفی از محاسبات الگوریتمی به حساب بیاوریم، آن‌را فقط از منظری فوق‌العاده محدود ملاحظه کرده‌ایم.

 پانوشته‌ها 

 جستارهای وابسته 
 ماشین‌های تورینگ

 منابع 

 Sudkamp, T. A. , An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed. , Pearson Education, Inc. , 2006.  

 پیوند به بیرون 
 تز چرچ-تورینگ، دائرةالمعارف فلسفهٔ استانفورد 

رده:آلن تورینگ
رده:فلسفه علوم رایانه
رده:نظریه بازگشت
رده:نظریه محاسبات