آلة تورينج

أنواع الأوتوماتا

آلة تورينج هي نموذج رياضي للحوسبة يصف آلة مجردة ^{[ 1 ]} تعالج الرموز على شريط لاصق وفقًا لجدول من القواعد. ^{[ 2 ]} على الرغم من بساطة النموذج، إلا أنه قادر على تنفيذ أي خوارزمية حاسوبية . ^{[ 3 ]}

تعمل الآلة على شريط ذاكرة لانهائي ^{[ 4 ]} مُقسّم إلى خلايا منفصلة ، ^{​​[ 5 ]} تستطيع كل منها استيعاب رمز واحد مُختار من مجموعة محدودة من الرموز تُسمى أبجدية الآلة. تحتوي الآلة على "رأس" يتموضع فوق إحدى هذه الخلايا في أي لحظة من تشغيلها، و"حالة" مُختارة من مجموعة محدودة من الحالات. في كل خطوة من خطوات تشغيلها، يقرأ الرأس الرمز الموجود في خليته. ثم، بناءً على الرمز وحالة الآلة الحالية، تكتب الآلة رمزًا في الخلية نفسها، وتُحرّك الرأس خطوة واحدة إلى اليسار أو اليمين، ^{[ 6 ]} أو تُوقف الحساب. يعتمد اختيار رمز الاستبدال المراد كتابته، واتجاه تحريك الرأس، وقرار الإيقاف، على جدول محدود يُحدد الإجراء المطلوب لكل تركيبة من الحالة الحالية والرمز المقروء. وكما هو الحال في برامج الحاسوب الحقيقية، من الممكن أن تدخل آلة تورينج في حلقة لا نهائية لا تتوقف أبدًا.

اخترع آلان تورينج آلة تورينج عام 1936 ، ^{[ 7 ] [ 11 ]} وأطلق عليها اسم "آلة أوتوماتيكية". ^{[ 12 ]} وكان ألونسو تشيرش ، المشرف على أطروحة تورينج ، هو من صاغ مصطلح "آلة تورينج" لاحقًا في مراجعة. ^{[ 13 ]} وباستخدام هذا النموذج، تمكن تورينج من الإجابة على سؤالين بالنفي:

• هل توجد آلة يمكنها تحديد ما إذا كانت أي آلة عشوائية على شريطها "دائرية" (على سبيل المثال، تتجمد، أو تفشل في مواصلة مهمتها الحسابية)؟
• هل توجد آلة قادرة على تحديد ما إذا كانت أي آلة عشوائية على شريطها قد طبعت رمزًا معينًا؟ ^{[ 14 ] [ 15 ]}

وهكذا، من خلال تقديم وصف رياضي لجهاز بسيط للغاية قادر على إجراء عمليات حسابية عشوائية، تمكن من إثبات خصائص الحساب بشكل عام، وعلى وجه الخصوص، عدم إمكانية حساب مشكلة القرار (Entscheidungsproblem )، أو "مشكلة القرار" (ما إذا كانت كل عبارة رياضية قابلة للإثبات أو النفي). ^{[ 16 ]}

أثبتت آلات تورينج وجود قيود أساسية على قدرة الحوسبة الميكانيكية. ^{[ 3 ]}

على الرغم من قدرتها على التعبير عن عمليات حسابية عشوائية، إلا أن تصميمها البسيط يجعلها بطيئة للغاية بالنسبة للحساب في الممارسة العملية: تعتمد أجهزة الكمبيوتر في العالم الحقيقي على تصميمات مختلفة، على عكس آلات تورينج، تستخدم ذاكرة الوصول العشوائي .

اكتمال تورينج هو قدرة نموذج حسابي أو نظام تعليمات على محاكاة آلة تورينج. لغة البرمجة التي تتمتع باكتمال تورينج قادرة نظريًا على التعبير عن جميع المهام التي يمكن للحواسيب إنجازها؛ وتُعتبر جميع لغات البرمجة تقريبًا كاملة تورينج إذا تم تجاهل قيود الذاكرة المحدودة.

