دالة تكرارية أولية

استُخدم مصطلح "ابتدائي" لأول مرة من قِبل لازلو كالمار في سياق نظرية الحوسبة . ^{[ 1 ] [ 2 ]} عرّف كالمار فئة الدوال الاسترجاعية الابتدائية ( "دوال كالمار الابتدائية" ) على أنها مجموعة فرعية من الدوال الاسترجاعية الأولية ، وتحديدًا تلك التي يمكن حسابها باستخدام مجموعة محدودة من العمليات مثل التركيب، والمجاميع المحدودة، والمنتجات المحدودة. ^{[ 3 ]} لا تنمو هذه الدوال أسرع من سلسلة أسية ذات ارتفاع ثابت (على سبيل المثال،${\displaystyle O(2^{2^{n}})}$ليست كل الدوال التكرارية الأولية دوالًا ابتدائية؛ على سبيل المثال، تنمو دالة التكرار الثلاثي بسرعة كبيرة جدًا بحيث لا يمكن إدراجها في فئة الدوال الابتدائية. تتوافق الدوال التكرارية الابتدائية مع الفئة${\displaystyle {\mathcal {E}}^{3}}$من التسلسل الهرمي Grzegorczyk . ^{[ 4 ]}

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

${\displaystyle {\mathsf {ELEMENTARY}}=\bigcup _{k\in \mathbb {N} }{\text{DTIME}}(\exp ^{k}(n^{c}))}$

أين${\displaystyle \exp ^{k}(n)}$يشير إلى برج أسي من المستوى k (على سبيل المثال،${\displaystyle 2^{2^{\cdot ^{\cdot ^{n}}}}}$).

على الرغم من أن الاسم يأتي من نفس الأصل التاريخي، إلا أن فئة التعقيد ELEMENTARY تتعامل مع مشاكل القرار ووقت تشغيل آلة تورينج، بدلاً من الوظائف الكلية.

تُعرَّف الدوال الاسترجاعية الأولية بنفس تعريفات الدوال الاسترجاعية البدائية ، باستثناء استبدال الاسترجاع البدائي بالجمع المحدود والضرب المحدود. ^{[ 1 ] [ 3 ] [ 5 ]} تعمل جميع الدوال على الأعداد الطبيعية . الدوال الأساسية، وجميعها دوال استرجاعية أولية، هي:

1. دالة الصفر . تُرجع صفرًا:${\displaystyle f(x)=0}$.
2. الوظيفة اللاحقة :${\displaystyle f(x)=x+1}$غالباً ما يُشار إلى ذلك بـ${\displaystyle S}$كما في${\displaystyle S(x)}$من خلال التطبيق المتكرر لدالة لاحقة، يمكن تحقيق الجمع.
3. دوال الإسقاط : تُستخدم هذه الدوال لتجاهل الوسائط. على سبيل المثال،${\displaystyle f(a,b)=a}$هي دالة إسقاط.
4. دالة الطرح :${\displaystyle f(x,y)=\max(xy,0)}$تُستخدم هذه الدالة لتعريف الشروط والتكرار.

انطلاقاً من هذه الوظائف الأساسية، يمكننا بناء وظائف تكرارية أولية أخرى.

1. التركيب : تطبيق قيم من دالة تكرارية أولية كمعامل لدالة تكرارية أولية أخرى.${\displaystyle f}$يُعرَّف بأنه التركيب${\displaystyle f(x_{1},\ldots ,x_{n})=h{\bigl (}g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m}(x_{1},\ldots ,x_{n}){\bigr )}}$تكون عملية الاستدعاء الذاتي الأولية إذا${\displaystyle h}$هي عملية تكرارية أولية وكل${\displaystyle g_{i}}$هي دالة تكرارية أولية.
2. المجموع المحدود :${\displaystyle f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$تكون عملية الاستدعاء الذاتي الأولية إذا${\displaystyle g}$هي دالة تكرارية أولية.
3. المنتج المقيد :${\displaystyle f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$تكون عملية الاستدعاء الذاتي الأولية إذا${\displaystyle g}$هي دالة تكرارية أولية.

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

بصورة أكثر رسمية، لنفترض:

• ${\displaystyle f(x_{1},\dots ,x_{k})}$هو${\displaystyle k}$الدالة -ary، و
• ${\displaystyle g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n})}$نكون${\displaystyle n}$الدوال من الرتبة -ary.

ثم ينتج عن تراكب هذه الدوال دالة جديدة${\displaystyle n}$الدالة -ary:

${\displaystyle h(x_{1},\dots ,x_{n})=f(g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n}))}$.

تتطابق فئة الدوال الاسترجاعية الأولية مع الإغلاق تحت التراكب لدوال الإسقاط وإحدى مجموعات الدوال الأولية التالية:

• ${\displaystyle \{n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;2^{n}\}}$^{[ 6 ]}
• ${\displaystyle \{n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;nm,\;n^{m}\}}$^{[ 7 ]}
• ${\displaystyle \{n+m,\;n{\bmod {m}},\;n^{2},\;2^{n}\}}$^{[ 8 ]}
• ${\displaystyle \{n+m,\;n{\bmod {m}},\;2^{n}\}}$^{[ 9 ]}

