ما شاء الله طلبات متنوعة وبعضها يبي لها كورس بالجامعة وليس تغريدات في تويتر 😅. لكن راح أبدأ باول طلب عن #TheHaltingProblem من حبيبنا @SaifAlHarthi . هي اهم نظرية في الحاسب وسأستغل الفرصة لأقص لكم تاريخ ونشأة الحاسب وعلومه ومتاكد راح تعجبك القصة سواء كنت متخصص او محب للتاريخ.
نبدأ حديثنا عن هذه النظرية بالسؤال التالي: كيف فكر الإنسان بالحاسب؟ و ما هو الفرق بين الحاسبة calculator و الحاسب (أو الحاسوب) computer؟ الكثير لا ينتبه إلى الفرق في التسمية ولكنه فرق أساسي وجوهري وله عمق تاريخي كبير وفهم الفرق يساعدك على فهم نشأة الحاسب وعلومه
#مفاهيم_تقنية
#مفاهيم_تقنية
نبدأ القصة من الفيزيائي والرياضي الفرنسي بليز باسكال Blaise Pascal الذي عاش في القرن السابع عشر وهو أول من اخترع الآلة الحاسبة الميكانيكية en.wikipedia.org/wiki/Pascal%27…. كانت مهمة هذه الآلة هي القيام بالعمليات الرياضية الأربع الجمع والطرح والضرب والقسمة وكانت تعمل بطريقة ميكانيكية.
على ما يبدو انبهر لايبنتز Leibnitz - الفيلسوف والرياضي والمخترع الألماني والذي عاش أيضا في القرن السابع عشر en.wikipedia.org/wiki/Gottfried… - إلى هذا الاختراع المذهل فلم يكتف فقط بتطويره، بل بدأ في التفكير بكيفية تعميمه ليتجاوز هذه العمليات الحسابية إلى القيام بالتفكير والاثبات الرياضي
لقد كان حلم لايبنز هو اختراع آلة يمكنها التلاعب بالرموز والعبارات الرياضية ومعالجتها لاثبات صحتها من عدمه بدلا من الاكتفاء بالعمليات الحسابية البسيطة. كان حلمه اختراع آلة حوسبة computer لاثبات النظريات الرياضية وليس آلة حاسبة calculator فقط. en.wikipedia.org/wiki/Gottfried…
ولكنه أدرك منذ البداية أن هذا الحلم يحتاج إلى جهد أكبر بكثير مما تحتاجه الآلة الحاسبة وفي مقدمة هذا الجهد وجود لغة ونظام متكامل من الرموز والقواعد النحوية والمعاني ليستخدمه كلغة مشتركة بين علماء الرياضيات تكتب فيها النظريات الرياضية واثباتها ومن ثم يبني آلته استنادا إليها.
لو بحثنا قليلا لوجدنا أن هذا النظام موجود لدى الفلاسفة وعلماء الرياضيات منذ القدم وهو ما يسمى بالمنطق ولكنه لم يستخدم بشكل واضح لمثل هذا الغرض حتى أتى علماء الرياضيات في القرن التاسع عشر من أمثال George Boole و De Morgan وبدأوا بوضع حجر الأساس لذلك. en.wikipedia.org/wiki/Mathemati…
ولكن الانطلاقة الحقيقية للمنطق الرياضي بدأت من أعمال الرياضي الألماني Gottlob Frege en.wikipedia.org/wiki/Gottlob_F… في أواخر القرن التاسع العشر والذي ظلت أعماله مغمورة حتى نشرها وأشهرها الرياضي والأديب والفيلسوف البريطاني العظيم برتراند راسل Bertrand Russell en.wikipedia.org/wiki/Bertrand_…
من المفارقات الطريفة 😀 أني تعرفت على برتراند راسل منذر صغري وذلك من والدي المتخصص في اللغة الأدب - حيث أن راسل نال جائزة نوبل في الآداب - ولم أتعرف على برتراند راسل الفيلسوف الرياضي والمؤسس لنظرية الأنواع في لغات البرمجة types systems إلا في مرحلة الدراسات العليا
هنا يجب أنت نتوقف قليلا عند بداية القرن العشرين وتحديدا عام ١٩٠٠ وذلك عند مؤتمر الرياضيات العالمي المشهور en.wikipedia.org/wiki/Internati… والذي أقيم في باريس و كان له أثر عظيم في الرياضيات وعلومها حتى يومنا هذا
لقد عرض عالم الرياضيات الألماني المشهور هلبرت David Hilbert - والذي يعده البعض أكثر علماء الرياضيات تأثيرا في القرن التاسع عشر وبدايات القرن العشرين - تحديا على علماء الرياضيات حول العالم تمثل في ٢٣ مشكلة رياضية ليس لها حل في ذلك الوقت en.wikipedia.org/wiki/Hilbert%2…
هذه المجموعة من المشاكل الرياضية تعد الأشهر في تاريخ الرياضيات ومازال بعضها لم يتم حله حتى يومنا هذا. ما يهمنا فيها هي المشكلة الثانية en.wikipedia.org/wiki/Hilbert%2… والتي تتمحور حول اثبات ان المسلمات الرياضية axioms متسقة فيما بينها consistent ولا يمكن أن نستخدم أحدها لنثبت خطأ أخرى.
هذه المشكلة تعد الأهم بين المشاكل التي عرضها هلبرت والمقصد منها هو إيجاد أساس لعلوم الرياضيات foundation of mathematics يمكن الانطلاق منه لإثبات كل شيء في الرياضيات. لقد نبعت هذه المشكلة من أعمال برتراند راسل وفريجيه التي أشرنا لها سابقا.
راسل تعب كثيرا في العمل في هذا الجانب منطلقا من أحد أشهر التناقضات التي اكتشفها وهو Russell's paradox en.wikipedia.org/wiki/Russell%2…
قد لايكون من السهل فهم هذه المتناقضة الشهيرة ولكن يمكن قياسها على المتناقضة التالية: أعطاك شخص العبارة التالية "هذه العبارة غير صحيحة" ثم سألك هل العبارة صحيحة أم لا؟ توقف عن القراءة وفكر في الجواب 🤔؟ اذا كانت صحيحة فهي غير صحيحة والعكس أيضا صحيح 😅🤣
قام راسل بالتعاون مع عالم آخر هو وايتهيد Alfred Whitehead بتأليف سلسلة كتب مشهورة وهي Principia Mathematica en.wikipedia.org/wiki/Principia… لمحاولة ايجاد اطار منطقي متكامل لاثبات الرياضيات من أساسها وبالتالي حل مشكلة هلبيرت الثانية. صحيح أن راسل لم ينجح في ذلك - كما سأوضح - ولكنه (يتبع)
(يتبع) أسس لنظرية وأدوات مهمة في علوم الحاسب ولغات البرمجة وهي نظرية الأنواع type theory.
إذا نلاحظ حتى الآن مشكلتين بشكل عام:
١- هل يمكن أن نثبت كل شي في الرياضيات انطلاقا من مجموعة مسلمات غير متناقضة تمثل أساس الرياضيات؟
٢- اذا كان ذلك ممكنا فهل يمكن إسناده إلى آلة لتقوم به؟
إذا نلاحظ حتى الآن مشكلتين بشكل عام:
١- هل يمكن أن نثبت كل شي في الرياضيات انطلاقا من مجموعة مسلمات غير متناقضة تمثل أساس الرياضيات؟
٢- اذا كان ذلك ممكنا فهل يمكن إسناده إلى آلة لتقوم به؟
حتى نفهم مدى العمق الذي وصل إليه هؤلاء العلماء للإجابة على هذه الأسئلة هنا مقتطف شهير من كتاب Principia Mathematica لبرتراند راسل يثبت فيه أن ١ + ١ = ٢ 🙃😇 
بعد مرور حوالي ٣٠ سنة على المؤتمر في عام ١٩٠٠ قدم عالم الرياضيات الألماني الشهير كيرت جودل Kurt Gödel en.wikipedia.org/wiki/Kurt_G%C3… في عام ١٩٣١ (وكان عمره ٢٥ سنة) بما يعده الكثير أحد أهم النظريات الرياضية في القرن العشرين وهي incompleteness theorem en.wikipedia.org/wiki/G%C3%B6de…
جودل يعد من أهم علماء الرياضيات في القرن العشرين وقد كان جارا لآينشتاين في جامعة برنستون. في هذه النظرية أثبت جودل أنه لا يوجد آلية يمكنها إثبات كافة النظريات في الرياضيات. هزت هذه النظرية علماء الرياضيات و لم يعلق عليها هلبرت سلبا أو ايجابا حتى مماته
لقد حطمت هذه النظرية طموح الكثير من علماء الرياضيات في وضع أساس وآلية ينطلقون منهما ميكانيكيا في إثبات كافة النظريات (على الأقل حتى الآن) ولكنها لم توضح فيما إذا كان يمكن عمل خوارزمية لإثبات نظرية معينة من عدمه. وهنا ننتقل إلى مشكلة أخرى وهي Entscheidungsproblem 😁🤣
عارف الاسم طويل لأنه بالألمانية ويعني "مشكلة القرار" decision problem en.wikipedia.org/wiki/Entscheid… وهو أيضا تحدي قدمه هلبرت عام ١٩٢٩ - امتدادا للمشكلات التي قدمها سابقا - والمطلوب فيه ايجاد خوارزمية لاثبات صحة اي عبارة رياضية من عدمها باعتبار أن أي نظرية رياضية لابد أن تكتب كعبارة.
ما زلنا نلاحظ الاطار العام الذي تسير فيه الأمور وهو محاولة ايجاد طريقة (خوارزمية) آلية ميكانيكية لاثبات صحة أو خطأ أي نظرية رياضية انطلاقا من مجموعة من المسلمات الرياضية. هذا الطموح الكبير - وان كان مآله الفشل - لكنه أسس لعلوم الحاسب وللحوسبة كما نعرفها اليوم. كيف؟
في محاولته لحل "مشكلة القرار"، ومتأثرا بنظرية جودل، قام عالم الرياضيات البريطاني ألان تورنق Alan Turing en.wikipedia.org/wiki/Alan_Turi… - والذي يعتبره الكثير الأب المؤسس لعلوم الحاسب - بتأسيس آلة حاسوبية افتراضية ميكانيكية سماها آلة تورنق Turing Machine en.wikipedia.org/wiki/Turing_ma…
بعد ذلك قام تورنق باستخدام آلته الافتراضية الميكانيكية كنموذج رياضي لتعريف مفهوم الحوسبة computation والخوارزمية algorithm بشكل رياضي منضبط وفي جهد إبداعي عظيم أسس لعلوم الحاسب كما نعرفها اليوم. لاحظ أن تورنق ابتعد عن استخدام المنطق الرياضي ولغاته التي استخدمها برتراند راسل
بعد ذلك قام تورنق بتقديم "مشكلة التوقف" The Halting Problem (منطلق حديثنا) ليثبت التالي: لايمكن انشاء خوارزمية تقوم بتنفيذها آلة تورنق وتكون مهمتها ابلاغنا بأن أي خوارزمية أخرى تعمل على آلة أخرى بمدخلات معينة ستنهي عملها أو لا
تعريف صعب 😅 لكن ممكن أسهل كالتالي: هل تقدر تسوي برنامج مكافح فيروسات (خوارزمية) بحيث لو أعطيه أي برنامج ثاني (خوارزمية ثانية) مع مدخلات معينة راح يحدد لي اذا البرنامج الثاني فيروس راح يهنق بالجهاز (يستمر يشتغل بدون توقف).
من يفهم "مشكلة التوقف" بشكل عميق يعرف لماذا من المستحيل على أي شركة بناء مكافح للفيروسات يستطيع اكتشاف أي فيروس.
نرجع لقصتنا التاريخية. الان تورنق في ذلك الوقت لم يكن يفكر في الفيروسات ولكنه كان يفكر في حل "مشكلة القرار" وأثبت أنه لا يمكن حلها من خلال طريقة ذكية جدا.
نرجع لقصتنا التاريخية. الان تورنق في ذلك الوقت لم يكن يفكر في الفيروسات ولكنه كان يفكر في حل "مشكلة القرار" وأثبت أنه لا يمكن حلها من خلال طريقة ذكية جدا.
استخدم الان تورنق مفهوم القياس reduction وهو مفهوم يعمل كالتالي: "يمكنني حل مشكلة الذهاب من بيتي إلى بيت صديقي لو حللت مشكلة أخرى وهي تحديد الطريق بين بيتي وبيت صديقي على الخريطة". بنفس المفهوم أثبت تورنق أن حل "مشكلة القرار" يعني حل "مشكلة التوقف" ولكن (يتبع..)
(يتبع) بما أنه تم اثبات أن "مشكلة التوقف" لا يمكن حلها في آلة تورنق اذا نستنتج أن "مشكلة القرار" أيضا لا يمكن حلها. بالضبط كما أنه اذا لم يكن بامكانك حل مشكلة ايجاد طريق من منزلك إلى منزل صديقك على الخريطة فإنه لا يمكنك ايجاد طريق على أرض الواقع (بافتراض ان الخريطة مطابقة للواقع)
خلونا نلتقط الأنفاس قليلا. قد لا تكون عزيزي القارئ قد فهمت بالتفصيل كل ما سبق، ولكن ما أردت ايصاله لك هو التسلسل التاريخي لبعض الأفكار الطموحة لدى علماء الرياضيات والتي أوصلتنا إلى الحاسب والعصر الرقمي كما نعرفه اليوم وهو ما لم يحلموا به. وهكذا هو العلم يفاجؤنا يوما بعد يوم 🎁
استعرضت هنا معكم الجانب الرياضي التاريخي للحاسب وعلومه وكيف ظهر مفهوم الحوسبة computation كتطور طبيعي وطموح لمفهوم الحساب calculation. لا شك أن هذا التطور العلمي الرياضي في الجانب النظري صاحبه تطور هندسي مماثل في الجانب العملي في الآلات الميكانيكية والبخارية (يتبع)
(يتبع) ومن ثم الكهربائية منتهيا بالآلات الرقمية بين يدينا اليوم وقد يمتد إلى آلات الكوانتم.
كذلك استعرضنا تاريخيا كيف ظهرت "مشكلة التوقف" #TheHaltingProblem (أساس موضوعنا اليوم) وكيف أصبحت أساسا يتم الرجوع إليه لمعرفة ما إذا كان هناك خوارزمية لحل مشكلة ما computability
كذلك استعرضنا تاريخيا كيف ظهرت "مشكلة التوقف" #TheHaltingProblem (أساس موضوعنا اليوم) وكيف أصبحت أساسا يتم الرجوع إليه لمعرفة ما إذا كان هناك خوارزمية لحل مشكلة ما computability
نعم، ليست كل المشاكل computable أو قابلة للحل من خلال الحاسب وأبرز مثال على ذلك مشكلة اكتشاف الفيروسات. أثناء عملي في الدكتوراه كنا نبحث عن حل لاكتشاف بعض المشاكل الأمنية في مواقع الانترنت مثل ال Cross Site Scripting وال SQL Injection وأثبتنا قياسا على مشكلة التوقف (يتبع)
كيف أنه لا يمكن إيجاد خوارزمية تضمن اكتشاف هذه المشاكل الأمنية ١٠٠٪. هذا الأساس النظري كان نقطة الانطلاق ولكن لم نتوقف عندها بل بدأنا بمحاولة إيجاد حلول عملية تكتشف أكبر قدر ممكن من هذه المشاكل لجعل مهمة المهاجم صعبة وصعبة جدا عملا بمبدأ "ما لا يدرك جله لا يترك كله".
أنا مؤمن بأن هذا الخلط بين الجانب النظري والجانب العملي دائما ما يؤدي إلى نتائج عميقة ومهمة وممتازة جدا ولكني ألحظ للأسف إهمالا للجانب النظري في عالمنا العربي. اذا أردت الاستزادة أنصحك بهذا الكتاب العظيم amazon.com/Introduction-T…
هذا الكتاب يتحدث عن نظرية الحوسبة وكيف يمكننا أن نحدد فيما إذا كانت مشكلة ما يمكن حلها باستخدام الحاسب. ستجد فيه شرحا لجزء من الأعمال التي تحدثت عنها في هذه التغريدات إضافة إلى شرح كاف وواف لمفهوم الحوسبة والنظريات التي ظهرت بعد ألان تورنق و أسست لعلوم الحاسب كما نعرفها اليوم.
@SaifAlHarthi أتمنى أكون جاوبت على سؤالك الأول 🤣. عاد باقي السؤال الثاني واللي يستكمل حديثنا ويدخل في نظرية التعقيد complexity theory وهو هل P =? NP. هذا نتركه لوقت لاحق
