قابلية الحساب

القدرة على الحساب هي القدرة على حل مشكلة بطريقة فعالة. وهو موضوع رئيسي في مجال نظرية الحساب ضمن المنطق الرياضي ونظرية الحساب ضمن علوم الكمبيوتر . ترتبط قابلية حساب المشكلة ارتباطًا وثيقًا بوجود خوارزمية لحل المشكلة.

النماذج الأكثر دراسة على نطاق واسع للقابلية للحوسبة هي الدوال القابلة للحساب وفقًا لطريقة تورينج والدوال المتكررة وفقًا لطريقة μ ، وحساب لامدا ، وكلها لها قوة حسابية مكافئة. كما تتم دراسة أشكال أخرى من القابلية للحوسبة: تتم دراسة مفاهيم القابلية للحوسبة الأضعف من آلات تورينج في نظرية الأتمتة ، بينما تتم دراسة مفاهيم القابلية للحوسبة الأقوى من آلات تورينج في مجال الحوسبة الفائقة .

الفكرة المركزية في قابلية الحساب هي فكرة المشكلة ( الحسابية ) ، وهي مهمة يمكن استكشاف قابليتها للحساب.

هناك نوعان رئيسيان من المشاكل:

• تحدد مشكلة القرار مجموعة S ، والتي قد تكون مجموعة من السلاسل أو الأعداد الطبيعية أو أشياء أخرى مأخوذة من مجموعة أكبر U. ومن الأمثلة الخاصة للمشكلة تحديد ما إذا كانت u موجودة في S ، وذلك بالنظر إلى عنصر u من U. على سبيل المثال، دع U تكون مجموعة الأعداد الطبيعية و S مجموعة الأعداد الأولية. تتوافق مشكلة القرار المقابلة مع اختبار الأعداد الأولية .
• تتكون مشكلة الدالة من دالة f من مجموعة U إلى مجموعة V. ومن أمثلة هذه المشكلة حساب العنصر المقابل f ( u ) في V ، مع العلم أن العنصر u في U. على سبيل المثال، قد تكون U و V مجموعة من جميع السلاسل الثنائية المحدودة، وقد تأخذ f سلسلة وتعيد السلسلة التي تم الحصول عليها عن طريق عكس أرقام المدخلات (لذا فإن f(0101) = 1010).

وتشمل الأنواع الأخرى من المشاكل مشاكل البحث ومشاكل التحسين .

أحد أهداف نظرية الحساب هو تحديد المشاكل، أو فئات المشاكل، التي يمكن حلها في كل نموذج من نماذج الحساب.

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

حساب لامدا

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

المنطق التركيبي

مفهوم له العديد من أوجه التشابه مع حساب التفاضل والتكامل، ولكن هناك أيضًا اختلافات مهمة (على سبيل المثال، فإن مركب النقطة الثابتة Y له شكل طبيعي في المنطق التوافقي ولكن ليس في حساب التفاضل والتكامل). تم تطوير المنطق التوافقي بطموحات كبيرة: فهم طبيعة المفارقات، وجعل أسس الرياضيات أكثر اقتصادية (مفاهيميًا)، والقضاء على مفهوم المتغيرات (وبالتالي توضيح دورها في الرياضيات).${\displaystyle \lambda }$${\displaystyle \lambda }$

وظائف μ-التكرارية

تتكون العملية الحسابية من دالة متكررة μ، أي تسلسلها المحدد، وأي قيمة (قيم) إدخال وتسلسل من الدوال المتكررة التي تظهر في التسلسل المحدد مع المدخلات والمخرجات. وبالتالي، إذا ظهرت الدالتان g ( x ) و h ( x ، y ) في التسلسل المحدد للدالة المتكررة f ( x ) ، فقد تظهر حدود من النموذج g (5) = 7 أو h (3,2) = 10. يجب أن يكون كل مدخل في هذا التسلسل تطبيقًا لدالة أساسية أو يتبع المدخلات أعلاه باستخدام التركيب أو التكرار البدائي أو التكرار μ . على سبيل المثال، إذا كانت f ( x ) = h ( x ، g ( x )) ، فلكي تظهر f (5) = 3 ، يجب أن تظهر حدود مثل g (5) = 6 و h (5,6) = 3 أعلاه. تنتهي العملية الحسابية فقط إذا أعطى المصطلح الأخير قيمة الدالة المتكررة المطبقة على المدخلات.

أنظمة إعادة كتابة السلسلة

تتضمن خوارزميات ماركوف ، التي تستخدم قواعد نحوية للعمل على سلاسل الرموز؛ كما تتضمن أيضًا نظام ما بعد الكنسي .

ماكينة تسجيل

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

آلة تورينج

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

آلة تورينج متعددة الأشرطة

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

ب′′

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

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

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

وتشمل النماذج المقيدة الأخرى للحساب ما يلي:

الأتمتة المحدودة الحتمية (DFA)

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

الأتمتة المحدودة غير الحتمية (NFA)

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

آلة الدفع للأسفل

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

وباستخدام هذه النماذج الحسابية، يمكننا تحديد حدودها. أي ما هي فئات اللغات التي يمكنها قبولها؟

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

من الأمثلة على هذه اللغة مجموعة كل السلاسل المكونة من الحرفين "a" و"b" والتي تحتوي على عدد متساوٍ من الحرفين "a" و"b". لمعرفة سبب عدم تمكن آلة الحالة المحدودة من التعرف على هذه اللغة بشكل صحيح، افترض أولاً وجود مثل هذه الآلة M. يجب أن تحتوي M على عدد من الحالات n . الآن، ضع في اعتبارك السلسلة x المكونة من الحرفين "a" متبوعًا بـ "b". ${\displaystyle (n+1)}$${\displaystyle (n+1)}$

