فرضیه چرچ-تورینگ

فرضیه چرچ-تورینگ بیان می‌کند که هر تابعی که توسط هر رویه مؤثر قابل محاسبه باشد، توسط یک ماشین تورینگ قابل محاسبه است و ایده غیررسمی یک الگوریتم را با یک مدل ریاضی دقیق برابر می‌داند.

Definition

فرضیه چرچ-تورینگ این ادعا است که توابع قابل محاسبه شهودی دقیقاً همان توابعی هستند که توسط یک ماشین تورینگ، یا به طور معادل توسط حساب لامبدا یا توابع بازگشتی عمومی قابل محاسبه‌اند؛ این یک فرضیه است تا یک قضیه، زیرا مفهوم شهودی به طور رسمی تعریف نشده است.

Scope

این موضوع شامل بیان فرضیه، شواهد همگرا از مدل‌های مستقل پیشنهاد شده، تمایز بین فرضیه اصلی در مورد قابلیت محاسبه مؤثر و انواع قوی‌تر فیزیکی یا نظریه پیچیدگی، و نقش فرضیه به عنوان پلی بین شهود و اثبات رسمی در نظریه محاسبه‌پذیری است.

Core questions

• شناسایی مفهوم غیررسمی الگوریتم با یک مدل رسمی به چه معناست؟
• چرا همگرایی مدل‌های مستقل به عنوان شواهد قوی برای این فرضیه در نظر گرفته می‌شود؟
• آیا این فرضیه یک قضیه ریاضی، یک تعریف یا یک ادعای تجربی است؟
• نسخه‌های فیزیکی و نظریه پیچیدگی چگونه فراتر از بیان اصلی می‌روند؟

Key theories

همگرایی مدل‌های محاسباتی

ماشین‌های تورینگ، حساب لامبدای چرچ، و توابع بازگشتی گودل و هربراند نشان داده شد که دقیقاً همان کلاس توابع را تعریف می‌کنند، و این توافق مستقل اصلی‌ترین شواهد ارائه شده برای این فرضیه است.

وضعیت به عنوان یک فرضیه، نه یک قضیه

از آنجا که مفهوم شهودی رویه مؤثر رسمی نشده است، این ادعا قابل اثبات نیست؛ این به عنوان یک شناسایی بنیادی پذیرفته شده است که به استدلال‌های الگوریتمی غیررسمی اجازه می‌دهد جایگزین ساختارهای رسمی ماشین تورینگ شوند.

Clinical relevance

این فرضیه به رویه روزمره توصیف الگوریتم‌ها در شبه‌کد سطح بالا به جای ماشین‌های تورینگ مجوز می‌دهد، زیرا هر مفهوم معقولی از رویه مؤثر معادل تورینگ فرض می‌شود؛ همچنین بحث‌ها را در مورد اینکه آیا دستگاه‌های فیزیکی یا کوانتومی می‌توانند فراتر از قابلیت محاسبه تورینگ محاسبه کنند، چارچوب‌بندی می‌کند.

History

در سال ۱۹۳۶، چرچ پیشنهاد کرد که قابلیت محاسبه مؤثر را با تعریف‌پذیری لامبدا شناسایی کند، و تورینگ به طور مستقل برای مدل ماشین خود استدلال کرد، پس از آن تورینگ، کلینی و دیگران ثابت کردند که اینها و توابع بازگشتی معادل هستند. گودل، که در ابتدا شکاک بود، تحلیل تورینگ را قطعی دانست و ادعای ترکیبی به عنوان فرضیه چرچ-تورینگ شناخته شد.

Debates

آیا محاسبات فیزیکی می‌تواند از حد تورینگ فراتر رود؟

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

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

چرا به آن فرضیه می‌گویند نه قضیه؟

این فرضیه یک مدل رسمی را به ایده غیررسمی یک رویه مؤثر مرتبط می‌کند، و آن ایده غیررسمی هیچ تعریف ریاضی برای اثبات چیزها ندارد. شواهد قوی این است که هر تلاش مستقل برای رسمی‌سازی محاسبات، همان کلاس توابع را به دست آورده است، اما این پشتیبانی مفهومی است تا یک اثبات.

آیا کامپیوترهای کوانتومی فرضیه چرچ-تورینگ را رد می‌کنند؟

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