نظرية كلين للتكرار

يستخدم البرهان دالة حسابية كلية محددة${\displaystyle h}$، كما هو مُعرَّف على النحو التالي. بالنظر إلى عدد طبيعي${\displaystyle x}$، الوظيفة${\displaystyle h}$يُخرج فهرس الدالة القابلة للحساب الجزئي التي تُجري الحساب التالي:

بفرض مدخلات${\displaystyle y}$، المحاولة الأولى للحساب${\displaystyle \varphi _{x}(x)}$إذا أسفرت تلك العملية الحسابية عن مخرجات${\displaystyle e}$ثم احسب${\displaystyle \varphi _{e}(y)}$وإرجاع قيمته، إن وجدت. وبالتالي، لجميع المؤشرات${\displaystyle x}$من الدوال القابلة للحساب الجزئي، إذا${\displaystyle \varphi _{x}(x)}$إذا تم تعريفها، فإن${\displaystyle \varphi _{h(x)}\simeq \varphi _{\varphi _{x}(x)}}$. لو${\displaystyle \varphi _{x}(x)}$إذا لم يتم تعريفها، فـ${\displaystyle \varphi _{h(x)}}$هي دالة غير مُعرَّفة في أي مكان.${\displaystyle h}$يمكن بناؤها من الدالة القابلة للحساب الجزئي${\displaystyle g(x,y)}$الموصوف أعلاه ونظرية Smn   : لكل${\displaystyle x}$الرقم${\displaystyle h(x)}$هو فهرس برنامج يقوم بحساب الدالة${\displaystyle y\mapsto g(x,y)}$.

لإكمال البرهان، دع${\displaystyle F}$لتكن أي دالة قابلة للحساب الكلي، وقم بإنشاء${\displaystyle h}$كما سبق. دع${\displaystyle e}$يكون مؤشرًا على التركيب${\displaystyle F\circ h}$وهي دالة قابلة للحساب كليًا، لذا${\displaystyle \varphi _{e}(e)}$يتم تعريفها. ثم${\displaystyle \varphi _{h(e)}\simeq \varphi _{\varphi _{e}(e)}}$بحسب تعريف${\displaystyle h}$لكن، لأن${\displaystyle e}$هو فهرس لـ${\displaystyle F\circ h}$،${\displaystyle \varphi _{e}(e)=(F\circ h)(e)=F(h(e))}$وبالتالي${\displaystyle \varphi _{h(e)}\simeq \varphi _{F(h(e))}}$. لذلك${\displaystyle \varphi _{n}\simeq \varphi _{F(n)}}$ل${\displaystyle n=h(e)}$.

هذا البرهان هو بناء لدالة تكرارية جزئية تنفذ مُركِّب Y.

وظيفة${\displaystyle F}$بحيث${\displaystyle \varphi _{e}\not \simeq \varphi _{F(e)}}$للجميع${\displaystyle e}$يُطلق عليها اسم "خالية من النقطة الثابتة" . تُبيّن نظرية النقطة الثابتة أنه لا توجد دالة قابلة للحساب كليًا خالية من النقطة الثابتة، ولكن توجد العديد من الدوال غير القابلة للحساب الخالية من النقطة الثابتة. ينص معيار اكتمال أرسلانوف على أن درجة تورينج الوحيدة القابلة للتعداد التكراري التي تحسب دالة خالية من النقطة الثابتة هي 0 ′ ، وهي درجة مسألة التوقف . ^{[ 5 ]}

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

من الأمثلة الكلاسيكية التي تستخدم نظرية الاستدعاء الذاتي الثانية الدالة${\displaystyle Q(x,y)=x}$. الفهرس المقابل${\displaystyle p}$في هذه الحالة، ينتج عنها دالة قابلة للحساب تُخرج فهرسها الخاص عند تطبيقها على أي قيمة. ^{[ 8 ]} وعند التعبير عنها كبرامج حاسوبية، تُعرف هذه الفهارس باسم "كوينز" .

يوضح المثال التالي في لغة ليسب كيف${\displaystyle p}$يمكن استنتاج النتيجة بشكل فعال من الدالة${\displaystyle Q}$الدالة الموجودةs11 في الكود هي الدالة التي تحمل هذا الاسم والتي تم إنتاجها بواسطة نظرية Smn   .

Qيمكن تغييرها إلى أي دالة ذات وسيطين.

( setq Q ' ( lambda ( x y ) x )) ( setq s11 ' ( lambda ( f x ) ( list 'lambda ' ( y ) ( list f x 'y )))) ( setq n ( list 'lambda ' ( x y ) ( list Q ( list s11 'x 'x ) 'y ))) ( setq p ( eval ( list s11 n n )))

ينبغي أن تكون نتائج التعبيرات التالية متطابقة.${\displaystyle \varphi }$p(nil)

( eval ( list p nil ))

Q(p, nil)

( eval ( list Q p nil ))

لنفترض أن${\displaystyle g}$و${\displaystyle h}$هي دوال قابلة للحساب بالكامل تُستخدم في تعريف تكراري لدالة ما${\displaystyle f}$:

${\displaystyle f(0,y)\simeq g(y),}$

${\displaystyle f(x+1,y)\simeq h(f(x,y),x,y),}$

يمكن استخدام نظرية الاستدعاء الذاتي الثانية لإثبات أن هذه المعادلات تُعرّف دالة قابلة للحساب، حيث لا يشترط مفهوم قابلية الحساب، ظاهريًا، السماح بالتعريفات الاستدعائية (على سبيل المثال، يمكن تعريفه بواسطة الاستدعاء الذاتي μ ، أو بواسطة آلات تورينج ). ويمكن تحويل هذا التعريف الاستدعائي إلى دالة قابلة للحساب.${\displaystyle \varphi _{F}(e,x,y)}$هذا يفترض${\displaystyle e}$هو فهرس لنفسه، لمحاكاة التكرار:

${\displaystyle \varphi _{F}(e,0,y)\simeq g(y),}$

${\displaystyle \varphi _{F}(e,x+1,y)\simeq h(\varphi _{e}(x,y),x,y).}$

تُثبت نظرية الاستدعاء الذاتي وجود دالة قابلة للحساب${\displaystyle \varphi _{f}}$بحيث${\displaystyle \varphi _{f}(x,y)\simeq \varphi _{F}(f,x,y)}$. هكذا ${\displaystyle f}$يفي بالتعريف التكراري المعطى.

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

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

ضع في اعتبارك المعادلات التكرارية لدالة المضروب f :$${\displaystyle {\begin{aligned}&f(0)=1\\&f(n+1)=(n+1)\cdot f(n)\end{aligned}}}$$سيحتوي عامل الاستدعاء الذاتي المقابل Φ على معلومات تُحدد كيفية الوصول إلى القيمة التالية لـ f من القيمة السابقة. ومع ذلك، سيُحدد عامل الاستدعاء الذاتي في الواقع الرسم البياني لـ f . أولًا، سيحتوي Φ على الزوج${\displaystyle (\varnothing ,(0,1))}$يشير هذا إلى أن f (0) هي 1 بشكل قاطع، وبالتالي فإن الزوج (0،1) موجود في الرسم البياني لـ f .

بعد ذلك، لكل من n و m ، ستحتوي Φ على الزوج${\displaystyle (\{(n,m)\},(n+1,(n+1)\cdot m))}$يشير هذا إلى أنه إذا كانت f ( n ) تساوي m ، فإن f ( n +1) تساوي ( n +1) m ، وبالتالي فإن الزوج ( n +1, ( n +1) m ) يقع ضمن تمثيل f البياني . على عكس الحالة الأساسية f (0) = 1 ، يتطلب عامل الاستدعاء الذاتي بعض المعلومات حول f ( n ) قبل تحديد قيمة f ( n +1) .

تنص نظرية الاستدعاء الذاتي الأولى (وتحديداً الجزء 1) على وجود مجموعة F بحيث يكون Φ( F ) = F. ستتكون المجموعة F بالكامل من أزواج مرتبة من الأعداد الطبيعية، وستكون الرسم البياني لدالة المضروب f ، كما هو مطلوب.

يضمن تقييد المعادلات التكرارية التي يمكن إعادة صياغتها كمؤثرات تكرارية أن المعادلات التكرارية تُعرّف بالفعل نقطة ثابتة صغرى . على سبيل المثال، لننظر إلى مجموعة المعادلات التكرارية التالية:$${\displaystyle {\begin{aligned}&g(0)=1\\&g(n+1)=1\\&g(2n)=0\end{aligned}}}$$لا توجد دالة g تحقق هذه المعادلات، لأنها تستلزم g (2) = 1 وتستلزم أيضًا g (2) = 0. وبالتالي، لا توجد نقطة ثابتة g تحقق هذه المعادلات التكرارية. من الممكن إنشاء عامل تعداد يُطابق هذه المعادلات، ولكنه لن يكون عاملًا تكراريًا.

يُمكن إثبات الجزء الأول من نظرية الاستدعاء الذاتي الأولى بتكرار عامل التعداد Φ بدءًا من المجموعة الفارغة . أولًا، يتم إنشاء متتالية F _{k ، لـ}${\displaystyle k=0,1,\ldots }$ليكن F₀ المجموعة _{الفارغة . بالاستمرار في الاستقراء ،} لكل k _، ليكن Fₖ₊₁${\displaystyle F_{k}\cup \Phi (F_{k})}$وأخيرًا، يُعتبر F${\textstyle \bigcup F_{k}}$يتألف الجزء المتبقي من البرهان من التحقق من أن F قابلة للتعداد بشكل متكرر وأنها أصغر نقطة ثابتة لـ Φ. يتوافق التسلسل F _k المستخدم في هذا البرهان مع سلسلة كلين في برهان نظرية كلين للنقطة الثابتة .

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

بالمقارنة مع نظرية التكرار الثانية، تُنتج نظرية التكرار الأولى استنتاجًا أقوى، ولكن فقط عند تحقق فرضيات أضيق. يستخدم روجرز مصطلح " نظرية التكرار الضعيفة" لنظرية التكرار الأولى، و "نظرية التكرار القوية" لنظرية التكرار الثانية. ^{[ 3 ]}

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

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