संगणनीय फलन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (6 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{short description|Mathematical function that can be computed by a program}} | {{short description|Mathematical function that can be computed by a program}} | ||
संगणनीय | संगणनीय कार्य संगणनीयता सिद्धांत अध्ययन की मौलिक वस्तुएं हैं। संगणनीय कार्य [[Index.php?title=एल्गोरिथम|एल्गोरिथम]] की सहज धारणा के औपचारिक रूप हैं, इसका अर्थ है कि यह एक फंक्शन गणना योग्य है यदि कोई एल्गोरिथम सम्मलित है जो फंक्शन संगणनीयता का कार्य कर सकता है, अर्थात् फंक्शन कार्यक्षेत्र में एक इनपुट होता है जो आनुषंगिक उत्पाद को वापस कर सकता है। संगणनीय कार्य का उपयोग गणना के किसी भी ठोस मॉडल जैसे कि [[ट्यूरिंग मशीन]] या [[रजिस्टर मशीन]] के [[Index.php?title= संदर्भ|संदर्भ]] के अतिरिक्त संगणनीयता पर चर्चा करने के लिए किया जाता है। चूंकि, किसी भी परिभाषा की गणना करने के लिये कुछ विशिष्ट मॉडल का उल्लेख होना चाहिए, परंतु सभी मान्य परिभाषाएँ समान वर्ग में कार्य करती हैं। | ||
अभिकलन के विशेष मॉडल जो संगणनीय | अभिकलन के विशेष मॉडल जो संगणनीय कार्य के सेट को जन्म देते हैं, वे [[Index.php?title=ट्यूरिंग-गणनीय फलन|ट्यूरिंग-गणनीय फलन]] और [[Index.php?title=सामान्य पुनरावर्ती फलन|सामान्य पुनरावर्ती फलन]] हैं। | ||
संगणनीय | संगणनीय कार्य की सटीक परिभाषा से पहले, [[Index.php?title= मैथेमेटिशन|मैथेमेटिशन]] अधिकांशतः अनौपचारिक शब्द का प्रभावी ढंग से गणना योग्य उपयोग करते थे। तब से यह शब्द संगणनीय कार्य के साथ पहचाना जाने लगा है। इन कार्यों की प्रभावी संगणनीयता का अर्थ यह नहीं है कि उनकी कुशलता से गणना की जा सकती है। वास्तव में, कुछ प्रभावी रूप से गणना योग्य कार्यों के लिए यह दिखाया जा सकता है कि उनकी गणना करने वाला कोई भी एल्गोरिथम का समय इनपुट की लंबाई के साथ [[घातीय वृद्धि]] से(या [[Index.php?title=सुपरएक्सपोनेंशियली|सुपरएक्सपोनेंशियली]]) को बढ़ाता है। व्यवहार्य संगणनीयता और संगणनात्मक जटिलता के साथ उन क्षेत्र के कार्यों का अध्ययन करते हैं। | ||
चर्च -ट्यूरिंग थीसिस के अनुसार, संगणनीय फलन वास्तव में ऐसे कार्य हैं जिनकी गणना एक यांत्रिक गणना उपकरण का उपयोग करके असीमित मात्रा में समय और भंडारण स्थान के साथ की जा सकती है, समतुल्य रूप से, यह थीसिस बताती है कि एक फलन संगणनीय है और एकमात्र इसमें एल्गोरिथम हो। इस अर्थ में एक एल्गोरिथम को असीमित स्थिति के रूप में समझा जाता है। | चर्च -ट्यूरिंग थीसिस के अनुसार, संगणनीय फलन वास्तव में ऐसे कार्य हैं जिनकी गणना एक यांत्रिक गणना उपकरण का उपयोग करके असीमित मात्रा में समय और भंडारण स्थान के साथ की जा सकती है, समतुल्य रूप से, यह थीसिस बताती है कि एक फलन संगणनीय है और एकमात्र इसमें एल्गोरिथम हो। इस अर्थ में एक एल्गोरिथम को असीमित स्थिति के रूप में समझा जाता है। | ||
ब्लम स्वयंसिद्धों का उपयोग संगणनीय | ब्लम स्वयंसिद्धों का उपयोग संगणनीय कार्य के सेट पर एक अमूर्त [[Index.php?title=संगणनात्मक जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]] को परिभाषित करने के लिए किया जा सकता है। संगणनात्मक जटिलता सिद्धांत में, एक संगणनीय फलन की जटिलता को निर्धारण करने की समस्या को एक कार्य प्रायौगिक के रूप में जाना जाता है। | ||
== परिभाषा == | == परिभाषा == | ||
| Line 13: | Line 13: | ||
किसी कार्य की संगणनीयता एक अनौपचारिक धारणा है। इसका वर्णन करने का एक नियम यह है कि एक कार्य गणना योग्य है यदि इसका मूल्य एक प्रभावी विधि द्वारा प्राप्त किया जा सकता है। अधिक कठोरता के साथ, एक कार्य <math>f:\mathbb N^k\rightarrow\mathbb N</math> | किसी कार्य की संगणनीयता एक अनौपचारिक धारणा है। इसका वर्णन करने का एक नियम यह है कि एक कार्य गणना योग्य है यदि इसका मूल्य एक प्रभावी विधि द्वारा प्राप्त किया जा सकता है। अधिक कठोरता के साथ, एक कार्य <math>f:\mathbb N^k\rightarrow\mathbb N</math> | ||
संगणनीय है यदि एकमात्र कोई प्रभावी प्रक्रिया है, तो अभिकलनात्मक है {{mvar|k}}-[[ | संगणनीय है यदि एकमात्र कोई प्रभावी प्रक्रिया है, तो अभिकलनात्मक है {{mvar|k}}-[[Index.php?title= टपल|टपल]] <math>\mathbf x</math> प्राकृतिक संख्याओं का, मूल्य का उत्पादन करेगा <math>f(\mathbf x)</math>.<ref>{{cite book|last1=Enderton|first1=Herbert|title=A Mathematical Introduction to Logic|date=2002|publisher=Elsevier|location=USA|isbn=0-12-238452-0|page=209|edition=Second}}</ref> संगणनीय कार्य तर्कों के रूप में कई [[Index.php?title=प्राकृतिक संख्याएँ|प्राकृतिक संख्याएँ]] लेते हैं और एक मूल्य का उत्पादन करते हैं जो एक एकल प्राकृतिक संख्या है। | ||
इस अनौपचारिक विवरण के समकक्षों के रूप में, कई औपचारिक, गणितीय परिभाषाएँ सम्मलित हैं। संगणनीय | इस अनौपचारिक विवरण के समकक्षों के रूप में, कई औपचारिक, गणितीय परिभाषाएँ सम्मलित हैं। संगणनीय कार्य के वर्ग को संगणना के कई समकक्ष मॉडल में परिभाषित किया जा सकता है | ||
* ट्यूरिंग मशीनें | * ट्यूरिंग मशीनें | ||
* μ- पुनरावर्ती कार्य | * μ- पुनरावर्ती कार्य | ||
| Line 24: | Line 24: | ||
यद्यपि ये मॉडल कार्यों, उनके इनपुट, और उनके आउटपुट के लिए अलग -अलग प्रतिनिधित्व का उपयोग करते हैं, अनुवाद किसी भी दो मॉडलों के बीच सम्मलित हैं, और इसलिए प्रत्येक मॉडल अनिवार्य रूप से कार्यों के समान वर्ग का वर्णन करता है, इसका अभिप्राय यह है कि औपचारिक संगणनीयता स्वाभाविक है संकीर्ण।<ref>{{cite book|last1=Enderton|first1=Herbert|title=A Mathematical Introduction to Logic|date=2002|publisher=Elsevier|location=USA|isbn=0-12-238452-0|page=208,262|edition=Second}}</ref> इन कार्यों को कभी -कभी पुनरावर्ती के रूप में संदर्भित किया जाता है अनौपचारिक शब्द "गणना योग्य" के विपरीत,<ref>C. J. Ash, J. Knight, ''Computable Structures and the Hyperarithmetical Hierarchy'' (Studies in Logic and the Foundation of Mathematics, 2000), p. 4</ref> क्लेन और गोडेल के बीच 1934 की चर्चा से उत्पन्न एक अंतर है।<ref>R. Soare, [http://www.people.cs.uchicago.edu/~soare/History/compute.pdf Computability and Recursion] (1995). Accessed 9 November 2022.</ref><sup>p.6 </sup> | यद्यपि ये मॉडल कार्यों, उनके इनपुट, और उनके आउटपुट के लिए अलग -अलग प्रतिनिधित्व का उपयोग करते हैं, अनुवाद किसी भी दो मॉडलों के बीच सम्मलित हैं, और इसलिए प्रत्येक मॉडल अनिवार्य रूप से कार्यों के समान वर्ग का वर्णन करता है, इसका अभिप्राय यह है कि औपचारिक संगणनीयता स्वाभाविक है संकीर्ण।<ref>{{cite book|last1=Enderton|first1=Herbert|title=A Mathematical Introduction to Logic|date=2002|publisher=Elsevier|location=USA|isbn=0-12-238452-0|page=208,262|edition=Second}}</ref> इन कार्यों को कभी -कभी पुनरावर्ती के रूप में संदर्भित किया जाता है अनौपचारिक शब्द "गणना योग्य" के विपरीत,<ref>C. J. Ash, J. Knight, ''Computable Structures and the Hyperarithmetical Hierarchy'' (Studies in Logic and the Foundation of Mathematics, 2000), p. 4</ref> क्लेन और गोडेल के बीच 1934 की चर्चा से उत्पन्न एक अंतर है।<ref>R. Soare, [http://www.people.cs.uchicago.edu/~soare/History/compute.pdf Computability and Recursion] (1995). Accessed 9 November 2022.</ref><sup>p.6 </sup> | ||
कोई गणना योग्य कार्यों को μ- पुनरावर्ती कार्यों के रूप में औपचारिक रूप दे सकता है, जो [[आंशिक कार्य]] हैं जो [[Index.php?title=प्राकृतिक संख्याओं|प्राकृतिक संख्याओं]] के परिमित ट्यूपल्स लेते हैं और एक भी प्राकृतिक संख्या लौटा देते हैं। वे आंशिक कार्यों का सबसे छोटा वर्ग हैं जिनमें निरंतर, उत्तराधिकारी और प्रक्षेपण कार्य सम्मलित हैं, और रचना, आदिम पुनरावर्ती | कोई गणना योग्य कार्यों को μ- पुनरावर्ती कार्यों के रूप में औपचारिक रूप दे सकता है, जो [[आंशिक कार्य]] हैं जो [[Index.php?title=प्राकृतिक संख्याओं|प्राकृतिक संख्याओं]] के परिमित ट्यूपल्स लेते हैं और एक भी प्राकृतिक संख्या लौटा देते हैं। वे आंशिक कार्यों का सबसे छोटा वर्ग हैं जिनमें निरंतर, उत्तराधिकारी और प्रक्षेपण कार्य सम्मलित हैं, और रचना, आदिम पुनरावर्ती फंक्शन और μ संचालक के तहत [[Index.php?title=पूर्ण|पूर्ण]] है। | ||
समान रूप से, संगणनीय | समान रूप से, संगणनीय कार्य को उन कार्यों में औपचारिक रूप दिया जा सकता है, जिसकी गणना एक आदर्श कंप्यूटिंग एजेंट जैसे कि ट्यूरिंग मशीन या रजिस्टर मशीन द्वारा की जा सकती है। औपचारिक रूप से, एक आंशिक फंक्शन <math>f:\mathbb N^k\rightarrow\mathbb N</math> क्या गणना की जा सकती है यदि एकमात्र वहाँ निम्न गुणों के साथ एक कंप्यूटर प्रोग्राम सम्मलित है: | ||
# यदि <math>f(\mathbf x)</math> परिभाषित किया गया है, तो कार्यक्रम इनपुट पर समाप्त हो जाएगा <math>\mathbf x</math> मूल्य के साथ <math>f(\mathbf x)</math> कंप्यूटर मेमोरी में संग्रहीत होता है। | # यदि <math>f(\mathbf x)</math> परिभाषित किया गया है, तो कार्यक्रम इनपुट पर समाप्त हो जाएगा <math>\mathbf x</math> मूल्य के साथ <math>f(\mathbf x)</math> कंप्यूटर मेमोरी में संग्रहीत होता है। | ||
# यदि <math>f(\mathbf x)</math> अपरिभाषित है, तो कार्यक्रम इनपुट पर कभी समाप्त नहीं होता है <math>\mathbf x</math>। | # यदि <math>f(\mathbf x)</math> अपरिभाषित है, तो कार्यक्रम इनपुट पर कभी समाप्त नहीं होता है <math>\mathbf x</math>। | ||
| Line 34: | Line 34: | ||
{{main| एल्गोरिथम}} | {{main| एल्गोरिथम}} | ||
एक संगणनीय | एक संगणनीय कार्य की मूल विशेषता यह है कि कार्य की गणना कैसे करें, यह बताने वाली एक परिमित प्रक्रिया (एक एल्गोरिथम) होनी चाहिए। सूचीबद्ध गणना एक मॉडल प्रक्रिया है और इसका उपयोग कैसे किया जाता है, इसकी व्याख्या अलग -अलग करते हैं, परंतु ये व्याख्या कई गुणों को साझा करती है। तथ्य यह है कि ये मॉडल संगणनीय कार्य के समान वर्ग देते हैं, इस तथ्य से लाभ है कि प्रत्येक मॉडल किसी भी अन्य मॉडलों के लिए यह प्रक्रिया सक्षम है, जितना कि एक [[Index.php?title=कंपाइलर|कंपाइलर]] एक कंप्यूटर भाषा में निर्देशों को पढ़ने और निर्देशों का उत्सर्जन करने में सक्षम होता है। | ||
[[हर्बर्ट एंडर्टन]] [1977] एक संगणनीय फलन की गणना के लिए एक प्रक्रिया की निम्नलिखित विशेषताएं होती है; ट्यूरिंग [1936], रोजर्स [1967], और अन्य लोगों द्वारा इसी तरह के वर्णन दिए गए हैं। | [[हर्बर्ट एंडर्टन]] [1977] एक संगणनीय फलन की गणना के लिए एक प्रक्रिया की निम्नलिखित विशेषताएं होती है; ट्यूरिंग [1936], रोजर्स [1967], और अन्य लोगों द्वारा इसी तरह के वर्णन दिए गए हैं। | ||
* प्रक्रिया के लिए सटीक निर्देश, समय में परिमित होना चाहिए। इस प्रकार प्रत्येक संगणनीय | * प्रक्रिया के लिए सटीक निर्देश, समय में परिमित होना चाहिए। इस प्रकार प्रत्येक संगणनीय कार्य में एक परिमित कार्यक्रम होना चाहिए जो पूरी तरह से वर्णन करता है कि कार्य की गणना कैसे की जाती है। एकमात्र निर्देशों का पालन करके कार्य की गणना करना संभव है;कोई अनुमान या विशेष अंतर्दृष्टि की आवश्यकता नहीं है। | ||
* यदि प्रक्रिया को F के डोमेन में k-tuple 'x' दिया जाता है, तो असतत चरणों की एक परिमित संख्या के बाद प्रक्रिया को समाप्त होना चाहिए और F ('x') को उत्पादन करना चाहिए। सहज रूप से, प्रक्रिया गणना के प्रत्येक चरण में क्या करना है, इसे कवर करने के लिए एक विशिष्ट नियम के साथ सहजता से, प्रक्रिया चरण दर चरण आगे बढ़ती है। | * यदि प्रक्रिया को F के डोमेन में k-tuple 'x' दिया जाता है, तो असतत चरणों की एक परिमित संख्या के बाद प्रक्रिया को समाप्त होना चाहिए और F ('x') को उत्पादन करना चाहिए। सहज रूप से, प्रक्रिया गणना के प्रत्येक चरण में क्या करना है, इसे कवर करने के लिए एक विशिष्ट नियम के साथ सहजता से, प्रक्रिया चरण दर चरण आगे बढ़ती है। फंक्शन का मूल्य लौटाए जाने से पहले एकमात्र सूक्ष्म रूप से कई चरणों को पूरा किया जा सकता है। | ||
*यदि प्रक्रिया को k-tuple 'X' दिया जाता है, जो F की डोमेन में नहीं है, तो प्रक्रिया हमेशा के लिए चल सकती है, कभी भी रुक नहीं सकती। या किसी बिंदु पर अटक नहीं सकती है ('अर्थात, इसके निर्देशों में से किसी एक को भी निष्पादित नहीं किया जा सकता है), परंतु इसे 'x' पर f के लिए एक मूल्य का उत्पादन करने का दिखावा नहीं करना चाहिए। इस प्रकार यदि f ('x') के लिए कोई मूल्य कभी पाया जाता है, तो यह सही मूल्य होना चाहिए। कंप्यूटिंग एजेंट के लिए यह आवश्यक नहीं है कि वह सही परिणामों को गलत परिणामों से सही परिणामों से करे चूंकि प्रक्रिया को सही के रूप में परिभाषित किया गया है। | *यदि प्रक्रिया को k-tuple 'X' दिया जाता है, जो F की डोमेन में नहीं है, तो प्रक्रिया हमेशा के लिए चल सकती है, कभी भी रुक नहीं सकती। या किसी बिंदु पर अटक नहीं सकती है ('अर्थात, इसके निर्देशों में से किसी एक को भी निष्पादित नहीं किया जा सकता है), परंतु इसे 'x' पर f के लिए एक मूल्य का उत्पादन करने का दिखावा नहीं करना चाहिए। इस प्रकार यदि f ('x') के लिए कोई मूल्य कभी पाया जाता है, तो यह सही मूल्य होना चाहिए। कंप्यूटिंग एजेंट के लिए यह आवश्यक नहीं है कि वह सही परिणामों को गलत परिणामों से सही परिणामों से करे चूंकि प्रक्रिया को सही के रूप में परिभाषित किया गया है। | ||
एंडर्टन एक संगणनीय | एंडर्टन एक संगणनीय कार्य के लिए प्रक्रिया की इन 3 आवश्यकताओं के कई स्पष्टीकरणों को सूचीबद्ध करता है:<!-- must be enumerated for the "#Church–Turing thesis" below--> | ||
# प्रक्रिया को सैद्धांतिक रूप से मनमाने ढंग से बड़े तर्कों के लिए काम करना चाहिए। यह नहीं माना जाता है कि तर्क पृथ्वी में परमाणुओं की संख्या से कम हैं, | # प्रक्रिया को सैद्धांतिक रूप से मनमाने ढंग से बड़े तर्कों के लिए काम करना चाहिए। यह नहीं माना जाता है कि तर्क पृथ्वी में परमाणुओं की संख्या से कम हैं, | ||
# आउटपुट उत्पन्न करने के लिए प्रक्रिया को कई चरणों मे समाप्त होना आवश्यक है, परंतु रुकने से पहले यह मनमाने ढंग से कई कदम उठा सकता है। इसमे कोई समय सीमा नहीं मानी जाती है। | # आउटपुट उत्पन्न करने के लिए प्रक्रिया को कई चरणों मे समाप्त होना आवश्यक है, परंतु रुकने से पहले यह मनमाने ढंग से कई कदम उठा सकता है। इसमे कोई समय सीमा नहीं मानी जाती है। | ||
| Line 54: | Line 54: | ||
== संगणनीय सेट और संबंध == | == संगणनीय सेट और संबंध == | ||
प्राकृतिक संख्याओं के एक सेट को संगणनीय कहा जाता है (समानार्थी: पुनरावर्ती,निर्णायक) यदि कोई संगणनीय, योग | प्राकृतिक संख्याओं के एक सेट को संगणनीय कहा जाता है (समानार्थी: पुनरावर्ती,निर्णायक) यदि कोई संगणनीय, योग कार्य है जैसे कि किसी भी प्राकृतिक संख्या {{math|<var>n</var>}} के लिए, {{math|''f''(<var>n</var>) {{=}} 1}} {{math|<var>n</var>}}, {{math|<var>A</var>}} में है और {{math|''f''(<var>n</var>) {{=}} 0}} {{math|<var>n</var>}}, {{math|<var>A</var>}} में नहीं है। | ||
प्राकृतिक संख्याओं के एक सेट को संगणनीय गणना योग्य कहा जाता है (समानार्थक: पुनरावर्ती रूप से गणना करने योग्य, अर्ध-निर्णायक) यदि कोई संगणनीय फलन {{math|''f''}} है जैसे कि प्रत्येक संख्या {{math|<var>n</var>}} के लिए, {{math|''f''(<var>n</var>)}} को परिभाषित किया जाता है [[यदि और एकमात्र]] {{math|<var>n</var>}} सेट में है। इस प्रकार एक सेट संगणनीय रूप से यदि और , एकमात्र यह कुछ संगणनीय फसन का डोमेन है। गणना योग्य शब्द का उपयोग किया जाता है चूंकि निम्नलिखित प्राकृतिक संख्याओं के एक गैर-खाली सबसेट {{math|<var>B</var>}} के समरूप हैं: | प्राकृतिक संख्याओं के एक सेट को संगणनीय गणना योग्य कहा जाता है (समानार्थक: पुनरावर्ती रूप से गणना करने योग्य, अर्ध-निर्णायक) यदि कोई संगणनीय फलन {{math|''f''}} है जैसे कि प्रत्येक संख्या {{math|<var>n</var>}} के लिए, {{math|''f''(<var>n</var>)}} को परिभाषित किया जाता है [[यदि और एकमात्र]] {{math|<var>n</var>}} सेट में है। इस प्रकार एक सेट संगणनीय रूप से यदि और , एकमात्र यह कुछ संगणनीय फसन का डोमेन है। गणना योग्य शब्द का उपयोग किया जाता है चूंकि निम्नलिखित प्राकृतिक संख्याओं के एक गैर-खाली सबसेट {{math|<var>B</var>}} के समरूप हैं: | ||
* {{math|<var>B</var>}} एक संगणनीय | * {{math|<var>B</var>}} एक संगणनीय कार्य का क्षेत्र है। | ||
* {{math|<var>B</var>}} योग संगणनीय | * {{math|<var>B</var>}} योग संगणनीय कार्य की श्रेणी है। यदि {{math|<var>B</var>}} अनंत है तो फलन को [[Index.php?title=इंजेक्शन|इंजेक्शन]] माना जा सकता है। | ||
यदि एक सेट {{math|<var>B</var>}} कार्य {{math|''f''}} की सीमा है तब | यदि एक सेट {{math|<var>B</var>}} कार्य {{math|''f''}} की सीमा है तब फंक्शन को {{math|<var>B</var>}} की गणना के रूप में देखा जा सकता है | ||
चूंकि सूची {{math|''f''(0), ''f''(1), ...}}में {{math|<var>B</var>}} के प्रत्येक तत्व सम्मलित होंगे। | चूंकि सूची {{math|''f''(0), ''f''(1), ...}}में {{math|<var>B</var>}} के प्रत्येक तत्व सम्मलित होंगे। | ||
| Line 71: | Line 71: | ||
एक औपचारिक भाषा की एक प्रमुख संपत्ति यह तय करने के लिए एक आवश्यक स्तर है कि कोई दिया गया शब्द भाषा में है या नहीं। इनपुट के रूप में भाषा में एक मनमाना शब्द लेने के लिए एक गणना योग्य कार्य की अनुमति देने के लिए कुछ कोडिंग सिस्टम विकसित किया जाना चाहिए; इसे सामान्यतः नियमित माना जाता है। एक भाषा को संगणनीय कहा जाता है (समानार्थक: पुनरावर्ती, निर्णायक) यदि कोई संगणनीय फलन है जैसे कि वर्णमाला के प्रत्येक शब्द {{math|''f''(<var>w</var>) {{=}} 1}} यदि शब्द भाषा में है और {{math|''f''(<var>w</var>) {{=}} 0}} यदि शब्द भाषा में नहीं है। इस प्रकार एक भाषा की गणना एकमात्र तभी की जा सकती है जब कोई ऐसी प्रक्रिया हो जो सही ढंग से यह बता सके कि भाषा में अनैतिक शब्द हैं या नहीं। | एक औपचारिक भाषा की एक प्रमुख संपत्ति यह तय करने के लिए एक आवश्यक स्तर है कि कोई दिया गया शब्द भाषा में है या नहीं। इनपुट के रूप में भाषा में एक मनमाना शब्द लेने के लिए एक गणना योग्य कार्य की अनुमति देने के लिए कुछ कोडिंग सिस्टम विकसित किया जाना चाहिए; इसे सामान्यतः नियमित माना जाता है। एक भाषा को संगणनीय कहा जाता है (समानार्थक: पुनरावर्ती, निर्णायक) यदि कोई संगणनीय फलन है जैसे कि वर्णमाला के प्रत्येक शब्द {{math|''f''(<var>w</var>) {{=}} 1}} यदि शब्द भाषा में है और {{math|''f''(<var>w</var>) {{=}} 0}} यदि शब्द भाषा में नहीं है। इस प्रकार एक भाषा की गणना एकमात्र तभी की जा सकती है जब कोई ऐसी प्रक्रिया हो जो सही ढंग से यह बता सके कि भाषा में अनैतिक शब्द हैं या नहीं। | ||
एक भाषा संगणनीय रूप से गणना योग्य है (समानार्थक: पुनरावर्ती रूप से गणना करने योग्य, अर्धविराम योग्य) यदि कोई संगणनीय | एक भाषा संगणनीय रूप से गणना योग्य है (समानार्थक: पुनरावर्ती रूप से गणना करने योग्य, अर्धविराम योग्य) यदि कोई संगणनीय कार्य है जैसे कि {{math|''f''(<var>w</var>)}} परिभाषित किया गया है यदि और एकमात्र शब्द {{math|<var>w</var>}} भाषा में है। गणना योग्य शब्द की व्युत्पत्ति वैसी ही है जैसी प्राकृतिक संख्याओं के संगणनीय रूप से गणना योग्य सेटों में होती है। | ||
== उदाहरण == | == उदाहरण == | ||
| Line 77: | Line 77: | ||
निम्नलिखित कार्य गणना योग्य हैं: | निम्नलिखित कार्य गणना योग्य हैं: | ||
* एक परिमित डोमेन के साथ प्रत्येक | * एक परिमित डोमेन के साथ प्रत्येक फंक्शन; उदाहरण के लिए, प्राकृतिक संख्याओं का कोई परिमित क्रम नही है। | ||
* प्रत्येक स्थिर | * प्रत्येक स्थिर फंक्शन f: 'n'<sup>K </do> → 'n', f (n (n<sub>1</sub>,...एन<sub>''k''</sub>): = एन। | ||
* योग एफ: 'एन'<sup>2 </sup> → n, '' f '' ('' n ''<sub>1</sub>,एन<sub>''2''</sub>): = n<sub>1</sub> + एन<sub>2</sub> | * योग एफ: 'एन'<sup>2 </sup> → n, '' f '' ('' n ''<sub>1</sub>,एन<sub>''2''</sub>): = n<sub>1</sub> + एन<sub>2</sub> | ||
* दो संख्याओं का सबसे बड़ा सामान्य विभाजक | * दो संख्याओं का सबसे बड़ा सामान्य विभाजक | ||
| Line 84: | Line 84: | ||
* एक संख्या का सबसे छोटा [[मुख्य कारक है]] | * एक संख्या का सबसे छोटा [[मुख्य कारक है]] | ||
यदि f और g गणना योग्य हैं, तो वे हैं: f + g, गुणन | f * g, | यदि f और g गणना योग्य हैं, तो वे हैं: f + g, गुणन | f * g, फंक्शन रचना |<math>\color{Blue} f \circ g</math>यदि | ||
f unary है, max (f, g), min (f, g), {{math|[[arg max]]{{mset|''y'' ≤ ''f''(''x'')}}}} और कई और संयुक्त है। | f unary है, max (f, g), min (f, g), {{math|[[arg max]]{{mset|''y'' ≤ ''f''(''x'')}}}} और कई और संयुक्त है। | ||
निम्नलिखित उदाहरण बताते हैं कि एक | निम्नलिखित उदाहरण बताते हैं कि एक फंक्शन संगणनीय हो सकता है, चूंकि यह ज्ञात नहीं है कि कौन सा एल्गोरिथम इसकी गणना करता है। | ||
* | * फंक्शन f (n) = 1 यदि दशमलव विस्तार में कम से कम n लगातार पाँचों का एक अनुक्रम है {{Pi}}, और f (n) = 0 अन्यथा, गणना योग्य है। (फंक्शन F या तो स्थिरांक 1 फंक्शन है, जो गणना योग्य है, f (n) = 1 यदि n <k और f (n) = 0 यदि n ≥ k। ऐसा प्रत्येक फंक्शन गणना योग्य है। यह ज्ञात नहीं है कि क्या π के दशमलव विस्तार में मनमाने ढंग से लंबे समय तक फाइव्स हैं, इसलिए हम नहीं जानते कि उन कार्यों में से कौन सी है। फिर भी, हम जानते हैं कि फंक्शन f को गणना योग्य होना चाहिए।) | ||
* प्राकृतिक संख्याओं के एक अगणनीय अनुक्रम का प्रत्येक परिमित खंड (जैसे व्यस्त बीवर | * प्राकृतिक संख्याओं के एक अगणनीय अनुक्रम का प्रत्येक परिमित खंड (जैसे व्यस्त बीवर फंक्शन Σ) संगणनीय है। उदाहरण के लिए, प्रत्येक प्राकृतिक संख्या n के लिए, एक एल्गोरिथम सम्मलित है जो परिमित अनुक्रम σ (0), σ (1), σ (2), ..., σ (n) - इस तथ्य के विपरीत है कि कोई कलन विधि जो पूरे σ- अनुक्रम की गणना करता है, अर्थात् सभी n के लिए σ (n)।इस प्रकार, प्रिंट 0, 1, 4, 6, 13 एक तुच्छ एल्गोरिथ्म है, जो σ (0), σ (1), σ (2), σ (3), σ (4) की गणना करने के लिए एक तुच्छ एल्गोरिथ्म सम्मलित है (भले ही यह कभी भी ज्ञात या किसी के द्वारा निर्मित नहीं हो सकता है) σ (0), σ (1), σ (2), ..., σ n। | ||
== चर्च -ट्र्यूरिंग थीसिस == | == चर्च -ट्र्यूरिंग थीसिस == | ||
| Line 98: | Line 98: | ||
चर्च -ट्रिंग थीसिस में कहा गया है सूचीबद्ध तीन गुणों वाली प्रक्रिया से संगणनीय कोई भी कार्य एक गणना योग्य कार्य है। चूंकि इन तीन गुणों को औपचारिक रूप से नहीं बताया गया है, चर्च -ट्यूरिंग थीसिस को सिद्ध नहीं किया जा सकता है। निम्नलिखित तथ्यों को अधिकांशतः थीसिस के साक्ष्य के रूप में लिया जाता है: | चर्च -ट्रिंग थीसिस में कहा गया है सूचीबद्ध तीन गुणों वाली प्रक्रिया से संगणनीय कोई भी कार्य एक गणना योग्य कार्य है। चूंकि इन तीन गुणों को औपचारिक रूप से नहीं बताया गया है, चर्च -ट्यूरिंग थीसिस को सिद्ध नहीं किया जा सकता है। निम्नलिखित तथ्यों को अधिकांशतः थीसिस के साक्ष्य के रूप में लिया जाता है: | ||
* अभिकलन के कई समकक्ष मॉडल ज्ञात हैं, और वे सभी संगणनीय फलन (या कुछ उदाहरणों में एक कमजोर संस्करण) की समान परिभाषा देते हैं। | * अभिकलन के कई समकक्ष मॉडल ज्ञात हैं, और वे सभी संगणनीय फलन (या कुछ उदाहरणों में एक कमजोर संस्करण) की समान परिभाषा देते हैं। | ||
* संगणना का कोई ठोस मॉडल प्रस्तावित नहीं किया गया है, जिसे | * संगणना का कोई ठोस मॉडल प्रस्तावित नहीं किया गया है, जिसे सामान्यतः [[प्रभावी रूप से गणना योग्य]] माना जाता है। | ||
चर्च -ट्राईिंग थीसिस को कभी-कभी सबूतों में प्रयोग किया जाता है इसलिये यह प्रमाणित किया जा सके कि गणना के लिए एक प्रक्रिया का ठोस विवरण देकर एक विशेष कार्य गणना योग्य है। चूंकि यह माना जाता है कि थीसिस के ऐसे सभी उपयोगों को गणना के कुछ मॉडल में | चर्च -ट्राईिंग थीसिस को कभी-कभी सबूतों में प्रयोग किया जाता है इसलिये यह प्रमाणित किया जा सके कि गणना के लिए एक प्रक्रिया का ठोस विवरण देकर एक विशेष कार्य गणना योग्य है। चूंकि यह माना जाता है कि थीसिस के ऐसे सभी उपयोगों को गणना के कुछ मॉडल में फंक्शन के लिए एक औपचारिक प्रक्रिया लिखने की कठिन प्रक्रिया द्वारा हटाया जा सकता है। | ||
== प्रोवेबिलिटी == | == प्रोवेबिलिटी == | ||
फंक्शन एकमात्र गणना होने पर प्रभावित हो सकता है, किन्तु यह एक विशेष प्रमाण प्रणाली में सिद्ध किया जा सकता है (सामान्यतः [[पीनो अंकगणित]] का प्रथम-क्रम ) कार्य जिसे संगणनीय सिद्ध किया जा सकता है, उसे 'प्रॉमिस टोटल' कहा जाता है। | |||
कुल कार्यों का सेट पुनरावर्ती रूप से गणना योग्य है: कोई भी उनके सभी संगत प्रमाणों की गणना करके सभी सिद्ध कुल कार्यों की गणना कर सकता है, जो उनकी संगणना को प्रमाणित करते हैं। यह साक्ष्य प्रणाली के सभी प्रमाणों की गणना करके और अप्रासंगिक लोगों को अप्रत्यक्ष करके किया जा सकता है। | कुल कार्यों का सेट पुनरावर्ती रूप से गणना योग्य है: कोई भी उनके सभी संगत प्रमाणों की गणना करके सभी सिद्ध कुल कार्यों की गणना कर सकता है, जो उनकी संगणना को प्रमाणित करते हैं। यह साक्ष्य प्रणाली के सभी प्रमाणों की गणना करके और अप्रासंगिक लोगों को अप्रत्यक्ष करके किया जा सकता है। | ||
| Line 110: | Line 110: | ||
=== पुनरावर्ती परिभाषित कार्यों के संबंध === | === पुनरावर्ती परिभाषित कार्यों के संबंध === | ||
एक [[पुनरावर्ती परिभाषा]] द्वारा परिभाषित एक फलन में, प्रत्येक मान को अन्य के एक निश्चित प्रथम-क्रम सूत्र द्वारा परिभाषित किया जाता है, पहले एक ही | एक [[पुनरावर्ती परिभाषा]] द्वारा परिभाषित एक फलन में, प्रत्येक मान को अन्य के एक निश्चित प्रथम-क्रम सूत्र द्वारा परिभाषित किया जाता है, पहले एक ही फंक्शन या अन्य कार्यों के परिभाषित मूल्यों, जो केवल स्थिरांक हो सकते हैं। इनमें से एक सबसेट आदिम पुनरावर्ती कार्य है। इस तरह के प्रत्येक कार्य योग्य है: इस तरह के एक [[arity]] के लिए | k-ary फंक्शन f, प्रत्येक मान <math>f(n_1, n_2... n_k)</math> परिभाषा का अनुसरण करके ओर, पुनरावृत्ति रूप से, और पुनरावृत्ति की परिमित संख्या के बाद (जैसा कि सरलता से सिद्ध किया जा सकता है), एक स्थिरांक की गणना कर के पहुंचा जा सकता है। | ||
आक्षेप सत्य नहीं है, चूंकि प्रत्येक प्रमाणित कार्य योग्य आदिम पुनरावर्ती नहीं है। वास्तव ,कोई भी सभी आदिम पुनरावर्ती कार्यों की गणना कर सकता है और एक | आक्षेप सत्य नहीं है, चूंकि प्रत्येक प्रमाणित कार्य योग्य आदिम पुनरावर्ती नहीं है। वास्तव ,कोई भी सभी आदिम पुनरावर्ती कार्यों की गणना कर सकता है और एक फंक्शन n को इस तरह परिभाषित कर सकता है जैसे कि सभी n, m: en (n, m) = f के लिए<sub>''n''</sub>(एम), जहां एफ<sub>''n''</sub> एन-वें आदिम पुनरावर्ती फंक्शन है (arity के लिए | k-are फंक्शन, f पर सेट किया जाएगा<sub>''n''</sub>(एम, एम ... एम))।अब, g (n) = en (n, n) +1 एक [[Index.php?title=विकर्णीकरण|विकर्णीकरण]] तर्क द्वारा सिद्ध है, परंतु आदिम पुनरावर्ती नहीं है: j, g = f <sub>''j''</sub>, , g (j) = en (j, j) +1 = f ,<sub>''j''</sub> (j)+1 = g (j) +1, एक विरोधाभास। (सभी आदिम पुनरावर्ती कार्यों की गोडेल संख्या को एक आदिम पुनरावर्ती कार्य द्वारा गणना की जा सकती है, चूंकि आदिम पुनरावर्ती कार्यों के मान नहीं हो सकते हैं।) | ||
एक ऐसा कार्य, जो सिद्ध करने योग्य है, परंतु आदिम पुनरावर्ती नहीं है, [[Index.php?title=एकरमन फलन|एकरमन फलन]] है: चूंकि यह पुनरावर्ती रूप से परिभाषित किया गया है, इसकी संगणना को सिद्ध करना वास्तव में सरल है (चूंकि, पुनरावर्ती परिभाषा द्वारा परिभाषित सभी कार्यों के लिए एक समान विकर्ण तर्क भी बनाया जा सकता है ; इस प्रकार, सिद्ध करने योग्य कार्य हैं जिन्हें पुनरावर्ती रूप से परिभाषित नहीं किया जा सकता है {{citation needed|date=June 2016}})। | एक ऐसा कार्य, जो सिद्ध करने योग्य है, परंतु आदिम पुनरावर्ती नहीं है, [[Index.php?title=एकरमन फलन|एकरमन फलन]] है: चूंकि यह पुनरावर्ती रूप से परिभाषित किया गया है, इसकी संगणना को सिद्ध करना वास्तव में सरल है (चूंकि, पुनरावर्ती परिभाषा द्वारा परिभाषित सभी कार्यों के लिए एक समान विकर्ण तर्क भी बनाया जा सकता है ; इस प्रकार, सिद्ध करने योग्य कार्य हैं जिन्हें पुनरावर्ती रूप से परिभाषित नहीं किया जा सकता है {{citation needed|date=June 2016}})। | ||
| Line 120: | Line 120: | ||
एक [[Index.php?title=ध्वनि|ध्वनि]] प्रमाण प्रणाली में, प्रत्येक सिद्ध योग कार्य वास्तव में योग है, परंतु इसका विलोम सत्य नहीं है: प्रत्येक प्रथम-क्रम प्रमाण प्रणाली में जो पर्याप्त सुदृढ़ और ध्वनि (पीनो अंकगणित सहित) है, कोई भी (दूसरे प्रमाण प्रणाली में) सिद्ध कर सकता है योग कार्यों का अस्तित्व जो प्रमाण प्रणाली में योग सिद्ध नहीं किया जा सकता है। | एक [[Index.php?title=ध्वनि|ध्वनि]] प्रमाण प्रणाली में, प्रत्येक सिद्ध योग कार्य वास्तव में योग है, परंतु इसका विलोम सत्य नहीं है: प्रत्येक प्रथम-क्रम प्रमाण प्रणाली में जो पर्याप्त सुदृढ़ और ध्वनि (पीनो अंकगणित सहित) है, कोई भी (दूसरे प्रमाण प्रणाली में) सिद्ध कर सकता है योग कार्यों का अस्तित्व जो प्रमाण प्रणाली में योग सिद्ध नहीं किया जा सकता है। | ||
यदि ट्यूरिंग मशीनों के माध्यम से कुल संगणनीय कार्यों की गणना की जाती है, तो उपरोक्त कथन दिखाया जा सकता है,यदि प्रमाण प्रणाली ध्वनि है, तो एक समान विकर्ण तर्क द्वारा, पहले दिए गए कुल | |||