دالة تكرارية بدائية

📅 آخر تحديث: ٣٠ يوليو ٢٠٢٦
✍️ نُشر في: ٣٠ يوليو ٢٠٢٦
الموسوعة الحرة

في المنطق الرياضي ، تُعدّ الدوال التكرارية الأولية تعميمًا للدوال التكرارية الأولية في نظرية الأنواع العليا . وهي تتألف من مجموعة من الدوال في جميع الأنواع المنتهية البحتة.

تُعدّ الدوال التكرارية الأولية مهمة في نظرية البرهان والرياضيات البنائية . وهي جزء أساسي من تفسير ديالكتيكا للحساب الحدسي الذي طوره كورت غودل .

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

خلفية

لكل دالة تكرارية أولية نوعٌ يُحدد نوع المدخلات التي تستقبلها ونوع المخرجات التي تُنتجها. الكائن من النوع 0 هو ببساطة عدد طبيعي ؛ ويمكن اعتباره أيضًا دالة ثابتة لا تستقبل أي مدخلات وتُرجع مخرجًا من مجموعة الأعداد الطبيعية N.

بالنسبة لأي نوعين σ و τ، يُمثل النوع σ→τ دالةً تأخذ مُدخلاً من النوع σ وتُعيد مُخرجاً من النوع τ. بالتالي، فإن الدالة f ( n ) = n + 1 هي من النوع 0→0. يختلف النوعان (0→0)→0 و 0→(0→0)؛ واصطلاحاً، يُشير الرمز 0→0→0 إلى 0→(0→0). في مصطلحات نظرية الأنواع، تُسمى الكائنات من النوع 0→0 دوالاً ، وتُسمى الكائنات التي تأخذ مُدخلات من أنواع أخرى غير 0 دوالاً وظيفية .

لأي نوعين σ و τ، يُمثل النوع σ×τ زوجًا مرتبًا ، العنصر الأول فيه من النوع σ والعنصر الثاني من النوع τ. على سبيل المثال، لنفترض الدالة A التي تأخذ كمدخلات دالة f من N إلى N ، وعددًا طبيعيًا n ، وتُرجع f ( n ). عندئذٍ يكون نوع A هو (0 × (0→0))→0. ويمكن كتابة هذا النوع أيضًا على النحو 0→(0→0)→0، باستخدام تقنية التخصيص الجزئي (currying ).

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

تعريف

الدوال التكرارية الأولية هي أصغر مجموعة من الكائنات ذات النوع المحدود بحيث:

  • الدالة الثابتة f ( n ) = 0 هي دالة استرجاعية أولية
  • الدالة اللاحقة g ( n ) = n + 1 هي دالة تكرارية أولية
  • لأي نوع σ×τ، فإن الدالة K( xσ , yτ ) = x هي دالة استرجاعية أولية
  • لأية أنواع ρ، σ، τ، الوظيفية
    S( r ρ→σ→τ , s ρ→σ , t ρ ) = ( r ( t ))( s ( t ))
    هي دالة تكرارية بدائية
  • لأي نوع τ، و f من النوع τ، وأي g من النوع 0→τ→τ، فإن الدالة R ( f , g ) 0→τ المعرفة بشكل تكراري هي
    R ( f , g )(0) = f ,
    R ( f , g )( n +1) = g ( n , R ( f , g )( n ))
    هي دالة تكرارية بدائية

انظر أيضاً

مراجع