सामान्य रूप (सार पुनर्लेखन): Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Expression that cannot be rewritten further}} सार पुनर्लेखन में,<ref>{{cite book |author=Franz Baader |author2=Tobi...")
 
No edit summary
Line 1: Line 1:
{{Short description|Expression that cannot be rewritten further}}
{{Short description|Expression that cannot be rewritten further}}
[[सार पुनर्लेखन]] में,<ref>{{cite book |author=[[Franz Baader]] |author2=[[Tobias Nipkow]] |title=टर्म पुनर्लेखन और वह सब|year=1998 |publisher=[[Cambridge University Press]] |isbn=9780521779203 |url=https://books.google.com/books?id=N7BvXVUCQk8C&q=%22normal+form%22}}</ref> एक वस्तु सामान्य रूप में होती है यदि इसे आगे फिर से नहीं लिखा जा सकता है, अर्थात यह अप्रासंगिक है। पुनर्लेखन प्रणाली के आधार पर, एक वस्तु कई सामान्य रूपों में फिर से लिख सकती है या बिल्कुल भी नहीं। पुनर्लेखन प्रणालियों के कई गुण सामान्य रूपों से संबंधित हैं।
[[सार पुनर्लेखन]] में<ref>{{cite book |author=[[Franz Baader]] |author2=[[Tobias Nipkow]] |title=टर्म पुनर्लेखन और वह सब|year=1998 |publisher=[[Cambridge University Press]] |isbn=9780521779203 |url=https://books.google.com/books?id=N7BvXVUCQk8C&q=%22normal+form%22}}</ref> एक वस्तु सामान्य रूप में होती है यदि इसे आगे फिर से नहीं लिखा जा सकता है अर्थात यह अप्रासंगिक है। पुनर्लेखन प्रणाली के आधार पर एक वस्तु कई सामान्य रूपों में फिर से लिख सकती है या पूर्ण रूप से भी नहीं पुनर्लेखन प्रणालियों के कई गुण सामान्य रूपों से संबंधित हैं।


== परिभाषाएँ <अवधि वर्ग = एंकर आईडी = परिभाषा> </span> ==
== परिभाषाएँ '''<अवधि वर्ग = एंकर आईडी = परिभाषा>'''==
औपचारिक रूप से कहा गया है, अगर (A,→) एक अमूर्त पुनर्लेखन प्रणाली # परिभाषा है, x∈A 'सामान्य रूप' में है यदि कोई y∈A मौजूद नहीं है जैसे कि x→y, यानी x एक अप्रासंगिक शब्द है।
औपचारिक रूप से कहा गया है, यदि (A,→) एक अमूर्त पुनर्लेखन प्रणाली या परिभाषा है, x∈A 'सामान्य रूप' में है यदि कोई y∈A उपस्थित नहीं है जैसे कि x→y, यानी x एक अप्रासंगिक शब्द है।
 
एक वस्तु a 'अशक्त रूप से सामान्यीकरण' है यदि वहाँ से प्रारंभ होने वाले पुनर्लेखन का कम से कम एक विशेष क्रम उपस्थित  है जो अंततः एक सामान्य रूप देता है। एक पुनर्लेखन प्रणाली में 'अशक्त सामान्यीकरण गुण' होता है या (अशक्त ) सामान्यीकरण (डब्ल्यू एन) होता है यदि प्रत्येक वस्तु अशक्त रूप से सामान्य हो रही हो। एक वस्तु a 'दृढ़ता से सामान्य' होती है यदि a से प्रारंभ होने वाले पुनर्लेखन का प्रत्येक क्रम अंततः सामान्य रूप से समाप्त हो जाता है। एक सार पुनर्लेखन प्रणाली जोरदार सामान्यीकरण समाप्ति नोथेरियन है, या '(शसक्त) सामान्यीकरण संपत्ति' (एसएन) है यदि इसकी प्रत्येक वस्तु दृढ़ता से सामान्य हो रही है।<ref>{{cite journal |last1=Ohlebusch |first1=Enno |title=एब्स्ट्रैक्ट रिडक्शन मोडुलो ए इक्वैलेंस रिलेशन के लिए चर्च-रॉसर प्रमेय|journal=Rewriting Techniques and Applications |series=Lecture Notes in Computer Science |date=1998 |volume=1379 |page=18 |doi=10.1007/BFb0052358 |isbn=978-3-540-64301-2 |url=https://books.google.com/books?id=ESr6CAAAQBAJ&pg=PA18}}</ref>
 
एक पुनर्लेखन प्रणाली में सामान्य रूप गुण (एनएफ) होता है यदि सभी वस्तुओं के लिए a और सामान्य रूप b, b को पुनर्लेखन की एक श्रृंखला द्वारा a से पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a b तक कम हो जाता है। एक पुनर्लेखन प्रणाली में अद्वितीय सामान्य रूप गुण (यूएन) होता है यदि सभी सामान्य रूपों के लिए a, b ∈ S, a तक b से पुनर्लेखन की श्रृंखला द्वारा पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a, b के समान हो एक पुनर्लेखन प्रणाली में कमी के संबंध में विशिष्ट सामान्य रूप की संपत्ति होती है (UN<sup>→</sup>) यदि प्रत्येक पद को सामान्य रूपों a और b में कम करने के लिए, a, b के समान है।<ref name="NF">{{cite journal |last1=Klop |first1=J.W. |last2=de Vrijer |first2=R.C. |title=विशेषण जोड़ी के साथ लैम्ब्डा कैलकुलस के लिए अद्वितीय सामान्य रूप|journal=Information and Computation |date=February 1989 |volume=80 |issue=2 |pages=97–113 |doi=10.1016/0890-5401(89)90014-X |doi-access=free }}</ref>


एक वस्तु a 'कमजोर रूप से सामान्यीकरण' है यदि वहाँ से शुरू होने वाले पुनर्लेखन का कम से कम एक विशेष क्रम मौजूद है जो अंततः एक सामान्य रूप देता है। एक पुनर्लेखन प्रणाली में 'कमजोर सामान्यीकरण गुण' होता है या (कमजोर) सामान्यीकरण (WN) होता है यदि प्रत्येक वस्तु कमजोर रूप से सामान्य हो रही हो। एक वस्तु a 'दृढ़ता से सामान्य' होती है यदि a से शुरू होने वाले पुनर्लेखन का प्रत्येक क्रम अंततः सामान्य रूप से समाप्त हो जाता है। एक सार पुनर्लेखन प्रणाली जोरदार सामान्यीकरण, समाप्ति, नोथेरियन है, या '(मजबूत) सामान्यीकरण संपत्ति' (एसएन) है, यदि इसकी प्रत्येक वस्तु दृढ़ता से सामान्य हो रही है।<ref>{{cite journal |last1=Ohlebusch |first1=Enno |title=एब्स्ट्रैक्ट रिडक्शन मोडुलो ए इक्वैलेंस रिलेशन के लिए चर्च-रॉसर प्रमेय|journal=Rewriting Techniques and Applications |series=Lecture Notes in Computer Science |date=1998 |volume=1379 |page=18 |doi=10.1007/BFb0052358 |isbn=978-3-540-64301-2 |url=https://books.google.com/books?id=ESr6CAAAQBAJ&pg=PA18}}</ref>
एक पुनर्लेखन प्रणाली में सामान्य रूप गुण (NF) होता है यदि सभी वस्तुओं के लिए a और सामान्य रूप b, b को पुनर्लेखन की एक श्रृंखला द्वारा a से पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a b तक कम हो जाता है। एक पुनर्लेखन प्रणाली में अद्वितीय सामान्य रूप गुण (यूएन) होता है यदि सभी सामान्य रूपों के लिए a, b ∈ S, a तक b से पुनर्लेखन की श्रृंखला द्वारा पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a, b के बराबर हो। एक पुनर्लेखन प्रणाली में कमी के संबंध में विशिष्ट सामान्य रूप की संपत्ति होती है (UN<sup>→</sup>) यदि प्रत्येक पद को सामान्य रूपों a और b में कम करने के लिए, a, b के बराबर है।<ref name=NF>{{cite journal |last1=Klop |first1=J.W. |last2=de Vrijer |first2=R.C. |title=विशेषण जोड़ी के साथ लैम्ब्डा कैलकुलस के लिए अद्वितीय सामान्य रूप|journal=Information and Computation |date=February 1989 |volume=80 |issue=2 |pages=97–113 |doi=10.1016/0890-5401(89)90014-X |doi-access=free }}</ref>




Line 12: Line 14:


यह खंड कुछ प्रसिद्ध परिणाम प्रस्तुत करता है। सबसे पहले, SN का अर्थ WN है।<ref>{{cite web |title=logic - What is the difference between strong normalization and weak normalization in the context of rewrite systems? |url=https://cs.stackexchange.com/questions/68080/what-is-the-difference-between-strong-normalization-and-weak-normalization-in-th |website=Computer Science Stack Exchange |access-date=12 September 2021}}</ref>
यह खंड कुछ प्रसिद्ध परिणाम प्रस्तुत करता है। सबसे पहले, SN का अर्थ WN है।<ref>{{cite web |title=logic - What is the difference between strong normalization and weak normalization in the context of rewrite systems? |url=https://cs.stackexchange.com/questions/68080/what-is-the-difference-between-strong-normalization-and-weak-normalization-in-th |website=Computer Science Stack Exchange |access-date=12 September 2021}}</ref>
संगम (शब्द पुनर्लेखन) (संक्षिप्त सीआर) का अर्थ है NF का अर्थ है UN का अर्थ है UN<sup>→ </सुप>।<ref name=NF/>उल्टे निहितार्थ आम तौर पर पकड़ में नहीं आते हैं। {a→b,a→c,c→c,d→c,d→e} UN है<sup>→</sup> लेकिन UN नहीं क्योंकि b=e और b,e सामान्य रूप हैं। {a→b,a→c,b→b} यूएन है लेकिन एनएफ नहीं है क्योंकि बी = सी, सी एक सामान्य रूप है, और बी सी को कम नहीं करता है। {a→b,a→c,b→b,c→c} एनएफ है क्योंकि कोई सामान्य रूप नहीं है, लेकिन सीआर नहीं है क्योंकि बी और सी को कम करता है, और बी, सी में कोई सामान्य कमी नहीं है।
डब्ल्यूएन और यूएन<sup>→</sup> मतलब संगम। इसलिए सीआर, एनएफ, यूएन और यूएन<sup>→</sup> यदि WN धारण करता है तो मेल खाता है।<ref>{{cite book |last1=Ohlebusch |first1=Enno |title=टर्म पुनर्लेखन में उन्नत विषय|date=17 April 2013 |publisher=Springer Science & Business Media |isbn=978-1-4757-3661-8 |pages=13–14 |url=https://books.google.com/books?id=jSHaBwAAQBAJ&pg=PA13 |language=en}}</ref>


संगम (संक्षिप्त CR) का अर्थ है NF का अर्थ है UN का अर्थ है UN<sup>→</sup> उत्क्रम निहितार्थ सामान्यतः पकड़ में नहीं आते हैं।<sup><ref name="NF" /> {a→b,a→c,c→c,d→c,d→e} UN<sup>→</sup> है किंतु  UN नहीं क्योंकि b=e और b,e सामान्य रूप हैं।{a→b,a→c,b→b} UN  है किंतु  NF  नहीं है क्योंकि b=c, c एक सामान्य रूप है, और बी सी को कम नहीं करता है। {a→b,a→c,b→b,c→c}  NF है क्योंकि कोई सामान्य रूप नहीं है किंतु  CR नहीं है क्योंकि b और c को कम करता है, और b,c में कोई सामान्य कमी नहीं है।WN और UN<sup>→</sup> अर्थ संगम इसलिए CR, NF , UN और UN<sup>→</sup> यदि WN धारण करता है तो मेल खाता है।<ref>{{cite book |last1=Ohlebusch |first1=Enno |title=टर्म पुनर्लेखन में उन्नत विषय|date=17 April 2013 |publisher=Springer Science & Business Media |isbn=978-1-4757-3661-8 |pages=13–14 |url=https://books.google.com/books?id=jSHaBwAAQBAJ&pg=PA13 |language=en}}</ref>
== उदाहरण ==
== उदाहरण ==


एक उदाहरण यह है कि अंकगणितीय व्यंजकों को सरल बनाने से एक संख्या उत्पन्न होती है - अंकगणित में, सभी संख्याएँ सामान्य रूप होती हैं। एक उल्लेखनीय तथ्य यह है कि सभी अंकगणितीय अभिव्यक्तियों का एक अनूठा मूल्य है, इसलिए पुनर्लेखन प्रणाली दृढ़ता से सामान्यीकृत और संगम है:<ref>{{cite book |author1=Terese |title=टर्म पुनर्लेखन प्रणाली|date=2003 |publisher=Cambridge University Press |location=Cambridge, UK |isbn=0-521-39115-6 |page=1}}</ref>
एक उदाहरण यह है कि अंकगणितीय व्यंजकों को सरल बनाने से एक संख्या उत्पन्न होती है - अंकगणित में सभी संख्याएँ सामान्य रूप होती हैं। एक उल्लेखनीय तथ्य यह है कि सभी अंकगणितीय अभिव्यक्तियों का एक अद्वितीय मान है इसलिए पुनर्लेखन प्रणाली दृढ़ता से सामान्यीकृत और संगम है:<ref>{{cite book |author1=Terese |title=टर्म पुनर्लेखन प्रणाली|date=2003 |publisher=Cambridge University Press |location=Cambridge, UK |isbn=0-521-39115-6 |page=1}}</ref>
:(3 + 5) * (1 + 2) ⇒ 8 * (1 + 2) ⇒ 8 * 3 ⇒ 24
:(3 + 5) * (1 + 2) ⇒ 8 * (1 + 2) ⇒ 8 * 3 ⇒ 24
:(3 + 5) * (1 + 2) ⇒ (3 + 5) * 3 ⇒ 3*3 + 5*3 ⇒ 9 + 5*3 ⇒ 9 + 15 ⇒ 24
:(3 + 5) * (1 + 2) ⇒ (3 + 5) * 3 ⇒ 3*3 + 5*3 ⇒ 9 + 5*3 ⇒ 9 + 15 ⇒ 24


गैर-सामान्यीकृत प्रणालियों के उदाहरणों (कमजोर या दृढ़ता से नहीं) में अनंत तक गिनती (1 ⇒ 2 ⇒ 3 ⇒ ...) और लूप जैसे [[Collatz अनुमान]] के परिवर्तन समारोह (1 ⇒ 2 ⇒ 4 ⇒ 1 ⇒ ...) शामिल हैं। , अगर Collatz रूपांतरण के कोई अन्य लूप हैं तो यह एक खुली समस्या है)।<ref>{{cite book |author1=Terese |title=टर्म पुनर्लेखन प्रणाली|date=2003 |publisher=Cambridge University Press |location=Cambridge, UK |isbn=0-521-39115-6 |page=2}}</ref> एक अन्य उदाहरण एकल-नियम प्रणाली है { r(x,y) → r(y,x) }, जिसमें किसी भी शब्द से कोई सामान्य गुण नहीं है, उदा। r(4,2) एक एकल पुनर्लेखन क्रम शुरू होता है, अर्थात। r(4,2) → r(2,4) → r(4,2) → r(2,4) → ..., जो असीम रूप से लंबा है। यह मोडुलो [[ क्रमविनिमेयता ]] को फिर से लिखने के विचार की ओर ले जाता है जहां कोई नियम सामान्य रूप में होता है यदि कोई नियम नहीं है लेकिन कम्यूटेटिविटी लागू होती है।<ref>{{cite book| first1=Nachum|last1=Dershowitz|first2=Jean-Pierre|last2=Jouannaud| chapter=6. Rewrite Systems|title=सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका| year=1990| volume=B| publisher=Elsevier| editor=Jan van Leeuwen| editor-link=Jan van Leeuwen| series=सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका|citeseerx=10.1.1.64.3114|isbn=0-444-88074-7|pages=9–10}}</ref>
गैर-सामान्यीकृत प्रणालियों के उदाहरणों (अशक्त या दृढ़ता से नहीं) में अनंत तक गिनती (1 ⇒ 2 ⇒ 3 ⇒ ...) और लूप जैसे [[Collatz अनुमान|कोलात्ज़ अनुमान]] के परिवर्तन कार्य (1 ⇒ 2 ⇒ 4 ⇒ 1 ⇒ ...) सम्मिलित हैं। यदि कोलात्ज़ रूपांतरण के कोई अन्य लूप हैं तो यह एक विवर्त समस्या है)।<ref>{{cite book |author1=Terese |title=टर्म पुनर्लेखन प्रणाली|date=2003 |publisher=Cambridge University Press |location=Cambridge, UK |isbn=0-521-39115-6 |page=2}}</ref> एक अन्य उदाहरण एकल-नियम प्रणाली है { { ''r''(''x'',''y'') → ''r''(''y'',''x'') }, जिसमें किसी भी शब्द से कोई सामान्य गुण नहीं है, उदा। r(4,2) एक एकल पुनर्लेखन क्रम प्रारंभ होता है, अर्थात  ''r''(4,2) → ''r''(2,4) → ''r''(4,2) → ''r''(2,4) → ..., जो असीम रूप से लंबा है। यह मोडुलो [[ क्रमविनिमेयता | क्रमविनिमेयता]] को फिर से लिखने के विचार की ओर ले जाता है जहां कोई नियम सामान्य रूप में होता है यदि कोई नियम नहीं है किंतु  कम्यूटेटिविटी प्रयुक्त होती है।<ref>{{cite book| first1=Nachum|last1=Dershowitz|first2=Jean-Pierre|last2=Jouannaud| chapter=6. Rewrite Systems|title=सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका| year=1990| volume=B| publisher=Elsevier| editor=Jan van Leeuwen| editor-link=Jan van Leeuwen| series=सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका|citeseerx=10.1.1.64.3114|isbn=0-444-88074-7|pages=9–10}}</ref>
 
[[File:Cyclic_locally,_but_not_globally_confluent_rewrite_system.png|thumb|अशक्त किंतु  दृढ़ता से पुनर्लेखन प्रणाली को सामान्य नहीं कर रहा है<ref name="Dershowitz.Jouannaud.1990.Fig2">{{cite book | isbn=0-444-88074-7 | editor=Jan van Leeuwen | title=औपचारिक मॉडल और शब्दार्थ| publisher=Elsevier | series=Handbook of Theoretical Computer Science | volume=B | year=1990 | author=N. Dershowitz and J.-P. Jouannaud | contribution=Rewrite Systems | page=268}}</ref>]]
 


[[File:Cyclic_locally,_but_not_globally_confluent_rewrite_system.png|thumb|कमजोर लेकिन दृढ़ता से पुनर्लेखन प्रणाली को सामान्य नहीं कर रहा है<ref name="Dershowitz.Jouannaud.1990.Fig2">{{cite book | isbn=0-444-88074-7 | editor=Jan van Leeuwen | title=औपचारिक मॉडल और शब्दार्थ| publisher=Elsevier | series=Handbook of Theoretical Computer Science | volume=B | year=1990 | author=N. Dershowitz and J.-P. Jouannaud | contribution=Rewrite Systems | page=268}}</ref>]]सिस्टम {बी → ए, बी → सी, सी → बी, सी → डी} (चित्रित) कमजोर सामान्यीकरण का एक उदाहरण है, लेकिन दृढ़ता से सामान्यीकरण प्रणाली नहीं है। ए और डी सामान्य रूप हैं, और बी और सी को ए या डी में घटाया जा सकता है, लेकिन अनंत कमी बी → सी → बी → सी → ... का अर्थ है कि न तो बी और न ही सी दृढ़ता से सामान्यीकरण कर रहा है।
प्रणाली {''b'' → ''a'', ''b'' → ''c'', ''c'' → ''b'', ''c'' → ''d''} (चित्रित) अशक्त सामान्यीकरण का एक उदाहरण है, किंतु दृढ़ता से सामान्यीकरण प्रणाली नहीं है। ''a'' और ''d'' सामान्य रूप हैं, और ''b''  और ''c'' को ''a'' या ''d'' में घटाया जा सकता है, किंतु अनंत कमी ''b'' → ''c'' → ''b'' → ''c'' → ... का अर्थ है कि न तो ''b'' और न ही ''c'' दृढ़ता से सामान्यीकरण कर रहा है।


=== अनटाइप्ड [[लैम्ब्डा कैलकुलस]] ===
=== अनटाइप्ड [[लैम्ब्डा कैलकुलस]] ===
शुद्ध अप्रकाशित लैम्ब्डा कैलकुलस मजबूत सामान्यीकरण संपत्ति को संतुष्ट नहीं करता है, और कमजोर सामान्यीकरण संपत्ति को भी नहीं। शब्द पर विचार करें <math>\lambda x . x x x</math> (आवेदन सहयोगी छोड़ दिया गया है)। इसका निम्नलिखित पुनर्लेखन नियम है: किसी भी पद के लिए <math>t</math>,
शुद्ध अप्रकाशित लैम्ब्डा कैलकुलस शसक्त सामान्यीकरण संपत्ति को संतुष्ट नहीं करता है, और अशक्त सामान्यीकरण संपत्ति को भी नहीं शब्द <math>\lambda x . x x x</math> पर विचार करें। (अनुप्रयोग बाएं साहचर्य है) इसका निम्नलिखित पुनर्लेखन नियम है: किसी भी पद <math>t</math> के लिए,


: <math>(\mathbf{\lambda} x . x x x) t \rightarrow t t t</math>
: <math>(\mathbf{\lambda} x . x x x) t \rightarrow t t t</math>
लेकिन विचार करें कि जब हम आवेदन करते हैं तो क्या होता है <math>\lambda x . x x x</math> खुद को:
किंतु  विचार करें कि जब हम <math>\lambda x . x x x</math> प्रयुक्त करते हैं तो क्या होता है खुद के लिए:


: <math>\begin{align}
: <math>\begin{align}
Line 44: Line 46:
\end{align}
\end{align}
</math>
</math>
इसलिए, शब्द <math>(\lambda x . x x x) (\lambda x . x x x)</math> दृढ़ता से सामान्यीकरण नहीं कर रहा है। और यह केवल कमी का क्रम है, इसलिए यह कमजोर रूप से सामान्यीकरण भी नहीं कर रहा है।
इसलिए शब्द <math>(\lambda x . x x x) (\lambda x . x x x)</math> दृढ़ता से सामान्यीकरण नहीं कर रहा है। और यह केवल कमी का क्रम है इसलिए यह अशक्त रूप से सामान्यीकरण भी नहीं कर रहा है।


=== लैम्ब्डा कैलकुलस टाइप किया ===
=== लैम्ब्डा कैलकुलस टाइप किया ===


टाइप किए गए लैम्ब्डा कैलकुलस की विभिन्न प्रणालियाँ जिनमें शामिल हैं
टाइप किए गए लैम्ब्डा कैलकुलस की विभिन्न प्रणालियाँ जिनमें सामान्य रूप से टाइप किए गए लैम्ब्डा कैलकुलस जीन-यवेस गिरार्ड के प्रणाली एफ और [[थिएरी कोक्वांड]] के निर्माण के कैलकुलस सम्मिलित हैं दृढ़ता से सामान्यीकरण कर रहे हैं।
बस टाइप किया हुआ लैम्ब्डा कैलकुलस, [[जीन-यवेस गिरार्ड]] का [[सिस्टम एफ]], और [[थिएरी कोक्वांड]] का निर्माण का कैलकुलस दृढ़ता से सामान्यीकरण कर रहा है।
 
सामान्यीकरण संपत्ति के साथ एक लैम्ब्डा कैलकुलस सिस्टम को एक प्रोग्रामिंग भाषा के रूप में देखा जा सकता है, जिसमें संपत्ति का प्रत्येक कार्यक्रम [[समाप्ति विश्लेषण]] होता है। हालांकि यह एक बहुत ही उपयोगी संपत्ति है, इसमें एक खामी है: सामान्यीकरण संपत्ति के साथ एक प्रोग्रामिंग भाषा [[ट्यूरिंग पूर्ण]] नहीं हो सकती है, अन्यथा कोई प्रोग्राम के प्रकार की जांच करके हॉल्टिंग समस्या को हल कर सकता है। इसका मतलब यह है कि ऐसे संगणनीय कार्य हैं जिन्हें केवल टाइप किए गए लैम्ब्डा कैलकुलस में परिभाषित नहीं किया जा सकता है, और इसी तरह निर्माण और सिस्टम एफ के कैलकुलस के लिए। एक विशिष्ट उदाहरण मेटा-सर्कुलर मूल्यांकनकर्ता का है # कुल प्रोग्रामिंग भाषाओं में स्व-व्याख्या | स्वयं कुल प्रोग्रामिंग भाषा में दुभाषिया।<ref>{{cite book |last1=Riolo |first1=Rick |last2=Worzel |first2=William P. |last3=Kotanchek |first3=Mark |title=जेनेटिक प्रोग्रामिंग सिद्धांत और अभ्यास बारहवीं|date=4 June 2015 |publisher=Springer |isbn=978-3-319-16030-6|page=59 |url=https://books.google.com/books?id=rfDLCQAAQBAJ&pg=PA59 |access-date=8 September 2021 |language=en}}</ref>
 


सामान्यीकरण संपत्ति के साथ एक लैम्ब्डा कैलकुलस प्रणाली को एक प्रोग्रामिंग भाषा के रूप में देखा जा सकता है, जिसमें संपत्ति का प्रत्येक कार्यक्रम [[समाप्ति विश्लेषण]] होता है। चूँकि यह एक बहुत ही उपयोगी संपत्ति है इसमें एक खामी है: सामान्यीकरण संपत्ति के साथ एक प्रोग्रामिंग भाषा [[ट्यूरिंग पूर्ण]] नहीं हो सकती है, अन्यथा कोई प्रोग्राम के प्रकार की जांच करके हॉल्टिंग समस्या को हल कर सकता है। इसका अर्थ यह है कि ऐसे संगणनीय कार्य हैं जिन्हें केवल टाइप किए गए लैम्ब्डा कैलकुलस में परिभाषित नहीं किया जा सकता है, और इसी तरह निर्माण और प्रणाली एफ के कैलकुलस के लिए एक विशिष्ट उदाहरण कुल प्रोग्रामिंग भाषा में एक स्व-दुभाषिया का है।<ref>{{cite book |last1=Riolo |first1=Rick |last2=Worzel |first2=William P. |last3=Kotanchek |first3=Mark |title=जेनेटिक प्रोग्रामिंग सिद्धांत और अभ्यास बारहवीं|date=4 June 2015 |publisher=Springer |isbn=978-3-319-16030-6|page=59 |url=https://books.google.com/books?id=rfDLCQAAQBAJ&pg=PA59 |access-date=8 September 2021 |language=en}}</ref>
== यह भी देखें ==
== यह भी देखें ==
* [[कानूनी फॉर्म]]
* [[कानूनी फॉर्म]]

Revision as of 14:36, 24 May 2023

सार पुनर्लेखन में[1] एक वस्तु सामान्य रूप में होती है यदि इसे आगे फिर से नहीं लिखा जा सकता है अर्थात यह अप्रासंगिक है। पुनर्लेखन प्रणाली के आधार पर एक वस्तु कई सामान्य रूपों में फिर से लिख सकती है या पूर्ण रूप से भी नहीं पुनर्लेखन प्रणालियों के कई गुण सामान्य रूपों से संबंधित हैं।

परिभाषाएँ <अवधि वर्ग = एंकर आईडी = परिभाषा>

औपचारिक रूप से कहा गया है, यदि (A,→) एक अमूर्त पुनर्लेखन प्रणाली या परिभाषा है, x∈A 'सामान्य रूप' में है यदि कोई y∈A उपस्थित नहीं है जैसे कि x→y, यानी x एक अप्रासंगिक शब्द है।

एक वस्तु a 'अशक्त रूप से सामान्यीकरण' है यदि वहाँ से प्रारंभ होने वाले पुनर्लेखन का कम से कम एक विशेष क्रम उपस्थित है जो अंततः एक सामान्य रूप देता है। एक पुनर्लेखन प्रणाली में 'अशक्त सामान्यीकरण गुण' होता है या (अशक्त ) सामान्यीकरण (डब्ल्यू एन) होता है यदि प्रत्येक वस्तु अशक्त रूप से सामान्य हो रही हो। एक वस्तु a 'दृढ़ता से सामान्य' होती है यदि a से प्रारंभ होने वाले पुनर्लेखन का प्रत्येक क्रम अंततः सामान्य रूप से समाप्त हो जाता है। एक सार पुनर्लेखन प्रणाली जोरदार सामान्यीकरण समाप्ति नोथेरियन है, या '(शसक्त) सामान्यीकरण संपत्ति' (एसएन) है यदि इसकी प्रत्येक वस्तु दृढ़ता से सामान्य हो रही है।[2]

एक पुनर्लेखन प्रणाली में सामान्य रूप गुण (एनएफ) होता है यदि सभी वस्तुओं के लिए a और सामान्य रूप b, b को पुनर्लेखन की एक श्रृंखला द्वारा a से पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a b तक कम हो जाता है। एक पुनर्लेखन प्रणाली में अद्वितीय सामान्य रूप गुण (यूएन) होता है यदि सभी सामान्य रूपों के लिए a, b ∈ S, a तक b से पुनर्लेखन की श्रृंखला द्वारा पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a, b के समान हो एक पुनर्लेखन प्रणाली में कमी के संबंध में विशिष्ट सामान्य रूप की संपत्ति होती है (UN→) यदि प्रत्येक पद को सामान्य रूपों a और b में कम करने के लिए, a, b के समान है।[3]


परिणाम

यह खंड कुछ प्रसिद्ध परिणाम प्रस्तुत करता है। सबसे पहले, SN का अर्थ WN है।[4]

संगम (संक्षिप्त CR) का अर्थ है NF का अर्थ है UN का अर्थ है UN→ उत्क्रम निहितार्थ सामान्यतः पकड़ में नहीं आते हैं।[3] {a→b,a→c,c→c,d→c,d→e} UN→ है किंतु UN नहीं क्योंकि b=e और b,e सामान्य रूप हैं।{a→b,a→c,b→b} UN है किंतु NF नहीं है क्योंकि b=c, c एक सामान्य रूप है, और बी सी को कम नहीं करता है। {a→b,a→c,b→b,c→c} NF है क्योंकि कोई सामान्य रूप नहीं है किंतु CR नहीं है क्योंकि b और c को कम करता है, और b,c में कोई सामान्य कमी नहीं है।WN और UN→ अर्थ संगम इसलिए CR, NF , UN और UN→ यदि WN धारण करता है तो मेल खाता है।[5]

उदाहरण

एक उदाहरण यह है कि अंकगणितीय व्यंजकों को सरल बनाने से एक संख्या उत्पन्न होती है - अंकगणित में सभी संख्याएँ सामान्य रूप होती हैं। एक उल्लेखनीय तथ्य यह है कि सभी अंकगणितीय अभिव्यक्तियों का एक अद्वितीय मान है इसलिए पुनर्लेखन प्रणाली दृढ़ता से सामान्यीकृत और संगम है:[6]

(3 + 5) * (1 + 2) ⇒ 8 * (1 + 2) ⇒ 8 * 3 ⇒ 24
(3 + 5) * (1 + 2) ⇒ (3 + 5) * 3 ⇒ 3*3 + 5*3 ⇒ 9 + 5*3 ⇒ 9 + 15 ⇒ 24

गैर-सामान्यीकृत प्रणालियों के उदाहरणों (अशक्त या दृढ़ता से नहीं) में अनंत तक गिनती (1 ⇒ 2 ⇒ 3 ⇒ ...) और लूप जैसे कोलात्ज़ अनुमान के परिवर्तन कार्य (1 ⇒ 2 ⇒ 4 ⇒ 1 ⇒ ...) सम्मिलित हैं। यदि कोलात्ज़ रूपांतरण के कोई अन्य लूप हैं तो यह एक विवर्त समस्या है)।[7] एक अन्य उदाहरण एकल-नियम प्रणाली है { { r(x,y) → r(y,x) }, जिसमें किसी भी शब्द से कोई सामान्य गुण नहीं है, उदा। r(4,2) एक एकल पुनर्लेखन क्रम प्रारंभ होता है, अर्थात r(4,2) → r(2,4) → r(4,2) → r(2,4) → ..., जो असीम रूप से लंबा है। यह मोडुलो क्रमविनिमेयता को फिर से लिखने के विचार की ओर ले जाता है जहां कोई नियम सामान्य रूप में होता है यदि कोई नियम नहीं है किंतु कम्यूटेटिविटी प्रयुक्त होती है।[8]

अशक्त किंतु दृढ़ता से पुनर्लेखन प्रणाली को सामान्य नहीं कर रहा है[9]


प्रणाली {b → a, b → c, c → b, c → d} (चित्रित) अशक्त सामान्यीकरण का एक उदाहरण है, किंतु दृढ़ता से सामान्यीकरण प्रणाली नहीं है। a और d सामान्य रूप हैं, और b और c को a या d में घटाया जा सकता है, किंतु अनंत कमी b → c → b → c → ... का अर्थ है कि न तो b और न ही c दृढ़ता से सामान्यीकरण कर रहा है।

अनटाइप्ड लैम्ब्डा कैलकुलस

शुद्ध अप्रकाशित लैम्ब्डा कैलकुलस शसक्त सामान्यीकरण संपत्ति को संतुष्ट नहीं करता है, और अशक्त सामान्यीकरण संपत्ति को भी नहीं शब्द पर विचार करें। (अनुप्रयोग बाएं साहचर्य है) इसका निम्नलिखित पुनर्लेखन नियम है: किसी भी पद के लिए,

किंतु विचार करें कि जब हम प्रयुक्त करते हैं तो क्या होता है खुद के लिए:

इसलिए शब्द दृढ़ता से सामान्यीकरण नहीं कर रहा है। और यह केवल कमी का क्रम है इसलिए यह अशक्त रूप से सामान्यीकरण भी नहीं कर रहा है।

लैम्ब्डा कैलकुलस टाइप किया

टाइप किए गए लैम्ब्डा कैलकुलस की विभिन्न प्रणालियाँ जिनमें सामान्य रूप से टाइप किए गए लैम्ब्डा कैलकुलस जीन-यवेस गिरार्ड के प्रणाली एफ और थिएरी कोक्वांड के निर्माण के कैलकुलस सम्मिलित हैं दृढ़ता से सामान्यीकरण कर रहे हैं।

सामान्यीकरण संपत्ति के साथ एक लैम्ब्डा कैलकुलस प्रणाली को एक प्रोग्रामिंग भाषा के रूप में देखा जा सकता है, जिसमें संपत्ति का प्रत्येक कार्यक्रम समाप्ति विश्लेषण होता है। चूँकि यह एक बहुत ही उपयोगी संपत्ति है इसमें एक खामी है: सामान्यीकरण संपत्ति के साथ एक प्रोग्रामिंग भाषा ट्यूरिंग पूर्ण नहीं हो सकती है, अन्यथा कोई प्रोग्राम के प्रकार की जांच करके हॉल्टिंग समस्या को हल कर सकता है। इसका अर्थ यह है कि ऐसे संगणनीय कार्य हैं जिन्हें केवल टाइप किए गए लैम्ब्डा कैलकुलस में परिभाषित नहीं किया जा सकता है, और इसी तरह निर्माण और प्रणाली एफ के कैलकुलस के लिए एक विशिष्ट उदाहरण कुल प्रोग्रामिंग भाषा में एक स्व-दुभाषिया का है।[10]

यह भी देखें

टिप्पणियाँ


संदर्भ

  1. ↑ Franz Baader; Tobias Nipkow (1998). टर्म पुनर्लेखन और वह सब. Cambridge University Press. ISBN 9780521779203.
  2. ↑ Ohlebusch, Enno (1998). "एब्स्ट्रैक्ट रिडक्शन मोडुलो ए इक्वैलेंस रिलेशन के लिए चर्च-रॉसर प्रमेय". Rewriting Techniques and Applications. Lecture Notes in Computer Science. 1379: 18. doi:10.1007/BFb0052358. ISBN 978-3-540-64301-2.
  3. ↑ 3.0 3.1 Klop, J.W.; de Vrijer, R.C. (February 1989). "विशेषण जोड़ी के साथ लैम्ब्डा कैलकुलस के लिए अद्वितीय सामान्य रूप". Information and Computation. 80 (2): 97–113. doi:10.1016/0890-5401(89)90014-X.
  4. ↑ "logic - What is the difference between strong normalization and weak normalization in the context of rewrite systems?". Computer Science Stack Exchange. Retrieved 12 September 2021.
  5. ↑ Ohlebusch, Enno (17 April 2013). टर्म पुनर्लेखन में उन्नत विषय (in English). Springer Science & Business Media. pp. 13–14. ISBN 978-1-4757-3661-8.
  6. ↑ Terese (2003). टर्म पुनर्लेखन प्रणाली. Cambridge, UK: Cambridge University Press. p. 1. ISBN 0-521-39115-6.
  7. ↑ Terese (2003). टर्म पुनर्लेखन प्रणाली. Cambridge, UK: Cambridge University Press. p. 2. ISBN 0-521-39115-6.
  8. ↑ Dershowitz, Nachum; Jouannaud, Jean-Pierre (1990). "6. Rewrite Systems". In Jan van Leeuwen (ed.). सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका. सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका. Vol. B. Elsevier. pp. 9–10. CiteSeerX 10.1.1.64.3114. ISBN 0-444-88074-7.
  9. ↑ N. Dershowitz and J.-P. Jouannaud (1990). "Rewrite Systems". In Jan van Leeuwen (ed.). औपचारिक मॉडल और शब्दार्थ. Handbook of Theoretical Computer Science. Vol. B. Elsevier. p. 268. ISBN 0-444-88074-7.
  10. ↑ Riolo, Rick; Worzel, William P.; Kotanchek, Mark (4 June 2015). जेनेटिक प्रोग्रामिंग सिद्धांत और अभ्यास बारहवीं (in English). Springer. p. 59. ISBN 978-3-319-16030-6. Retrieved 8 September 2021.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सामान्य_रूप_(सार_पुनर्लेखन)&oldid=183195’