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

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

صنف فرعي من	نظرية
جزء من	علم المعلومات — علم الحاسوب
فروع	علم الخوارزميات
المواضيع	خوارزمية — التعقيد الحسابي — التعقيد في أسوأ حالة — average-case complexity (en)

نظرية الحوسبة أو النظرية الحسابية أو النظرية الاحتسابية (بالإنجليزية: Theory of Computation)‏ في علم الحاسوب يدرس إمكانية حل المسائل المطروحة بكفاءة بوساطة حاسوب ويدرس ما يمكن للحاسوب أن يقوم باحتسابة حاليا وإمكانية تطوره في المستقبل. لذلك يمكن تقسيمها إلى: نظرية الحاسوبية ونظرية التعقيد الحسابي. و كلاهما يتعاملان مع النماذج الرياضية للتحسيب.

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

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

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

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

تاريخها

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

كان من ضمن الرائدين في نظرية الحوسبة رامون لول، ألونزو تشرتش، وكورت غودل، وآلان تورنغ، وستيفن كلين، وروزنا بيتر، وجون فون نيومان وكلود شانون.

الأقسام

نظرية التشغيل الذاتي

القواعد	اللغات	الأوتومات	قواعد الإنشاء(القيود)
نوع-0	قابلة للعد بشكل تراجعي	آلة تورنغ	$\alpha \rightarrow \beta$
نوع-1	حساسة للسياق	آلة تورنغ خطية غير حتمية	$\alpha A\beta \rightarrow \alpha \gamma \beta$
نوع-2	حساسة للسياق	أوتومات دفع سفلي غير حتمي	$A\rightarrow \gamma$
نوع-3	منتظمة	أوتومات ذو حالة منتهية	$A\rightarrow a$ و $A\rightarrow aB$

نظرية التشغيل الذاتي هي دراسة الآلات المجردة (أو بالأحرى، أنظمة أو آلات «رياضياتية» مجردة) والمسائل الحسابية التي يمكن حلها باستخدام هذه الآلات. تسمى هذه الآلات المجردة بالآلات ذاتية التشغيل. تأتي جذور كلمة آلة ذاتية التشغيل(Automata) من الكلمة اليونانية (Αυτόματα) والتي تعني شيئًا يقوم بفعلٍ ما من تلقاء نفسه. نظرية التشغيل الذاتي تتعلق أيضًا بنظرية اللغة الشكلية، وتُصنف الآلات ذاتية التشغيل غالبًا حسب نوع اللغات الشكلية التي يمكنها أن تتعرف عليها. يمكن أن يكون الأوتومات تمثيلًا منتهيًا للغة شكلية ويمكن أن يكون مجموعة منتهية. تُستخدم الآلات ذاتية التشغيل بمثابة نماذج نظرية للآلات الحسابية، وبمثابة براهين على قابلية التحسيب.

نظرية اللغة الشكلية

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

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

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

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

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

نظرية التعقيد الحاسوبية

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

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

لتبسيط المسألة اعتمد علماء الحاسوب على ما يسمى رمز O الكبير الذي يسمح بمقارنة التوابع بطريقة تؤكد أنه يمكننا عدم أخذ جوانب محددة من بناء الآلة بعين الاعتبار، لكن بدلًا من ذلك نتبع الأسلوب المقارب فقط مع ازدياد حجم المسائل. إذّا في مثالنا السابق يمكن أن نقول إن المسألة تتطلب O(n) أو ن خطوة لحلها.

ربما تكون أهم مسألة مفتوحة في علوم الحاسب هي مسألة فيما إذا كان صف معين من المسائل التي يرمز لها NP (أي كثير حدود غير قطعي) قابلة للحل بكفاءة. نوقشت تلك الفكرة بشكل أكبر في صفوف التعقيد P (أي كثير حدود) وصفوف NP (أي كثير حدود غير قطعي)، وتعتبر مسألة كثير حدود وكثير حدود غير قطعي (P=NP?) واحدة من سبع مسائل جوائز الألفية، وصرح عنها معهد كلاي للرياضيات في عام 2000. طرح وصف المسألة، الفائز بجائزة تورنغ، ستيفن كوك.

اقرأ أيضاً

• نظرية حاسوبية للعقل