توابع محاسبهپذیر و تز چرچ-تورینگ
توابع محاسبهپذیر آنهایی هستند که یک رویه مکانیکی میتواند آنها را ارزیابی کند، و تز چرچ-تورینگ این مفهوم غیررسمی را با چندین مدل ریاضی دقیق که همگی یک کلاس را تعریف میکنند، یکسان میداند.
Definition
یک تابع محاسبهپذیر است اگر یک ماشین تورینگ، یا به طور معادل یک تعریف بازگشتی جزئی، خروجی آن را برای هر ورودی که در آن تعریف شده است، تولید کند؛ تز چرچ-تورینگ ادعا میکند که این کلاس دقیق ریاضی با کلاس شهودی توابع قابل محاسبه مؤثر مطابقت دارد.
Scope
این موضوع شامل ماشینهای تورینگ، توابع بازگشتی جزئی ساخته شده از توابع پایه با ترکیب، بازگشت اولیه و کمینهسازی، حساب لامبدا و ماشینهای ثبات، اثباتهای معادل بودن این مدلها، ماشینهای جهانی، و تز چرچ-تورینگ است که بیان میکند آنها تمام محاسبات مؤثر را در بر میگیرند.
Core questions
- ماشین تورینگ چیست و چگونه یک محاسبه را تعریف میکند؟
- توابع بازگشتی جزئی چگونه از عملیاتهای پایه تولید میشوند؟
- چرا همه مدلهای معقول محاسبات، توابع یکسانی را تعریف میکنند؟
- وضعیت و اهمیت تز چرچ-تورینگ چیست؟
Key theories
- مدل ماشین تورینگ
- ماشین تورینگ یک دستگاه حالت متناهی است که بر روی یک نوار نامحدود عمل میکند، و توابعی که محاسبه میکند، مفهوم الگوریتم را بر اساس دستکاری نمادهای ابتدایی رسمی میکند.
- معادل بودن مدلها
- ماشینهای تورینگ، توابع بازگشتی جزئی، حساب لامبدا، و ماشینهای ثبات همگی دقیقاً یک کلاس از توابع را محاسبه میکنند، که نشاندهنده استحکام مفهوم محاسبهپذیری است.
- ماشین جهانی و شمارش
- یک ماشین تورینگ جهانی وجود دارد که هر ماشینی را با کد آن شبیهسازی میکند، بنابراین توابع محاسبهپذیر را میتوان به طور مؤثر شمارش کرد و به عنوان داده در نظر گرفت، که اساس نتایج خودارجاعی است.
Clinical relevance
مفهوم تابع محاسبهپذیر اساس علوم نظری کامپیوتر است: ماشین جهانی پیشدرآمد کامپیوتر با برنامه ذخیرهشده است، معادل بودن مدلها یک تعریف قوی از الگوریتم را توجیه میکند، و چارچوب، بستر دقیقی را فراهم میکند که در آن عدم تصمیمپذیری و پیچیدگی مورد مطالعه قرار میگیرند.
History
در سال ۱۹۳۶، چرچ قابلیت محاسبه مؤثر را از طریق حساب لامبدا و تورینگ از طریق ماشینهای خود تعریف کردند، و این دو مفهوم به زودی معادل توابع بازگشتی کلینی اثبات شدند. تز چرچ-تورینگ حاصل، تعریف پذیرفته شده الگوریتم شد، و ماشین جهانی تورینگ به یک جد مفهومی برای کامپیوترهای عمومی تبدیل شد.
Key figures
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
Related topics
Seminal works
- cutland1980
- turing1936
- sipser2013
Frequently asked questions
- آیا برخی توابع محاسبهپذیر نیستند؟
- بله. از آنجا که برنامهها را میتوان شمارش کرد اما توابع را نمیتوان، یک استدلال شمارشی نشان میدهد که بیشتر توابع محاسبهپذیر نیستند، و مثالهای خاصی مانند تابع توقف به طور اثباتپذیری غیرقابل محاسبه هستند. محاسبهپذیری یک محدودیت واقعی بر روی توابعی است که الگوریتمها میتوانند ارزیابی کنند.
- آیا تز چرچ-تورینگ آنچه را که کامپیوترها میتوانند انجام دهند، محدود میکند؟
- این تز بیان میکند که هیچ مدل محاسبه مؤثری، کلاس توابع محاسبهپذیر را فراتر از ماشینهای تورینگ گسترش نمیدهد. سختافزار سریعتر یا معماریهای متفاوت، کارایی را تغییر میدهند، نه مرز آنچه اصولاً محاسبهپذیر است، بنابراین این تز یک حد مطلق برای حلپذیری الگوریتمی تعیین میکند.