الاستدعاء الذاتي لسلسلة القيم

في نظرية الحوسبة ، يُعدّ التكرار باستخدام مسار القيم أسلوبًا لتعريف الدوال العددية باستخدام التكرار . في تعريف الدالة f باستخدام التكرار باستخدام مسار القيم، تُحسب قيمة f ( n ) من المتتالية.${\displaystyle \langle f(0),f(1),\ldots ,f(n-1)\rangle }$.

إن إمكانية تحويل هذه التعريفات إلى تعريفات باستخدام شكل أبسط من الاستدعاء الذاتي تُستخدم غالبًا لإثبات أن الدوال المعرفة باستخدام الاستدعاء الذاتي لسلسلة القيم هي دوال استدعاء ذاتي بدائية . على عكس الاستدعاء الذاتي لسلسلة القيم، في الاستدعاء الذاتي البدائي، لا يتطلب حساب قيمة دالة سوى القيمة السابقة لها؛ على سبيل المثال، بالنسبة لدالة استدعاء ذاتي بدائية أحادية الرتبة g ، تُحسب قيمة g ( n +1) من g ( n ) و n فقط .

يتم تعريف دالة المضروب n ! بشكل متكرر بواسطة القواعد

${\displaystyle 0!=1,}$

${\displaystyle (n+1)!=n!(n+1).}$

هذا الاستدعاء التكراري هو استدعاء تكراري أولي لأنه يحسب القيمة التالية ( n + 1)! للدالة بناءً على قيمة n والقيمة السابقة n ! للدالة. من ناحية أخرى، تُعرَّف الدالة Fib( n )، التي تُعيد العدد النوني من متتالية فيبوناتشي ، بمعادلات الاستدعاء التكراري التالية.

${\displaystyle Fib(0)=0,}$

${\displaystyle Fib(1)=1,}$

${\displaystyle Fib(n+2)=Fib(n+1)+Fib(n).}$

لحساب Fib( n +2)، يلزم معرفة القيمتين الأخيرتين لدالة Fib. وأخيرًا، لننظر في الدالة g المعرفة بمعادلات التكرار.

${\displaystyle g(0)=0,}$

${\displaystyle g(n+1)=\sum _{i=0}^{n}g(i)^{ni}.}$

لحساب g ( n +1) باستخدام هذه المعادلات، يجب حساب جميع القيم السابقة لـ g ؛ فليس هناك عدد محدد وثابت من القيم السابقة يكفي عمومًا لحساب g . تُعدّ الدالتان Fib و g مثالين على الدوال المعرفة بواسطة التكرار في مسار القيم.

بشكل عام، تُعرَّف الدالة f بواسطة التكرار ذي مسار القيم إذا كانت هناك دالة تكرارية أولية ثابتة h بحيث يكون لكل n ،

${\displaystyle f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )}$

أين${\displaystyle \langle f(0),f(1),\ldots ,f(n-1)\rangle }$هو رقم غودل الذي يرمز إلى التسلسل المشار إليه. على وجه الخصوص

${\displaystyle f(0)=h(0,\langle \rangle )}$

تُحدد القيمة الابتدائية للتكرار. قد تختبر الدالة h وسيطها الأول لتوفير قيم ابتدائية صريحة، على سبيل المثال، بالنسبة لـ Fib، يمكن استخدام الدالة المُعرَّفة بواسطة

${\displaystyle h(n,s)={\begin{cases}n&{\text{if }}n<2\\s[n-2]+s[n-1]&{\text{if }}n\geq 2\end{cases}}}$

حيث يشير s [ ​​i ] إلى استخراج العنصر i من تسلسل مشفر s ؛ ومن السهل ملاحظة أن هذه دالة تكرارية بدائية (بافتراض استخدام ترقيم غودل المناسب).

لتحويل تعريف باستخدام التكرار ذي مسار القيم إلى تكرار أولي، تُستخدم دالة مساعدة. لنفترض أننا نريد الحصول على

${\displaystyle f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )}$.

لتعريف f باستخدام الاستدعاء الذاتي الأولي، قم أولاً بتعريف دالة مسار القيم المساعدة التي يجب أن تحقق

${\displaystyle {\bar {f}}(n)=\langle f(0),f(1),\ldots ,f(n-1)\rangle }$

حيث يُعتبر الجانب الأيمن ترقيم غودل للتسلسلات .

هكذا${\displaystyle {\bar {f}}(n)}$تُشفّر الدالة أول n قيمة من f .${\displaystyle {\bar {f}}}$يمكن تعريفها بواسطة الاستدعاء الذاتي البدائي لأن${\displaystyle {\bar {f}}(n+1)}$يتم الحصول عليها عن طريق الإلحاق بـ${\displaystyle {\bar {f}}(n)}$العنصر الجديد${\displaystyle h(n,{\bar {f}}(n))}$:

${\displaystyle {\bar {f}}(0)=\langle \rangle }$،

${\displaystyle {\bar {f}}(n+1)={\mathit {append}}(n,{\bar {f}}(n),h(n,{\bar {f}}(n))),}$

حيث تقوم الدالة append ( n , s , x ) بحساب، كلما مثّلت s متتالية طولها n ، متتالية جديدة t طولها n + 1 بحيث يكون t [ n ] = x و t [ i ] = s [ i ] لجميع i < n . هذه دالة تكرارية بدائية، بافتراض ترقيم غودل المناسب؛ يُفترض أن h دالة تكرارية بدائية في البداية. وبالتالي، يمكن كتابة علاقة التكرار على النحو التالي:

${\displaystyle {\bar {f}}(n+1)=g(n,{\bar {f}}(n))}$

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

${\displaystyle g(i,j)={\mathit {append}}(i,j,h(i,j)),}$

منح${\displaystyle {\bar {f}}}$يمكن تعريف الدالة الأصلية f بواسطة${\displaystyle f(n)={\bar {f}}(n+1)[n]}$وهذا يدل على أنها أيضاً دالة تكرارية بدائية.

في سياق الدوال التكرارية الأولية ، من الملائم وجود وسيلة لتمثيل المتتاليات المنتهية من الأعداد الطبيعية كأعداد طبيعية مفردة. إحدى هذه الطرق، وهي ترميز غودل ، تمثل متتالية من الأعداد الصحيحة الموجبة.${\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle }$مثل

${\displaystyle \prod _{i=0}^{k}p_{i}^{n_{i}}}$،

حيث يمثل pᵢ العدد الأولي رقم i . _ويمكن إثبات أنه باستخدام هذا التمثيل، فإن العمليات العادية على المتتاليات هي عمليات بدائية تكرارية. وتشمل هذه العمليات

• تحديد طول التسلسل،
• استخراج عنصر من سلسلة معينة بناءً على فهرسه،
• دمج سلسلتين.

باستخدام هذا التمثيل للمتتاليات، يمكن ملاحظة أنه إذا كانت الدالة h ( m ) دالة تكرارية أولية، فإن الدالة

${\displaystyle f(n)=h(\langle f(0),f(1),f(2),\ldots ,f(n-1)\rangle )}$.

وهي أيضًا بدائية تكرارية.

عندما يكون التسلسل${\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle }$يُسمح بتضمين الأصفار، ويتم تمثيلها بدلاً من ذلك على النحو التالي:

${\displaystyle \prod _{i=0}^{k}p_{i}^{(n_{i}+1)}}$،

مما يجعل من الممكن تمييز رموز التسلسلات${\displaystyle \langle 0\rangle }$و${\displaystyle \langle 0,0\rangle }$.

لا يمكن تحويل كل تعريف تكراري إلى تعريف تكراري أولي. ومن الأمثلة المعروفة دالة أكرمان ، التي تأخذ الشكل A ( m , n ) ومن المؤكد أنها ليست تكرارية أولية.

في الواقع، تعتمد كل قيمة جديدة A ( m +1, n +1) على سلسلة القيم المُعرَّفة سابقًا A ( i , j )، ولكن القيمتين i و j اللتين يجب أن تُضمَّن فيهما A ( i , j ) في هذه السلسلة تعتمدان بدورهما على القيم المحسوبة سابقًا للدالة؛ أي ( i , j ) = ( m , A ( m +1, n )). وبالتالي، لا يمكن ترميز سلسلة القيم المحسوبة سابقًا بطريقة تكرارية بدائية كما هو مُقترح أعلاه (أو على الإطلاق، إذ تبيَّن أن هذه الدالة ليست تكرارية بدائية).

• هينمان، بي جي، 2006، أساسيات المنطق الرياضي ، إيه كيه بيترز.
• أوديفردي، بي جي ، 1989، نظرية الاستدعاء الكلاسيكية ، نورث هولاند؛ الطبعة الثانية، 1999.