عندما يقرأ M في x ، يجب أن تكون هناك حالة ما في الآلة تتكرر أثناء قراءتها في السلسلة الأولى من 'a's، نظرًا لوجود 'a's و n حالة فقط وفقًا لمبدأ Pigeonhole . نسمي هذه الحالة S ، ودع d يكون عدد 'a's التي تقرأها آلتنا من أجل الانتقال من أول ظهور لـ S إلى بعض الظهورات اللاحقة أثناء تسلسل 'a'. نعلم، إذن، أنه في هذا الظهور الثاني لـ S ، يمكننا إضافة d إضافي (حيث ) 'a's وسنكون مرة أخرى في الحالة S. هذا يعني أننا نعلم أن سلسلة 'a's يجب أن تنتهي في نفس حالة سلسلة 'a's. هذا يعني أنه إذا قبلت آلتنا x ، فيجب أن تقبل أيضًا سلسلة 'a's تليها 'b's، وهو أمر ليس في لغة السلاسل التي تحتوي على عدد متساوٍ من 'a's و'b's. بعبارة أخرى، لا يستطيع M التمييز بشكل صحيح بين سلسلة من عدد متساوٍ من "a" و "b" وسلسلة تحتوي على "a" و "b". ${\displaystyle (n+1)}$${\displaystyle d>0}$${\displaystyle (n+d+1)}$${\displaystyle (n+1)}$${\displaystyle (n+d+1)}$${\displaystyle (n+1)}$${\displaystyle (n+d+1)}$${\displaystyle n+1}$

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

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

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

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

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

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

السؤال الذي يجب طرحه هو: هل توجد لغات يمكن إحصاؤها بشكل متكرر، ولكنها ليست كذلك؟ وعلاوة على ذلك، هل توجد لغات لا يمكن إحصاؤها بشكل متكرر؟

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

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

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

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

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

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

إن أحد الأمثلة البسيطة على مثل هذه اللغة هو مكمل لغة التوقف؛ أي اللغة التي تتكون من جميع آلات تورينج المقترنة بسلاسل الإدخال حيث لا تتوقف آلات تورينج عند مدخلاتها. لنرى أن هذه اللغة ليست قابلة للعد بشكل متكرر، تخيل أننا نبني آلة تورينج M قادرة على إعطاء إجابة محددة لجميع آلات تورينج هذه، ولكنها قد تعمل إلى الأبد على أي آلة تورينج تتوقف في النهاية. يمكننا بعد ذلك بناء آلة تورينج أخرى تحاكي تشغيل هذه الآلة، جنبًا إلى جنب مع محاكاة مباشرة لتنفيذ الآلة الواردة في الإدخال أيضًا، عن طريق التداخل بين تنفيذ البرنامجين. نظرًا لأن المحاكاة المباشرة ستتوقف في النهاية إذا توقف البرنامج الذي تحاكيه، وبما أنه بناءً على افتراض أن محاكاة M ستتوقف في النهاية إذا لم يتوقف برنامج الإدخال أبدًا، فإننا نعلم أن ستتوقف في النهاية إحدى نسخها الموازية. وبالتالي فهي حاسمة لمشكلة التوقف. لقد أظهرنا سابقًا، مع ذلك، أن مشكلة التوقف غير قابلة للحسم. لدينا تناقض، وبذلك نكون قد أثبتنا أن افتراضنا بوجود M غير صحيح. وبالتالي فإن مكمل اللغة المتوقفة غير قابل للعد بشكل متكرر. ${\displaystyle M'}$${\displaystyle M'}$${\displaystyle M'}$

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

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

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

${\displaystyle 1=\sum _{n=1}^{\infty }{\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+{\frac {1}{16}}+\cdots }$

وحدة زمنية (ووحدة طاقة واحدة...) للتشغيل. تتقارب هذه السلسلة اللانهائية إلى 1، مما يعني أن آلة زينو هذه يمكنها تنفيذ عدد لا نهائي قابل للعد من الخطوات في وحدة زمنية واحدة (باستخدام وحدة طاقة واحدة...). هذه الآلة قادرة على حل مشكلة التوقف عن طريق محاكاة تنفيذ الآلة المعنية بشكل مباشر. بالتوسع، ستعمل أي سلسلة لا نهائية متقاربة [يجب أن تكون لا نهائية يمكن إثباتها]. وبافتراض أن السلسلة اللانهائية تتقارب إلى قيمة n ، فإن آلة زينو ستكمل تنفيذًا لا نهائيًا قابلًا للعد في n وحدة زمنية.

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

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

• نظرية الأتمتة
• آلة مجردة
• قائمة المشاكل غير القابلة للحل
• نظرية التعقيد الحسابي
• منطق قابلية الحساب

• مايكل سيبسر (1997). مقدمة إلى نظرية الحوسبة . دار نشر PWS. رقم ISBN 0-534-94728-X.الجزء الثاني: نظرية الحسابية، الفصول 3-6، ص 123-222.
• كريستوس باباديميتريو (1993). التعقيد الحسابي (الطبعة الأولى). أديسون ويسلي. رقم ISBN 0-201-53082-1.الفصل الثالث: قابلية الحساب، ص 57-70.
• S. Barry Cooper (2004). نظرية قابلية الحساب (الطبعة الأولى). Chapman & Hall/CRC. ISBN 978-1-58488-237-4.