एकरमैन फलन

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 में रॉबर्ट क्रेटन बक|आर.सी. बक एक सहज ज्ञान युक्त दो-चर आधारित है प्रकार $\operatorname {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}}$