آلة تورينج هي نموذج مثالي لوحدة المعالجة المركزية (CPU) التي تتحكم في جميع عمليات معالجة البيانات التي يقوم بها الحاسوب، وتستخدم هذه الآلة ذاكرة تسلسلية لتخزين البيانات. عادةً ما تُمثَّل الذاكرة التسلسلية بشريط ذي طول غير محدود، حيث يمكن للآلة إجراء عمليات القراءة والكتابة عليه.

في سياق نظرية اللغات الرسمية ، تُعرف آلة تورينج (أو الأوتوماتون ) بقدرتها على تعداد أي مجموعة فرعية من السلاسل النصية الصحيحة في الأبجدية . وتُسمى مجموعة السلاسل النصية التي يمكن تعدادها بهذه الطريقة لغة قابلة للتعداد التكراري . ويمكن تعريف آلة تورينج، بشكل مكافئ، بأنها نموذج يتعرف على سلاسل الإدخال الصحيحة، بدلاً من تعداد سلاسل الإخراج.

بالنظر إلى آلة تورينج M وسلسلة عشوائية s ، فإنه من غير الممكن عمومًا تحديد ما إذا كانت M ستنتج s في النهاية . ويعود ذلك إلى أن مشكلة التوقف غير قابلة للحل، وهو ما له آثار كبيرة على الحدود النظرية للحوسبة.

تُسمى آلة تورينغ القادرة على محاكاة أي آلة تورينغ أخرى بآلة تورينغ شاملة (UTM، أو ببساطة آلة شاملة). وقد قدّم ألونسو تشيرش صيغة رياضية أخرى، هي حساب لامدا ، ذات طبيعة "شاملة" مماثلة . تداخل عمل تشيرش مع عمل تورينغ ليشكل أساسًا لأطروحة تشيرش-تورينغ . تنص هذه الأطروحة على أن آلات تورينغ، وحساب لامدا، وغيرها من الصيغ الحسابية المماثلة ، تُجسّد بالفعل المفهوم غير الرسمي للأساليب الفعّالة في المنطق والرياضيات ، وبالتالي تُقدّم نموذجًا يُمكن من خلاله التفكير في خوارزمية أو "إجراء ميكانيكي" بطريقة رياضية دقيقة دون التقيد بأي صيغة محددة. وقد أسفرت دراسة الخصائص المجردة لآلات تورينغ عن العديد من الرؤى في علوم الحاسوب ، ونظرية الحوسبة ، ونظرية التعقيد .

تُحاكي آلة تورينج رياضيًا آلة تعمل ميكانيكيًا على شريط. يحتوي هذا الشريط على رموز، تستطيع الآلة قراءتها وكتابتها، رمزًا تلو الآخر، باستخدام رأس الشريط. وتُحدد عملية التشغيل بالكامل بواسطة مجموعة محدودة من التعليمات الأساسية، مثل: "في الحالة 42، إذا كان الرمز المرئي هو 0، فاكتب 1؛ إذا كان الرمز المرئي هو 1، فانتقل إلى الحالة 17؛ في الحالة 17، إذا كان الرمز المرئي هو 0، فاكتب 1 وانتقل إلى الحالة 6"؛ إلخ. في المقالة الأصلية (" حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار "، انظر أيضًا المراجع أدناه )، لا يتخيل تورينج آلية، بل شخصًا يُطلق عليه اسم "الحاسوب"، يُنفذ هذه القواعد الميكانيكية الحتمية بشكل آلي (أو كما يقول تورينج، "بطريقة عشوائية").

وبشكل أكثر تحديداً، تتكون آلة تورينج من:

