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

ركزت نظرية الحوسبة في المنطق الرياضي تقليديًا على الحوسبة النسبية ، وهي تعميم لحوسبة تورينج، مُعرَّفة باستخدام آلات تورينج المُعَوِّضة ، والتي قدمها تورينج عام 1939. ^{[ 14 ]} آلة تورينج المُعَوِّضة هي جهاز افتراضي، بالإضافة إلى قيامه بوظائف آلة تورينج العادية، قادر على طرح أسئلة على مُعَوِّض ، وهو مجموعة مُحددة من الأعداد الطبيعية. لا يُمكن لآلة المُعَوِّض طرح سوى أسئلة من نوع "هل العدد n ينتمي إلى مجموعة المُعَوِّض؟". سيتم الإجابة على كل سؤال بشكل صحيح فورًا، حتى لو كانت مجموعة المُعَوِّض غير قابلة للحساب. وبالتالي، فإن آلة المُعَوِّض المزودة بمُعَوِّض غير قابل للحساب ستكون قادرة على حساب مجموعات لا تستطيع آلة تورينج غير المزودة بمُعَوِّض حسابها.

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

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

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

تُعدّ قابلية الاختزال المتعدد إلى عنصر واحد "أقوى" من قابلية الاختزال التورينغية: فإذا كانت المجموعة A قابلة للاختزال المتعدد إلى عنصر واحد إلى المجموعة B ، فإن A قابلة للاختزال التورينغي إلى B ، ولكن العكس ليس صحيحًا دائمًا. على الرغم من أن الأمثلة الطبيعية للمجموعات غير القابلة للحساب متكافئة متعددًا إلى عنصر واحد، فمن الممكن إنشاء مجموعتين قابلتين للحساب A و B بحيث تكون A قابلة للاختزال التورينغي إلى B ولكنها غير قابلة للاختزال المتعدد إلى B. يمكن إثبات أن كل مجموعة قابلة للحساب قابلة للاختزال المتعدد إلى عنصر واحد إلى مسألة التوقف، وبالتالي فإن مسألة التوقف هي أكثر المجموعات القابلة للحساب تعقيدًا فيما يتعلق بقابلية الاختزال المتعدد إلى عنصر واحد وفيما يتعلق بقابلية الاختزال التورينغية. في عام 1944، تساءل بوست ^{[ 15 ]} عما إذا كانت كل مجموعة قابلة للحساب قابلة للحساب أو مكافئة تورينغيًا لمسألة التوقف، أي ما إذا كانت لا توجد مجموعة قابلة للحساب بدرجة تورينغية متوسطة بين هاتين الدرجتين.

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

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

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

ركزت العديد من الأبحاث الحديثة حول درجات تورينج على البنية العامة لمجموعة درجات تورينج، ومجموعة درجات تورينج التي تحتوي على مجموعات قابلة للتعداد الحسابي. تنص نظرية عميقة لشور وسلامان ^{[ 16 ]} على أن الدالة التي تربط درجة x بدرجة قفزة تورينج الخاصة بها قابلة للتعريف في الترتيب الجزئي لدرجات تورينج. يقدم استعراض أجراه أمبوس-سبيس وفيجر ^{[ 17 ]} نظرة عامة على هذا البحث وتطوره التاريخي.

يُعنى مجال بحثي مستمر في نظرية الحوسبة بدراسة علاقات الاختزال الأخرى غير اختزال تورينج. وقد قدّم بوست ^{[ 15 ]} العديد من علاقات الاختزال القوية ، التي سُمّيت بهذا الاسم لأنها تستلزم اختزال جدول الحقيقة . تستطيع آلة تورينج التي تُطبّق علاقة اختزال قوية حساب دالة كلية بغض النظر عن الوسيط المُقدّم لها. أما علاقات الاختزال الضعيفة فهي تلك التي قد لا تنتهي فيها عملية الاختزال لجميع الوسائط؛ واختزال تورينج مثال على ذلك.

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

قابلية الاختزال أحاديًا : يكون 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 : مجموعة ce رقم e التي _تنتمي إلى C } تتمتع بخاصية أن مسألة التوقف أو مكملتها قابلة للاختزال إلى E باستخدام اختزال متعدد إلى واحد ، أي يمكن تمثيلها باستخدام اختزال متعدد إلى واحد إلى E (انظر نظرية رايس لمزيد من التفاصيل). ولكن، العديد من مجموعات الفهارس هذه أكثر تعقيدًا من مسألة التوقف. يمكن تصنيف هذا النوع من المجموعات باستخدام التسلسل الهرمي الحسابي . على سبيل المثال، تقع مجموعة الفهارس FIN لفئة جميع المجموعات المنتهية على المستوى Σ2 _، وتقع مجموعة الفهارس REC لفئة جميع المجموعات المتكررة على المستوى Σ3 _، وتقع مجموعة الفهارس COFIN لجميع المجموعات المنتهية المشتركة أيضًا على المستوى Σ3 ، وتقع مجموعة الفهارس COMP لفئة جميع المجموعات الكاملة تورينج على _{المستوى Σ4} . تُعرَّف مستويات التسلسل الهرمي هذه استقرائيًا، حيث تحتوي المجموعة Σ _{n + 1} على جميع المجموعات القابلة للحساب بالنسبة إلى المجموعة Σ _n ؛ بينما تحتوي المجموعة Σ ₁ على المجموعات القابلة للحساب. وتكون مجموعات الفهرسة المُعطاة هنا كاملةً حتى بالنسبة لمستوياتها، أي أنه يمكن اختزال جميع المجموعات في هذه المستويات إلى مجموعات الفهرسة المُعطاة.

يتساءل برنامج الرياضيات العكسية عن بديهيات وجود المجموعات اللازمة لإثبات نظريات رياضية محددة في الأنظمة الفرعية للحساب من الرتبة الثانية . بدأ هذه الدراسة هارفي فريدمان، ودرسها ستيفن سيمبسون وآخرون بتفصيل أكبر؛ وفي عام ١٩٩٩، قدم سيمبسون ^{[ ١٨ ]} مناقشة مفصلة للبرنامج. تتوافق بديهيات وجود المجموعات المذكورة بشكل غير رسمي مع بديهيات تنص على أن مجموعة قوى الأعداد الطبيعية مغلقة في ظل مفاهيم اختزال مختلفة. أضعف هذه البديهيات التي دُرست في الرياضيات العكسية هي الفهم التكراري ، الذي ينص على أن مجموعة قوى الأعداد الطبيعية مغلقة في ظل اختزال تورينج.

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

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

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

عندما عرّف بوست مفهوم المجموعة البسيطة بأنها مجموعة قابلة للحساب مع مكمل لانهائي لا يحتوي على أي مجموعة قابلة للحساب لانهائية، بدأ بدراسة بنية المجموعات القابلة للحساب تحت التضمين. أصبحت هذه الشبكة بنية مدروسة جيدًا. يمكن تعريف المجموعات القابلة للحساب في هذه البنية من خلال النتيجة الأساسية التي تنص على أن المجموعة قابلة للحساب إذا وفقط إذا كانت المجموعة ومكملها قابلتين للحساب. تحتوي المجموعات القابلة للحساب اللانهائية دائمًا على مجموعات جزئية قابلة للحساب لانهائية؛ ولكن من ناحية أخرى، توجد مجموعات بسيطة ولكن ليس لديها دائمًا مجموعة فائقة قابلة للحساب لانهائية. قدم بوست ^{[ 15 ]} بالفعل المجموعات فائقة البساطة والمجموعات فائقة التعقيد؛ وفي وقت لاحق تم بناء المجموعات القصوى، وهي مجموعات قابلة للحساب بحيث تكون كل مجموعة فائقة قابلة للحساب إما متغيرًا منتهيًا للمجموعة القصوى المعطاة أو مجموعة فائقة الانتهاء. كان الدافع الأصلي لبوست في دراسة هذه الشبكة هو إيجاد مفهوم بنيوي بحيث لا تقع أي مجموعة تحقق هذه الخاصية ضمن درجة تورينج للمجموعات القابلة للحساب ولا ضمن درجة تورينج لمسألة التوقف. لم يجد بوست مثل هذه الخاصية، ولذا اعتمد حل مشكلته على أساليب الأولوية؛ وفي عام 1991، توصل هارينغتون وسوار ^{[ 19 ]} في نهاية المطاف إلى إيجاد مثل هذه الخاصية.

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

إلى جانب شبكة المجموعات القابلة للحساب، تُدرس التشاكلات الذاتية أيضًا لبنية درجات تورينج لجميع المجموعات، وكذلك لبنية درجات تورينج لمجموعات ce. في كلتا الحالتين، يدّعي كوبر أنه أنشأ تشاكلات ذاتية غير تافهة تربط بعض الدرجات بدرجات أخرى؛ إلا أن هذا البناء لم يُتحقق منه، ويعتقد بعض الزملاء أنه يحتوي على أخطاء، وأن مسألة وجود تشاكل ذاتي غير تافه لدرجات تورينج لا تزال من أهم المسائل العالقة في هذا المجال. ^{[ 21 ] [ 17 ]}

