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