A Turing machine is an abstract computational model that manipulates symbols on a tape.تتكون آلة تورينج رسمياً من شريط لا نهائي مقسم إلى خلايا، تحتوي كل منها على رمز من أبجدية محدودة؛ ووحدة تحكم بذاكرة حالات محدودة؛ ورأس قادر على القراءة والكتابة والانتقال خلية واحدة. تحدد دالة الانتقال (transition function) بناءً على الحالة الحالية والرمز المقروء رمزاً جديداً، واتجاه الحركة (يسار/يمين)، وحالة جديدة. تبدأ الآلة بكلمة مدخلة على الشريط ويمكنها أن تتوقف في حالة قبول أو رفض، أو أن تعلق في حلقة لا نهائية. ويمكن لآلة تورينج العامة (universal Turing machine) أن تحاكي أي آلة أخرى بناءً على وصفها — مما يُعد استباقاً لمفهوم الحاسوب المبرمج.
في عام 1936، أثناء حل آلان تورينج لمسألة القرار (Entscheidungsproblem) التي طرحها ديفيد هيلبرت، قدم مفهوم «الآلة-أ» (الآلة التلقائية) في ورقته «عن الأعداد القابلة للحساب». كان هدفه صياغة المفهوم الحدسي للخوارزمية بصورة شكلية. وبشكل مستقل، توصل ألونزو تشرش إلى مفهوم مكافئ هو حساب اللامدا (λ-calculus). تؤكد أطروحة تشرش-تورينج أن أي عملية يمكن حسابها حدسياً قابلة للتحقيق على آلة تورينج. في عام 1945، استخدم جون فون نيومان هذا النموذج في معمارية EDVAC — النموذج الأولي للحواسيب الحديثة. وفي عام 1985، اقترح ديفيد دويتش آلة تورينج الكمومية، ممهداً الطريق للحوسبة الكمومية.
تحسب آلة تورينج من خلال معالجة سلاسل الرموز. وهي من حيث الخوارزمية مكافئة للغة برمجة تحتوي على مصفوفة وحيدة ذات طول لا نهائي. من خصائصها الأساسية: وجود الآلة العامة (المفسّر interpreter)، وعدم قابلية مسألة التوقف للحل (halting problem) (لا يمكن تقرير ما إذا كانت آلة ما ستتوقف على مدخل معين خوارزمياً)، ومبرهنة العودية (recursion theorem) (يمكن للآلة الحصول على وصف لذاتها). وفي نظرية التعقيد، تُدرس الآلات العرَّافية (oracle machines) (التي تملك معلومات إضافية) والآلات الاحتمالية (probabilistic machines) (ذات مولّد بتات عشوائية). وتعمل آلات تورينج الكمومية على حالات في فضاء هيلبرت (Hilbert space) وتستخدم تحويلات واحدية (unitary transformations)؛ وهي لا تخالف أطروحة تشرش-تورينج، لكنها قد تحقق تسريعاً أسياً لبعض المسائل.
أي برنامج حاسوبي — من الآلة الحاسبة إلى المساعد الذكي — يتحول إلى تعليمات يمكن لآلة تورينج تنفيذها. وتقوم عليها نظرية الحوسبة بأكملها.
أبسط آلة تورينج عامة، التي ابتكرها مارفن مينسكي، تستخدم 7 حالات فقط و4 رموز — ومع ذلك فهي قادرة على حساب كل ما يستطيعه حاسوب فائق القوة، ولو ببطء شديد.










