أرشيف الكاتب: yousify32

ما هو نظريات علوم الحاسب؟

ما سأذكره هنا هو ترجمة من تعريف نظريات علوم الحاسب من كتاب: The Princeton Companion to Mathematics، ص7، وهو تعريف مختصر:

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

 

 

آلة تيرنغ الشاملة!

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

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

أول شخص أسس لهذا المبدأ هو أبو موسى محمد الخوارزمي فهو أعطى خوارزمية لصنف معين من المسائل الرياضية وهي معادلات الدرجة الثانية التي تكون كالتالي:

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

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

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

كانوا الرياضيون يعتقدون أن كل آلة قادرة أنها تحل عدد من الخوارزميات. جتى جاء آلان تيرنغ صاحب النهضة لثورة الحواسيب، عام ١٩٣٦ حيث اخترع بما يسمى لاحقاً “آلة تيرنغ” (Turing Machine) اسهل بكثير من الآلات التي اخترعت بحيث أن آلته لديها خصيصة ليست في غيرها وهي أنها “شاملة” (Universality).

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

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

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

تميز آلة تيرنغ بالشمولية هي التي نفهمها اليوم الاختلاف بين البرمجيات (Software) والعتاد (Hardare). بهذا الشكل أصبح من السهل على الناس ألا يفكروا في قضية العتاد لحل مسألة ما. حيث يعرف المبرمجون أو مصممي الخوارزميات أنهم قادرون أنهم ينفذونها في آلة تيرنغ من خلال فرضية تشارش-تيرنغ (Church-Turing Thesis) هي فرضية تقول أن أي خوارزمية ممكن تفكر فيها يتم محاكاتها عن طريق آلة تيرنغ. للسبب هذا أصبح لدينا حاسوب واحد ينفذ مختلف الخوارزميات.

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

إذا كان آلة تيرنغ هي آلة شمولية إذن لماذا ما زالت هناك أبحاث عن آلة تيرنغ وما هي المشكلات الموجودة حالياً؟ السبب هو أن النموذج الذي قدمه تيرنغ هو فقط يقول لنا ما هو المحوسب (computable) وغير المحوسب (uncomputable) ولا يقول لنا الوقت المستغرق لحل المسألة، أو الذاكرة التي تحتاجها، وهذا بالضبط فرع جديد في الحوسبة ظهر لاحقاً مع ظهور الحاسوب عام 1971 وهو ما يعرف بنظرية التعقيد الحسابي (Computational Complexity Theory).

أنظر للفيديو التالي عن آلة تيرنغ الشاملة حيث معظم ما كتبته هنا هو ملخص لما في هذا الفيديو بالإضافة إلى الفصل 1.2 من كتاب أوديد غولدريتش بعنوان: “Computational Complexity – A Conceptual Perspective”.

التدوينة الأولى

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