أين${\displaystyle n\mathbin {\dot {-}} m=\max(nm,0)}$يشير إلى الطرح المقتطع ( monus ).

في عام 2025، أثبت كل من ميهاي برونيسكو ولورينزو ساوراس-ألتوزارا وجوزيف إم. شونيا أن فئة الدوال الأولية لكالمار يمكن توليدها استقرائيًا من الجمع (${\displaystyle n+m}$باقي القسمة (${\displaystyle n{\bmod {m}}}$) والأسس ذات الأساس 2 (${\displaystyle 2^{n}}$وقد حسّنوا النتائج السابقة التي توصل إليها مازنتي ^{[ 7 ]} ومارشنكوف ^{[ 8 ]} . كما أثبتوا أن أساس الاستبدال المحدد بهذه العمليات الثلاث هو أساس أدنى ^{[ 10 ]} . ويبقى السؤال مفتوحًا حول ما إذا كان${\displaystyle \{n+m,\;\lfloor n/m\rfloor ,\;2^{n}\}}$وهو أساس بديل.

المثال 1

يترك $${\displaystyle f(a,b)=a{\bmod {b}},\quad g_{1}(n)=2^{n+n},\quad g_{2}(n)=2^{n}+n\,.}$$ ثم الدالة $${\displaystyle h(n)=f(g_{1}(n),g_{2}(n))=2^{n+n}{\bmod {(}}2^{n}+n)}$$ تُعرّف الدالة التربيعية${\displaystyle h(n)=n^{2}}$عن طريق التراكب فقط. ^{[ 11 ]} يوضح هذا كيف يمكن التعبير عن وظائف مثل التربيع باستخدام الجمع فقط، وباقي العدد الصحيح، والأس ذي الأساس 2 من خلال التراكب، دون الحاجة إلى استدعاء ذاتي صريح .

المثال 2

ومن الأمثلة الأخرى على الدوال التكرارية الأولية دالة دلتا كرونكر$${\displaystyle \delta _{ij}=2^{(2^{i}{\bmod {(}}2^{j}+1))+(2^{j}{\bmod {(}}2^{i}+1)){\bmod {(}}2^{i}+2^{j})}{\bmod {2}}\,,}$$ وهو ما يرضي${\displaystyle \delta _{ij}=1}$لو${\displaystyle i=j}$و${\displaystyle 0}$خلاف ذلك.

أمثلة أخرى

${\displaystyle x\mathbin {\dot {-}} y=((2^{x+y}+x){\bmod {(}}2^{x+y}+y)){\bmod {(}}2^{x+y}+x)}$[ ^{12 ]​}

${\displaystyle 2xy=(x+y)^{2}\mathbin {\dot {-}} (x^{2}+y^{2})}$[ ^{13 ]​}

${\displaystyle \lfloor x/y\rfloor =(2(x+1)(x\mathbin {\dot {-}} (x{\bmod {y}}))){\bmod {(}}2(x+1)y\mathbin {\dot {-}} 1)}$[ ^{14 ]​}

${\displaystyle xy=\lfloor 2xy/2\rfloor }$[ ^{15 ]​}

${\displaystyle x^{y}=2^{(xy+x+1)y}{\bmod {(}}2^{xy+x+1}\mathbin {\dot {-}} x)}$[ ^{16 ]​}

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

تُعرف الدوال التكرارية الأولية الدنيا أيضًا باسم دوال سكوليم الأولية. ^{[ 17 ] [ 18 ]}

بينما تتمتع الدوال التكرارية الأولية بنمو محتمل يتجاوز النمو الأسي، فإن الدوال التكرارية الأولية الأدنى تتمتع بنمو متعدد الحدود.

تُوصَف فئة الدوال الأولية الدنيا من حيث تركيب الدوال البسيطة، على غرار ما هو مُوَصَّل للدوال الأولية. ^{[ 18 ] [ 19 ]} أي أن الدالة المحدودة بمتعدد الحدود تكون أولية دنيا إذا وفقط إذا أمكن التعبير عنها باستخدام تركيب الدوال التالية: الإسقاطات،${\displaystyle n+1}$،${\displaystyle nm}$،${\displaystyle n\mathbin {\dot {-}} m}$،${\displaystyle n\wedge m}$،${\displaystyle \lfloor n/m\rfloor }$دالة أسية واحدة (${\displaystyle 2^{n}}$أو${\displaystyle n^{m}}$) مع القيد التالي على بنية الصيغ: لا يمكن أن تحتوي الصيغة على أكثر من طابقين بالنسبة للأس (على سبيل المثال،${\displaystyle xy(z+1)}$يتكون من طابق واحد،${\displaystyle (x+y)^{yz+x}+z^{x+1}}$يتكون من طابقين،${\displaystyle 2^{2^{x}}}$(يحتوي على 3 طوابق). هنا${\displaystyle n\wedge m}$هي عملية AND منطقية بين n و m .

• ابتدائي
• الحساب الوظيفي الأساسي
• دالة تكرارية بدائية
• التسلسل الهرمي لغريغورتشيك
• حلقة (لغة برمجة)
• وقت الخبرة