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

على سبيل التعريف، نظرية الحوسبة أو النظرية الحسابية أو النظرية الاحتسابية في علم الحاسوب يدرس إمكانية حل المسائل المطروحة بكفاءة بوساطة حاسوب ويدرس ما يمكن للحاسوب أن يقوم باحتسابة في الوقت الحالي وإمكانية تطوره في المستقبل. لذلك يمكن تقسيمها إلى: نظرية الحاسوبية ونظرية التعقيد الحسابي. و كلاهما يتعاملان مع النماذج الرياضية للتحسيب. ونتناول فيما يلي مزيدًا من التفاصيل.
إضافةً إلى ذلك، في علم الحاسوب النظري والرياضيات، نظرية الحوسبة هي الفرع الذي يختص بفعالية حل المشاكل من خلال نموذج حوسبي باستخدام خوارزمية ما. ينقسم هذا المجال إلى ثلاثة أقسام رئيسية هي: نظرية التشغيل الذاتي واللغات، والنظرية الحاسوبية، ونظرية التعقيد الحسابي اللواتي يربطهن السؤال التالي: «ما هي الإمكانات والقيود الأساسية لأجهزة الحاسوب؟».
من جهة ثانية، شرط محدودية الذاكرة ضروري جدا لأن هذا ما يجعل آلة تورنغ واقعية، ويجعل تنبؤات آلة تورنغ مقبولة فأي مسألة يمكن حلها بوساطة آلة تورنغ يمكن حلها كذلك بوساطة أي حاسوب شخصي ذو ذاكرة كافية.
من جانب آخر، من أجل إجراء دراسة دقيقة للحوسبة، يعمل علماء الحاسوب مع تجريد رياضي للحواسيب يسمى بنموذج الحوسبة. تُستعمل الكثير من النماذج لكن أكثرها شيوعًا هي آلة تورنغ. يدرس علماء الحاسوب آلة تورنغ لأنها سهلة التشكيل، ويمكن تحليلها واستخدامها لإثبات النتائج، ولأنها تمثل ما يعتبره كثيرون أقوى نموذج حسابي «منطقي» ممكن. يبدو أن احتمالية وجود سعة ذاكرة لانهائية هي ميزة غير قابلة للتحقيق، لكن أي مشكلة يُقرر حلها عن طريق آلة تورنغ ستتطلب دائمًا كمية ذاكرة محدودة فقط. لذلك من حيث المبدأ، فإن أي مشكلة يمكن (تَقرّر) حلها عن طريق آلة تورنغ بالتالي يمكن حلها من خلال حاسوب يمتلك كمية محدودة من الذاكرة.
ومن ناحية أخرى، لإنجاز دراسة منهجية للتحسيب، يشكل علماء الحاسوب نماذج رياضية مجردة من الحواسيب تدعى نموذج التحسيب model of computation. توجد عدة أنماط من هذه النماذج قيد الاستعمال، لكن أهمها وأكثرها شيوعا هو آلة تورنغ. يمكن أن نتصور آلة تورنغ على أنها حاسوب منزلي مع سعة ذاكرة محدودة، ولايمكن الوصول إلا إلى قطاعات صغيرة متفرقة من هذه الذاكرة. تعتبر آلات تورنغ سهلة التصور والتصميم ومن الممكن تحليلها ودراستها للبرهنة عن النتائج المتوقعة بالتالي تمثل نموذجا معقولا لعملية التحسيب.
نظرية التعقيد الحاسوبية
وفي هذا السياق، ربما تكون أهم مسألة مفتوحة في علوم الحاسب هي مسألة فيما إذا كان صف معين من المسائل التي يرمز لها NP (أي كثير حدود غير قطعي) قابلة للحل بكفاءة. نوقشت تلك الفكرة بشكل أكبر في صفوف التعقيد P (أي كثير حدود) وصفوف NP (أي كثير حدود غير قطعي)، وتعتبر مسألة كثير حدود وكثير حدود غير قطعي (P=NP?) واحدة من سبع مسائل جوائز الألفية، وصرح عنها معهد كلاي للرياضيات في سنة 2000. طرح وصف المسألة، الفائز بجائزة تورنغ، ستيفن كوك.
وفي السياق ذاته، لا تهتم نظرية التعقيد فقط فيما إذا كانت مسألة ما قابلة للحل أم لا على الحاسوب، لكنها تهتم كذلك بالكفاءة التي يمكن حل المسألة بها. هناك مفهومان رئيسيان يؤخذان بعين الاعتبار هما: التعقيد الزمني والتعقيد المكاني، واللذان يشيران على التتالي إلى عدد الخطوات التي يتطلبها إجراء الحوسبة، وكمية الذاكرة المطلوبة لإجراء هذه الحوسبة.
إضافةً إلى ذلك، لتحليل كمية الزمن والمكان الذي تتطلبه خوارزمية ما، يعبر علماء الحاسوب عن الزمن والمكان المطلوب لحل المسألة على أنه تابع لحجم مدخلات المسألة. مثلًا، إيجاد رقم محدد في قائمة طويلة من الأرقام يصبح أصعب كلما كانت قائمة الأرقام أكبر. إذا قلنا إن هناك ن(n) رقم في قائمة ما، في حال كانت القائمة غير مرتبة أو غير مفهرسة بأي شكل، سنضطر إلى المقارنة مع كل رقم من أجل إيجاد الرقم الذي نبحث عنه. لذلك نقول إنه من أجل حل هذه المسألة، يحتاج الحاسوب لإجراء مجموعة من الخطوات تزداد خطيًا مع ازدياد حجم المسألة.
نظرية حاسوبية للعقل
اقرأ كذلك
ومن جهة أخرى، لتبسيط المسألة اعتمد علماء الحاسوب على ما يسمى رمز O الكبير الذي يسمح بمقارنة التوابع بطريقة تؤكد أنه يمكننا عدم أخذ جوانب محددة من بناء الآلة بعين الاعتبار، لكن بدلًا من ذلك نتبع الأسلوب المقارب فقط مع ازدياد حجم المسائل. إذّا في مثالنا السابق يمكن أن نقول إن المسألة تتطلب O(n) أو ن خطوة لحلها.
تاريخها
وفي السياق ذاته، كان من ضمن الرائدين في نظرية الحوسبة رامون لول، ألونزو تشرتش، وكورت غودل، وآلان تورنغ، وستيفن كلين، وروزنا بيتر، وجون فون نيومان وكلود شانون.
وعلى صعيد آخر، يمكن أن نعتبر أن نظرية الحوسبة هي إنشاء نماذج من جميع الأنواع في مجال علوم الحاسب. ولذلك يُستعمل فيها الرياضيات والمنطق. أصبحت في العقد الأخير قسمًا أكاديميًا مستقلًا وفُصلت عن الرياضيات.
الأقسام
نظرية التشغيل الذاتي
علاوةً على ذلك، نظرية التشغيل الذاتي هي دراسة الآلات المجردة (أو بالأحرى، أنظمة أو آلات «رياضياتية» مجردة) والمسائل الحسابية التي يمكن حلها باستخدام هذه الآلات. تسمى هذه الآلات المجردة بالآلات ذاتية التشغيل. تأتي جذور كلمة آلة ذاتية التشغيل(Automata) من الكلمة اليونانية (Αυτόματα) والتي تعني شيئًا يقوم بفعلٍ ما من تلقاء نفسه. نظرية التشغيل الذاتي تتعلق كذلك بنظرية اللغة الشكلية، وتُصنف الآلات ذاتية التشغيل غالبًا حسب نوع اللغات الشكلية التي يمكنها أن تتعرف عليها. يمكن أن يكون الأوتومات تمثيلًا منتهيًا للغة شكلية ويمكن أن يكون مجموعة منتهية. تُستعمل الآلات ذاتية التشغيل بمثابة نماذج نظرية للآلات الحسابية، وبمثابة براهين على قابلية التحسيب.
نظرية الحاسوبية
وعلى صعيد آخر، تتعامل نظرية الحاسوبية في المقام الأول مع مسألة المدى الذي تكون فيه المسألة قابلة للحل على الحاسوب. التأكيد على أن مسألة التوقف غير ممكنة الحل من خلال آلة تورنغ هي واحدة من أهم النتائج في نظرية الحاسوبية، إذ أنها مثال لمشكلة ملموسة سهلة الحدوث ولكنها مستحيلة الحل باستخدام آلة تورنغ. تعتمد نظرية الحاسوبية في أغلبها على نتائج مسألة التوقف.
وفي السياق ذاته، نظرية الحاسوبية مرتبطة بشكل وثيق بفرع المنطق الرياضي الذي يسمى بنظرية التراجعية، التي تزيل القيود عن دراسة نماذج التحسيب فقط التي يمكن اختزالها إلى نموذج تورنغ. الكثير من علماء الرياضيات وواضعي النظريات الحاسوبية الذين يدرسون النظرية التراجعية يشيرون إليها على أنها نظرية الحاسوبية.
في هذا الإطار، الخطوة الأخرى المهمة في نظرية الحاسوبية هي نظرة رايس الرياضية، التي توضح أنه من أجل جميع الخصائص غير البسيطة للتوابع الجزئية، لا يمكن اتخاذ قرار فيما إذا كانت آلة تورنغ تحسب تابع جزئي عن طريق تلك الخاصية.
نظرية اللغة الشكلية
من جانب آخر، نظرية اللغة هي فرع من الرياضيات تهتم بوصف اللغات على أنها مجموعة من العمليات على الحروف الأبجدية. وترتبط بشكل وثيق بنظرية التشغيل الذاتي، لأن الآلات ذاتية الشغيل تُستعمل لتوليد اللغات الشكلية والتعرف عليها. يوجد الكثير من أنواع اللغات الشكلية، تمنح كل منها اللغة مواصفاتٍ أكثر تعقيدًا من سابقتها، مثال: هرمية تشومسكي، وتتوافق كل منها مع نمط من الآلات ذاتية التشغيل تستطيع التعرف عليها. اللغات الشكلية هي الأسلوب المُفضل لتوصيف أي مسألة يجب حسابها، لأن الآلات ذاتية التشغيل تُستعمل بمثابة نماذج للتحسيب.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