سوال 144

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