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

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

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

مشاكل

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

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

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

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

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

النماذج الرسمية للحوسبة

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

حساب التفاضل والتكامل لامدا: تتكون العملية الحسابية من تعبير لامدا أولي (أو اثنين إذا كنت تريد فصل الدالة ومدخلاتها) بالإضافة إلى سلسلة محدودة من حدود لامدا، يتم استنتاج كل منها من الحد السابق من خلال تطبيق واحد لاختزال بيتا .
المنطق التوافقي: مفهوم له أوجه تشابه كثيرة مع $\lambda$ - حساب التفاضل والتكامل، ولكن توجد أيضًا اختلافات مهمة (على سبيل المثال، مُركِّب النقطة الثابتة Y له شكل طبيعي في المنطق التوافقي ولكن ليس في $\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′′ إلى الاحتفاظ بحالة مميزة، لأن جميع الوظائف "الشبه ذاكرية" يمكن توفيرها فقط من خلال الشريط. فبدلاً من إعادة كتابة الرمز الحالي، يمكنها إجراء عملية زيادة حسابية نمطية عليه. كما تحتوي P′′ على زوج من التعليمات لدورة تفحص الرمز الفارغ. وعلى الرغم من طبيعتها البسيطة، فقد أصبحت اللغة الرسمية الأم للغة برمجة مُطبقة ومستخدمة (لأغراض الترفيه) تُسمى Brainfuck .

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

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

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

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

قوة الأوتوماتا

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

قوة الآلات ذات الحالة المحدودة

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

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

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

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

قوة الأتمتة المدفوعة

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

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

قوة آلات تورينج

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

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

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

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

مشكلة التوقف

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

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

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

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

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

ما وراء اللغات القابلة للتعداد بشكل متكرر

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

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

النماذج القائمة على التزامن

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

نماذج حسابية أكثر قوة

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

تنفيذ لا نهائي

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

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.الفصل 3: قابلية الحوسبة، الصفحات 57-70.
إس. باري كوبر (2004). نظرية الحوسبة ( الطبعة الأولى). تشابمان آند هول/سي آر سي. رقم ISBN 978-1-58488-237-4.

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