نظرية الحسوبية

نظرية الحاسوبية

نظرية الحاسوبية (بالإنجليزية: computability theory)‏ وتعرف أيضاً بالنظرية العودية وأيضا بنظرية الاستدعاء الذاتي (بالإنجليزية: Recursion theory)‏ وهي أحد فروع المعلوماتية النظرية تم تأسيسه في عام 1930م علم الحاسوب النظري والتي تدرس مسائل قابلة للحل حاسوبيا باستخدام نماذج مختلفة للحوسبة.

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

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

تتضمن الأسئلة الأساسية التي تتناولها نظرية الحوسبة ما يلي:

• ماذا يعني أن تكون دالة على الأعداد الطبيعية قابلة للحساب؟
• كيف يمكن تصنيف الوظائف غير القابلة للحوسبة في تسلسل هرمي بناءً على مستوى عدم قابليتها للحوسبة؟

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

المجموعات المحسوبة وغير القابلة للحساب

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

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

" لقد شدد تارسكي في محاضرته (وأعتقد بحق) على الأهمية الكبرى لمفهوم التكرار العام (أو قابلية تورينج الحسابية). يبدو لي أن هذه الأهمية ترجع إلى حد كبير إلى حقيقة أنه مع هذا المفهوم نجح المرء لأول مرة في إعطاء فكرة مطلقة لمفهوم معرفي مثير للاهتمام، أي مفهوم لا يعتمد على الشكلية المختارة. * "(جوديل 1946 في ديفس 1965: 84).

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

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

إن دراسة الإنشاءات الرياضية التي يمكن إجراؤها بفعالية تسمى أحيانًا الرياضيات العودية؛ يغطي دليل الرياضيات العودية (ارشوف 1998) العديد من النتائج المعروفة في هذا المجال.

تورينج الحوسبة

تم تقديم الشكل الرئيسي للحسابات المدروسة في نظرية الحوسبة بواسطة تورينج (1936). يُقال أن مجموعة الأرقام الطبيعية هي مجموعة قابلة للحساب (تسمى أيضًا مجموعة قابلة للحساب أو متكررة أو مجموعة تورينج القابلة للحساب ) إذا كانت هناك آلة تورينج التي، عند إعطاء رقم n، تتوقف عند الإخراج 1 إذا كانت n في المجموعة وتتوقف مع الإخراج 0 إذا لم يكن n في المجموعة. الوظيفة f من الأعداد الطبيعية إلى الأعداد الطبيعية هي دالة (تورينج) قابلة للحساب، أو دالة تكرارية إذا كانت هناك آلة تورينج تقوم، عند الإدخال n، بإيقاف وإرجاع الإخراج f ( n ). استخدام آلات تورينج هنا ليس ضروريًا ؛ هناك العديد من النماذج الأخرى للحوسبة التي لها نفس قوة الحوسبة مثل آلات تورينج ؛ على سبيل المثال، الدوال العودية μ التي تم الحصول عليها من العودية البدائية والعامل μ.

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

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

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

مجالات البحث

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

الحوسبة النسبية ودرجات تورينج

المقالات الرئيسة: تخفيض تورينج ودرجة تورينج

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

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

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

1. يتم عدها حسابيًا، و
2. يمكن ترجمة كل منها إلى أي دولة أخرى عن طريق تخفيض متعدد واحد . أي، بالنظر إلى هاتين المجموعتين A و B، هناك دالة حسابية إجمالية f مثل A = { x : و ( س ) ∈ ب }. يُقال أن هذه المجموعات مكافئة للعديد من الوحدات (أو مكافئ m ).

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

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

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

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

ركزت الكثير من الأبحاث الحديثة حول درجات تورينج على الهيكل العام لمجموعة درجات تورينج ومجموعة درجات تورينج التي تحتوي على مجموعات قابلة للحساب. تنص نظرية عميقة لـ شور وسلمان (1999) على أن وظيفة تعيين درجة x إلى درجة قفزة تورينج يمكن تحديدها بالترتيب الجزئي لدرجات تورينج. يعطي مسح حديث أجراه أمبوس جواسيس وفجر (2006) لمحة عامة عن هذا البحث وتطوره التاريخي.

قابلية الاختزال الأخرى

المقالة الرئيسة: التخفيض (نظرية العودية)

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

تشمل قابلية الاختزال القوية ما يلي:

قابلية اختزال واحدة

A هو واحد قابل للاختزال (أو 1 قابل للاختزال ) إلى B إذا كان هناك دالة حقن إجمالية قابلة للحساب f بحيث يكون كل n في A إذا وفقط إذا كانت f ( n ) في B.

