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

المشكلات

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

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

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

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

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

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

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

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

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

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

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

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

مشكلة التوقف

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

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

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

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

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

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

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

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

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

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

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

التطبيق غير المحدود

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

${\displaystyle 1+{1 \over 2 +{1 \over 4 +\cdots$

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

آلات الأوركل

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

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

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

انظر أيضا

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

فيديو

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

المراجع

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