ماشین های تورینگ شبیه ماشین های خودکار محدود/ماشین های حالت محدود هستند اما مزیت حافظه نامحدود دارند… آنها قادر به شبیه سازی رایانه های معمولی هستند. مشکلی که یک کامپیوتر معمولی می تواند حل کند (با داشتن حافظه کافی) با استفاده از ماشین تورینگ نیز قابل حل خواهد بود و بالعکس.
تفاوت RAM و TM چیست؟
یک ماشین تورینگ نمی تواند یک ماشین RAM می تواند حساب را در O(1) انجام دهد (تحت محدودیت های خاص). ماشین تورینگ نمی تواند. ماشین‌های تورینگ ماشین‌های RAM را به‌صورت چند جمله‌ای شبیه‌سازی می‌کنند، یعنی برای مقداری ثابت c، هر ماشین رمی که در زمان O(nk) کار می‌کند می‌تواند توسط ماشین تورینگ در زمان O(nck) شبیه‌سازی شود.
آیا نوار ماشین تورینگ نامحدود است؟
A Turing Machine (TM) یک ماشین حالت است که از دو حافظه تشکیل شده است: یک نوار نامحدود و یک جدول کنترل حالت محدود. نوار داده ها را به عنوان نماد نگه می دارد. دستگاه دارای مجموعه بسیار کوچکی از عملکردهای مناسب، اصلاً 6 (خواندن، نوشتن، حرکت به چپ، حرکت به راست، تغییر حالت، توقف) روی نوار است.
چرا ماشین تورینگ قدرتمند است؟
ماشین های تورینگ چقدر قدرتمند هستند؟ ماشین های تورینگ می توانند هر زبان معمولی یا بدون زمینه را بپذیرند. ماشین های تورینگ می توانند محاسبات حسابی پایه را انجام دهند … پایان نامه تورینگ بیان می کند که هر محاسباتی که می تواند با "وسیله مکانیکی" انجام شود، می تواند توسط ماشین تورینگ انجام شود (با نادیده گرفتن مسائل بازده).
آیا ماشین های تورینگ می توانند برای همیشه حلقه بزنند؟
turing(turingDescrip) نه می تواند برای همیشه متوقف شود و نه حلقه حلقه شود; به هر حال منطقی نیست.
