تز چرچ-تورینگ
در نظریهٔ محاسبات، تز چرچ-تورینگ (Church–Turing thesis) پیرامون مفهوم یک روش مؤثر یا مکانیکی در منطق و ریاضیات شکل یافته‌است.
در اویل قرن ۲۰ تلاش‌های فراوانی برای فرمول سازی محاسبات انجام شد.
- ریاضیدان آمریکایی آلونزو چرچ[۱] برای تعریف تابع روشی به نام جبر لاندا[۲] ابداع کرد.
- ریاضیدان انگلیسی آلن تورینگ مدلی تئوری که حالا به نام ماشین جهانی تورینگ[۳] شناخته می‌شود ابداع کرد.
- چرچ همراه با یک ریاضیدانی به نام استفان کل کلین[۴] و منطقدانی به نام جان بارکلی روزر[۵] تعریفی رسمی از گروهی از توابع که با کمک آنها می‌توان مقدارشان را به طور بازگشتی محاسبه کرد ارائه دادند.
هر سه روش محاسبات بالا هم ارز یکدیگرند و هر سه نگرش یک گروه از توابع را تعریف می‌کنند. همین باعث این شد که ریاضیدانان و محققین علم کامپیوتر به این نتیجه برسند که نظریه محاسبات به وسیله همین سه روش مشخص و تعریف می‌شود. به عبارتی تز چرچ-تورینگ بیان می‌کند اگر الگوریتمی برای انجام محاسبات وجود داشته باشد، آنگاه همان الگوریتم توسط ماشین تورینگ انجام می‌شود.
تز چرچ-تورینگ بیانکننده طبیعت محاسبات است و نمی‌توان آن را اثبات کرد. حتی اگر هم اثبات شود سه روش فوق معادل یکدیگرند، اما یک اصل اساسی است که آن حس مبهمی که این تز دارد بنابراین این تز همچنان به شکل فرضیه باقی می‌ماند.
علیرغم اینکه تز چرچ-تورینگ هنوز اثبات نشده‌است , ولی تقریباً به طور جهانی پذیرفته شده‌است.
بیان رسمی
[ویرایش]سخرانی روزر در سال ۱۹۳۶ در مورد مفهوم شمارش پذیری مؤثر بدین صورت بود که: واضح است که وجود CC و RC (اثبات چرج و روزر) مستلزم تعریف دقیق از " مؤثر بودن " است.روش مؤثر بودن[۶] در اینجا در مفهوم نسبتاً خاصی از یک روش که در آن هر مرحله دقیقاً از پیش تعیین شده و مسلم است به تولید پاسخ در تعداد متناهی مرحله، استفاده می‌شود. بنابراین صفت و قید "مؤثر بودن "در اینجا به یک معنا است و آن," گرفتن یک تصمیم مطمئن یا اثر مطمئن است " و " توانایی رسیدن به نتیجه ".
همچنین در ادامه کلمه شمارش پذیری مؤثر به معنای " به هر طریقی به طور مستقیم مؤثر تولید کردن " و محاسبه پذیری مؤثر به معنای " توسط ماشین تورینگ یا هر ماشین مکانیکی معادل تولید شدن " است. تعریف "تورینگ" در پاورقی رساله دکتری خود به نام " سیستم‌های منطقی برحسب ترتیب"[۷] که زیر نظر چرچ در سال ۱۹۳۹تهیه کرده بود، تقریباًَ یکسان اند.
"ما باید از عبارت "توابع قابل محاسبه" به منظور تابعی که با ماشین محاسبه شده است استفاده کنیم، و عبارت "شمارش پذیر مؤثر" را برای اشاره به ایده‌هایحسی که با توجه به این تعاریف هیچ هویتی ندارند، استفاده کنیم."
همچین در این پایان‌نامه عبارت زیر وجود دارد که:
"تمام توابع شمارش پذیر مؤثر همان توابع قابل محاسبه‌اند.[۸]"
تاریخچه و اهمیت
[ویرایش]مسئله تصمیم[۹]داوید هیلبرت یکی از مسائل مهم منطق در سال‌های ۱۹۳۶ بود که بیان می‌کرد: یک روش مکانیکی برای جداسازی حقایق ریاضی از دروغ‌های ریاضی وجود دارد. برای این کار لازم است که مفهوم "الگوریتم" و "شمارش پذیری" از هم جدا شوند. بنابراین قید و صفت مؤثر بودن در اینجا به یک معنا است که آن," تصمیم گرفتن یا اثر مورد دلخواه و توانایی تولید نتیجه" است.
تز چرچ-تورینگ را آلونزو چرچ در سال ۱۹۳۶ میلادی پیشنهاد نموده‌است. این تز بیان می‌دارد که هر محاسبهٔ مؤثر[۱۰] صورت‌یافته، در هر سیستم الگوریتمی را می‌توانیم با استفاده از یک ماشین تورینگ به انجام برسانیم. چنانچه بخواهیم این تز بسیار اساسی در تئوری محاسبات را تنها به‌عنوان تعریفی از محاسبات الگوریتمی به حساب بیاوریم، آن‌را فقط از منظری فوق‌العاده محدود ملاحظه کرده‌ایم.
پانوشته‌ها
[ویرایش]- ↑ Alonzo Church
- ↑ Lambda calculus
- ↑ Universal Turing machine
- ↑ Stephen Cole Kleene
- ↑ J. Barkley Rosser
- ↑ 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. ISBN 0-321-32221-5 [۱]
پیوند به بیرون
[ویرایش]- تز چرچ-تورینگ، دائرةالمعارف فلسفهٔ استانفورد (انگلیسی)