العديد من الاختزال

هذا هو في الأساس قابلية اختزال واحدة بدون قيود أن تكون f حقنة. A يمكن اختزاله (أو اختزاله m ) إلى B إذا كان هناك دالة حسابية إجمالية f بحيث يكون كل n في A إذا وفقط إذا كانت f ( n ) في B.

اختزال جدول الحقيقة

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

مزيد من الاختزال (موجبة، منفصلة، موصولة، خطية ونسخها الضعيفة والمحدودة) تمت مناقشتها في مقالة التخفيض (نظرية الحوسبة) .

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

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

نظرية رايس والتسلسل الهرمي الحسابي

أظهر رايس أنه بالنسبة لكل فئة C غير بديهية (التي تحتوي على بعض وليس كل مجموعات ce)، فإن مجموعة الفهرس E = { e : the e th ce set W _e in C } لها خاصية إما مشكلة التوقف أو مكملتها كثيرة - يمكن اختزال واحد إلى E، أي يمكن تعيينه باستخدام اختزال متعدد واحد إلى E (انظر نظرية رايس لمزيد من التفاصيل). لكن العديد من مجموعات الفهارس هذه أكثر تعقيدًا من مشكلة التوقف. يمكن تصنيف هذا النوع من المجموعات باستخدام التسلسل الهرمي الحسابي. على سبيل المثال، مجموعة الفهرس (FIN) لفئة جميع المجموعات المحدودة موجودة على المستوى Σ ₂، مجموعة الفهرس (REC) لفئة جميع المجموعات العودية على المستوى Σ ₃، مجموعة الفهرس (COFIN) لجميع مجموعات كوفينيت قيد التشغيل أيضًا المستوى Σ ₃ ومجموعة الفهرس (COMP) لفئة جميع مجموعات تورينج كومبليت Σ ₄. يتم تعريف مستويات التسلسل الهرمي هذه بشكل استقرائي، Σ _{n +1} تحتوي فقط على جميع المجموعات التي يمكن تعدادها حسابيًا بالنسبة إلى _n ؛ Σ ₁ يحتوي على المجموعات التي يمكن عدها حسابيًا. مجموعات الفهرس الواردة هنا كاملة حتى بالنسبة لمستوياتها، أي أن جميع المجموعات في هذه المستويات يمكن أن تكون عدة مجموعات - واحدة مخفضة إلى مجموعات الفهرس المحددة.

عكس الرياضيات

المقالة الرئيسة: عكس الرياضيات

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

الترقيم

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

طريقة الأولوية

لمعلوماتٍ أكثر: تورينج درجة §  مشكلة ما بعد وطريقة الأولوية

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

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

شبكة المجموعات التي يمكن عدها حسابيًا

عندما حدد بوست مفهوم المجموعة البسيطة كمجموعة CE مع تكملة لانهائية لا تحتوي على أي مجموعة ce لانهائية، بدأ في دراسة بنية المجموعات القابلة للحساب تحت التضمين. أصبحت هذه الشبكة بنية مدروسة جيدًا. يمكن تعريف المجموعات القابلة للحساب في هذه البنية من خلال النتيجة الأساسية التي مفادها أن المجموعة قابلة للحساب إذا وفقط إذا كانت المجموعة ومكملتها قابلة للعد بشكل محسوب. تحتوي مجموعات CE اللانهائية دائمًا على مجموعات فرعية قابلة للحساب غير محدودة ؛ ولكن من ناحية أخرى، توجد مجموعات بسيطة ولكنها لا تحتوي دائمًا على مجموعة فرعية قابلة للحساب غير محدودة. قدم بوست (1944) مجموعات مفرطة البساطة بالفعل؛ تم إنشاء مجموعات قصوى لاحقة وهي مجموعات CE بحيث تكون كل مجموعة شاملة إما متغيرًا محدودًا للمجموعة القصوى المحددة أو أنها محدودة. كان الدافع الأصلي لـ بوست في دراسة هذه الشبكة هو العثور على فكرة هيكلية مثل أن كل مجموعة ترضي هذه الخاصية ليست في درجة تورينج للمجموعات القابلة للحساب ولا في درجة تورينج لمشكلة التوقف. لم يعثر بوست على مثل هذه الخاصية وطبق حل مشكلته طرق الأولوية بدلاً من ذلك ؛ وجد هارينجتون وسوير (1991) في النهاية مثل هذه الممتلكات.