تطوّر مجال تعقيد كولموغوروف والعشوائية الخوارزمية خلال ستينيات وسبعينيات القرن العشرين على يد تشايتين، وكولموغوروف، وليفين، ومارتن-لوف، وسولومونوف (الأسماء مذكورة هنا بالترتيب الأبجدي؛ إذ كان جزء كبير من البحث مستقلاً، ولم يكن مفهوم وحدة العشوائية مفهوماً آنذاك). وتتلخص الفكرة الرئيسية في اعتبار آلة تورينغ شاملة U ، وقياس تعقيد العدد (أو السلسلة) x على أنه طول أقصر مدخل p بحيث تُخرج U ( p ) القيمة x . أحدث هذا النهج ثورة في الطرق السابقة لتحديد ما إذا كانت متتالية لانهائية (أو ما يعادلها، دالة مميزة لمجموعة جزئية من الأعداد الطبيعية) عشوائية أم لا، وذلك من خلال استحضار مفهوم العشوائية للأشياء المحدودة. لم يصبح تعقيد كولموغوروف موضوعاً للدراسة المستقلة فحسب، بل يُطبّق أيضاً على مواضيع أخرى كأداة للحصول على البراهين. ولا تزال هناك العديد من المشكلات المفتوحة في هذا المجال. ^{[ د ]}

يُحلل هذا الفرع من نظرية الحوسبة السؤال التالي: بالنسبة لقيم ثابتة لـ m و n حيث 0 < m < n ، ما هي الدوال A التي يُمكن حسابها لأي n مُدخلات مختلفة x₁ _, x₂ _, ... , xₙ ، _بحيث تكون مجموعة من n أعداد y₁ , y₂ , ..., yₙ _صحيحة ، وذلك لأي n مُدخل مختلف _x₁ , _x₂ , _... , xₙ ؟ تُعرف هذه المجموعات باسم المجموعات ( m , n )-التكرارية. أول نتيجة رئيسية في هذا الفرع من نظرية الحوسبة هي نتيجة تراختنبروت التي تنص _على أن المجموعة قابلة للحوسبة إذا كانت ( m , n )-تكرارية لبعض m و n حيث 2m > n . من جهة أخرى، تُعدّ مجموعات جوكوش شبه المتكررة (التي كانت معروفة بشكل غير رسمي قبل أن يُقدّمها جوكوش عام ١٩٦٨) أمثلةً على مجموعات تكون متكررة من الرتبة ( م ، ن ) إذا وفقط إذا كان ٢ م < ن + ١. يوجد عدد لا يُحصى من هذه المجموعات، بالإضافة إلى بعض المجموعات القابلة للحساب ولكنها غير قابلة للحساب من هذا النوع. لاحقًا، وضع ديجتيف تسلسلًا هرميًا للمجموعات القابلة للحساب التي تكون متكررة من الرتبة (١، ن + ١) ولكنها ليست متكررة من الرتبة (١، ن ). بعد مرحلة طويلة من البحث من قِبل علماء روس، عاد هذا الموضوع إلى الواجهة في الغرب بفضل أطروحة بيجل حول الاستعلامات المحدودة، والتي ربطت حساب التردد بالاختزالات المحدودة المذكورة أعلاه ومفاهيم أخرى ذات صلة. كانت إحدى النتائج الرئيسية هي نظرية كومر للعددية ^{[ 22 ] [ 23 ]} ، والتي تنص على أن المجموعة A قابلة للحساب إذا وفقط إذا وُجدت آلة تورينج، عند إعطائها n مدخلات x1، x2 ، ... _، xn _، تُرجع على الأكثر _n مخرجات ، إحداها هي عدد عناصر المجموعة { x1 _، x2 _، ... ، xn _} ∩ A (يوجد n + 1 قيمة ممكنة فقط لعدد العناصر: 0، ...، n) .                                 ).

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

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

تُعدّ نظرية الحوسبة الرقمية متطورةً للغاية. أما نظرية الحوسبة التناظرية ، التي تحدث في الحواسيب التناظرية ، ومعالجة الإشارات التناظرية ، والإلكترونيات التناظرية ، والشبكات العصبية الاصطناعية ، ونظرية التحكم في الزمن المستمر ، والتي تُنمذج بواسطة المعادلات التفاضلية والأنظمة الديناميكية المستمرة ، فهي أقل تطورًا . ^{[ 25 ] [ 26 ]} على سبيل المثال، قامت نماذج الحوسبة، مثل نموذج آلة بلوم-شوب-سميل، بصياغة الحوسبة على الأعداد الحقيقية.