الحاسوبية

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

المشكلات

الفكرة المحورية في الحاسوبية هي تلك الخاصة بالمشكلة الحسابية، وهي مهمة يمكن استكشاف حاسوبيتها.

هناك صنفين رئيسين من المشكلات:

• مشكلة القرار تعالج المجموعة م، والتي قد تكون مجموعة من الحروف، الأعداد الطبيعية أو أشياء أخرى مأخوذة من بعض المجموعات الأكبر ج. مثال خاص للمشكلة هو أن تقرر، بفرض العنصر ج من ج، حيث ج موجودة في م. على بيل المثال، إجعل ج هي مجموعة الأعداد الطبيعية وم هي مجموعة الأرقام الأولية. فإن مشكلة القرار المماثلة تتفق مع اختبار الأولية.
• مشكلة الدالة تتكون من الدالة د من المجموعة ج إلى المجموعة ك. مثال على المشكلة يكون بحساب -معطى العنصر ج في ج- العنصر المماثل د (ج) في ك. على سبيل المثال، قد تكون ج وك هما كل مجموعة الحروف الثنائية المتناهية، وقد تأخذ د حرف ما وتعيد الحرف الذي تم الحصول عليه عن طريق عكس أرقام المدخلات (فتكون د (0101)=1010).

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

نماذج الحساب الرسمية

المقالة الرئيسية: نموذج حوسبة

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

حسابات اللامدا

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

المنطق الإتحادي

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

دوال مايكرو المتغيرة

الحساب يتكون من الدالة المتكرره، تعني تعاقبها التعريفي، أي قيم (ه) مدخلة وتعاقب الدوال المتكررة تظهر في التعاقب التعريفي مع المدخلات والمخرجات. وهكذا، إذا كان التعاقب التعريفي لدلة متكررة د (س) فإن الدوال ر (س) وز (س) ستظهر، ثم قد تظهر بنود النموذج ر (5)=7 أو ز (3,2)=10. كل مدخل في هذا الترتيب يحتاج لأن يكون تطبيق للدالة الأساسية أو تابع للمدخلات بالأعلى عن طريق استخدام التكوين، التكرار الأولي أو دالة التكرار. على سبيل المثال إذا كانت د (س)=ز (س، ر (س))، إذاً ستظهر د (5)=3، ويجب أن تحدث بالأعلى بنود مثل ر (5)=6 وز (3,6)=3. تنتهي الحسابات فقط إذا كان البند الأخير يعطي قيمة الدالة المتكررة المطبقة على المدخلات.

خوارزمية ماركوف

هو نظام كتابة حرفي يستخدم قواعد شبيهة بالكتابة للعمل على سلسة من الرموز.

آلة التسجيل

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

أ"

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

آلة تورنغ

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

آلة تورنغ متعددة الشرائط

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

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

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

بعض النماذج الأخرى المقيدة للحساب تشمل:

آلة الوضع المتناهي القطعية

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

آلة الوضع المتناهي غير القطعية

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

مستودع معلومات الكومبيوتر الذاتي

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

قوة الحركة الذاتية

بوجود هذه النماذج الحسابية لدينا، يمكننا تعيين حدودهم. بمعنى، أي أصناف اللغات يمكنهم قبولها؟

قوة آلة الوضع المتناهي

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

مثال على هذه اللغة هو مجموعة كل الحروف المكونة من الحرفين «أ» و«ب» والتي تحتوي على عدد متساوي من الحرف «أ» و«ب». لتري سبب كون هذه اللغة لا يمكن إدراكها بشكل صحيح من قبل آلة الوضع المتناهي، لنفترض أولاً أن هذه الآلة ل موجودة.يجب أن يوجد في ل عدد ما من الحالات «ر». الآن، لنعتبر أن الحرف س يتكون من (ر+1) من «أ» متبوعاً ب (ر+1) من «ب». عندما تقرأ ل في س، فيجب أن تكون هناك حالة متكررة في الآلة عندما تقرأ السلسة الأولى من «أ»، حيث أنه يوجد (ر+1) من «أ» وفقط ر من الحالات طبقاً لمبدأ الرص في الفجوات. لنسمي هذه الحالة ح ولنجعل ھ أيضاً هو عدد «أ» الذي تقرأه الآلة حتى تبدأ من الحدث الأول في ح، والذي يمكننا إضافته عن طريق ھ إضلفية (حيث ھ >0) من «أ» وسوف تصبح في الحالة ح مرة أخرى. هذا يعني أننا سوف نعلم أن الحرف (ر+ ھ +1) من «أ» يجب أن ينتهي في نفس الحالة كما الحرف (ر+1) من «أ». وهذا يدل على أن الآلة تقبل س، وهو ليس من ضمن لغة الحروف التي تشمل عدد متساوي من «أ» و«ب». بمعنى، لا تستطيع ل أن تفرق بشكل صحيح بين حرف عدد متساوي من «أ» و«ب» والحرف (ر+ ھ +1) من «أ» و (ر+1) من «ب».

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

قوة مستودع معلومات الكومبيوتر الذاتي

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

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

قوة آلات تورنغ

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

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

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

السؤال الذي يجب أن نسأله هو: هل توجد لغات معدودة بشكل متكرر، ولكنها غير متكرره؟ وعلاوة على ذلك، هل توجد لغات ليست حتى معدودة بشكل متكرر.

مشكلة التوقف

مشكلة التوقف هي أحد أشهر المشاكل في علوم الكومبيوتر، لأن لها آثار عميقة على نظرية الحسابية وعلى كيفية استخدام حاسباتنا يومياً. يمكن أن نعبر عن المشكلة كالتالي:

بافتراض وصف لآلة تورنغ ومُدخله الأساسي، لتحديد إذا كان البرنامج، عندما يتم تنفيذه على هذا المدخل، سيتوقف أبداً (يكتمل). البديل هو أنه سيعمل للأبد بدون توقف.

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

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

ما وراء اللغات المعدودة بشكل متكرر

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

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

نماذج معتمدة على التوافق

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

نماذج أقوى من الحاسوبية

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

التنفيذ غير المحدود

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

$1+\frac{1}{2}+\frac{1}{4}+\cdots$

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

آلات الأوركل

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

حدود الفوق حاسوبية

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

انظر أيضا

• نظرية التشغيل الذاتي
• نظرية التعقيد الحسابي
• Important publications in computability

فيديو

• شرح مادة نظرية الحوسبة والأتوماتا (اللغات والنحو في هرمية تشومسكي Chomsky) Theory of Automata

المراجع

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. Part Two: Computability Theory, Chapters 3–6, pp. 123–222.
• Christos Papadimitriou (1993). Computational Complexity (ط. 1st). Addison Wesley. Chapter 3: Computability, pp. 57–70.
• إس. باري كوبر (2004). Computability Theory (ط. 1st). Chapman & Hall/CRC.