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