الجمعة، يوليو 24، 2009

لغات البرمجة المكتملة و معيار تورنغ Turing Complete Programming Languages

بسم الله و الحمد لله و الصلاة و السلام على رسول الله و بعد...
كنت أراجع مؤشرتيوب (TIOBE Index) لمدى شيوع لغات البرمجة, إلا أني وجدته قد أغفل لغات أخرى أحسبها من الأهمية بمكان. فلما قاربت على الانتهاء من قراءة صفحة المؤشر, وجدت القوم عللوا عدم ذكر هذه اللغات بأنها لغات غير مكتملة (و هذه ترجمة متصرفة للمصطلح Turing Completeness) فأحببت أن أعرف ما معنى اكتمال لغة البرمجة؟ و ما هو المعيار الذي قاسوا عليه مدى اكتمال لغة البرمجة؟ وهذا ما اهتديت إليه...
1- ابتكر عالم الرياضيات الإنكليزي آلان تورنغ Alan Turing نموذج نظري بسيط يحاكي طريقة عمل الحاسوب, و أسماه آلة تورنغ (1) Turing Machine. هذا النموذج قادر على تنفيذ كل خوارزمية قابلة للتنفيذ بواسطة أي حاسوب متطور. لذلك يمكن معرفة إذا كانت عملية معينة قابلة للتنفيذ بواسطة الحاسوب أم لا عن طريق فحصها بواسطة آلة تورنغ. وهو ما يسمى علم قابلية الحساب Computability.
2- تعتبر لغة البرمجة كاملة Turing Complete إذا كان لكل عملية تستطيعها آلة تورنغ استطعنا إيجاد برنامج يقوم بنفس العملية مكتوب بلغة البرمجة هذه.
3- تعتبر لغة برمجة ما مكتملة إذا توفر فيها أحد هذين الشرطين(1) (يمكننا تسمية هذه الطريقة معيار تورنغ):
  1. هناك برنامج مكتوب بهذه اللغة مناظر لكل عملية تستطيعها آلة تورنغ
  2. إذا كانت هذه اللغة مناظرة أو تحوي لغة أخرى ثبت أنها مكتملة
4-إذا طبقنا معيار تورنغ على لغات البرمجة الشائعة فإننا سنجد الآتي:
  • أغلب لغات البرمجة الشائعة تعتبر مكتملة, مثل++C و Java و #C...إلخ.
  • بعض اللغات الأخرى الشائعة لا تعتبر مكتملة, و من أمثلة ذلك:
  1. HTML و XML: حيث أنها تستخدم لعرض و تمثيل البيانات فقط
  2. SQL: حيث لا يمكننا مثلا عمل دالة تكرار غير منتهية infinite loop (على الرغم من أن الامتدادات التي أضافتها شركات عدة لهذه اللغة (مثل PL/SQL و T-SQL) تجعلها لغة برمجة مكتملة).
------------------
(1) ورد في معجم الحاسبات التعريف التالي: آلة تيورنج Turing Machine : آلة تصورية صممها العالم آلان تيورنج سنة 1936 م لتحقيق فكرة برمجة الخوارزمات. و تعد هذه الآلة أول إشارة للحاسبات الآلية كما نعرفها الآن. ا.هـ.
(2) المصدر: http://www.iwriteiam.nl/Ha_bf_Turing.html

ليست هناك تعليقات: