الحاسوبية

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

آلات الأوركل

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

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

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