كمال تورنغ

نظرية الأتومات

• الرسمية القواعد الصورية (مولدات اللغة)
• اللغة الصورية (التعرف على اللغة)
• حسابات اللامدا

كمال تورنغ

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

نظرية الحاسوبية

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

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

تكافؤ تورنغ

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

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

العمومية (الحسابية)

إيحاءات تورنغ

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

أمثلة

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

معظم اللغات التي تستخدم نماذج أقل شيوعا

نظم إعادة الكتابة كذلك كاملة حسب تورنغ-.

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

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

• وظيفية لغات مثل Lisp وهاسكل.
• لغات  البرمجة المنطقية مثل Prolog.
• لغات التعريفية  مثل XSLT.

بوكيمون الأصفر

ألعاب الورق:

التاريخ

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

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

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

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

لغات البيانات

كذلك، مفهوم كمال تورنغ لا ينطبق على لغات مثل XML، HTML، JSON, YAML وتعبيرات-S لأنها تستعمل عادة لتمثيل البيانات المهيكلة، وليس لتصف المحاسبات.  يشار إليها في بعض الأحيان لغات الترميز أو أكثر بشكل دقة «لغات الاحتواء» أو «لغات وصف البيانات». غير أن القاعدة 110، الاتومات الخلوي الكمال حسب تورنغ، قد طبقت بنجاح في CSS ، مما يثبت (إلى حد ما) كمالها حسب تورنغ  (في الواقع لا يتفق الجميع، مثل فرانسيس مكابي  على أن CSS  كاملة حسب تورنغ لأنه لا يوجد خيار لبناء التوابع في CSS).

• ملاحظات
• المراجع
• وصلات خارجية

الفيزياء الرقمية

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

آلات ما بعد تورنغ

• أغلب لغات البرمجةالتقليدية وغير التقليدية، هي كاملة حسب تورنغ. وهذا يشمل:
• جميع اللغات ذات الأغراض العامة التي تستعمل على نطاق واسع.
• لغات البرمجة الإجرائية  مثل C، Pascal.
• لغات البرمجة كائنية التوجه  مثل CIL، جافا، وSmalltalk.
• اللغات متعددة نموذج  مثل آدا، C++, Common Lisp, اوبجكت باسكال.

لغات غير كاملة حسب تورنغ

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

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

السحر: الجمع

ألعاب صفر-أشخاص (المحاكاة):

لعبة كونواي الحياة

الاستخدام غير الرياضي

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

من جانب آخر، في العامية استخدام مصطلحي «كامل حسب تورنغ» أو «تكافؤ تورنغ» كان يعني أن أي العالم الحقيقي العامة الغرض الكمبيوتر أو الكمبيوتر لغة يمكن أن ما يقرب من محاكاة الجوانب الحسابية من أي دولة أخرى في العالم الحقيقي الكمبيوتر للأغراض العامة أو لغة الكمبيوتر.

الألعاب

• الكثير من الألعاب كاملة حسب تورنغ- عن طريق الصدفة.
• ألعاب الفيديو:
• جديلة
• قزم القلعة
• ماين كرافت
• كاسحة ألغام
• ليتل بيغ بلانت
• Factorio

تعاريف رسمية

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