एकरमैन फलन

This article is about the mathematical function. For other uses, see Ackermann (disambiguation).

संगणनीयता सिद्धांत में, विल्हेम एकरमैन के नाम पर एकरमैन फलन, जो सबसे सरल फलन में से एक है और सबसे पहले खोजे गए पूर्ण संगणनीय फलन का उदाहरण है जो मूल पुनरावर्ती फलन नहीं हैं। सभी मूल पुनरावर्ती फलन पूर्ण और संगणनीय हैं, लेकिन एकरमैन फलन यह दर्शाता है कि सभी पूर्ण संगणनीय फलन मूल फलन की पुनरावर्ती नहीं हैं। एकरमैन के प्रकाशन के बाद उनके फलन के (जिसमें तीन ऋणोतर पूर्णांक प्राचर थे), कई लेखकों ने इसे विभिन्न उद्देश्यों के अनुरूप संशोधित किया, ताकि आज एकरमैन फलन मूल फलन के कई रूपों में से किसी को भी संदर्भित कर सके। एक सामान्य संस्करण, दो-प्राचर एकरमैन-पीटर फलन को ऋणोतर पूर्णांक m और n के लिए निम्नानुसार परिभाषित किया गया है:

${\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m+1,0)&=&\operatorname {A} (m,1)\\\operatorname {A} (m+1,n+1)&=&\operatorname {A} (m,\operatorname {A} (m+1,n))\end{array}}$

छोटे आगम के लिए भी इसका मान तेजी से बढ़ता है। उदाहरण के लिए, A(4, 2) 19,729 दशमलव अंकों का पूर्णांक है ( 2⁶⁵⁵³⁶−3 के बराबर, अथवा 2²²²²−3).

इतिहास

1920 के दशक के अंत में, गणितज्ञ गेब्रियल सूडान और विल्हेम एकरमैन, डेविड हिल्बर्ट के छात्र, संगणना की नींव का अध्ययन कर रहे थे। सूडान और एकरमैन दोनों को पूर्ण संगणनीय फलन की खोज के लिए श्रेय दिया जाता है (जिसे कुछ संदर्भों में केवल "पुनरावर्ती" कहा जाता है) जो मूल पुनरावर्ती फलन नहीं हैं। सूडान ने कम प्रसिद्ध सूडान फलन प्रकाशित किया, फिर कुछ ही समय बाद और स्वतंत्र रूप से, 1928 में, एकरमैन ने अपना फलन $\varphi$ (ग्रीक अक्षर फ़ाई) प्रकाशित किया। एकरमैन का तीन-प्राचर फलन, $\varphi (m,n,p)$, को इस तरह से परिभाषित किया गया है कि यह जैसे $p=0,1,2$, के लिए और यह योग, गुणन और घातांक के बुनियादी परिचालनों का पुनरावृत्त करता है।

${\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,n,1)&=m\times n\\\varphi (m,n,2)&=m^{n}\end{aligned}}$

और P > 2 के लिए यह इस तरह के बुनियादी परिचालनों को बढ़ाता है जिसकी तुलना अतिसंचालन से की जा सकती है:

${\begin{aligned}\varphi (m,n,3)&=m[4](n+1)\\\varphi (m,n,p)&\gtrapprox m[p+1](n+1)&&{\text{for }}p>3\end{aligned}}$

( इसकी ऐतिहासिक भूमिका के अलावा यह कुल-गणना योग्य-लेकिन-मूल-पुनरावर्ती फलन के रूप में नहीं, एकरमैन के मूल फलन को घातांक से परे बुनियादी अंकगणितीय संचालन का विस्तार करने के लिए देखा जाता है, हालांकि एकरमैन फलन के रूपांतरों के समान नहीं है जो विशेष रूप से डिज़ाइन किए गए हैं। जैसे कि - रूबेन गुडस्टीन का अतिसंचालन अनुक्रम।)

अनंत पर, डेविड हिल्बर्ट ने परिकल्पना की कि एकरमैन फलन मूल पुनरावर्ती नहीं था, लेकिन यह एकरमैन, हिल्बर्ट के निजी सचिव और पूर्व छात्र थे, जिन्होंने वास्तव में अपने कागज में वास्तविक संख्या के निर्माण पर परिकल्पना को सिद्ध किया था।

