توابع بازگشتی و ماشینهای ثبات
نظریه توابع بازگشتی، توابع محاسبهپذیر را از تعداد انگشتشماری از عملیات اساسی میسازد، در حالی که ماشینهای ثبات با اعداد صحیح ذخیره شده در ثباتها محاسبه میکنند. این دو مدل، ماشین تورینگ را در بر میگیرند و استحکام مفهوم محاسبهپذیری را تأیید میکنند.
Definition
توابع بازگشتی عمومی آنهایی هستند که از ثابتها، تابع جانشین و پروجکشنها با ترکیب، بازگشت اولیه و کمینهسازی نامحدود ساخته میشوند؛ ماشینهای ثبات دستگاههای انتزاعی هستند که با افزایش، کاهش و آزمایش محتویات مجموعهای متناهی از ثباتها که اعداد طبیعی را نگه میدارند، محاسبه میکنند.
Scope
این موضوع شامل توابع بازگشتی اولیه، افزودن کمینهسازی نامحدود برای به دست آوردن توابع بازگشتی عمومی، تابع آکرمن به عنوان یک تابع محاسبهپذیر که بازگشتی اولیه نیست، ماشینهای ثبات و شمارنده و جامعیت آنها، و معادل بودن همه این مدلها با محاسبهپذیری تورینگ است.
Core questions
- چگونه میتوان توابع محاسبهپذیر را به صورت حسابی و بدون هیچ ماشینی تعریف کرد؟
- چرا کمینهسازی نامحدود فراتر از بازگشت اولیه مورد نیاز است؟
- چگونه ماشینهای ثبات ساده به قدرت کامل محاسبه دست مییابند؟
- چرا این مدلهای حسابی و ماشینی با ماشینهای تورینگ منطبق هستند؟
Key theories
- معادل بودن با محاسبهپذیری تورینگ
- توابع بازگشتی عمومی و توابعی که توسط ماشینهای ثبات محاسبه میشوند، دقیقاً همان توابع تورینگ-محاسبهپذیر هستند، که فرضیه چرچ-تورینگ را از طریق مدلهایی که بر حسب مفاهیم کاملاً حسابی و ماشینی ابتدایی تعریف شدهاند، تقویت میکند.
- فراتر از بازگشت اولیه
- تابع آکرمن کلی و محاسبهپذیر است، با این حال آنقدر سریع رشد میکند که نمیتواند بازگشتی اولیه باشد، که نشان میدهد جستجوی نامحدود ضروری است و توابع بازگشتی اولیه زیرمجموعهای مناسب از توابع محاسبهپذیر هستند.
- جامعیت ماشینهای ثبات
- مینسکي نشان داد که یک ماشین تنها با دو شمارنده و عملیات افزایش، کاهش و آزمایش صفر، از قبل تورینگ-کامل است، که نمایشی افراطی از این است که محاسبه کامل به چه میزان ساختار کمی نیاز دارد.
Clinical relevance
ماشینهای ثبات، حساب اعداد صحیح پردازندههای واقعی را مستقیمتر از نوارها مدلسازی میکنند، بازگشت اولیه با برنامههایی که همیشه خاتمه مییابند مطابقت دارد و زیربنای زبانهای تابعی کلی و تحلیل خاتمه است، و دیدگاه تابع بازگشتی، محاسبه را به مبانی ریاضیات متصل میکند.
History
گودل و هربراند توابع بازگشتی عمومی را در اوایل دهه ۱۹۳۰ تعریف کردند و کلینی این نظریه را توسعه داد، از جمله نقش کمینهسازی. آکرمن پیش از این تابع با رشد سریع خود را نشان داده بود، و مینسکي در دهه ۱۹۶۰ ماشینهای ثبات و شمارنده را معرفی کرد و حتی جامعیت ماشینهای دو شمارندهای را اثبات نمود.
Key figures
- Kurt Gödel
- Stephen Kleene
- Wilhelm Ackermann
- Marvin Minsky
Related topics
Seminal works
- cutland1980
- minsky1967
Frequently asked questions
- تفاوت بین توابع بازگشتی اولیه و توابع بازگشتی عمومی چیست؟
- توابع بازگشتی اولیه با استفاده از حلقههای محدود ساخته میشوند و همیشه خاتمه مییابند، اما همه توابع محاسبهپذیر را پوشش نمیدهند. افزودن کمینهسازی نامحدود، که یک جستجو است و ممکن است به طور نامحدود ادامه یابد، توابع بازگشتی عمومی را به دست میدهد که دقیقاً با توابع تورینگ-محاسبهپذیر منطبق هستند.
- چگونه یک ماشین تنها با دو شمارنده میتواند به اندازه یک کامپیوتر قدرتمند باشد؟
- مینسکي نشان داد که دو ثبات حاوی اعداد طبیعی، تنها با عملیات افزایش، کاهش و آزمایش صفر، میتوانند یک ماشین تورینگ را با کدگذاری نوار آن در ثباتها شبیهسازی کنند. این ساختار بسیار ناکارآمد است، اما ثابت میکند که حداقل سختافزار از قبل به قدرت کامل محاسبه دست مییابد.