• شريط مقسم إلى خلايا متجاورة. تحتوي كل خلية على رمز من أبجدية محدودة. تتضمن الأبجدية رمزًا خاصًا فارغًا (يُكتب هنا '0') ورمزًا واحدًا أو أكثر. يُفترض أن الشريط قابل للتمديد بشكل غير محدود إلى اليسار واليمين، بحيث تُزود آلة تورينج دائمًا بالقدر الكافي من الشريط لإجراء حساباتها. تُملأ الخلايا التي لم تُكتب من قبل بالرمز الفارغ. في بعض النماذج، يكون للشريط طرف أيسر مُعلّم برمز خاص؛ ويمتد الشريط أو يكون قابلاً للتمديد إلى اليمين بلا حدود.
• رأس قراءة وكتابة الرموز على الشريط، وتحريك الشريط يمينًا ويسارًا خلية واحدة (فقط) في كل مرة. في بعض الطرازات، يتحرك الرأس بينما يبقى الشريط ثابتًا .
• سجل حالة يخزن حالة آلة تورينج، وهو واحد من عدد محدود من السجلات. من بين هذه السجلات حالة البداية الخاصة التي يُهيأ بها سجل الحالة. يكتب تورينج أن هذه الحالات تحل محل "حالة الذهن" التي يكون عليها الشخص الذي يُجري العمليات الحسابية عادةً.
• جدول محدود ^{[ 19 ]} من التعليمات ^{[ 20 ]} التي، بالنظر إلى الحالة (q _{i ) التي توجد} فيها الآلة حاليًا والرمز (a _{j ) الذي تقرأه على الشريط (الرمز} الموجود حاليًا أسفل الرأس)، تخبر الآلة بالقيام بما يلي بالتسلسل (بالنسبة لنماذج 5- tuple ):

1. إما امسح أو اكتب رمزًا (استبدال _j بـ _j1 ).
2. حرك الرأس (الذي يتم وصفه بواسطة d _k ويمكن أن تكون له القيم التالية: 'L' لخطوة واحدة إلى اليسار أو 'R' لخطوة واحدة إلى اليمين أو 'N' للبقاء في نفس المكان).
3. افترض نفس الحالة أو حالة جديدة كما هو محدد (انتقل إلى الحالة q _i1 ).

في نماذج الرباعيات، تُحدد عملية مسح أو كتابة رمز (a _j1 ) وتحريك رأس القراءة/الكتابة يمينًا أو يسارًا (d _{k ) كتعليمات منفصلة. يُخبر الجدول الآلة بما يلي: (أ) مسح أو كتابة رمز} ، أو (ب) تحريك رأس القراءة/الكتابة يمينًا أو يسارًا، ثم (ب) اتخاذ الحالة نفسها أو حالة جديدة كما هو مُحدد، ولكن لا يُمكن تنفيذ كلا الإجراءين (أ) و(ب) في نفس التعليمة. في بعض النماذج، إذا لم يكن هناك مدخل في الجدول للتركيبة الحالية من الرمز والحالة، فإن الآلة ستتوقف؛ بينما تتطلب نماذج أخرى ملء جميع المدخلات.

كل جزء من أجزاء الآلة (أي حالتها ، ومجموعات الرموز، والشريط المستخدم في أي وقت معين) وإجراءاتها (مثل الطباعة والمسح وتحريك الشريط) محدودة ومنفصلة وقابلة للتمييز ؛ إن الكمية غير المحدودة من الشريط ووقت التشغيل هي التي تمنحها مساحة تخزين غير محدودة .