مشاكل التشكل الآلي

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

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

تعقيد كولموغوروف

المقالة الرئيسة: تعقيد كولموغوروف

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

حساب التردد

حلل هذا الفرع من نظرية الحوسبة السؤال التالي: للحصول على ثابت m و n مع 0 < م < n، لأي من الوظائف A يمكن حساب أي n مدخلات مختلفة x ₁، × ₂، ...، x _n مجموعة مكونة من n أعداد y ₁، y ₂، ...، y _n بحيث تكون m على الأقل من المعادلات A ( x _k ) = y _k صحيحة. تُعرف هذه المجموعات باسم ( م، ن ) - مجموعات متسلسلة. أول نتيجة رئيسية في هذا الفرع من نظرية الحوسبة هي نتيجة تراختنبروت أن المجموعة قابلة للحساب إذا كانت ( m، ن ) - متسلسل لبعض م، ن 2 م > ص . من ناحية أخرى، فإن مجموعات جوكوش شبه المتصلة (التي كانت معروفة بالفعل بشكل غير رسمي قبل أن يقدمها جوكوش في عام 1968) هي أمثلة على المجموعة التي هي ( m، ن ) - متسلسل إذا وفقط إذا كان 2 م < ن + 1. يوجد عدد لا يحصى من هذه المجموعات وأيضًا بعض المجموعات القابلة للحساب ولكن غير القابلة للحساب من هذا النوع. في وقت لاحق، أنشأ ديغتيف تسلسلًا هرميًا للمجموعات التي يمكن تعدادها حسابيًا والتي هي (1، ن + 1) - متسلسل ولكن ليس (1، ن ) - متسلسل. بعد مرحلة طويلة من البحث من قبل العلماء الروس، تمت إعادة نشر هذا الموضوع في الغرب من خلال أطروحة بيجل حول الاستعلامات المحدودة، والتي ربطت بين حساب التردد وقابلية الاختزال المحددة المذكورة أعلاه والمفاهيم الأخرى ذات الصلة. كانت إحدى النتائج الرئيسية هي نظرية كارديناليتي كومير التي تنص على أن المجموعة أ قابلة للحساب إذا وفقط إذا كان هناك n بحيث تعداد بعض الخوارزمية لكل مجموعة من n أعداد مختلفة حتى ن العديد من الخيارات الممكنة من أصل هذه المجموعة من عدد n تتقاطع مع A ؛ يجب أن تحتوي هذه الاختيارات على العلاقة الأساسية الحقيقية مع استبعاد واحدة خاطئة واحدة على الأقل.

الاستدلال الاستقرائي