पीटर रोजसा और राफेल रॉबिन्सन ने बाद में एकरमैन फलन का एक दो-चर संस्करण को विकसित किया जो बाद में लगभग सभी लेखकों द्वारा पसंद किया गया।

सामान्यीकृत अतिसंचालन, उदाहरण - $G(m,a,b)=a[m]b$, एकरमैन फलन का भी एक संस्करण है। 1963 में आर.सी. बक अतिसंचालन सीक्वेंस पर एक सहज ज्ञान युक्त दो-चर वेरिएंट F पर आधारित है:

$\operatorname {F} (m,n)=2[m]n.$

अधिकांश अन्य संस्करणों की तुलना में बक के फलन में कोई अनावश्यक ऑफ़सेट नहीं है:

${\begin{aligned}\operatorname {F} (0,n)&=2[0]n=n+1\\\operatorname {F} (1,n)&=2[1]n=2+n\\\operatorname {F} (2,n)&=2[2]n=2\times n\\\operatorname {F} (3,n)&=2[3]n=2^{n}\\\operatorname {F} (4,n)&=2[4]n=2^{2^{2^{{}^{.^{.^{{}_{.}2}}}}}}\\&\quad \vdots \end{aligned}}$

एकरमैन फलन के कई अन्य संस्करणों का अन्वेषण भी किया गया है।

परिभाषा

परिभाषा: एम-एरी फलन के रूप में

एकरमैन का मूल तीन-प्राचर फलन $\varphi (m,n,p)$ ऋणोतर पूर्णांकों के लिए निम्नानुसार पुनरावर्तन परिभाषित किया गया है $m,n,$ तथा $p$:

${\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,0,1)&=0\\\varphi (m,0,2)&=1\\\varphi (m,0,p)&=m&&{\text{for }}p>2\\\varphi (m,n,p)&=\varphi (m,\varphi (m,n-1,p),p-1)&&{\text{for }}n,p>0\end{aligned}}$

विभिन्न दो-प्राचर संस्करणों में से, पेटर और रॉबिन्सन द्वारा विकसित एक (जिसे अधिकांश लेखकों द्वारा एकरमैन फलन कहा जाता है) को ऋणोतर पूर्णांकों के लिए परिभाषित किया गया है $m$ तथा $n$ निम्नलिखित नुसार:

${\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m+1,0)&=&\operatorname {A} (m,1)\\\operatorname {A} (m+1,n+1)&=&\operatorname {A} (m,A(m+1,n))\end{array}}$

अतिसंचालन के संबंध में एकरमेन फलन भी व्यक्त किया गया है:

$A(m,n)={\begin{cases}n+1&m=0\\2[m](n+3)-3&m>0\\\end{cases}}$

या, नुथ के उच्च-तीर संकेतन में लिखा गया है (पूर्णांक सूचकांकों तक विस्तारित $\geq -2$):

$={\begin{cases}n+1&m=0\\2\uparrow ^{m-2}(n+3)-3&m>0\\\end{cases}}$

या, समतुल्य रूप से, बक के फलन F के संदर्भ में: :::$={\begin{cases}n+1&m=0\\F(m,n+3)-3&m>0\\\end{cases}}$

=== परिभाषा: पुनरावृत्त 1-एरी फलन === के रूप में परिभाषित करना $f^{n}$ के n-वें पुनरावृति के रूप में $f$:

${\begin{array}{rll}f^{0}(x)&=&x\\f^{n+1}(x)&=&f(f^{n}(x))\,\,\,\,\{{\textrm {for}}\,\,n\geq 1\}\end{array}}$

पुनरावृत्त फलन एक निश्चित संख्या में स्वयं के साथ एक फलन बनाने की प्रक्रिया है। फलन रचना एक साहचर्य ऑपरेशन है, इसलिए $f(f^{n}(x))=f^{n}(f(x))$.

एकरमैन फलन को एकल फलन के अनुक्रम के रूप में समझना, कोई सेट कर सकता है $\operatorname {A} _{m}(n)=\operatorname {A} (m,n)$.

फलन तब एक अनुक्रम बन जाता है $\operatorname {A} _{0},\operatorname {A} _{1},\operatorname {A} _{2},...$ एकल का फलन, इटरेटेड फलन से परिभाषित:

${\begin{array}{lcl}\operatorname {A} _{0}(n)&=&n+1\\\operatorname {A} _{m+1}(n)&=&\operatorname {A} _{m}^{n+1}(1)\\\end{array}}$

संगणना

एकरमैन फलन की पुनरावर्ती परिभाषा को स्वाभाविक रूप से पुनर्लेखन | टर्म पुनर्लेखन प्रणाली (TRS) में स्थानांतरित किया जा सकता है।

=== टीआरएस, 2-एरी फलन === पर आधारित है 2-ary एकरमैन फलन की परिभाषा स्पष्ट कमी नियमों की ओर ले जाती है

${\begin{array}{lll}{\text{(r1)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r2)}}&A(S(m),0)&\rightarrow &A(m,S(0))\\{\text{(r3)}}&A(S(m),S(n))&\rightarrow &A(m,A(S(m),n))\end{array}}$

उदाहरण

गणना करना $A(1,2)\rightarrow _{*}4$ घटाव क्रम है

Leftmost-outermost (one-step) strategy:	Leftmost-innermost (one-step) strategy:
${\underline {A(S(0),S(S(0)))}}$	${\underline {A(S(0),S(S(0)))}}$
$\rightarrow _{r3}{\underline {A(0,A(S(0),S(0))}})$	$\rightarrow _{r3}A(0,{\underline {A(S(0),S(0))}})$
$\rightarrow _{r1}S({\underline {A(S(0),S(0))}})$	$\rightarrow _{r3}A(0,A(0,{\underline {A(S(0),0)}}))$
$\rightarrow _{r3}S({\underline {A(0,A(S0,0))}})$	$\rightarrow _{r2}A(0,A(0,{\underline {A(0,S(0))}}))$
$\rightarrow _{r1}S(S({\underline {A(S(0),0)}}))$	$\rightarrow _{r1}A(0,{\underline {A(0,S(S(0)))}})$
$\rightarrow _{r2}S(S({\underline {A(0,S(0))}}))$	$\rightarrow _{r1}{\underline {A(0,S(S(S(0))))}}$
$\rightarrow _{r1}S(S(S(S(0))))$	$\rightarrow _{r1}S(S(S(S(0))))$

गणना करना $\operatorname {A} (m,n)$ कोई स्टैक (अमूर्त डेटा प्रकार) का उपयोग कर सकता है, जिसमें प्रारंभ में तत्व होते हैं $\langle m,n\rangle$.

फिर बार-बार दो शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है

${\begin{array}{lllllllll}{\text{(r1)}}&0&,&n&\rightarrow &(n+1)\\{\text{(r2)}}&(m+1)&,&0&\rightarrow &m&,&1\\{\text{(r3)}}&(m+1)&,&(n+1)&\rightarrow &m&,&(m+1)&,&n\end{array}}$

योजनाबद्ध रूप से, से शुरू $\langle m,n\rangle$:

जबकि ढेर की लंबाई <> 1
{
   पीओपी 2 तत्व;
   PUSH 1 या 2 या 3 तत्व, नियमों को लागू करते हुए r1, r2, r3
}

स्यूडोकोड प्रकाशित हो चुकी है। Grossman & Zeitman (1988).

उदाहरण के लिए, आगम पर $\langle 2,1\rangle$,

the stack configurations	reflect the reduction
${\underline {2,1}}$	${\underline {A(2,1)}}$
$\rightarrow 1,{\underline {2,0}}$	$\rightarrow _{r1}A(1,{\underline {A(2,0)}})$
$\rightarrow 1,{\underline {1,1}}$	$\rightarrow _{r2}A(1,{\underline {A(1,1)}})$
$\rightarrow 1,0,{\underline {1,0}}$	$\rightarrow _{r3}A(1,A(0,{\underline {A(1,0)}}))$
$\rightarrow 1,0,{\underline {0,1}}$	$\rightarrow _{r2}A(1,A(0,{\underline {A(0,1)}}))$
$\rightarrow 1,{\underline {0,2}}$	$\rightarrow _{r1}A(1,{\underline {A(0,2)}})$
$\rightarrow {\underline {1,3}}$	$\rightarrow _{r1}{\underline {A(1,3)}}$
$\rightarrow 0,{\underline {1,2}}$	$\rightarrow _{r3}A(0,{\underline {A(1,2)}})$
$\rightarrow 0,0,{\underline {1,1}}$	$\rightarrow _{r3}A(0,A(0,{\underline {A(1,1)}}))$
$\rightarrow 0,0,0,{\underline {1,0}}$	$\rightarrow _{r3}A(0,A(0,A(0,{\underline {A(1,0)}})))$
$\rightarrow 0,0,0,{\underline {0,1}}$	$\rightarrow _{r2}A(0,A(0,A(0,{\underline {A(0,1)}})))$
$\rightarrow 0,0,{\underline {0,2}}$	$\rightarrow _{r1}A(0,A(0,{\underline {A(0,2)}}))$
$\rightarrow 0,{\underline {0,3}}$	$\rightarrow _{r1}A(0,{\underline {A(0,3)}})$
$\rightarrow {\underline {0,4}}$	$\rightarrow _{r1}{\underline {A(0,4)}}$
$\rightarrow 5$	$\rightarrow _{r1}5$