استنادًا إلى هوبكروفت وأولمان (1979)، ^{[ 21 ]} يمكن تعريف آلة تورينج (ذات الشريط الواحد) رسميًا على أنها مجموعة سباعية${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$أين

• ${\displaystyle Q}$هي مجموعة محدودة وغير فارغة من الحالات ؛
• ${\displaystyle \Gamma }$هي مجموعة محدودة وغير فارغة من رموز الأبجدية الشريطية ؛
• ${\displaystyle b\in \Gamma }$هو الرمز الفارغ (الرمز الوحيد المسموح بظهوره على الشريط بشكل لا نهائي في أي خطوة أثناء الحساب)؛
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$هي مجموعة رموز الإدخال ، أي مجموعة الرموز المسموح بظهورها في محتويات الشريط الأولية؛
• ${\displaystyle \delta$ الدالة الجزئية :(Q\setminus F)\times \Gamma \rightharpoonup Q\times \Gamma \times \{L,R\}} تسمى دالة الانتقال، حيث L هي الإزاحة إلى اليسار، وR هي الإزاحة إلى اليمين.${\displaystyle \delta }$إذا لم يتم تعريفها على الحالة الحالية ورمز الشريط الحالي، فإن الآلة تتوقف؛ ^{[ 22 ]} بشكل بديهي، تحدد دالة الانتقال الحالة التالية التي تم الانتقال إليها من الحالة الحالية، والرمز الذي سيتم استبداله بالرمز الحالي الذي يشير إليه الرأس، وحركة الرأس التالية.
• ${\displaystyle q_{0}\in Q}$هي الحالة الابتدائية ؛
• ${\displaystyle F\subseteq Q}$هي مجموعة الحالات النهائية أو حالات القبول . ويُقال إن محتويات الشريط الأولية قد تم قبولها بواسطة${\displaystyle M}$إذا توقف في نهاية المطاف في حالة من${\displaystyle F}$.

يسمح أحد المتغيرات بـ "عدم الإزاحة"، ولنقل N، كعنصر ثالث في مجموعة الاتجاهات${\displaystyle \{L,R\}}$.

تبدو المجموعة المكونة من 7 عناصر لآلة القندس المشغولة ذات الحالات الثلاث كما يلي (انظر المزيد حول آلة القندس المشغولة هذه في أمثلة آلة تورينج ):

• ${\displaystyle Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}}$(الولايات)؛
• ${\displaystyle \Gamma =\{0,1\}}$(رموز الأبجدية على الشريط)؛
• ${\displaystyle b=0}$(رمز فارغ)؛
• ${\displaystyle \Sigma =\{1\}}$(رموز الإدخال)؛
• ${\displaystyle \delta =}$انظر إلى جدول الحالة أدناه (دالة الانتقال).
• ${\displaystyle q_{0}={\mbox{A}}}$(الحالة الأولية)؛
• ${\displaystyle F=\{{\mbox{HALT}}\}}$(الحالات النهائية)؛

في البداية، يتم تمييز جميع خلايا الشريط بـ${\displaystyle 0}$.

على حد تعبير فان إمدي بواس (1990): "إن الكائن النظري للمجموعات [وصفه الرسمي المكون من سبعة عناصر مشابه لما سبق] لا يوفر سوى معلومات جزئية حول كيفية تصرف الآلة وكيف ستبدو حساباتها." ^{[ 23 ]}

على سبيل المثال،

• سيكون هناك حاجة إلى اتخاذ العديد من القرارات بشأن الشكل الفعلي للرموز، وطريقة مضمونة لقراءة وكتابة الرموز إلى أجل غير مسمى.
• قد تؤدي عمليات الإزاحة لليسار والإزاحة لليمين إلى تحريك رأس الشريط عبر الشريط، ولكن عند بناء آلة تورينج فعليًا، يكون من العملي أكثر جعل الشريط ينزلق ذهابًا وإيابًا أسفل الرأس بدلاً من ذلك.
• يمكن أن يكون الشريط محدودًا، ويُمدد تلقائيًا بفراغات حسب الحاجة (وهو الأقرب إلى التعريف الرياضي)، ولكن من الشائع تصوره على أنه يمتد بلا حدود من أحد طرفيه أو كليهما، ومملوء مسبقًا بفراغات باستثناء الجزء المحدود المحدد الذي يوجد عليه رأس القراءة/الكتابة (وهذا، بالطبع، غير قابل للتطبيق عمليًا). لا يمكن أن يكون طول الشريط ثابتًا، لأن ذلك لا يتوافق مع التعريف المذكور، وسيحد بشكل كبير من نطاق العمليات الحسابية التي يمكن للجهاز إجراؤها، بحيث يقتصر على عمليات آلة خطية محدودة إذا كان طول الشريط متناسبًا مع حجم المدخلات، أو على آلة ذات حالات محدودة إذا كان طوله ثابتًا تمامًا.

