اكتمال تورينج

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

مفهوم ذو صلة هو مفهوم تكافؤ تورينج - يُقال إن جهازين حاسوبيين P و Q متكافئان إذا كان بإمكان P محاكاة Q و Q محاكاة P. ^{[ 4 ]} تفترض فرضية تشيرش -تورينج أن أي دالة يمكن حساب قيمها بواسطة خوارزمية يمكن حسابها بواسطة آلة تورينج، وبالتالي إذا كان بإمكان أي جهاز حاسوبي في العالم الحقيقي محاكاة آلة تورينج، فهو مكافئ تورينج لآلة تورينج. يمكن استخدام آلة تورينج شاملة لمحاكاة أي آلة تورينج، وبالتالي الجوانب الحسابية البحتة لأي جهاز حاسوبي ممكن في العالم الحقيقي. ^{[ 5 ] [ 6 ]} 

لإثبات أن شيئًا ما كامل تورينج، يكفي إثبات إمكانية استخدامه لمحاكاة نظام كامل تورينج. لا يمكن لأي نظام فيزيائي أن يمتلك ذاكرة غير محدودة، ولكن إذا تم تجاهل قيد الذاكرة المحدودة، فإن معظم لغات البرمجة تكون كاملة تورينج فيما عدا ذلك. ^{[ 7 ] [ 8 ]}

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

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

في نظرية الحوسبة ، تُستخدم عدة مصطلحات وثيقة الصلة لوصف القدرة الحسابية لنظام حاسوبي (مثل آلة مجردة أو لغة برمجة ):

اكتمال تورينج

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

تكافؤ تورينج

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

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

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

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

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

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

سرعان ما تم تحديد المفهوم الفعلي للحساب، بدءًا من نظرية عدم الاكتمال لغودل . أوضحت هذه النظرية أن أنظمة البديهيات محدودة عند التفكير في الحساب الذي يستنتج نظرياتها. أثبت كل من تشرش وتورينج، بشكل مستقل، أن مسألة هيلبرت (مسألة القرار) غير قابلة للحل، ^{[ 9 ]} وبذلك حددا جوهر الحساب في نظرية عدم الاكتمال. أثبت هذا العمل، إلى جانب عمل غودل على الدوال التكرارية العامة ، وجود مجموعات من التعليمات البسيطة، التي يمكنها، عند تجميعها، إنتاج أي عملية حسابية. أظهر عمل غودل أن مفهوم الحساب فريد من نوعه في جوهره.

في عام ١٩٤١، أنجز كونراد تسوزه حاسوب Z3 . لم يكن تسوزه مُلِمًّا بأعمال تورينج في مجال الحوسبة آنذاك. وعلى وجه الخصوص، افتقر Z3 إلى إمكانيات مُخصصة للقفزات الشرطية، مما حال دون كونه حاسوبًا كاملًا من منظور تورينج. مع ذلك، في عام ١٩٩٨، أثبت روخاس أن Z3 قادر على محاكاة القفزات الشرطية، وبالتالي فهو حاسوب كامل من منظور تورينج نظريًا. وللقيام بذلك، يجب أن يكون برنامج الشريط الخاص به طويلًا بما يكفي لتنفيذ كل مسار مُمكن عبر جانبي كل فرع. ^{[ ١٠ ]}

كان أول جهاز كمبيوتر قادر على التفرع الشرطي عمليًا، وبالتالي كامل تورينج عمليًا، هو ENIAC في عام 1946. كان جهاز الكمبيوتر Z4 الخاص بـ Zuse يعمل في عام 1945، لكنه لم يدعم التفرع الشرطي حتى عام 1950. ^{[ 11 ]}

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

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

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

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

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

لكل قوانين الفيزياء المعروفة نتائج قابلة للحساب عبر سلسلة من التقريبات على حاسوب رقمي. تفترض فرضية تُعرف بالفيزياء الرقمية أن هذا ليس من قبيل الصدفة، لأن الكون نفسه قابل للحساب على آلة تورينغ عالمية. وهذا يعني أنه لا يمكن بناء حاسوب أقوى من آلة تورينغ العالمية فعليًا. ^{[ 12 ]}

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

• نظرية الأوتوماتا
• القواعد النحوية الرسمية (مولدات اللغة)
• اللغة الرسمية (برامج التعرف على اللغة)
• حساب التفاضل والتكامل لامدا
• آلات ما بعد التورينج
• حساب العمليات

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

• جميع اللغات العامة المستخدمة على نطاق واسع.
  • لغات البرمجة الإجرائية مثل C و Pascal .
  • لغات البرمجة الكائنية مثل جافا ، سمول توك، أو سي شارب .
  • لغات متعددة الأنماط مثل Ada و C ++ و Common Lisp و Fortran و JavaScript و Object Pascal و Perl و Python و R.
• معظم اللغات التي تستخدم نماذج أقل شيوعًا:
  • اللغات الوظيفية مثل لغة ليسب ولغة هاسكل .
  • لغات البرمجة المنطقية مثل برولوج .
  • معالج ماكرو للأغراض العامة مثل m4 .
  • اللغات التصريحية مثل SQL و XSLT . ^{[ 13 ] [ 14 ]}
  • لغة وصف الأجهزة VHDL وغيرها من لغات وصف الأجهزة.
  • TeX ، وهو نظام تنضيد.
  • لغات البرمجة الباطنية ، وهي شكل من أشكال الترفيه الرياضي حيث يعمل المبرمجون على إيجاد طريقة لتحقيق بنى البرمجة الأساسية بلغة صعبة للغاية ولكنها مكافئة رياضياً لتورينغ.

بعض أنظمة إعادة الكتابة كاملة تورينج.

اكتمال تورينج هو وصف مجرد للقدرة، وليس وصفًا لخصائص لغوية محددة تُستخدم لتنفيذ تلك القدرة. قد تختلف الخصائص المستخدمة لتحقيق اكتمال تورينج اختلافًا كبيرًا؛ فأنظمة فورتران تستخدم حلقات التكرار أو ربما حتى عبارات goto لتحقيق التكرار؛ أما لغتا هاسكل وبرولوج، اللتان تفتقران إلى حلقات التكرار بشكل شبه كامل، فتستخدمان الاستدعاء الذاتي . تصف معظم لغات البرمجة العمليات الحسابية على بنى فون نيومان ، التي تحتوي على ذاكرة (RAM ومسجلات) ووحدة تحكم. هذان العنصران يجعلان هذه البنية كاملة تورينج. حتى اللغات الوظيفية البحتة كاملة تورينج. ^{[ 15 ] [ 16 ]}

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

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

القاعدة 110 ولعبة كونواي للحياة ، وكلاهما من الأوتوماتا الخلوية ، هما كاملتان تورينج.

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

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

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

• "مجموعة تورينج الكاملة" . wiki.c2.com .