टिप्पणियां

• रोसेटा कोड पर 225 कंप्यूटर भाषाओं में सबसे वामपंथी-अंतरतम रणनीति लागू की गई है।
• सभी के लिए $m,n$ की गणना $A(m,n)$ से अधिक नहीं लेता है $(A(m,n)+1)^{m}$ कदम।
• Grossman & Zeitman (1988) बताया कि की गणना में $\operatorname {A} (m,n)$ ढेर की अधिकतम लंबाई है $\operatorname {A} (m,n)$, जब तक कि $m>0$.

उनका अपना एल्गोरिदम, स्वाभाविक रूप से पुनरावृत्त, गणना करता है $\operatorname {A} (m,n)$ अंदर ${\mathcal {O}}(m\operatorname {A} (m,n))$ समय और भीतर ${\mathcal {O}}(m)$ अंतरिक्ष।

=== टीआरएस, पुनरावृत्त 1-एरी फलन === पर आधारित है पुनरावृत्त 1-ary एकरमैन फलन की परिभाषा विभिन्न कमी नियमों की ओर ले जाती है

${\begin{array}{lll}{\text{(r4)}}&A(S(0),0,n)&\rightarrow &S(n)\\{\text{(r5)}}&A(S(0),S(m),n)&\rightarrow &A(S(n),m,S(0))\\{\text{(r6)}}&A(S(S(x)),m,n)&\rightarrow &A(S(0),m,A(S(x),m,n))\end{array}}$

जैसा कि फलन रचना साहचर्य है, नियम r6 के बजाय परिभाषित किया जा सकता है

${\begin{array}{lll}{\text{(r7)}}&A(S(S(x)),m,n)&\rightarrow &A(S(x),m,A(S(0),m,n))\end{array}}$

पिछले खंड की तरह की गणना $\operatorname {A} _{m}^{1}(n)$ ढेर के साथ लागू किया जा सकता है।

प्रारंभ में ढेर में तीन तत्व होते हैं $\langle 1,m,n\rangle$.

फिर बार-बार तीन शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है:${\begin{array}{lllllllll}{\text{(r4)}}&1&,0&,n&\rightarrow &(n+1)\\{\text{(r5)}}&1&,(m+1)&,n&\rightarrow &(n+1)&,m&,1\\{\text{(r6)}}&(x+2)&,m&,n&\rightarrow &1&,m&,(x+1)&,m&,n\\\end{array}}$ योजनाबद्ध रूप से, से शुरू $\langle 1,m,n\rangle$:

जबकि ढेर की लंबाई <> 1
{
   पीओपी 3 तत्व;
   पुश 1 या 3 या 5 तत्व, नियमों को लागू करना r4, r5, r6;
}

उदाहरण

आगम पर $\langle 1,2,1\rangle$ क्रमिक ढेर विन्यास हैं

${\begin{aligned}&{\underline {1,2,1}}\rightarrow _{r5}{\underline {2,1,1}}\rightarrow _{r6}1,1,{\underline {1,1,1}}\rightarrow _{r5}1,1,{\underline {2,0,1}}\rightarrow _{r6}1,1,1,0,{\underline {1,0,1}}\\&\rightarrow _{r4}1,1,{\underline {1,0,2}}\rightarrow _{r4}{\underline {1,1,3}}\rightarrow _{r5}{\underline {4,0,1}}\rightarrow _{r6}1,0,{\underline {3,0,1}}\rightarrow _{r6}1,0,1,0,{\underline {2,0,1}}\\&\rightarrow _{r6}1,0,1,0,1,0,{\underline {1,0,1}}\rightarrow _{r4}1,0,1,0,{\underline {1,0,2}}\rightarrow _{r4}1,0,{\underline {1,0,3}}\rightarrow _{r4}{\underline {1,0,4}}\rightarrow _{r4}5\end{aligned}}$

