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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در نظریهٔ محاسبات، تز چرچ-تورینگ (Church–Turing thesis) پیرامون مفهوم یک روش مؤثر یا مکانیکی در منطق و ریاضیات شکل یافته‌است.
در اویل قرن ۲۰ تلاش‌های فراوانی برای فرمول سازی محاسبات انجام شد.

  • ریاضیدان آمریکایی آلونزو چرچ[۱] برای تعریف تابع روشی به نام جبر لاندا[۲] ابداع کرد.
  • ریاضیدان انگلیسی آلن تورینگ مدلی تئوری که حالا به نام ماشین جهانی تورینگ[۳] شناخته می‌شود ابداع کرد.
  • چرچ همراه با یک ریاضیدانی به نام استفان کل کلین[۴]و منطقدانی به نام جان بارکلی روزر[۵] تعریفی رسمی از گروهی از توابع که با کمک آنها می‌توان مقدارشان را به طور بازگشتی محاسبه کرد ارائه دادند.


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

بیان رسمی[ویرایش]

سخرانی روزر در سال ۱۹۳۶ در مورد مفهوم شمارش پذیری موثر بدین صورت بود که: واضح است که وجود CC و RC (اثبات چرج و روزر) مستلزم تعریف دقیق از " موثر بودن " است.روش موثر بودن[۶]در اینجا در مفهوم نسبتاً خاصی از یک روش که در آن هر مرحله دقیقاً از پیش تعیین شده و مسلم است به تولید پاسخ در تعداد متناهی مرحله، استفاده می‌شود. بنابراین صفت و قید "موثر بودن "در اینجا به یک معنا است و آن," گرفتن یک تصمیم مطمئن و یا اثر مطمئن است " و " توانایی رسیدن به نتیجه ".
همچنین در ادامه کلمه شمارش پذیری موثر به معنای " به هر طریقی به طور مستقیم موثر تولید کردن " و محاسبه پذیری موثر به معنای " توسط ماشین تورینگ یا هر ماشین مکانیکی معادل تولید شدن " است. تعریف "تورینگ" در پاورقی رساله دکتری خود به نام " سیستم‌های منطقی برحسب ترتیب"[۷] که زیر نظر چرچ در سال ۱۹۳۹تهیه کرده بود، تقریباًَ یکسان اند.
"ما باید از عبارت "توابع قابل محاسبه" به منظور تابعی که با ماشین محاسبه شده‌استاستفاده کنیم، و عبارت "شمارش پذیر موثر" را برای اشاره به ایده‌هایحسی که با توجه به این تعاریف هیچ هویتی ندارند، استفاده کنیم."
همچین در این پایان‌نامه عبارت زیر وجود دارد که:
"تمام توابع شمارش پذیز موثر همان توابع قابل محاسبه‌اند.[۸]"

تاریخچه و اهمیت[ویرایش]

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


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

پانوشته‌ها[ویرایش]

  1. Alonzo Church
  2. Lambda calculus
  3. Universal Turing machine
  4. Stephen Cole Kleene
  5. J. Barkley Rosser
  6. Effective method
  7. Systems of Logic Based on Ordinals
  8. 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.
  9. Entscheidungsproblem
  10. 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 [۱]

پیوند به بیرون[ویرایش]