ماشین تورینگ: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات: حذف پارامتر اول انبار-رده به جهت آنکه رده مذکور هیچ عضوی ندارد |
جز ربات ردهٔ همسنگ (۲۶) +املا+مرتب+تمیز (۹.۱): + رده:نظریه اتوماتا+رده:زبان‌های صوری |
||
خط ۱:
{{تمیزکاری}}
[[پرونده: Maquina.png|بندانگشتی|300px|نمایش هنری یک ماشین تورینگ]]
'''ماشین تورینگ''' {{انگلیسی|Turing machine}} یک دستگاه فرضی است که روی نشان‌های روی یک قطعه نوار بر اساس جدول قوانین دستکاری انجام می‌دهد. با وجود اینکه مکانیزم ماشین تورینگ مقدماتی است مفهومش برای پوشش عملکردهای بسیار پیچیده کافی و گسترده‌است. ماشین تورینگ می‌تواند برای شبیه‌سازی [[الگوریتم|الگوریتمهای]]
=== تاریخچه ===
خط ۴۴:
۴. یک جدول محدود (که گاهی جدول عمل یا تابع انتقال نامیده می‌شود)، از دستورالعمل‌ها وجود دارد که در حال حاضر، حالت (q_i) و نماد (a_j) به ماشین داده می‌شود (برای مدلهای ۵تایی و گاهی ۴تایی) که روی نوار خوانده می‌شود و می‌گوید که ماشین، این موارد را به تزتیب زیر برای مدلهای ۵تایی انجام دهد:
* یا پاک کردن و یا نوشتن یک نماد (بصورت جایگزین کردن
* حرکت کردن کلاهک نوار (که توسط d_k مشخص می‌شود و می‌تواند مقادیر L برای حرکت به چپ و R برای حرکت به سمت راست به خود بگیرد. همچنین مقدار N نشان دهنده ساکن بودن نوار است).
* فرض کنید یک حالت مشابه یا یک حالت جدید مشخص شده است (رفتن به وضعیت q_i۱)
خط ۵۷:
=== چرا ماشین‌های تورینگ مدلهای مناسبی برای رایانه‌های واقعی هستند؟ ===
۱. هرچیزی که ماشین واقعی می‌تواند محاسبه کند، ماشین تورینگ هم می‌تواند. برای مثال ماشین تورینگ، می‌تواند هرچیز طبق روالی که در زبان‌های برنامه نویسی پیدا می‌شود شبیه سازی کند. همچنین می‌تواند
۲. تفاوت، تنها در قابلیت ماشین تورینگ برای دخالت در مقدار محدودی اطلاعات نهفته است. بنابراین، ماشین تورینگ می‌تواند در مدت زمان محدودی، در اطلاعات دخالت داشته باشد.
۳. ماشین واقعی همانند ماشین‌های تورینگ می‌توانند حافظه مورد نیازش را به کمک دیسک‌های بیشتر، بزرگ کند. اما حقیقت این است که هم ماشین تورینگ و هم ماشین واقعی، برای محاسبات نیازی به فضا در
۴. شرح برنامه‌های ماشین واقعی که از مدل ساده تر انتزاعی استفاده می‌کنند، پیچیده تر از شرح برنامه‌های ماشین تورینگ است.
خط ۶۹:
ماشین تورینگ به ما اجازه می‌دهد درباره الگوریتم‌هایی که برای همیشه نگه داشته می‌شوند، توصیفاتی ارائه دهیم؛ بدون در نظر گرفتن پیش رفت در معماری محاسبات با ماشین معمولی.
۶. ماشین تورینگ جملات الگوریتم را ساده می‌کند. الگوریتمهای در حال اجرا در ماشین آلات انتزاعی معادل تورینگ،
== محدودیت‌های ماشین تورینگ ==
خط ۷۹:
=== همزمانی ===
یکی دیگر از محدودیت‌های ماشین تورینگ این است که همزمانی را خوب ارئه نمی‌دهد. برای مثال برای اندازه عدد صحیحی
== پانویس ==
خط ۸۷:
== جستارهای وابسته ==
* [[ماشین محاسبه تورینگ]]
* [[تز چرچ-تورینگ]]
سطر ۱۲۹ ⟵ ۱۲۸:
[[رده:اختراعات انگلیسی]]
[[رده:روش‌های صوری]]
[[رده:زبان‌های صوری]]
[[رده:علوم رایانه در ۱۹۳۷ (میلادی)]]
[[رده:علوم نظری رایانه]]
[[رده:مدلهای محاسباتی]]
[[رده:نظریه اتوماتا]]
[[رده:نظریه بازگشت]]
| |||