संगत समानताएं हैं

${\begin{aligned}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1))=A_{1}(A_{0}^{2}(1))=A_{1}(A_{0}(A_{0}(1)))\\&=A_{1}(A_{0}(2))=A_{1}(3)=A_{0}^{4}(1)=A_{0}(A_{0}^{3}(1))=A_{0}(A_{0}(A_{0}^{2}(1)))\\&=A_{0}(A_{0}(A_{0}(A_{0}(1))))=A_{0}(A_{0}(A_{0}(2)))=A_{0}(A_{0}(3))=A_{0}(4)=5\end{aligned}}$

जब नियम r6 के बजाय कमी नियम r7 का उपयोग किया जाता है, तो स्टैक में प्रतिस्थापन का पालन किया जाएगा

${\begin{array}{lllllllll}{\text{(r7)}}&(x+2)&,m&,n&\rightarrow &(x+1)&,m&,1&,m&,n\end{array}}$

क्रमिक स्टैक कॉन्फ़िगरेशन तब होगा

${\begin{aligned}&{\underline {1,2,1}}\rightarrow _{r5}{\underline {2,1,1}}\rightarrow _{r7}1,1,{\underline {1,1,1}}\rightarrow _{r5}1,1,{\underline {2,0,1}}\rightarrow _{r7}1,1,1,0,{\underline {1,0,1}}\\&\rightarrow _{r4}1,1,{\underline {1,0,2}}\rightarrow _{r4}{\underline {1,1,3}}\rightarrow _{r5}{\underline {4,0,1}}\rightarrow _{r7}3,0,{\underline {1,0,1}}\rightarrow _{r4}{\underline {3,0,2}}\\&\rightarrow _{r7}2,0,{\underline {1,0,2}}\rightarrow _{r4}{\underline {2,0,3}}\rightarrow _{r7}1,0,{\underline {1,0,3}}\rightarrow _{r4}{\underline {1,0,4}}\rightarrow _{r4}5\end{aligned}}$

संगत समानताएं हैं

${\begin{aligned}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1))=A_{1}(A_{0}^{2}(1))=A_{1}(A_{0}(A_{0}(1)))\\&=A_{1}(A_{0}(2))=A_{1}(3)=A_{0}^{4}(1)=A_{0}^{3}(A_{0}(1))=A_{0}^{3}(2)\\&=A_{0}^{2}(A_{0}(2))=A_{0}^{2}(3)=A_{0}(A_{0}(3))=A_{0}(4)=5\end{aligned}}$

टिप्पणियां

• किसी दिए गए आगम पर अब तक प्रस्तुत टीआरएस समान चरणों में अभिसरण करते हैं। वे समान कटौती नियमों का भी उपयोग करते हैं (इस तुलना में नियमों r1, r2, r3 को क्रमशः नियम r4, r5, r6/r7 के समान माना जाता है)। उदाहरण के लिए, की कमी $A(2,1)$ 14 चरणों में अभिसरित होता है: 6 × r1, 3 × r2, 5 × r3। की कमी $A_{2}(1)$ समान 14 चरणों में अभिसरित होता है: 6 × r4, 3 × r5, 5 × r6/r7। टीआरएस उस क्रम में भिन्न होते हैं जिसमें कटौती नियम लागू होते हैं।
• कब $A_{i}(n)$ {r4, r5, r6} नियमों का पालन करते हुए गणना की जाती है, स्टैक की अधिकतम लंबाई नीचे रहती है $2\times A(i,n)$. जब नियम r6 के स्थान पर कमी नियम r7 का उपयोग किया जाता है, तो स्टैक की अधिकतम लंबाई केवल होती है $2(i+2)$. ढेर की लंबाई पुनरावर्ती गहराई को दर्शाती है। नियमों के अनुसार कमी के रूप में {r4, r5, r7} में पुनरावर्तन की एक छोटी अधिकतम गहराई शामिल है, यह गणना उस संबंध में अधिक कुशल है।