مخططات "الحالة"

جدول القندس المشغول ذي الحالات الثلاث ("P" = طباعة/كتابة "1")

رموز الشريط	الحالة الحالية أ			الحالة الحالية ب			الحالة الحالية ج
	كتابة الرموز	نقل الشريط	الولاية التالية	كتابة الرموز	نقل الشريط	الولاية التالية	كتابة الرموز	نقل الشريط	الولاية التالية
0	P	R	ب	P	ل	أ	P	ل	ب
1	P	ل	ج	P	R	ب	P	R	وقف

إلى اليمين: الجدول أعلاه كما هو موضح في مخطط "انتقال الحالة".

عادةً ما يُفضّل ترك الجداول الكبيرة على حالها (بوث، ص  74). إذ يسهل محاكاتها بواسطة الحاسوب في شكل جدولي (بوث، ص  74). مع ذلك، يمكن فهم بعض المفاهيم - مثل الآلات ذات حالات "إعادة الضبط" والآلات ذات الأنماط المتكررة (انظر هيل وبيترسون، ص  244 وما بعدها) - بشكل أوضح عند عرضها كرسم.

يجب على القارئ أن يقرر ما إذا كان الرسم يمثل تحسينًا على الجدول الخاص به، وذلك وفقًا للسياق المحدد.

ينبغي تنبيه القارئ مجدداً إلى أن هذه المخططات تمثل لقطة ثابتة لجدولها الزمني، وليست مسار عملية حسابية عبر الزمان والمكان. فبينما تتبع آلة "بيفر" المشغولة نفس مسار الحالة في كل مرة تُشغَّل فيها، لا ينطبق هذا على آلة "النسخ" التي يمكن تزويدها بمعاملات إدخال متغيرة.

يُظهر مخطط "تقدم الحساب" تقدم "حالة" (تعليمات) جهاز "بيفر المشغول" ثلاثي الحالات خلال عملية الحساب من البداية إلى النهاية. في أقصى اليمين، يظهر "التكوين الكامل" لتورينغ (وضع كلين ، ووصف هوبكروفت-أولمان اللحظي) في كل خطوة. إذا تم إيقاف الجهاز ومسحه بالكامل، بحيث يُفرغ كل من "سجل الحالة" والشريط بأكمله، يُمكن استخدام هذه "التكوينات" لإعادة تشغيل الحساب في أي مرحلة من مراحل تقدمه. ^{[ 38 ]}

يمكن إثبات أن العديد من الآلات التي قد يُظن أنها تمتلك قدرة حسابية أكبر من آلة تورينغ العالمية البسيطة لا تمتلك قدرة أكبر (هوبكروفت وأولمان، ص  159، انظر مينسكي (1967)). قد تكون أسرع في الحساب، أو تستخدم ذاكرة أقل، أو قد تكون مجموعة تعليماتها أصغر، لكنها لا تستطيع إجراء حسابات أكثر قوة (أي المزيد من الدوال الرياضية). ( تفترض نظرية تشيرش-تورينج أن هذا ينطبق على أي نوع من الآلات: أي شيء يمكن "حسابه" يمكن حسابه بواسطة آلة تورينغ).

تُعادل آلة تورينج آلة دفع ذات مكدس واحد (PDA) تم تحسين مرونتها واختصارها بتخفيف شرط " آخر ما يدخل أول ما يخرج" (LIFO) لمكدسها. إضافةً إلى ذلك، تُعادل آلة تورينج أيضًا آلة دفع ذات مكدسين (PDA) ذات دلالات LIFO القياسية، وذلك باستخدام مكدس واحد لنمذجة الشريط الموجود على يسار رأس القراءة/الكتابة، والمكدس الآخر للشريط الموجود على يمينه.

