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

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

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

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

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

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

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

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

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

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

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

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

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

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

مشكلة التوقف

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

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

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

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

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

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

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