टीआरएस, हाइपरऑपरेटरों पर आधारित

जैसा Sundblad (1971) - या Porto & Matos (1980) - स्पष्ट रूप से दिखाया गया है, एकरमेन फलन अतिसंचालन अनुक्रम के संदर्भ में व्यक्त किया जा सकता है:

$A(m,n)={\begin{cases}n+1&m=0\\2[m](n+3)-3&m>0\\\end{cases}}$

या, बक के फलन के संदर्भ में, पैरामीटर सूची से निरंतर 2 को हटाने के बाद

$={\begin{cases}n+1&m=0\\F(m,n+3)-3&m>0\\\end{cases}}$

बक का फलन $\operatorname {F} (m,n)=2[m]n$, एकरमैन फलन का एक भिन्न रूप, जिसकी गणना निम्न कमी नियमों के साथ की जा सकती है:

${\begin{array}{lll}{\text{(b1)}}&F(S(0),0,n)&\rightarrow &S(n)\\{\text{(b2)}}&F(S(0),S(0),0)&\rightarrow &S(S(0))\\{\text{(b3)}}&F(S(0),S(S(0)),0)&\rightarrow &0\\{\text{(b4)}}&F(S(0),S(S(S(m))),0)&\rightarrow &S(0)\\{\text{(b5)}}&F(S(0),S(m),S(n))&\rightarrow &F(S(n),m,F(S(0),S(m),0))\\{\text{(b6)}}&F(S(S(x)),m,n)&\rightarrow &F(S(0),m,F(S(x),m,n))\end{array}}$

नियम b6 के स्थान पर नियम को परिभाषित किया जा सकता है

${\begin{array}{lll}{\text{(b7)}}&F(S(S(x)),m,n)&\rightarrow &F(S(x),m,F(S(0),m,n))\end{array}}$

एकरमैन फलन की गणना करने के लिए तीन कटौती नियमों को जोड़ना पर्याप्त है

${\begin{array}{lll}{\text{(r8)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r9)}}&A(S(m),n)&\rightarrow &P(F(S(0),S(m),S(S(S(n)))))\\{\text{(r10)}}&P(S(S(S(m))))&\rightarrow &m\\\end{array}}$

ये नियम बेस केस ए (0, एन), संरेखण (एन + 3) और फज (-3) का ख्याल रखते हैं।

उदाहरण

गणना करना $A(2,1)\rightarrow _{*}5$