وعلى النقيض من ذلك، تبين أن بعض النماذج البسيطة للغاية مكافئة لآلة تورينج ، أي أنها تمتلك نفس القدرة الحسابية لنموذج آلة تورينج.

النماذج المكافئة الشائعة هي آلة تورينج متعددة الأشرطة ، وآلة تورينج متعددة المسارات ، والآلات ذات المدخلات والمخرجات، وآلة تورينج غير الحتمية (NDTM) على عكس آلة تورينج الحتمية (DTM) التي يحتوي جدول الإجراءات الخاص بها على مدخل واحد على الأكثر لكل مجموعة من الرمز والحالة.

آلات تورينج للقراءة فقط، والتي تتحرك لليمين، تعادل آلات DFA (وكذلك آلات NFA عن طريق التحويل باستخدام خوارزمية التحويل من NFA إلى DFA ).

لأغراض عملية وتعليمية، يمكن استخدام آلة التسجيل المكافئة كلغة برمجة تجميع عادية .

يبرز تساؤل هام حول ما إذا كان نموذج الحوسبة الذي تمثله لغات البرمجة الملموسة مكافئًا لآلة تورينج أم لا. فبينما تعتمد الحوسبة في الحاسوب الحقيقي على حالات محدودة، وبالتالي لا يمكنها محاكاة آلة تورينج، فإن لغات البرمجة نفسها لا تعاني بالضرورة من هذا القيد. وقد أظهر كيرنر وآخرون (2009) أن بعض لغات البرمجة العامة مكافئة لآلة تورينج، بينما البعض الآخر ليس كذلك. فعلى سبيل المثال، لغة ANSI C ليست مكافئة لآلة تورينج، إذ أن جميع تطبيقاتها (مع إمكانية وجود تطبيقات مختلفة لأن المعيار يترك بعض السلوكيات غير محددة عمدًا لأسباب تتعلق بالتوافق مع الأنظمة القديمة) تفترض ذاكرة ذات مساحة محدودة. ويعود ذلك إلى إمكانية الوصول إلى حجم أنواع بيانات مرجع الذاكرة، والتي تُسمى المؤشرات ، داخل اللغة. في المقابل، لا تمتلك لغات برمجة أخرى، مثل باسكال، هذه الميزة، مما يسمح لها بأن تكون مكافئة لآلة تورينج من حيث المبدأ. إنها كاملة تورينج من حيث المبدأ، حيث يُسمح بفشل تخصيص الذاكرة في لغة البرمجة، مما يعني أن لغة البرمجة يمكن أن تكون كاملة تورينج عند تجاهل عمليات تخصيص الذاكرة الفاشلة، ولكن البرامج المترجمة القابلة للتنفيذ على جهاز كمبيوتر حقيقي لا يمكنها ذلك.

في وقت مبكر من ورقته البحثية (1936)، يميز تورينج بين "الآلة الأوتوماتيكية" - "حركتها ... محددة تمامًا بواسطة التكوين" و "آلة الاختيار":

...  التي لا يتحدد شكل حركتها إلا جزئيًا بالتكوين ... عندما تصل هذه الآلة إلى أحد هذه التكوينات الغامضة، لا يمكنها الاستمرار حتى يتخذ مشغل خارجي قرارًا عشوائيًا. هذا ما سيحدث لو كنا نستخدم الآلات للتعامل مع الأنظمة البديهية.