هذا هو الفرع النظري للحساب في نظرية التعلم. وهو يعتمد على نموذج إي. مارك جولد للتعلم في حدود 1967 وقد طور منذ ذلك الحين المزيد والمزيد من نماذج التعلم. السيناريو العام هو ما يلي: بالنظر إلى فئة S من الوظائف القابلة للحساب، هل هناك متعلم (أي وظيفي محسوب) يقوم بإخراج أي مدخلات من النموذج ( f (0)، f (1)، ...، f ( ن ) فرضية. يتعلم المتعلم M الوظيفة f إذا كانت جميع الفرضيات تقريبًا هي نفس الفهرس e لـ f فيما يتعلق بترقيم متفق عليه مسبقًا لجميع الوظائف القابلة للحساب ؛ يتعلم M S إذا تعلمت M كل f في S. النتائج الأساسية هي أن جميع فئات الوظائف القابلة للحساب قابلة للتعلم بينما لا يمكن تعلم فئة REC لجميع الوظائف القابلة للحساب. تم النظر في العديد من النماذج ذات الصلة، كما أن تعلم فئات المجموعات التي يمكن تعدادها حسابيًا من البيانات الإيجابية هو موضوع تمت دراسته من ورقة جولد الرائدة في عام 1967 وما بعده.

تعميمات حساب تورينج

تتضمن نظرية الحوسبة دراسة المفاهيم المعممة لهذا المجال مثل الاختزال الحسابي وقابلية الاختزال المفرط ونظرية العودية α، كما وصفها ساكس (1990). تتضمن هذه المفاهيم المعممة عمليات اختزال لا يمكن تنفيذها بواسطة آلات تورينج ولكنها مع ذلك تعميمات طبيعية لإمكانية اختزال تورينج. تتضمن هذه الدراسات مناهج للتحقيق في التسلسل الهرمي التحليلي الذي يختلف عن التسلسل الهرمي الحسابي من خلال السماح بالقياس الكمي على مجموعات من الأرقام الطبيعية بالإضافة إلى القياس الكمي للأرقام الفردية. ترتبط هذه المناطق بنظريات حسن الترتيب والأشجار ؛ على سبيل المثال، مجموعة جميع مؤشرات الأشجار القابلة للحساب (غير الثنائية) بدون فروع لانهائية كاملة للمستوى $\Pi _{1}^{1}$ من التسلسل الهرمي التحليلي. كل من قابلية اختزال تورينج وإمكانية الاختزال الفائق الأهمية في مجال نظرية المجموعة الوصفية الفعالة . تتم دراسة الفكرة الأكثر عمومية لدرجات القابلية للبناء في نظرية المجموعات .

نظرية الحوسبة المستمرة

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

العلاقات بين التحديد والبرهان والحساب

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

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

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

المسمى

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

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

المنظمات المهنية

المنظمة المهنية الرئيسية لنظرية الحوسبة هي جمعية المنطق الرمزي، والتي تعقد العديد من المؤتمرات البحثية كل عام. كما تنظم جمعية الحوسبة البحثية متعددة التخصصات في أوروبا ( CiE ) سلسلة من المؤتمرات السنوية.

انظر أيضاً

• روبن غاندي.

• العودية (علوم الكمبيوتر).
• منطق الحوسبة.
• مشكلة حسابية.

مراجع

===

نصوص المرحلة الجامعي ===

• Cooper، S.B. (2004). Computability Theory. Chapman & Hall/CRC. ISBN:1-58488-237-9.
• Cutland، N. (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN:0-521-29465-7.
• Matiyasevich، Y. (1993). Hilbert's Tenth Problem. MIT Press. ISBN:0-262-13295-8.

نصوص متقدمة

• Jain، S.؛ Osherson، D.؛ Royer، J.؛ Sharma، A. (1999). Systems that learn, an introduction to learning theory (ط. 2nd). Bradford Book. ISBN:0-262-10077-0.
• Kleene، S. (1952). Introduction to Metamathematics. North-Holland. ISBN:0-7204-2103-9.
• Lerman، M. (1983). Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag. ISBN:3-540-12155-2.
• Nies، Andre (2009). Computability and Randomness. Oxford University Press. ISBN:978-0-19-923076-1.
• Odifreddi، P. (1989). Classical Recursion Theory. North-Holland. ISBN:0-444-87295-7.
• Odifreddi، P. (1999). Classical Recursion Theory. Elsevier. ج. II. ISBN:0-444-50205-X.
• Rogers, Jr.، H. (1987). The Theory of Recursive Functions and Effective Computability (ط. 2nd). MIT Press. ISBN:0-262-68052-1.
• Sacks، G. (1990). Higher Recursion Theory. Springer-Verlag. ISBN:3-540-19305-7.
• Simpson، S.G. (1999). Subsystems of Second Order Arithmetic. Springer-Verlag. ISBN:3-540-64882-8.
• Soare، R.I. (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN:0-387-15299-7.

أوراق ومجموعات المسح

• Ambos-Spies، K.؛ Fejer، P. (2006). "Degrees of Unsolvability" (PDF). مؤرشف من الأصل (PDF) في 2013-04-20. اطلع عليه بتاريخ 2006-10-27. طبع أولي غير منشور.
• Enderton، H. (1977). "Elements of Recursion Theory". في Barwise (المحرر). Handbook of Mathematical Logic. North-Holland. ص. 527–566. ISBN:0-7204-2285-X. {{استشهاد بكتاب}}: الوسيط غير المعروف |chapterurl= تم تجاهله يقترح استخدام |مسار الفصل= (مساعدة) وروابط خارجية في |chapterurl= (مساعدة)
• Ershov، Y.L.؛ Goncharov، S.S.؛ Nerode، A.؛ Remmel، J.B. (1998). Handbook of Recursive Mathematics. North-Holland. ISBN:0-7204-2285-X.
• Fairtlough، M.؛ Wainer، S.S. (1998). "Hierarchies of Provably Recursive Functions". في Buss (المحرر). Handbook of Proof Theory. Elsevier. ص. 149–208. ISBN:978-0-08-053318-6. {{استشهاد بكتاب}}: الوسيط غير المعروف |chapterurl= تم تجاهله يقترح استخدام |مسار الفصل= (مساعدة) وروابط خارجية في |chapterurl= (مساعدة)
• Soare، R.I. (1996). "Computability and recursion" (PDF). Bulletin of Symbolic Logic. ج. 2 ع. 3: 284–321. DOI:10.2307/420992. JSTOR:420992.

الأوراق البحثية والمجموعات

• Burgin، M.؛ Klinger، A. (2004). "Experience, Generations, and Limits in Machine Learning". Theoretical Computer Science. ج. 317 ع. 1–3: 71–91. DOI:10.1016/j.tcs.2003.12.005.
• Church، A. (1936). "An unsolvable problem of elementary number theory". American Journal of Mathematics. ج. 58 ع. 2: 345–363. DOI:10.2307/2371045. JSTOR:2371045. أعيد طبعه في Davis 1965 .
• Church، A. (1936). "A note on the Entscheidungsproblem". Journal of Symbolic Logic. ج. 1 ع. 1: 40–41. DOI:10.2307/2269326. JSTOR:2269326. أعيد طبعه في Davis 1965 .
• Davis، المحرر (2004) [1965]. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Courier. ISBN:978-0-486-43228-1.
• Friedberg، R.M. (1958). "Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition". The Journal of Symbolic Logic. ج. 23 ع. 3: 309–316. DOI:10.2307/2964290. JSTOR:2964290.
• Gold، E. Mark (1967). "Language Identification in the Limit" (PDF). Information and Control. ج. 10 ع. 5: 447–474. DOI:10.1016/s0019-9958(67)91165-5. [1]
• Harrington، L.؛ Soare، R.I. (1991). "Post's Program and incomplete recursively enumerable sets". Proc. Natl. Acad. Sci. U.S.A. ج. 88 ع. 22: 10242–6. Bibcode:1991PNAS...8810242H. DOI:10.1073/pnas.88.22.10242. PMID:11607241. {{استشهاد بدورية محكمة}}: الوسيط غير المعروف |PMCID= تم تجاهله يقترح استخدام |pmc= (مساعدة)
• Jockusch jr، C.G. (1968). "Semirecursive sets and positive reducibility". Trans. Amer. Math. Soc. ج. 137 ع. 2: 420–436. DOI:10.1090/S0002-9947-1968-0220595-7. JSTOR:1994957.
• Kleene، S.C.؛ Post، E.L. (1954). "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics. Second. ج. 59 ع. 3: 379–407. DOI:10.2307/1969708. JSTOR:1969708.
• Moore، C. (1996). "Recursion theory on the reals and continuous-time computation". Theoretical Computer Science. ج. 162 ع. 1: 23–44. DOI:10.1016/0304-3975(95)00248-0.
• Myhill، J. (1956). "The lattice of recursively enumerable sets". The Journal of Symbolic Logic. ج. 21: 215–220. DOI:10.1017/S002248120008525X.
• Orponen، P. (1997). "A survey of continuous-time computation theory". Advances in Algorithms, Languages, and Complexity: 209–224. DOI:10.1007/978-1-4613-3394-4_11. ISBN:978-1-4613-3396-8.
• Post، E. (1944). "Recursively enumerable sets of positive integers and their decision problems". Bulletin of the American Mathematical Society. ج. 50 ع. 5: 284–316. DOI:10.1090/S0002-9904-1944-08111-1. MR:0010514.
• Post، E. (1947). "Recursive unsolvability of a problem of Thue". Journal of Symbolic Logic. ج. 12 ع. 1: 1–11. DOI:10.2307/2267170. JSTOR:2267170. أعيد طبعه في Davis 1965 .
• Shore، Richard A.؛ Slaman، Theodore A. (1999). "Defining the Turing jump" (PDF). Mathematical Research Letters. ج. 6 ع. 6: 711–722. DOI:10.4310/mrl.1999.v6.n6.a10. MR:1739227.
• Slaman، T.؛ Woodin، W.H. (1986). "Definability in the Turing degrees". Illinois J. Math. ج. 30 ع. 2: 320–334. DOI:10.1215/ijm/1256044641. MR:0840131.
• Soare، R.I. (1974). "Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets". Annals of Mathematics. ج. 100 ع. 1: 80–120. DOI:10.2307/1970842. JSTOR:1970842.
• Turing، A. (1937). "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. s2-42 ع. 1: 230–265. DOI:10.1112/plms/s2-42.1.230. أعيد طبعه في Davis 1965 . ملف PDF من comlab.ox.ac.uk
• Turing، A.M. (1939). "Systems of logic based on ordinals". Proceedings of the London Mathematical Society. s2-45 ع. 1: 161–228. DOI:10.1112/plms/s2-45.1.161. أعيد طبعه في Davis 1965 .

روابط خارجية

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