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

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

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

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

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

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

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

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

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

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

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