لم يُسهب تورينج (1936) في شرح ذلك إلا في حاشيةٍ وصف فيها كيفية استخدام آلةٍ آليةٍ "لإيجاد جميع الصيغ القابلة للإثبات في حساب هيلبرت" بدلاً من استخدام آلة اختيار. وافترض أن "الاختيارات محصورةٌ دائمًا بين احتمالين: 0 و1. وبالتالي، يُحدَّد كل برهانٍ بتسلسلٍ من الاختيارات i1، i2، ...، in (حيث i1 = 0 أو 1، i2 = 0 أو 1، ...، in = 0 أو 1)، ومن ثم فإن العدد _2n + _i1 / _2n - ₁ + _i2 / _2n - ² + _... ⁺ in _{يُحدِّد} البرهانَ تمامًا ^. وتقوم _الآلة الآلية بتنفيذ البرهان 1، ثم البرهان 2، ثم البرهان 3، وهكذا بالتتابع." ^{[ 39 ]}

هذه هي بالفعل التقنية التي يمكن من خلالها استخدام آلة تورينج الحتمية (أي a-) لمحاكاة عمل آلة تورينج غير الحتمية ؛ وقد حل تورينج المسألة في حاشية ويبدو أنه يستبعدها من المزيد من الاعتبار.

آلة أوراكل أو آلة o هي آلة تورينج a التي توقف حسابها عند الحالة " o " بينما، لإكمال حسابها، "تنتظر قرار" "الأوراكل" - وهو كيان لم يحدده تورينج "باستثناء قوله إنه لا يمكن أن يكون آلة" (تورينج (1939)). ^{[ 40 ]}

كما كتب تورينج في كتابه "غير القابل للتقرير" (تمت إضافة الخط المائل): ^{[ 41 ]}

من الممكن ابتكار آلة واحدة قادرة على حساب أي متتالية قابلة للحساب. إذا زُوِّدت هذه الآلة (U) بشريط كُتب في بدايته سلسلة من الخماسيات مفصولة بفواصل منقوطة، مُسجَّلة بواسطة آلة حاسوبية (M) ، فإن (U) ستحسب نفس المتتالية التي تحسبها (M) .

^{يعتبر البعض [ 42 ]} أن نموذج الحوسبة الذي أطلق عليه تورينج اسم "الآلة العالمية" - " U " اختصارًا - كان بمثابة الاختراق النظري الأساسي الذي أدى إلى مفهوم الكمبيوتر ذي البرنامج المخزن .

تحتوي ورقة تورينج ... في جوهرها على اختراع الحاسوب الحديث وبعض تقنيات البرمجة التي رافقته.

من حيث التعقيد الحسابي ، لا يلزم أن تكون آلة تورينغ العالمية متعددة الأشرطة أبطأ إلا بمعامل لوغاريتمي مقارنةً بالآلات التي تحاكيها. وقد توصل إلى هذه النتيجة في عام 1966 كل من إف سي هيني وآر إي ستيرنز . ^{[ 44 ] [ 45 ]}

تتفوق آلات تورينج على بعض أنواع الآلات الأخرى، مثل آلات الحالة المحدودة وآلات الدفع لأسفل . ووفقًا لنظرية تشيرش-تورينج ، فإنها تضاهي الآلات الحقيقية في قوتها، وقادرة على تنفيذ أي عملية يمكن لبرنامج حقيقي تنفيذها. إلا أن ما يُغفل في هذا القول هو أن الآلة الحقيقية، نظرًا لأن عدد تكويناتها محدود ، فهي في جوهرها آلة حالة محدودة، بينما تتمتع آلة تورينج بمساحة تخزين غير محدودة لإجراء حساباتها.

هناك عدد من الطرق لشرح سبب كون آلات تورينج نماذج مفيدة لأجهزة الكمبيوتر الحقيقية:

