ماشین تورینگ: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جزبدون خلاصۀ ویرایش برچسب: نیازمند بازبینی |
ابرابزار تمیزکاری |
||
خط ۲:
{{تورینگ}}
[[پرونده: Maquina.png|بندانگشتی|300px|نمایش هنری یک ماشین تورینگ]]
'''ماشین تورینگ''' {{انگلیسی|Turing machine}} یک دستگاه فرضی است که روی نشان‌های روی یک قطعه نوار بر اساس جدول قوانین
=== تاریخچه ===
زمینه‌های تاریخی:ماشین محاسباتی
سطر ۲۳ ⟵ ۲۲:
=== تعریف منطقی (انتزاع ذهنی مفاهیم کلی) ===
ماشین تورینگ عبارت است از یک پنج-تاپل (پنج‌تایی) به‌صورت <math>M = (Q, \Sigma, \Gamma, \delta, q_0) \!</math>، که در اینجا:
* <math>M \!</math> برای نمایش مفهوم ماشین انتخاب شده است.
سطر ۲۹ ⟵ ۲۷:
* <math>\Gamma \!</math> مجموعه‌ای متناهی موسوم به الفبای نوار<ref>Tape alphabet</ref> و حاوی نمادی مخصوص <math>B \!</math> برای نمایش یک فاصلهٔ خالی روی نوار ماشین است.
* <math>\Sigma \!</math> [[زیرمجموعه|زیرمجموعه‌ای]] است از <math> \Gamma - \{B\} \!</math> و موسوم به الفبای ورودی. یعنی الفبای ورودی زیر مجموعه‌ای از الفبای نوار است که شامل خالی نیست. نوارهای خالی نمی‌توانند بعنوان ورودی استفاده شوند.
* <math>\delta \!</math> عبارت است از یک تابع جزئی،<ref>Partial function</ref> موسوم به تابع انتقال<ref>Transition function</ref> از دامنهٔ <math> Q \times \Gamma \!</math> به برد <math>Q \times \Gamma
* <math>q_0 \!</math> حالت شروع نام دارد، یعنی، حالتی از ماشین است که محاسبه را درآن آغاز می‌کنیم.
بطور کلی <math>\delta \!</math> یک تابع جزئی روی <math>Q \! \times \Gamma \!</math> است و تفسیرش عملکرد ماشین تورینگ را بیان می‌کند.
سطر ۵۰ ⟵ ۴۸:
در مدل‌های ۴تایی پاک کردن یا نوشتن یک نماد (a_j۱) و حرکت کلاهک نوار به سمت چپ یا راست (d_k) بصورت دستورالعمل‌های جداگانه مشخص شده‌اند. بطور خاص، جدول به ماشین می‌گوید که چیزی را پاک کند یا یک نماد را بنویسد (ia) و یا کلاهک نوار به سمت چپ و راست حرکت کند (ib). فرض کنید که حالتهای مشابه یا حالتهای جدیدی مشخص شده‌اند. اما عملیات‌های (ia) و (ib) دستورالعمل‌های یکسانی ندارند. در برخی از مدلها، اگر در جدول، ورودی از نمادها و حالتها نداشته باشیم، ماشین متوقف خواهد شد. سایر مدلها، نیاز به همه ورودی‌ها دارند تا پر شوند.
توجه داشته باشید که هر بخش از ماشین- حالتها و نمادها، مجموعه‌ها، اقدامات، چاپ کردن، پاک کردن و حرکت نوار- محدود، گسسته و تشخیص پذیر است. این، پتانسیل نامحدود نوارهاست که خود مقدار نامحدودی از یک فضای
=== مقایسه با ماشین‌های واقعی ===
اغلب گفته می‌شود که ماشین تورینگ، بر خلاف ماشین‌های اتومات، به اندازه ماشین‌های واقعی قدرتمند هستند و قادر به انجام هر عملیاتی که ماشین واقعی می‌تواند بکند هستند. چیزی که در این مطلب جا ماند این است که یک ماشین واقعی تنها می‌تواند در بسیاری از تنظیمات متناهی باشد؛ در واقع ماشین واقعی چیزی نیست جز یک ماشین اتوماتیک محدود خطی. از طرف دیگر ماشین تورینگ با ماشین‌هایی که دارای ظرفیت حافظه‌های نامحدود محاسباتی هستند، معادل است. از نظر تاریخی رایانه‌هایی که محاسبات را در حافظه داخلی شان انجام می‌دادند، بعدها توسعه داده شده‌اند.
=== چرا ماشین‌های تورینگ مدل‌های مناسبی برای رایانه‌های واقعی هستند؟ ===
۱. هرچیزی که ماشین واقعی می‌تواند محاسبه کند، ماشین تورینگ هم می‌تواند. برای مثال ماشین تورینگ، می‌تواند هرچیز طبق روالی که در زبان‌های برنامه نویسی پیدا می‌شود
۲. تفاوت، تنها در قابلیت ماشین تورینگ برای دخالت در مقدار محدودی اطلاعات نهفته
▲۱. هرچیزی که ماشین واقعی می‌تواند محاسبه کند، ماشین تورینگ هم می‌تواند. برای مثال ماشین تورینگ، می‌تواند هرچیز طبق روالی که در زبان‌های برنامه نویسی پیدا می‌شود شبیه سازی کند. همچنین می‌تواند فرایندهای بازگشتی و هریک از پارامترهای مکانیسم شناخته شده را شبیه سازی کند.
▲۲. تفاوت، تنها در قابلیت ماشین تورینگ برای دخالت در مقدار محدودی اطلاعات نهفته است. بنابراین، ماشین تورینگ می‌تواند در مدت زمان محدودی، در اطلاعات دخالت داشته باشد.
۳. ماشین واقعی همانند ماشین‌های تورینگ می‌توانند حافظه مورد نیازش را به کمک دیسک‌های بیشتر، بزرگ کند. اما حقیقت این است که هم ماشین تورینگ و هم ماشین واقعی، برای محاسبات نیازی به فضا در حافظه‌شان ندارند.
۴. شرح برنامه‌های ماشین واقعی که از مدل
۵. ماشین تورینگ الگوریتمهای مستقل را که چقدر از حافظه استفاده می‌کنند، توصیف می‌کند. در دارایی حافظه همهٔ ماشین‌ها، محدودیتی وجود دارد؛ ولی این محدودیت می‌تواند خود سرانه در طول زمان افزایش یابد.
سطر ۷۳ ⟵ ۶۹:
== محدودیت‌های ماشین تورینگ ==
=== نظریه پیچیدگی محاسباتی ===
یکی از محدودیت‌های ماشین‌های تورینگ این است که آنها توانایی چیدمان خوب را ندارند. برای مثال کامپیوترهای برنامه‌ای با ذخیره مدرن، نمونه‌هایی از یک مدل خاص ماشین انتزاعی که به نام ماشین برنامه دسترسی رندم یا مدل ماشین RASP می‌باشند.
=== همزمانی ===
یکی دیگر از محدودیت‌های ماشین تورینگ این است که همزمانی را خوب ارئه نمی‌دهد. برای مثال برای اندازه عدد صحیحی که می‌تواند توسط «متوقف کننده غیر قطعی دایمی» محاسبه شود، محدودیت وجود دارد. ماشین تورینگ روی یک نوار خالی شروع می‌کند. در مقابل، ماشین‌های «همیشه متوقف» همزمان هستند که بدون ورودی می‌توانند عدد صحیح نامتناهی را محاسبه کنند.
== پانویس ==
{{چپ‌چین}}
<
{{پایان چپ‌چین}}
| |||