ماشین تورینگ یک مدل نظری از محاسبات است که توسط آلن تورینگ در سال 1936 ارائه شد. این ماشین از چندین جزء تشکیل شده است که به آن امکان انجام محاسبات را می دهد.قطعات اصلی ماشین تورینگ عبارتند از:
نوار: نوار یک دنباله نامتناهی از سلول ها است که هر کدام قادر به نگه داشتن نمادی از یک الفبای محدود هستند.بی نهایت در هر دو جهت گسترش می یابد.نوار به عنوان ذخیره اصلی برای داده ها در طول محاسبات عمل می کند.
سر: سر یک مکانیسم خواندن/نوشتن است که نمادهای روی نوار را اسکن می کند.می تواند نماد را در موقعیت فعلی بخواند، یک نماد جدید بنویسد و در طول نوار به چپ یا راست حرکت کند.
کنترل حالت محدود: این جزء به عنوان مغز ماشین تورینگ عمل می کند.رفتار دستگاه را بر اساس وضعیت فعلی و نمادی که توسط سر اسکن می شود، تعیین می کند.کنترل حالت محدود مسئول انتقال بین حالت ها و به روز رسانی نوار است.
ثبت نام دولتی: ثبت وضعیت وضعیت فعلی ماشین تورینگ را نگه می دارد.رفتار دستگاه هم به وضعیت فعلی و هم به نماد در حال اسکن بستگی دارد.
الفبا: حروف الفبا مجموعه محدودی از نمادها است که ماشین تورینگ می تواند آنها را بخواند و روی نوار بنویسد.معمولاً شامل نمادهای ورودی و نمادهای ویژه ای است که برای اهداف کنترلی استفاده می شود.
