الحاسوبية

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

المشكلات

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

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

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

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

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

طالع أيضاً: Model of computation

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

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

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

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

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

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

الحساب يتكون من الدالة المتكرره، تعني تعاقبها التعريفي، أي قيم(ه) مدخلة وتعاقب الدوال المتكررة تظهر في التعاقب التعريفي مع المدخلات والمخرجات. وهكذا، إذا كان التعاقب التعريفي لدلة متكررة د(س) فإن الدوال ر(س) وز(س) ستظهر، ثم قد تظهر بنود النموذج ر(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 من الوقت. هذه الآلة قادرة على تحديد مشكلة التوقف عن طريق المحاكاة المباشرة لتنفيذ الجهاز محل السؤال. وبالتالي، فإن أي سلسلة متقاربة سوف تعمل. على افتراض أن السلسلة تتقارب إلى قيمة ن، فإن آلة تورينج سوف تستكمل تنفيذ لانهائي في ن من وحدات الوقت.

آلات الأوركل

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

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

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

أنظر أيضا

• Automata theory
• Abstract machine
• List of undecidable problems
• Computational complexity theory
• Computability logic
• Important publications in computability

المراجع

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. ‎ Part Two: Computability Theory, Chapters 3–6, pp. 123–222.
• Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. ‎ Chapter 3: Computability, pp. 57–70.
• S. Barry Cooper (2004). Computability Theory (1st ed.). Chapman & Hall/CRC. ISBN 978-1584882374. ‎

قالب:Computable knowledge

de:Berechenbarkeit Computability]] fr:Calculabilité he:חישוביות nl:Berekenbaarheid pt:Computabilidade