ماشینهای تورینگ
ماشین تورینگ یک دستگاه انتزاعی با کنترل متناهی و نوار نامحدود است که مفهوم شهودی یک الگوریتم را به تصویر میکشد و به عنوان مدل مرجع استاندارد برای آنچه قابل محاسبه است، عمل میکند.
Definition
یک ماشین تورینگ شامل مجموعهای متناهی از حالتها و یک نوار دوطرفه بینهایت از خانهها است؛ در هر مرحله، نماد زیر سر خود را میخواند، یک نماد مینویسد، به چپ یا راست حرکت میکند و حالت خود را طبق یک تابع انتقال تغییر میدهد و هنگامی که وارد حالت پذیرش یا رد میشود، متوقف میگردد.
Scope
این موضوع تعریف و عملکرد ماشینهای تورینگ، پیکربندیها و محاسبات، استحکام مدل تحت تغییراتی مانند نوارهای چندگانه و عدم قطعیت، ماشین تورینگ جهانی که میتواند هر ماشین دیگری را شبیهسازی کند، و رمزگذاری ماشینها به عنوان دادههایی که استدلالهای خودارجاعی و تصمیمناپذیری را ممکن میسازد، پوشش میدهد.
Core questions
- چگونه یک دستگاه ساده خواندن-نوشتن-حرکت میتواند مفهوم کامل الگوریتم را به تصویر بکشد؟
- چرا بسیاری از انواع مدل دقیقاً توابع یکسانی را محاسبه میکنند؟
- ماشین جهانی چیست و چرا وجود آن اهمیت دارد؟
- چگونه رمزگذاری ماشینها به عنوان رشتهها، اثباتهایی درباره رفتار خودشان را ممکن میسازد؟
Key theories
- جهانی بودن (Universality)
- یک ماشین تورینگ جهانی واحد وجود دارد که با دریافت رمزگذاری هر ماشینی و ورودی آن، محاسبات آن ماشین را شبیهسازی میکند، که پیشدرآمدی بر کامپیوتر با برنامه ذخیرهشده است که در آن برنامهها خود داده هستند.
- استحکام مدل (Robustness of the model)
- افزودن نوارها، سرهای متعدد، نوارهای دو بعدی یا عدم قطعیت، کلاس توابع قابل محاسبه را تغییر نمیدهد، بنابراین ماشین تورینگ مفهومی از محاسبه را به تصویر میکشد که نسبت به چنین جزئیاتی حساس نیست.
Clinical relevance
ماشین تورینگ معیاری است که قدرت زبانهای برنامهنویسی و معماریهای کامپیوتری با آن سنجیده میشود، و ماشین جهانی جد مفهومی کامپیوتر همهمنظوره با برنامه ذخیرهشده است که تمام محاسبات مدرن بر آن استوار است.
History
تورینگ ماشینهای خود را در سال ۱۹۳۶ معرفی کرد تا دقیقاً مشخص کند که قابل محاسبه بودن یک عدد به چه معناست و مسئله تصمیم هیلبرت را حل کند. ایده یک ماشین جهانی، که در آن یک توصیف ذخیرهشده یک دستگاه عمومی را کنترل میکند، یک دهه بعد بر طراحی کامپیوتر با برنامه ذخیرهشده توسط فون نویمان تأثیر گذاشت.
Key figures
- Alan Turing
- Emil Post
- John von Neumann
Related topics
Seminal works
- turing1937
- sipser2013
Frequently asked questions
- آیا ماشین تورینگ یک کامپیوتر واقعی است؟
- خیر، این یک انتزاع ریاضی با نوار نامحدود است و به سرعت یا هزینه حافظه توجهی ندارد. ارزش آن مفهومی است: دقیقاً مشخص میکند که چه چیزی اصولاً قابل محاسبه است، و هر کاری که یک کامپیوتر واقعی میتواند انجام دهد، یک ماشین تورینگ نیز میتواند با نوار و زمان کافی انجام دهد.
- چرا ماشین تورینگ جهانی مهم است؟
- این نشان میدهد که یک ماشین ثابت میتواند رفتار هر ماشین دیگری را هنگامی که توصیف آن ماشین به عنوان ورودی به آن داده میشود، انجام دهد. این پایه نظری کامپیوتر قابل برنامهریزی همهمنظوره است، که در آن نرمافزار دادهای است که به یک دستگاه تفسیری واحد داده میشود، به جای سیمکشی مجدد برای هر کار.