الحاسوبية

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

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

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

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

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

آلة التسجيل

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

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

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

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

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

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

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

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

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

أ"

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

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

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

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

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

المشكلات

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

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

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

أنواع أخرى من المشاكل وتشمل مشاكل البحث ومشاكل التحسين.

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

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

فيديو

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

مشكلة التوقف

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

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

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

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

آلات الأوركل

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