عمليه زايده

عمليه زايده

لنك عشوائى
تصانيف	شوف كمان
مصطلحات | مهن جهاز| جوايز كل الليستات	زامبا (فن)

متتالية العمليات الزايده فى الرياضيات ، معروفه بأنها متتالية لانهائية من العمليات الحسابية (بتتسمما العمليات الزايده فى السياق ده ) تبتدى بعملية أحادية ( دالة الخلف لما n = 0). وتستمر المتتالية بالعمليات الثنائية : الجمع ( n = 1)، والضرب ( n = 2)، والرفع للأس ( n = 3). بعد ذلك، تستمر المتتالية بعمليات ثنائية تانيه تتجاوز الرفع للأس، باستخدام خاصية التجميع من اليمين . بالنسبة للعمليات اللى تتجاوز الرفع للأس، يُطلق روبن غودستين على العنصر النونى فى دى المتتالية اسم "العدد n" نسبةً لالبادئة اليونانية n متبوعةً باللى بعد كده "-ation" ( زى "الترتيل" ( n = 4)، و"الخماسي" ( n = 5)، و"السداسي" ( n = 6)، إلخ) ، ويمكن كتابتها باستخدام n − 2 سهم فى تدوين كنوت للأسهم المتجهة للأعلى . ممكن فهم كل عملية زايده بشكل متكرر حسب العملية السابقة ليها من خلال:

$a[n]b=\underbrace {a[n-1](a[n-1](a[n-1](\cdots a[n-1](a[n-1](a[n-1]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a},\quad n\geq 2$

ممكن تعريفها كمان حسب جزء قاعدة الاستدعاء الذاتى من التعريف، زى ما هو الحال فى نسخة السهم العلوى لدالة أكرمان الخاصة بكنوث:

$a[n]b=a[n-1]\left(a[n]\left(b-1\right)\right),\quad n\geq 1$

يمكن استخدام ده لعرض أعداد اكبر بكتير من اللى ممكن عرضها باستخدام الترميز العلمى ، زى عدد سكيوز وعدد غوغولبلكسبلكس (مثل). $50[50]50$ اكبر بكتير من عدد سكيوز وعدد غوغولبلكسبلكس)، لكن هناك بعض الأعداد اللى مايقدروش لحد إظهارها بسهولة، زى عدد جراهام و TREE(3) .

قاعدة التكرار دى منتشرة فى كتير من أنواع العمليات الزايده .

تعريف

تسلسل العمليات الزايده هو تسلسل العمليات الثنائية $H_{n}\colon (\mathbb {N} _{0})^{2}\rightarrow \mathbb {N} _{0}$ تم تعريفها بشكل متكرر على النحو التالي: $$H_{n}(a,b)={\begin{cases}b+1&{\text{if }}n=0\\a&{\text{if }}n=1{\text{ and }}b=0\\0&{\text{if }}n=2{\text{ and }}b=0\\1&{\text{if }}n\geq 3{\text{ and }}b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{otherwise}}\end{cases}}.$$ بالنسبة لـ n = 0، 1، 2، 3، يُعيد التعريف ده إنتاج العمليات الحسابية الأساسية اللى بعد كده : عملية اللاحق (وهى عملية أحادية)، والجمع ، والضرب ، و الأس ، على التوالي، كاللى جاى: $${\begin{aligned}H_{0}(a,b)&=b+1,\\H_{1}(a,b)&=a+b,\\H_{2}(a,b)&=a\times b,\\H_{3}(a,b)&=a^{b}\end{aligned}}$$ لكل عددين صحيحين غير سالبين a و b . ممكن بالتالى اعتبار العمليات الزايده إجابة على السؤال "ما التالي؟" فى سلسلة الدوال اللى تبتدى باللاحق، بعدين الجمع، بعدين الضرب، بعدين الأسس. فا زى ما بييتعرف ضرب الأعداد الصحيحة بأنه جمع متكرر، وبييتعرف رفع الأعداد الصحيحة بأنه ضرب متكرر، العملية الزايده اللى بعد كده ، وهى التكرار ، بتتعرف بأنها رفع الأعداد الصحيحة لأس بشكل متكرر؛ زى ، $H_{4}(a,3)=\operatorname {tetration} (a,3)=a^{a^{a}}$ هو برج طاقة مكون من 3 a ، و $H_{4}(a,4)=\operatorname {tetration} (a,4)=a^{a^{a^{a}}}$ وبالمثل، بتتعرف عملية التكرار الخامسة، هيا عملية التكرار المتسلسل، عن طريق التكرار المتسلسل المتكرر، بحيث $H_{5}(a,3)=\operatorname {tetration} (a,\operatorname {tetration} (a,a))$ .

تُشار ساعات لمعلمات التسلسل الهرمى للعمليات الزايده بمصطلح الأس المماثل لها؛ علشان كده a هو الأساس ، وb هو الأس (أو الأس الفائق )، و n هو الرتبة (أو الدرجة ). بشكل عام، $H_{n}(a,b)$ ممكن قراءتها على أنها " النسخة الثانية من أ "، بحيث $H_{4}(7,9)$ تُقرأ على أنها "التكرار التاسع للعدد 7"، و $H_{123}(456,789)$ تُقرأ على أنها "الإصدار 789 من 456".

فيه طريقة بديلة لكتابة العمليات الزايده هيا الترميز المختصر. $a[n]b$ ل$H_{n}(a,b)$ فى الصيغة دى ، يُرمز لعملية الأسس بـ $a[3]b=a^{b}$ ، يُشار لالمعايرة بـ $a[4]b$ (للسبب ده $a[4]3=a^{a^{a}}$ ، يُشار للنضج بـ $a[5]b$ وهكذا. ممكن كمان التعبير عن العمليات الزايده باستخدام تدوين كنوت للسهم العلوى . فى ده التدوين، $a\uparrow b$ تمثل دالة الأس $a^{b}$ ، $a\uparrow \uparrow b$ يمثل التحلل، $a\uparrow \uparrow \uparrow b$ أو $a\uparrow ^{3}b$ يمثل الخماسى $a[5]b$ و بشكل أعم $H_{n}(a,b)=a\uparrow ^{n-2}b$ ل$n\geq 0.$ وثمة بديل آخر هو تدوين كونواى للأسهم المتسلسلة . فى ده التدوين، يكون عند المرء $H_{n}(a,b)=a[n]b=a\rightarrow b\rightarrow n-2$ ، بحيث (زى ) $a[5]b=a\rightarrow b\rightarrow 3$

أمثلة

السبع عمليات الزايده الأولى (من 0 ل6) (يتم تعريف 0⁰ على أنه 1).

n	Operation, Hn(a, b)	Definition	Names	Domain
0	$b+1$ or $a[0]b$	$\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}+1$	Increment, successor. zeration, hyper0	Arbitrary
1	$a+b$ or $a[1]b$	$a+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}$	Addition. hyper1
2	$a\times {b}$ or $a[2]b$	$\underbrace {a+a+a+\cdots +a+a+a} _{\displaystyle b{\mbox{ copies of }}a}$	Multiplication. hyper2
3	$a^{b}$ or $a[3]b$	$\underbrace {a\times a\times a\times \;\cdots \;\times a\times a\times a} _{\displaystyle b{\mbox{ copies of }}a}$	Exponentiation. hyper3	b real, with some multivalued extensions to complex numbers
4	$^{b}a$ or $a[4]b$	$\underbrace {a^{a^{\cdot ^{\cdot ^{a}}}}} _{\displaystyle b{\mbox{ copies of }}a}$	Tetration. hyper4	a ≥ 0 or an integer, b an integer ≥ −1 (with some proposed extensions)
5	$_{b}a$ or $a[5]b$	$\underbrace {a[4](a[4](a[4](\cdots [4](a[4](a[4]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}$	Pentation, hyper5	a, b integers ≥ −1
6	$a[6]b$	$\underbrace {a[5](a[5](a[5](\cdots [5](a[5](a[5]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}$	Hexation, hyper6

حالات خاصة

H _n (0, b ) =

ب + 1، لما ن = 0

ب ، لما ن = 1

0، لما n = 2

1، لما n = 3 و b = 0

0، لما n = 3 و b > 0

1، لما يكون n > 3 ويكون b زوجى (بما فيها 0)

0، لما يكون n > 3 ويكون b فردى

H _n (1, b ) =

ب ، لما ن = 2

1، لما يكون n ≥ 3

H _n ( a, 0) =

0، لما n = 2

1، لما يكون n = 0، أو n ≥ 3

أ ، لما ن = 1

H _n ( a, 1) =

2، لما n = 0

أ + 1، لما ن = 1

أ ، لما يكون ن ≥ 2

H _n ( a, a ) =

H _n+1 ( a, 2 )، لما n ≥ 1

H _n ( a, −1) =

0، لما n = 0، أو n ≥ 4

a − 1، لما n = 1

- أ ، لما ن = 2

n = 3

H _n (2, 2) =

3، لما n = 0

4، لما يكون n ≥ 1، ممكن إثبات ذلك بسهولة بشكل متكرر.

تاريخ

واحدة من أوائل المناقشات حول العمليات الزايده كانت هيا اللى عملها ألبرت بينيت سنة 1914، و اللى طوّر فيها جزء من نظرية العمليات الزايده التبادلية. بعد حوالى 12 سنه ، اتعرف ويلهلم أكرمان الدالة $\phi (a,b,n)$ ، و هو ما يشبه لحد ما تسلسل العمليات الزايده . فى بحثه المنشور سنة 1947، قدّم روبن غودستين تسلسل محددًا من العمليات اللى معروفه دلوقتى بالعمليات الزايده ، واقترح كمان الاسامى اليونانية زى tetration وpentation، وما لذلك، للعمليات الموسعة اللى تتجاوز الأسس (لأنها تُقابل المؤشرات 4 و5، وما لذلك). زى ، كدالة ذات 3 وسائط، $G(n,a,b)=H_{n}(a,b)$ بيتبص لسلسلة العمليات الزايده ككل على أنها نسخة من دالة أكرمان الأصلية $\phi (a,b,n)$ — تكرارى لكن مش تكرارى بدائى — كما عدّله جودستين لدمج دالة الخلف البدائية مع العمليات الحسابية الأساسية الثلاث التانيه ( الجمع والضرب و الأس )، ولجعل امتداد دى العمليات اكتر سلاسة لما بعد الأس.

دالة أكرمان الأصلية ذات الوسائط التلاته $\phi$ يستخدم نفس قاعدة التكرار اللى تستخدمها نسخة غودستين (أى تسلسل العمليات الزايده )، ولكنه يختلف عنها فى جانبين. الاول ، $\phi (a,b,n)$ بييحدد تسلسل العمليات بدايه من الجمع ( n = 0) بدل دالة التابع ، بعدين الضرب ( n = 1)، بعدين الأس ( n = 2)، وهكذا. ثانى، الشروط الابتدائية لـ $\phi$ ينتج عنه $\phi (a,b,3)=G(4,a,b+1)=a[4](b+1)$ و علشان كده، يختلف ده عن العمليات الزايده اللى تتجاوز الأسس. تكمن أهمية b + 1 فى التعبير السابق فى أن $\phi (a,b,3)$ = $a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}$ حيث يحسب b عدد العمليات (الأسس)، بدل حساب عدد المعاملات ("a") كما يفعل b فى $a[4]b$ و كده بالنسبة للعمليات ذات المستوى الأعلى. (شوف مقالة دالة أكرمان لمزيد من التفاصيل.)

رموز

الرموز المستخدمة فى العمليات الزايده .

Name	Notation equivalent to $H_{n}(a,b)$	Comment
Knuth's up-arrow notation	$a\uparrow ^{n-2}b$	Used by Knuth (for n ≥ 3), and found in several reference books.
Hilbert's notation	$\phi _{n}(a,b)$	Used by David Hilbert.
Goodstein's notation	$G(n,a,b)$	Used by Reuben Goodstein.
Original Ackermann function	${\begin{matrix}\phi (a,b,n-1)\ {\text{ for }}1\leq n\leq 3\\\phi (a,b-1,n-1)\ {\text{ for }}n\geq 4\end{matrix}}$	Used by Wilhelm Ackermann (for n ≥ 1)
Ackermann–Péter function	$A(n,b-3)+3\ {\text{for }}a=2$	This corresponds to hyperoperations for base 2 (a = 2)
Nambiar's notation	$a\otimes ^{n-1}b$	Used by Nambiar (for n ≥ 1)
Superscript notation	$a{}^{(n)}b$	Used by Robert Munafo.
Subscript notation (for lower hyperoperations)	$a{}_{(n)}b$	Used for lower hyperoperations by Robert Munafo.
Operator notation (for "extended operations")	$aO_{n-1}b$	Used for lower hyperoperations by John Doner and Alfred Tarski (for n ≥ 1).
Square bracket notation	$a[n]b$	Used in many online forums; convenient for ASCII.
Conway chained arrow notation	$a\to b\to (n-2)$	Used by John Horton Conway (for n ≥ 3)

متغير يبتدى من a

ويلهلم أكرمان سنة 1928، اتعرف دالة ذات 3 وسائط $\phi (a,b,n)$ اللى تطورت بالتدريج لدالة ذات وسيطين معروفه باسم دالة أكرمان . دالة أكرمان الأصلية $\phi$ كانت أقل شبهاً بالعمليات الجراحية الحديثة، لأن شروطه الأولية تبتدى بـ $\phi (a,0,n)=a$ لجميع قيم n > 2. هو كمان خصص الجمع لـ n = 0، والضرب لـ n = 1، والرفع الأسى لـ n = 2، علشان كده الشروط الأولية تنتج عمليات مختلفة تمام للرفع الأسى وما بعده.

ن	عملية	تعليق
0	$F_{0}(a,b)=a+b$
1	$F_{1}(a,b)=a\cdot b$
2	$F_{2}(a,b)=a^{b}$
3	$F_{3}(a,b)=a[4](b+1)$	شكل إزاحة من عملية التكرار . يختلف تكرار دى العملية عن تكرار عملية التكرار.
4	$F_{4}(a,b)=(x\mapsto a[4](x+1))^{b}(a)$	مش ضرورى الخلط بينها وبين التثبيط.

من الشروط الأولية التانيه اللى تم استخدامها : $A(0,b)=2b+1$ (حيث تكون القاعدة ثابتة) $a=2$ ), بسبب روزا بيتر ، اللى لا تشكل تسلسل هرمى للعمليات الزايده .

متغير يبتدى من 0

سى دبليو كلينشو و إف دبليو جيه أولفر سنة 1984، ابتدو مناقشة استخدام العمليات الزايده لمنع تجاوزات الأعداد العشرية فى الكومبيوتر. و من ساعتها ، جدد كتير من المؤلفين التانيين اهتمامهم بتطبيق العمليات الزايده على تمثيل الأعداد العشرية . (بما أن H _n ( a, b ) معرفة جميعها لما b = -1). وقت مناقشة التكرار ، افترض كلينشو و تانيين افترضو الشرط الأولى $F_{n}(a,0)=0$ وده بيعمل تسلسل هرمى آخر للعمليات الزايده . زى فى الصيغة السابقة، العملية الرابعة تُشبه لحد كبير عملية التكرار ، لكن مُزاحة بمقدار واحد.

ن	عملية	تعليق
0	$F_{0}(a,b)=b+1$
1	$F_{1}(a,b)=a+b$
2	$F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}$
3	$F_{3}(a,b)=a^{b}$
4	$F_{4}(a,b)=a[4](b-1)$	شكل إزاحة من عملية التكرار . يختلف تكرار دى العملية اختلاف كبير عن تكرار عملية التكرار.
5	$F_{5}(a,b)=\left(x\mapsto a[4](x-1)\right)^{b}(0)=0{\text{ if }}a>0$	مش ضرورى الخلط بينها وبين التثبيط.

عمليات فرطية أقل

ممكن الحصول على بديل للعمليات الزايده دى بالتقييم من اليسار لاليمين. بما أن

${\begin{aligned}a+b&=(a+(b-1))+1\\a\cdot b&=(a\cdot (b-1))+a\\a^{b}&=\left(a^{(b-1)}\right)\cdot a\end{aligned}}$

حدد (باستخدام ° أو رمز سفلى)

$a_{(n)}b=\left(a_{(n)}(b-1)\right)_{(n-1)}a$

مع

${\begin{aligned}a_{(1)}b&=a+b\\a_{(2)}0&=0\\a_{(n)}1&=a&{\text{for }}n>2\\\end{aligned}}$

دونر وتارسكى وسع المفهوم ده علشان يشمل الأعداد الترتيبية . يستخدمان الفهرس 0 بدل الفهرس 1 فى عملية الجمع. كما قاما بتوسيع الصيغ لتشمل كل عدد ترتيبى مش له سلف مباشر، و ده باستبدال b − 1 فى المعادلة السابقة بالقيمة العليا لجميع الأعداد الترتيبية الأقل من b ، ويتعاملان مع n بالمثل. نستخدم الحروف اليونانية للدلالة على أن دى أعداد ترتيبية و مش أعداد عد عادية.

${\begin{aligned}\alpha O_{0}\beta &=\alpha +\beta \\\alpha O_{\nu }\beta &=\sup \limits _{\delta <\beta ,~\mu <\nu }(\alpha O_{\nu }\delta )O_{\mu }\alpha \,.\end{aligned}}$

مع التعريفات دي، O0 هيا الجمع، و O1 هو الضرب، و O2 هو الأس. لكن O3 ما بيكوّنش "برج الأسس" بالشكل المتوقع فى العمليات الزايده (غير السفلية).[31][nb 1] بدل كده،

$\alpha O_{3}(1+\beta )=\alpha ^{\left(\alpha ^{\beta }\right)}.$

ن	عملية	تعليق
0	$F_{0}(a,b)=a+1$	زيادة، خليفة، صفر
1	$F_{1}(a,b)=a+b$
2	$F_{2}(a,b)=a\cdot b$
3	$F_{3}(a,b)=a^{b}$
4	$F_{4}(a,b)=a^{\left(a^{(b-1)}\right)}$	مش ضرورى الخلط بينها وبين التحلل الحرارى .
5	$F_{5}(a,b)=\left(x\mapsto x^{x^{(a-1)}}\right)^{b-1}(a)$	مش ضرورى الخلط بينها وبين التثبيط. يشبه عملية التحلل الحرارى .

العمليات الزايده التبادلية

ألبرت بينيت تناول العمليات الزايده التبادلية فى وقت مبكر من سنة 1914، [1] وده فى الغالب بيعتبر أقدم ملاحظة عن أى سلسلة من العمليات الزايده .

و بتتاتعرف العمليات الزايده التبادلية بقاعدة الاستدعاء الذاتى.

$F_{n+1}(a,b)=\exp(F_{n}(\ln(a),\ln(b)))$

و هيا متناظرة بالنسبة لـ a و b، وده معناه إن كل العمليات الزايده تبادلية.

المتتالية دى ما فيهاش عملية الأسس، و علشان كده ما بتكوّنش تسلسل هرمى للعمليات الزايده .

ن	عملية	تعليق
0	$F_{0}(a,b)=\ln \left(e^{a}+e^{b}\right)$	الحد الأقصى السلس ( LogSumExp )
1	$F_{1}(a,b)=a+b$
2	$F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}$	و سبب ده لخصايص اللوغاريتم .
3	$F_{3}(a,b)=a^{\ln(b)}=e^{\ln(a)\ln(b)}$	فى حقل محدود ، دى هيا عملية تبادل المفاتيح ديفي-هيلمان .
4	$F_{4}(a,b)=e^{e^{\ln(\ln(a))\ln(\ln(b))}}$	مش ضرورى الخلط بينها وبين التحلل الحرارى .

أنظمة الترقيم القائمة على تسلسل العمليات الزايده

آر إل غودستين استخدم سلسلة المؤثرات الزايده لإنشاء أنظمة ترقيم للأعداد الصحيحة اللى مشسالبة. ويمكن التعبير عن ما بيتسما بالتمثيل الوراثى الكامل للعدد الصحيح n ، عند المستوى k و الأساس b ، على النحو اللى بعد كده باستخدام أول k مؤثر فائق بس، وباستخدام الأرقام 0، 1، ...، b − 1 بس، و الأساس b نفسه:

• بالنسبة لـ 0 ≤ n ≤ b − 1، يتم تمثيل n ببساطة بالرقم المقابل.
• بالنسبة لـ n > b − 1، يتم إيجاد تمثيل n بشكل متكرر، حيث يتم تمثيل n الاول بالشكل التالي:

ب [ ك ] × _ك [ ك − 1] × _{ك − 1} [ ك - 2] ... [2] × ₂ [1] × ₁

حيث x _k ، ...، x ₁ هيا اكبر الأعداد الصحيحة اللى تحقق (بالتناوب)

ب [ ك ] × _ك ≤ ن

b [ k ] x _k [ k − 1] x _{k − 1} ≤ n

ب [ ك ] × _ك [ ك − 1] × _{ك − 1} [ ك - 2] ... [2] × ₂ [1] × ₁ ≤ ن

بعدين يتم إعادة التعبير عن أى x _i يتجاوز b − 1 بنفس الطريقة، وهكذا، مع تكرار ده الإجراء لحد يحتوى الشكل الناتج على الأرقام 0، 1، ...، b − 1 بس، و الأساس b .

يمكن تجنب الأقواس اللى مشضرورية بإعطاء عوامل التشغيل ذات المستوى الأعلى أولوية أعلى فى ترتيب التقييم؛ و علشان كده،

تمثيلات المستوى 1 ليها الشكل b [1] X، مع X كمان من ده الشكل؛

تمثيلات المستوى 2 ليها الشكل b [2] X [1] Y، مع X و Y كمان من ده الشكل؛

تمثيلات المستوى 3 ليها الشكل b [3] X [2] Y [1] Z، مع X و Y و Z كمان من ده الشكل؛

تمثيلات المستوى 4 ليها الشكل b [4] X [3] Y [2] Z [1] W، مع X و Y و Z و W كمان من ده الشكل؛

و هكذا دواليك.

فى النوع ده من التمثيل الوراثي ليه الأساس b ، بيظهر الأساس نفسه فى التعبيرات، و "الأرقام" من المجموعة {0، 1، ...، b − 1}. وده يختلف عن التمثيل العادي ليه الأساس 2 لما بييتكتتب الأخير بدلالة الأساس b ؛ زى ، فى الترميز العادى ليه الأساس 2، 6 = (110) ₂ = 2 [3] 2 [2] 1 [1] 2 [3] 1 [2] 1 [1] 2 [3] 0 [2] 0، فى الوقت نفسه التمثيل الوراثى ليه الأساس 2 من المستوى 3 هو 6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [1] 0). ممكن اختصار التمثيلات الوراثية عن طريق حذف أى حالات من [1] 0، [2] 1، [3] 1، [4] 1، إلخ؛ زى ، يتم اختصار التمثيل الأساسى 2 من المستوى 3 للعدد 6 ل2 [3] 2 [1] 2.

أمثلة: التمثيلات الفريدة للعدد 266 فى النظام الثنائي، عند المستويات 1 و2 و3 و4 و5، هيا كاللى جاى:

المستوى 1: 266 = 2 [1] 2 [1] 2 [1] ... [1] 2 (مع 133 من الرقم 2)

المستوى 2: 266 = 2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1)

المستوى 3: 266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2

المستوى 4: 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2

المستوى 5: 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2

حساب

يمكن نقل تعريفات تسلسل العمليات الزايده بشكل طبيعى لأنظمة إعادة كتابة المصطلحات (TRS) .

تم تحديد TRS بناء على التعريف الفرعى 1.1

يتوافق التعريف الأساسى لتسلسل العمليات الزايده مع قواعد الاختزال

${\begin{array}{lll}{\text{(r1)}}&H(0,a,b)&\rightarrow &S(b)\\{\text{(r2)}}&H(S(0),a,0)&\rightarrow &a\\{\text{(r3)}}&H(S(S(0)),a,0)&\rightarrow &0\\{\text{(r4)}}&H(S(S(S(n))),a,0)&\rightarrow &S(0)\\{\text{(r5)}}&H(S(n),a,S(b))&\rightarrow &H(n,a,H(S(n),a,b))\end{array}}$

لحساب $H_{n}(a,b)$ ممكن استخدام مكدس ، اللى يحتوى فى البداية على العناصر $\langle n,a,b\rangle$ .

ثم، بشكل متكرر لحد يبقا ذلك غير ممكن، يتم إزالة 3 عناصر واستبدالها حسب للقواعد

${\begin{array}{lllllllll}{\text{(r1)}}&0&,&a&,&b&\rightarrow &(b+1)\\{\text{(r2)}}&1&,&a&,&0&\rightarrow &a\\{\text{(r3)}}&2&,&a&,&0&\rightarrow &0\\{\text{(r4)}}&(n+3)&,&a&,&0&\rightarrow &1\\{\text{(r5)}}&(n+1)&,&a&,&(b+1)&\rightarrow &n&,&a&,&(n+1)&,&a&,&b\end{array}}$

بشكل تخطيطي، بدايه من $\langle n,a,b\rangle$ :

طالما أن طول المكدس لا يساوى 1
{
  عناصر POP 3؛
  ادفع عنصر واحد أو 5 عناصر حسب  للقواعد r1، r2، r3، r4، r5؛
}

مثال

الكومبيوترة $H_{2}(2,2)\rightarrow _{*}4$

تسلسل الاختزال هو

${\underline {H(S(S(0)),S(S(0)),S(S(0)))}}$

$\rightarrow _{r5}H(S(0),S(S(0)),{\underline {H(S(S(0)),S(S(0)),S(0))}})$

$\rightarrow _{r5}H(S(0),S(S(0)),H(S(0),S(S(0)),{\underline {H(S(S(0)),S(S(0)),0)}}))$

$\rightarrow _{r3}H(S(0),S(S(0)),{\underline {H(S(0),S(S(0)),0)}})$

$\rightarrow _{r2}{\underline {H(S(0),S(S(0)),S(S(0)))}}$

$\rightarrow _{r5}H(0,S(S(0)),{\underline {H(S(0),S(S(0)),S(0))}})$

$\rightarrow _{r5}H(0,S(S(0)),H(0,S(S(0)),{\underline {H(S(0),S(S(0)),0)}}))$

$\rightarrow _{r2}H(0,S(S(0)),{\underline {H(0,S(S(0)),S(S(0)))}})$

$\rightarrow _{r1}{\underline {H(0,S(S(0)),S(S(S(0))))}}$

$\rightarrow _{r1}S(S(S(S(0))))$

عند التنفيذ باستخدام مكدس، عند الإدخال $\langle 2,2,2\rangle$

the stack configurations	represent the equations
${\underline {2,2,2}}$	$H_{2}(2,2)$
$\rightarrow _{r5}1,2,{\underline {2,2,1}}$	$=H_{1}(2,H_{2}(2,1))$
$\rightarrow _{r5}1,2,1,2,{\underline {2,2,0}}$	$=H_{1}(2,H_{1}(2,H_{2}(2,0)))$
$\rightarrow _{r3}1,2,{\underline {1,2,0}}$	$=H_{1}(2,H_{1}(2,0))$
$\rightarrow _{r2}{\underline {1,2,2}}$	$=H_{1}(2,2)$
$\rightarrow _{r5}0,2,{\underline {1,2,1}}$	$=H_{0}(2,H_{1}(2,1))$
$\rightarrow _{r5}0,2,0,2,{\underline {1,2,0}}$	$=H_{0}(2,H_{0}(2,H_{1}(2,0)))$
$\rightarrow _{r2}0,2,{\underline {0,2,2}}$	$=H_{0}(2,H_{0}(2,2))$
$\rightarrow _{r1}{\underline {0,2,3}}$	$=H_{0}(2,3)$
$\rightarrow _{r1}4$	$=4$