• أي شيء يمكن لجهاز حاسوب حقيقي حسابه، يمكن لآلة تورينج حسابه أيضًا. على سبيل المثال: "يمكن لآلة تورينج محاكاة أي نوع من الإجراءات الفرعية الموجودة في لغات البرمجة، بما في ذلك الإجراءات التكرارية وأي من آليات تمرير المعاملات المعروفة" (هوبكروفت وأولمان، ص  157). كما يمكن لآلة الحالة المحدودة الكبيرة بما يكفي نمذجة أي جهاز حاسوب حقيقي، بغض النظر عن عمليات الإدخال والإخراج. وبالتالي، فإن أي بيان يتعلق بقيود آلات تورينج ينطبق أيضًا على أجهزة الحاسوب الحقيقية.
• يكمن الاختلاف فقط في قدرة آلة تورينج على معالجة كمية غير محدودة من البيانات. مع ذلك، في ظل وقت محدود، لا تستطيع آلة تورينج (مثل أي آلة حقيقية) معالجة سوى كمية محدودة من البيانات.
• مثل آلة تورينج، يمكن توسيع مساحة التخزين في الآلة الحقيقية حسب الحاجة، عن طريق الحصول على المزيد من الأقراص أو وسائط التخزين الأخرى.
• غالبًا ما تكون أوصاف برامج الآلات الحقيقية باستخدام نماذج مجردة أبسط أكثر تعقيدًا بكثير من الأوصاف التي تستخدم آلات تورينج. على سبيل المثال، قد تحتوي آلة تورينج التي تصف خوارزمية ما على بضع مئات من الحالات، بينما تحتوي الآلة المحدودة الحتمية المكافئة (DFA) على آلة حقيقية معينة على تريليونات الحالات. وهذا يجعل تحليل تمثيل DFA غير عملي.
• تصف آلات تورينج الخوارزميات بغض النظر عن حجم الذاكرة التي تستخدمها. صحيح أن هناك حدًا أقصى للذاكرة التي تمتلكها أي آلة حالية، إلا أن هذا الحد قد يرتفع بشكل غير محدود مع مرور الوقت. تتيح لنا آلات تورينج إمكانية إصدار أحكام حول الخوارزميات التي ستظل (نظريًا) صالحة إلى الأبد، بغض النظر عن التطورات في بنية أجهزة الحوسبة التقليدية .
• يمكن أن تحتوي الخوارزميات التي تعمل على آلات مجردة مكافئة لتورينغ على أنواع بيانات ذات دقة تعسفية متاحة ولا يتعين عليها أبدًا التعامل مع الظروف غير المتوقعة (بما في ذلك، على سبيل المثال لا الحصر، نفاد الذاكرة ).

يختلف النموذج الحسابي للحساب عن نموذج تورينج في جانبين: ^{[ 46 ]}

• في النموذج الحسابي، يتطلب كل عدد حقيقي خلية ذاكرة واحدة، بينما في نموذج تورينج يعتمد حجم تخزين العدد الحقيقي على عدد البتات المطلوبة لتمثيله.
• في النموذج الحسابي، يمكن إجراء كل عملية حسابية أساسية على الأعداد الحقيقية (الجمع والطرح والضرب والقسمة) في خطوة واحدة، بينما في نموذج تورينج يعتمد وقت تشغيل كل عملية حسابية على طول المعاملات.

بعض الخوارزميات تعمل في وقت متعدد الحدود في نموذج واحد ولكن ليس في النموذج الآخر. على سبيل المثال:

• تعمل خوارزمية إقليدس في وقت متعدد الحدود في نموذج تورينج، ولكن ليس في النموذج الحسابي.
• الخوارزمية التي تقرأ n من الأرقام ثم تحسب${\displaystyle 2^{2^{n}}}$يتم تنفيذ عمليات التربيع المتكررة في وقت متعدد الحدود في النموذج الحسابي، ولكن ليس في نموذج تورينج. ويعود ذلك إلى أن عدد البتات اللازمة لتمثيل النتيجة يتناسب أُسّيًا مع حجم المدخلات.

مع ذلك، إذا كان أداء خوارزمية ما يتم في زمن متعدد الحدود في النموذج الحسابي، وكان طول جميع الأعداد الثنائية المستخدمة متعدد الحدود بالنسبة لطول المدخلات، فإنها تعمل دائمًا في زمن متعدد الحدود في نموذج تورينج. ويُقال إن هذه الخوارزمية تعمل في زمن متعدد الحدود قوي .