ماشین تورینگ: تفاوت میان نسخه‌ها

'''ماشین تورینگ''' {{انگلیسی|Turing machine}} یک دستگاه فرضی است که روی نشان‌های روی یک قطعه نوار بر اساس جدول قوانین دست‌کاری انجام می‌دهد. با وجود اینکه مکانیزم ماشین تورینگ مقدماتی است، مفهومش برای پوشش عملکردهای بسیار پیچیده کافی و گسترده‌است. ماشین تورینگ می‌تواند برای شبیه‌سازی هر [[الگوریتم]] [[کامپیوتر]]ی و توضیح نحوه عملکرد یک [[واحد پردازشگر مرکزی]] به کار آید. حافظه این ماشین ساختاری بسیار ساده دارد. یعنی می‌تواند بصورتبه صورت یک آرایه یک بعدی از عناصر (سلولها) باشد که هر یک می‌توانند حافظ تنها یک نماد باشند. این آرایه از هر دو طرف باز و نامحدود است (حافظه بینهایت) و اطلاعات آن می‌توانند به هر ترتیبی فراخوانی شوند.

۲-هر ترتیبی از عملگرها قابل قبول است.

۱. یک نوار، به سلولهاییسلول‌هایی تقسیم‌بندی شده‌است و هر سلول شامل نمادهایی است. الفبا شامل نماد تهی خاصی و یک یا تعداد دیگری نماد است. فرض می‌شود که این نوار خودسرانه به چپ و راست رسانده شود. ماشین تورینگ از نوارهایی تأمین می‌شود که برای محاسبه لازم است.

۲. یک کلاهک وجود دارد که قادر به خواندن و نوشتن نمادهایی است که روی نوار قرار گرفته‌اند و بطور همزمان نوار را به سمت چپ و راست یکی از (و تنها یک) سلولهاسلول‌ها حرکت می‌دهد. در بعضی مدلها، کلاهک حرکت می‌کند و نوار ثابت می‌ماند.

۴. یک جدول محدود (که گاهی جدول عمل یا تابع انتقال نامیده می‌شود)، از دستورالعمل‌ها وجود دارد که در حال حاضر، حالت (q_i) و نماد (a_j) به ماشین داده می‌شود (برای مدل‌های ۵تایی و گاهی ۴تایی) که روی نوار خوانده می‌شود و می‌گوید که ماشین، این موارد را به ترتیب زیر برای مدلهایمدل‌های ۵تایی انجام دهد:

در مدل‌های ۴تایی پاک کردن یا نوشتن یک نماد (a_j۱) و حرکت کلاهک نوار به سمت چپ یا راست (d_k) بصورتبه صورت دستورالعمل‌های جداگانه مشخص شده‌اند. بطور خاص، جدول به ماشین می‌گوید که چیزی را پاک کند یا یک نماد را بنویسد (ia) یا کلاهک نوار به سمت چپ و راست حرکت کند (ib). فرض کنید که حالتهای مشابه یا حالتهای جدیدی مشخص شده‌اند. اما عملیات‌های (ia) و (ib) دستورالعمل‌های یکسانی ندارند. در برخی از مدلها، اگر در جدول، ورودی از نمادها و حالتها نداشته باشیم، ماشین متوقف خواهد شد. سایر مدلها، نیاز به همه ورودی‌ها دارند تا پر شوند.