|
=== تاریخچه ===
زمینه هایزمینه‌های تاریخی:ماشین محاسباتی
معرفی ماشین تورینگ توسط دانشمند [[انگلیس|انگلیسی]] [[آلن تورینگ]] در سال ۱۹۳۶ میلادی، گام دیگری را در مسیر ایجاد و پیدایش [[ماشین‌های محاسباتی حالات متناهی]] به نمایش می‌گذارد. رابین گندی یکی از دانشجویان آلن تورینگ و دوست صمیمی تمام عمرش، ریشه هایریشه‌های نظریه ماشین محاسباتی بابیج(۱۸۳۴) را کاوش کرد و در حقیقت نظریه بابیج را دوباره ارائه کرد:
آنالیز گندی در مورد ماشین تحلیلی بابیج پنج عملیات زیر را توضیح می دهدمی‌دهد:
۱-عملگرهای ریاضی + و - و *
۲-هر ترتیبی از عملگرها قابل قبول است
۵-انتقال شرطی
=== تعریف منطقی (انتزاع ذهنی مفاهیم کلی) ===
ماشین تورینگ عبارت است از یک پنج-تاپل (پنج‌تایی) به‌صورت <math>M = (Q, \Sigma, \Gamma, \delta, q_0) \!</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 \times \{L, R\} \!</math>.
* <math>q_0 \!</math> حالت شروع نام دارد، یعنی، حالتی از ماشین است که محاسبه را درآن آغاز می‌کنیم.
بطور کلی <math>\delta \!</math> یک تابع جزئی روی <math>Q \! \times \Gamma \!</math> است و تفسیرش عملکرد ماشین تورینگ را بیان می‌کند.
=== تعریف وصفی (عملی دنیای خارج از ذهن) ===
{{منبع-بخش}}
ماشین تورینگ به صورت ریاضی، ماشینی است که روی یک نوار عمل می کندمی‌کند. روی این نوار، نمادهایی است که ماشین هم می تواندمی‌تواند بخواند و هم می تواندمی‌تواند بنویسد و همزمان از آنها استفاده می کندمی‌کند. این عمل به طور کامل با یک سری دستورالعمل ساده محدود تعریف شده است.
ماشین تورینگ از موارد زیر تشکیل شده است:
1۱. یک نوار، به سلولهایی تقسیم بندی شده است و هر سلول شامل نمادهایی است. الفبا شامل نماد تهی خاصی و یک یا تعداد دیگری نماد است. فرض می شودمی‌شود که این نوار خودسرانه به چپ و راست رسانده شود. ماشین تورینگ از نوارهایی تامین می شودمی‌شود که برای محاسبه لازم است.
2۲. یک کلاهک وجود دارد که قادر به خواندن و نوشتن نمادهایی است که روی نوار قرار گرفته اندگرفته‌اند و بطور همزمان نوار را به سمت چپ و راست یکی از (و تنها یک) سلولها حرکت میدهدمی‌دهد. در بضی مدلها، کلاهک حرکت می کندمی‌کند و نوار ثابت می ماندمی‌ماند.
3۳. یک دستگاه ثبت حالت وجود دارد که حالت هایحالت‌های ماشین تورینگ را ذخیره می کندمی‌کند (یکی از تعداد زیادی حالت متناهی). یک حالت شروع وجود دارد که همراه با مقدار دهی اولیه است. این حالت ها،حالتها، حالت ذهن شخصی را که محاسبات را انجام می دهد،می‌دهد، جایگزین می کنندمی‌کنند.
4۴. یک جدول محدود (که گاهی جدول عمل یا تابع انتقال نامیده می شودمی‌شود)، از دستورالعمل هادستورالعمل‌ها وجود دارد که در حال حاضر، حالت (q_i) و نماد (a_j) به ماشین داده میمی‌شود شود( برای مدلمدل‌های های 5تایی۵تایی و گاهی 4تایی۴تایی) که روی نوار خوانده می شودمی‌شود و میگویدمی‌گوید که ماشین، این موارد را به تزتیب زیر برای مدلهای 5تایی۵تایی انجام دهد:
* یا پاک کردن و یا نوشتن یک نماد (بصورت جایگزین کردن a_i با a_j1a_j۱)
* حرکت کردن کلاهک نوار (که توسط d_k مشخص می شودمی‌شود و می تواندمی‌تواند مقادیر L برای حرکت به چپ و R برای حرکت به سمت راست به خود بگیرد. همچنین مقدار N نشان دهنده ساکن بودن نوار است).
* فرض کنید یک حالت مشابه یا یک حالت جدید مشخص شده است (رفتن به وضعیت q_i1 q_i۱)
در مدلمدل‌های های 4تایی۴تایی پاک کردن یا نوشتن یک نماد (a_j1a_j۱) و حرکت کلاهک نوار به سمت چپ یا راست (d_k) بصورت دستورالعمل هایدستورالعمل‌های جداگانه مشخص شده اندشده‌اند. بطور خاص، جدول به ماشین میگویدمی‌گوید که چیزی را پاک کند یا یک نماد را بنویسد (ia) و یا کلاهک نوار به سمت چپ و راست حرکت کند (ib). فرض کنید که حالتهای مشابه یا حالتهای جدیدی مشخص شده اندشده‌اند. اما عملیات هایعملیات‌های (ia) و (ib) دستورالعمل هایدستورالعمل‌های یکسانی ندارند. در برخی از مدلها، اگر در جدول، ورودی از نمادها و حالتها نداشته باشیم، ماشین متوقف خواهد شد. سایر مدلها، نیاز به همه ورودی هاورودی‌ها دارند تا پر شوند.
توجه داشته باشید که هر بخش از ماشین- حالتها و نمادها، مجموعه ها،مجموعه‌ها، اقدامات، چاپ کردن، پاک کردن و حرکت نوار- محدود، گسسته و تشخیص پذیر است. این، پتانسیل نامحدود نوارهاست که خود مقدار نامحدودی از یک فضای ذخیره سازی است.
=== مقایسه با ماشین هایماشین‌های واقعی ===
اغلب گفته می شودمی‌شود که ماشین تورینگ، بر خلاف ماشین هایماشین‌های اتومات، به اندازه ماشین هایماشین‌های واقعی قدرتمند هستند و قادر به انجام هر عملیاتی که ماشین واقعی می تواندمی‌تواند بکند هستند. چیزی که در این مطلب جا ماند این است که یک ماشین واقعی تنها می تواندمی‌تواند در بسیاری از تنظیمات متناهی باشد؛ در واقع ماشین واقعی چیزی نیست جز یک ماشین اتوماتیک محدود خطی. از طرف دیگر ماشین تورینگ با ماشین هاییماشین‌هایی که دارای ظرفیت حافظه هایحافظه‌های نامحدود محاسباتی هستند، معادل است. از نظر تاریخی رایانه هاییرایانه‌هایی که محاسبات را در حافظه داخلی شان انجام می دادند،می‌دادند، بعدها توسعه داده شده اندشده‌اند.
=== چرا ماشین هایماشین‌های تورینگ مدل هایمدل‌های مناسبی برای رایانه هایرایانه‌های واقعی هستند؟ ===
1۱. هرچیزی که ماشین واقعی میتواندمی‌تواند محاسبه کند، ماشین تورینگ هم می تواندمی‌تواند. برای مثال ماشین تورینگ، می تواندمی‌تواند هرچیز طبق روالی که در زبان هایزبان‌های برنامه نویسی پیدا می شودمی‌شود شبیه سازی کند. همچنین می تواندمی‌تواند فرآیندهای بازگشتی و هریک از پارامترهای مکانیسم شناخته شده را شبیه سازی کند.
2۲. تفاوت، تنها در قابلیت ماشین تورینگ برای دخالت در مقدار محدودی اطلاعات نهفته است. بنابراین، ماشین تورینگ میتواندمی‌تواند در مدت زمان محدودی، در اطلاعات دخالت داشته باشد.
3۳. ماشین واقعی همانند ماشین هایماشین‌های تورینگ می توانندمی‌توانند حافظه مورد نیازش را به کمک دیسک هایدیسک‌های بیشتر، بزرگ کند. اما حقیقت این است که هم ماشین تورینگ و هم ماشین واقعی، برای محاسبات نیازی به فضا در حافظه شان ندارند.
4۴. شرح برنامه هایبرنامه‌های ماشین واقعی که از مدل ساده تر انتزاعی استفاده می کنند،می‌کنند، پیچیده تر از شرح برنامه هایبرنامه‌های ماشین تورینگ است.
5۵. ماشین تورینگ الگوریتم هایالگوریتم‌های مستقل را که چقدر از حافظه استفاده می کنند،می‌کنند، توصیف می کندمی‌کند. در دارایی حافظه همههمهٔ ی ماشین ها،ماشین‌ها، محدودیتی وجود دارد؛ ولی این محدودیت می تواندمی‌تواند خود سرانه در طول زمان افزایش یابد.
ماشین تورینگ به ما اجازه می دهدمی‌دهد درباره الگوریتم هاییالگوریتم‌هایی که برای همیشه نگه داشته می شوند،می‌شوند، توصیفاتی ارائه دهیم؛ بدون در نظر گرفتن پیش رفت در معماری محاسبات با ماشین معمولی.
6۶. ماشین تورینگ جملات الگوریتم را ساده می کندمی‌کند. الگوریتم هایالگوریتم‌های در حال اجرا در ماشین آلات انتزاعی معادل تورینگ، معمولا نسبت به همتایان خود که در ماشین هایماشین‌های واقعی در حال اجرا هستند عمومی ترند. زیرا آنها دارای دقت دلخواه در انواع اطلاعات قابل دسترس هستند و هیچوقت با شرایط غیر منتظره روبرو نمی شوندنمی‌شوند. یکی از نقطه ضعف هایضعف‌های ماشین تورینگ این است که برنامه هایبرنامه‌های واقعی که نوشته می شوند ورودیمی‌شوند هایورودی‌های نامحدودی را در طول زمان دریافت می کنند؛می‌کنند؛ در نتیجه هرگز متوقف نمی شوندنمی‌شوند.
== محدودیت هایمحدودیت‌های ماشین تورینگ ==
=== نظریه پیچیدگی محاسباتی ===
یکی از محدودیتمحدودیت‌های های ماشین هایماشین‌های تورینگ این است که آنها توانایی چیدمان خوب را ندارند. برای مثال کامپیوترهای برنامه ایبرنامه‌ای با ذخیره مدرن، نمونه هایینمونه‌هایی از یک مدل خاص ماشین انتزاعی که به نام ماشین برنامه دسترسی رندم یا مدل ماشین RASP می باشندمی‌باشند.
=== همزمانی ===
یکی دیگر از محدودیت هایمحدودیت‌های ماشین تورینگ این است که همزمانی را خوب ارئه نمی دهدنمی‌دهد. برای مثال برای اندازه عدد صحیحی که میتواندمی‌تواند توسط « متوقف کننده غیر قطعی دایمی» محاسبه شود، محدودیت وجود دارد. ماشین تورینگ روی یک نوار خالی شروع می کندمی‌کند. در مقابل، ماشین هایماشین‌های «همیشه متوقف» همزمان هستند که بدون ورودی می توانندمی‌توانند عدد صحیح نامتناهی را محاسبه کنند.
== پانویس ==
== جستارهای وابسته ==
* [[ماشین محاسبه تورینگ]]
* [[تز چرچ-تورینگ]]
{{چپ‌چین}}
* Sudkamp, T. A. , ''An Introduction to the Theory of Computer Science, Languages and Machines'', 3rd۳rd ed. , Pearson Education, Inc. , 2006۲۰۰۶. ISBN 0-321-32221-5
* Johnsonbaugh, R. , ''Discrete Mathematics'', 4th۴th ed. , Prentice Hall, 1993. ISBN 0-13-518242-5
* Jackson, Jr. , Philip C. , ''Introduction to Artificial Intelligence'', 2nd۲nd enlarged and slightly corrected ed. , Dover Publications, Inc. , New York, 1985. ISBN 0-486-24864-X
{{پایان چپ‌چین}}
* {{یادکرد
|ویرایش= سوم
|صفحه=
|سال=1387۱۳۸۷
|شابک= ISBN 964-6342-49-3
}}
| 