using reduction rule ${\text{b7}}$:	using reduction rule ${\text{b6}}$:
${\underline {A(2,1)}}$	${\underline {A(2,1)}}$
$\rightarrow _{r9}P({\underline {F(1,2,4)}})$	$\rightarrow _{r9}P({\underline {F(1,2,4)}})$
$\rightarrow _{b5}P(F(4,1,{\underline {F(1,2,0)}}))$	$\rightarrow _{b5}P(F(4,1,{\underline {F(1,2,0)}}))$
$\rightarrow _{b3}P({\underline {F(4,1,0)}})$	$\rightarrow _{b3}P({\underline {F(4,1,0)}})$
$\rightarrow _{b7}P(F(3,1,{\underline {F(1,1,0)}}))$	$\rightarrow _{b6}P(F(1,1,{\underline {F(3,1,0)}}))$
$\rightarrow _{b2}P({\underline {F(3,1,2)}})$	$\rightarrow _{b6}P(F(1,1,F(1,1,{\underline {F(2,1,0)}})))$
$\rightarrow _{b7}P(F(2,1,{\underline {F(1,1,2)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,1,F(1,1,{\underline {F(1,1,0)}}))))$
$\rightarrow _{b5}P(F(2,1,F(2,0,{\underline {F(1,1,0)}})))$	$\rightarrow _{b2}P(F(1,1,F(1,1,{\underline {F(1,1,2)}})))$
$\rightarrow _{b2}P(F(2,1,{\underline {F(2,0,2)}}))$	$\rightarrow _{b5}P(F(1,1,F(1,1,F(2,0,{\underline {F(1,1,0)}}))))$
$\rightarrow _{b7}P(F(2,1,F(1,0,{\underline {F(1,0,2)}})))$	$\rightarrow _{b2}P(F(1,1,F(1,1,{\underline {F(2,0,2)}})))$
$\rightarrow _{b1}P(F(2,1,{\underline {F(1,0,3)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,1,F(1,0,{\underline {F(1,0,2)}}))))$
$\rightarrow _{b1}P({\underline {F(2,1,4)}})$	$\rightarrow _{b1}P(F(1,1,F(1,1,{\underline {F(1,0,3)}})))$
$\rightarrow _{b7}P(F(1,1,{\underline {F(1,1,4)}}))$	$\rightarrow _{b1}P(F(1,1,{\underline {F(1,1,4)}}))$
$\rightarrow _{b5}P(F(1,1,F(4,0,{\underline {F(1,1,0)}})))$	$\rightarrow _{b5}P(F(1,1,F(4,0,{\underline {F(1,1,0)}})))$
$\rightarrow _{b2}P(F(1,1,{\underline {F(4,0,2)}}))$	$\rightarrow _{b2}P(F(1,1,{\underline {F(4,0,2)}}))$
$\rightarrow _{b7}P(F(1,1,F(3,0,{\underline {F(1,0,2)}})))$	$\rightarrow _{b6}P(F(1,1,F(1,0,{\underline {F(3,0,2)}})))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(3,0,3)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,{\underline {F(2,0,2)}}))))$
$\rightarrow _{b7}P(F(1,1,F(2,0,{\underline {F(1,0,3)}})))$	$\rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,2)}})))))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(2,0,4)}}))$	$\rightarrow _{b1}P(F(1,1,F(1,0,F(1,0,{\underline {F(1,0,3)}}))))$
$\rightarrow _{b7}P(F(1,1,F(1,0,{\underline {F(1,0,4)}})))$	$\rightarrow _{b1}P(F(1,1,F(1,0,{\underline {F(1,0,4)}})))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(1,0,5)}}))$	$\rightarrow _{b1}P(F(1,1,{\underline {F(1,0,5)}}))$
$\rightarrow _{b1}P({\underline {F(1,1,6)}})$	$\rightarrow _{b1}P({\underline {F(1,1,6)}})$
$\rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)}}))$	$\rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)}}))$
$\rightarrow _{b2}P({\underline {F(6,0,2)}})$	$\rightarrow _{b2}P({\underline {F(6,0,2)}})$
$\rightarrow _{b7}P(F(5,0,{\underline {F(1,0,2)}}))$	$\rightarrow _{b6}P(F(1,0,{\underline {F(5,0,2)}}))$
$\rightarrow _{b1}P({\underline {F(5,0,3)}})$	$\rightarrow _{b6}P(F(1,0,F(1,0,{\underline {F(4,0,2)}})))$
$\rightarrow _{b7}P(F(4,0,{\underline {F(1,0,3)}}))$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,{\underline {F(3,0,2)}}))))$
$\rightarrow _{b1}P({\underline {F(4,0,4)}})$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(2,0,2)}})))))$
$\rightarrow _{b7}P(F(3,0,{\underline {F(1,0,4)}}))$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,2)}}))))))$
$\rightarrow _{b1}P({\underline {F(3,0,5)}})$	$\rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,3)}})))))$
$\rightarrow _{b7}P(F(2,0,{\underline {F(1,0,5)}}))$	$\rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,{\underline {F(1,0,4)}}))))$
$\rightarrow _{b1}P({\underline {F(2,0,6)}})$	$\rightarrow _{b1}P(F(1,0,F(1,0,{\underline {F(1,0,5)}})))$
$\rightarrow _{b7}P(F(1,0,{\underline {F(1,0,6)}}))$	$\rightarrow _{b1}P(F(1,0,{\underline {F(1,0,6)}}))$
$\rightarrow _{b1}P({\underline {F(1,0,7)}})$	$\rightarrow _{b1}P({\underline {F(1,0,7)}})$
$\rightarrow _{b1}{\underline {P(8)}}$	$\rightarrow _{b1}{\underline {P(8)}}$
$\rightarrow _{r10}5$	$\rightarrow _{r10}5$

मिलान करने वाली समानताएं हैं

• जब टीआरएस कटौती नियम के साथ ${\text{b6}}$ लागू की गई है:

${\text{b7}}$