संगणनीय फलन: Difference between revisions

Latest revision as of 11:16, 23 February 2023

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

संगणनीय कार्य की सटीक परिभाषा से पहले, मैथेमेटिशन अधिकांशतः अनौपचारिक शब्द का प्रभावी ढंग से गणना योग्य उपयोग करते थे। तब से यह शब्द संगणनीय कार्य के साथ पहचाना जाने लगा है। इन कार्यों की प्रभावी संगणनीयता का अर्थ यह नहीं है कि उनकी कुशलता से गणना की जा सकती है। वास्तव में, कुछ प्रभावी रूप से गणना योग्य कार्यों के लिए यह दिखाया जा सकता है कि उनकी गणना करने वाला कोई भी एल्गोरिथम का समय इनपुट की लंबाई के साथ घातीय वृद्धि से(या सुपरएक्सपोनेंशियली) को बढ़ाता है। व्यवहार्य संगणनीयता और संगणनात्मक जटिलता के साथ उन क्षेत्र के कार्यों का अध्ययन करते हैं।

चर्च -ट्यूरिंग थीसिस के अनुसार, संगणनीय फलन वास्तव में ऐसे कार्य हैं जिनकी गणना एक यांत्रिक गणना उपकरण का उपयोग करके असीमित मात्रा में समय और भंडारण स्थान के साथ की जा सकती है, समतुल्य रूप से, यह थीसिस बताती है कि एक फलन संगणनीय है और एकमात्र इसमें एल्गोरिथम हो। इस अर्थ में एक एल्गोरिथम को असीमित स्थिति के रूप में समझा जाता है।

ब्लम स्वयंसिद्धों का उपयोग संगणनीय कार्य के सेट पर एक अमूर्त संगणनात्मक जटिलता सिद्धांत को परिभाषित करने के लिए किया जा सकता है। संगणनात्मक जटिलता सिद्धांत में, एक संगणनीय फलन की जटिलता को निर्धारण करने की समस्या को एक कार्य प्रायौगिक के रूप में जाना जाता है।

परिभाषा

किसी कार्य की संगणनीयता एक अनौपचारिक धारणा है। इसका वर्णन करने का एक नियम यह है कि एक कार्य गणना योग्य है यदि इसका मूल्य एक प्रभावी विधि द्वारा प्राप्त किया जा सकता है। अधिक कठोरता के साथ, एक कार्य $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ संगणनीय है यदि एकमात्र कोई प्रभावी प्रक्रिया है, तो अभिकलनात्‍मक है $k$ -टपल $\mathbf {x}$ प्राकृतिक संख्याओं का, मूल्य का उत्पादन करेगा $f(\mathbf {x} )$ .^[1] संगणनीय कार्य तर्कों के रूप में कई प्राकृतिक संख्याएँ लेते हैं और एक मूल्य का उत्पादन करते हैं जो एक एकल प्राकृतिक संख्या है।

इस अनौपचारिक विवरण के समकक्षों के रूप में, कई औपचारिक, गणितीय परिभाषाएँ सम्मलित हैं। संगणनीय कार्य के वर्ग को संगणना के कई समकक्ष मॉडल में परिभाषित किया जा सकता है

ट्यूरिंग मशीनें
μ- पुनरावर्ती कार्य
लम्बा कैलकुलस
पोस्ट मशीनें (पोस्ट -ट्र्यूरिंग मशीन और टैग मशीन)।
रजिस्टर मशीनें

यद्यपि ये मॉडल कार्यों, उनके इनपुट, और उनके आउटपुट के लिए अलग -अलग प्रतिनिधित्व का उपयोग करते हैं, अनुवाद किसी भी दो मॉडलों के बीच सम्मलित हैं, और इसलिए प्रत्येक मॉडल अनिवार्य रूप से कार्यों के समान वर्ग का वर्णन करता है, इसका अभिप्राय यह है कि औपचारिक संगणनीयता स्वाभाविक है संकीर्ण।^[2] इन कार्यों को कभी -कभी पुनरावर्ती के रूप में संदर्भित किया जाता है अनौपचारिक शब्द "गणना योग्य" के विपरीत,^[3] क्लेन और गोडेल के बीच 1934 की चर्चा से उत्पन्न एक अंतर है।^[4]^p.6

कोई गणना योग्य कार्यों को μ- पुनरावर्ती कार्यों के रूप में औपचारिक रूप दे सकता है, जो आंशिक कार्य हैं जो प्राकृतिक संख्याओं के परिमित ट्यूपल्स लेते हैं और एक भी प्राकृतिक संख्या लौटा देते हैं। वे आंशिक कार्यों का सबसे छोटा वर्ग हैं जिनमें निरंतर, उत्तराधिकारी और प्रक्षेपण कार्य सम्मलित हैं, और रचना, आदिम पुनरावर्ती फंक्शन और μ संचालक के तहत पूर्ण है।

समान रूप से, संगणनीय कार्य को उन कार्यों में औपचारिक रूप दिया जा सकता है, जिसकी गणना एक आदर्श कंप्यूटिंग एजेंट जैसे कि ट्यूरिंग मशीन या रजिस्टर मशीन द्वारा की जा सकती है। औपचारिक रूप से, एक आंशिक फंक्शन $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ क्या गणना की जा सकती है यदि एकमात्र वहाँ निम्न गुणों के साथ एक कंप्यूटर प्रोग्राम सम्मलित है:

यदि $f(\mathbf {x} )$ परिभाषित किया गया है, तो कार्यक्रम इनपुट पर समाप्त हो जाएगा $\mathbf {x}$ मूल्य के साथ $f(\mathbf {x} )$ कंप्यूटर मेमोरी में संग्रहीत होता है।
यदि $f(\mathbf {x} )$ अपरिभाषित है, तो कार्यक्रम इनपुट पर कभी समाप्त नहीं होता है $\mathbf {x}$ ।

संगणनीय फलन की विशेषताएं

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

हर्बर्ट एंडर्टन [1977] एक संगणनीय फलन की गणना के लिए एक प्रक्रिया की निम्नलिखित विशेषताएं होती है; ट्यूरिंग [1936], रोजर्स [1967], और अन्य लोगों द्वारा इसी तरह के वर्णन दिए गए हैं।

प्रक्रिया के लिए सटीक निर्देश, समय में परिमित होना चाहिए। इस प्रकार प्रत्येक संगणनीय कार्य में एक परिमित कार्यक्रम होना चाहिए जो पूरी तरह से वर्णन करता है कि कार्य की गणना कैसे की जाती है। एकमात्र निर्देशों का पालन करके कार्य की गणना करना संभव है;कोई अनुमान या विशेष अंतर्दृष्टि की आवश्यकता नहीं है।
यदि प्रक्रिया को F के डोमेन में k-tuple 'x' दिया जाता है, तो असतत चरणों की एक परिमित संख्या के बाद प्रक्रिया को समाप्त होना चाहिए और F ('x') को उत्पादन करना चाहिए। सहज रूप से, प्रक्रिया गणना के प्रत्येक चरण में क्या करना है, इसे कवर करने के लिए एक विशिष्ट नियम के साथ सहजता से, प्रक्रिया चरण दर चरण आगे बढ़ती है। फंक्शन का मूल्य लौटाए जाने से पहले एकमात्र सूक्ष्म रूप से कई चरणों को पूरा किया जा सकता है।
यदि प्रक्रिया को k-tuple 'X' दिया जाता है, जो F की डोमेन में नहीं है, तो प्रक्रिया हमेशा के लिए चल सकती है, कभी भी रुक नहीं सकती। या किसी बिंदु पर अटक नहीं सकती है ('अर्थात, इसके निर्देशों में से किसी एक को भी निष्पादित नहीं किया जा सकता है), परंतु इसे 'x' पर f के लिए एक मूल्य का उत्पादन करने का दिखावा नहीं करना चाहिए। इस प्रकार यदि f ('x') के लिए कोई मूल्य कभी पाया जाता है, तो यह सही मूल्य होना चाहिए। कंप्यूटिंग एजेंट के लिए यह आवश्यक नहीं है कि वह सही परिणामों को गलत परिणामों से सही परिणामों से करे चूंकि प्रक्रिया को सही के रूप में परिभाषित किया गया है।

एंडर्टन एक संगणनीय कार्य के लिए प्रक्रिया की इन 3 आवश्यकताओं के कई स्पष्टीकरणों को सूचीबद्ध करता है:

प्रक्रिया को सैद्धांतिक रूप से मनमाने ढंग से बड़े तर्कों के लिए काम करना चाहिए। यह नहीं माना जाता है कि तर्क पृथ्वी में परमाणुओं की संख्या से कम हैं,
आउटपुट उत्पन्न करने के लिए प्रक्रिया को कई चरणों मे समाप्त होना आवश्यक है, परंतु रुकने से पहले यह मनमाने ढंग से कई कदम उठा सकता है। इसमे कोई समय सीमा नहीं मानी जाती है।
यद्यपि प्रक्रिया एक सफल गणना के समय एक सीमित मात्रा में संग्रह स्थान का उपयोग कर सकती है, परंतु उपयोग किए जाने वाले स्थान की मात्रा पर कोई बाध्यता नहीं है। यह माना जाता है कि जब भी कार्यविधि को आवश्यकता होती है, तो अतिरिक्त संग्रह स्थान कार्यविधि को दिया जा सकता है।

संक्षेप में, इस दृश्य के आधार पर एक कार्य की गणना की जा सकती है:

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

अभिकलनात्मक जटिलता अध्ययन का क्षेत्र एक सफल संगणना में अनुमत समय और/या स्थान पर निर्धारित सीमा के साथ कार्य करता है।

संगणनीय सेट और संबंध

प्राकृतिक संख्याओं के एक सेट को संगणनीय कहा जाता है (समानार्थी: पुनरावर्ती,निर्णायक) यदि कोई संगणनीय, योग कार्य है जैसे कि किसी भी प्राकृतिक संख्या $n$ के लिए, $f (n) = 1$ $n$ , $A$ में है और $f (n) = 0$ $n$ , $A$ में नहीं है।

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

$B$ एक संगणनीय कार्य का क्षेत्र है।
$B$ योग संगणनीय कार्य की श्रेणी है। यदि $B$ अनंत है तो फलन को इंजेक्शन माना जा सकता है।

यदि एक सेट $B$ कार्य $f$ की सीमा है तब फंक्शन को $B$ की गणना के रूप में देखा जा सकता है चूंकि सूची $f (0), f (1), ...$ में $B$ के प्रत्येक तत्व सम्मलित होंगे।

चूंकि प्राकृतिक संख्याओं पर प्रत्येक परिमित संबंध को प्राकृतिक संख्याओं के परिमित अनुक्रमों के संगत समुच्चय के साथ पहचाना जा सकता है, संगणनीय संबंध और संगणनीय रूप से गणना योग्य संबंध की धारणाओं को सेट के लिए उनके अनुरूपों से परिभाषित किया जा सकता है।

औपचारिक भाषाएँ

कंप्यूटर विज्ञान में अभिकलन सिद्धांत में, औपचारिक भाषाओं पर विचार करना साधारण है। एक 'वर्णमाला' एक मनमाना सेट है। एक वर्णमाला पर एक 'शब्द' वर्णमाला से प्रतीकों का एक परिमित अनुक्रम है; एक ही चिन्ह का एक से अधिक बार प्रयोग किया जा सकता है। उदाहरण के लिए, बाइनरी स्ट्रिंग्स वर्णमाला ${0, 1}$ पर सटीक शब्द हैं। एक भाषा एक निश्चित वर्णमाला पर सभी शब्दों के संग्रह का एक उपसमुच्चय है। उदाहरण के लिए, सभी बाइनरी श्रृंखला का संग्रह होते हैं, बाइनरी वर्णमाला एक भाषा है।

एक औपचारिक भाषा की एक प्रमुख संपत्ति यह तय करने के लिए एक आवश्यक स्तर है कि कोई दिया गया शब्द भाषा में है या नहीं। इनपुट के रूप में भाषा में एक मनमाना शब्द लेने के लिए एक गणना योग्य कार्य की अनुमति देने के लिए कुछ कोडिंग सिस्टम विकसित किया जाना चाहिए; इसे सामान्यतः नियमित माना जाता है। एक भाषा को संगणनीय कहा जाता है (समानार्थक: पुनरावर्ती, निर्णायक) यदि कोई संगणनीय फलन है जैसे कि वर्णमाला के प्रत्येक शब्द $f (w) = 1$ यदि शब्द भाषा में है और $f (w) = 0$ यदि शब्द भाषा में नहीं है। इस प्रकार एक भाषा की गणना एकमात्र तभी की जा सकती है जब कोई ऐसी प्रक्रिया हो जो सही ढंग से यह बता सके कि भाषा में अनैतिक शब्द हैं या नहीं।

एक भाषा संगणनीय रूप से गणना योग्य है (समानार्थक: पुनरावर्ती रूप से गणना करने योग्य, अर्धविराम योग्य) यदि कोई संगणनीय कार्य है जैसे कि $f (w)$ परिभाषित किया गया है यदि और एकमात्र शब्द $w$ भाषा में है। गणना योग्य शब्द की व्युत्पत्ति वैसी ही है जैसी प्राकृतिक संख्याओं के संगणनीय रूप से गणना योग्य सेटों में होती है।

उदाहरण

निम्नलिखित कार्य गणना योग्य हैं:

एक परिमित डोमेन के साथ प्रत्येक फंक्शन; उदाहरण के लिए, प्राकृतिक संख्याओं का कोई परिमित क्रम नही है।
प्रत्येक स्थिर फंक्शन f: 'n'^{K </do> → 'n', f (n (n₁,...एन_k): = एन।}
योग एफ: 'एन'² → n, f ( n ₁,एन₂): = n₁ + एन₂
दो संख्याओं का सबसे बड़ा सामान्य विभाजक
दो संख्याओं का बेज़ाउट गुणांक
एक संख्या का सबसे छोटा मुख्य कारक है

यदि f और g गणना योग्य हैं, तो वे हैं: f + g, गुणन | f * g, फंक्शन रचना | $\color {Blue}f\circ g$ यदि f unary है, max (f, g), min (f, g), $arg max {y \leq f (x)}$ और कई और संयुक्त है।

निम्नलिखित उदाहरण बताते हैं कि एक फंक्शन संगणनीय हो सकता है, चूंकि यह ज्ञात नहीं है कि कौन सा एल्गोरिथम इसकी गणना करता है।

फंक्शन f (n) = 1 यदि दशमलव विस्तार में कम से कम n लगातार पाँचों का एक अनुक्रम है $π$ , और 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।

चर्च -ट्र्यूरिंग थीसिस

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

अभिकलन के कई समकक्ष मॉडल ज्ञात हैं, और वे सभी संगणनीय फलन (या कुछ उदाहरणों में एक कमजोर संस्करण) की समान परिभाषा देते हैं।
संगणना का कोई ठोस मॉडल प्रस्तावित नहीं किया गया है, जिसे सामान्यतः प्रभावी रूप से गणना योग्य माना जाता है।

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

प्रोवेबिलिटी

फंक्शन एकमात्र गणना होने पर प्रभावित हो सकता है, किन्तु यह एक विशेष प्रमाण प्रणाली में सिद्ध किया जा सकता है (सामान्यतः पीनो अंकगणित का प्रथम-क्रम ) कार्य जिसे संगणनीय सिद्ध किया जा सकता है, उसे 'प्रॉमिस टोटल' कहा जाता है।

कुल कार्यों का सेट पुनरावर्ती रूप से गणना योग्य है: कोई भी उनके सभी संगत प्रमाणों की गणना करके सभी सिद्ध कुल कार्यों की गणना कर सकता है, जो उनकी संगणना को प्रमाणित करते हैं। यह साक्ष्य प्रणाली के सभी प्रमाणों की गणना करके और अप्रासंगिक लोगों को अप्रत्यक्ष करके किया जा सकता है।

पुनरावर्ती परिभाषित कार्यों के संबंध

एक पुनरावर्ती परिभाषा द्वारा परिभाषित एक फलन में, प्रत्येक मान को अन्य के एक निश्चित प्रथम-क्रम सूत्र द्वारा परिभाषित किया जाता है, पहले एक ही फंक्शन या अन्य कार्यों के परिभाषित मूल्यों, जो केवल स्थिरांक हो सकते हैं। इनमें से एक सबसेट आदिम पुनरावर्ती कार्य है। इस तरह के प्रत्येक कार्य योग्य है: इस तरह के एक arity के लिए | k-ary फंक्शन f, प्रत्येक मान $f(n_{1},n_{2}...n_{k})$ परिभाषा का अनुसरण करके ओर, पुनरावृत्ति रूप से, और पुनरावृत्ति की परिमित संख्या के बाद (जैसा कि सरलता से सिद्ध किया जा सकता है), एक स्थिरांक की गणना कर के पहुंचा जा सकता है।

आक्षेप सत्य नहीं है, चूंकि प्रत्येक प्रमाणित कार्य योग्य आदिम पुनरावर्ती नहीं है। वास्तव ,कोई भी सभी आदिम पुनरावर्ती कार्यों की गणना कर सकता है और एक फंक्शन n को इस तरह परिभाषित कर सकता है जैसे कि सभी n, m: en (n, m) = f के लिए_n(एम), जहां एफ_n एन-वें आदिम पुनरावर्ती फंक्शन है (arity के लिए | k-are फंक्शन, f पर सेट किया जाएगा_n(एम, एम ... एम))।अब, g (n) = en (n, n) +1 एक विकर्णीकरण तर्क द्वारा सिद्ध है, परंतु आदिम पुनरावर्ती नहीं है: j, g = f _j, , g (j) = en (j, j) +1 = f ,_j (j)+1 = g (j) +1, एक विरोधाभास। (सभी आदिम पुनरावर्ती कार्यों की गोडेल संख्या को एक आदिम पुनरावर्ती कार्य द्वारा गणना की जा सकती है, चूंकि आदिम पुनरावर्ती कार्यों के मान नहीं हो सकते हैं।)

एक ऐसा कार्य, जो सिद्ध करने योग्य है, परंतु आदिम पुनरावर्ती नहीं है, एकरमन फलन है: चूंकि यह पुनरावर्ती रूप से परिभाषित किया गया है, इसकी संगणना को सिद्ध करना वास्तव में सरल है (चूंकि, पुनरावर्ती परिभाषा द्वारा परिभाषित सभी कार्यों के लिए एक समान विकर्ण तर्क भी बनाया जा सकता है ; इस प्रकार, सिद्ध करने योग्य कार्य हैं जिन्हें पुनरावर्ती रूप से परिभाषित नहीं किया जा सकता है^{[citation needed]})।

योग कार्य जो सिद्ध रूप से योग नहीं हैं

एक ध्वनि प्रमाण प्रणाली में, प्रत्येक सिद्ध योग कार्य वास्तव में योग है, परंतु इसका विलोम सत्य नहीं है: प्रत्येक प्रथम-क्रम प्रमाण प्रणाली में जो पर्याप्त सुदृढ़ और ध्वनि (पीनो अंकगणित सहित) है, कोई भी (दूसरे प्रमाण प्रणाली में) सिद्ध कर सकता है योग कार्यों का अस्तित्व जो प्रमाण प्रणाली में योग सिद्ध नहीं किया जा सकता है।

यदि ट्यूरिंग मशीनों के माध्यम से कुल संगणनीय कार्यों की गणना की जाती है, तो उपरोक्त कथन दिखाया जा सकता है,यदि प्रमाण प्रणाली ध्वनि है, तो एक समान विकर्ण तर्क द्वारा, पहले दिए गए कुल कार्यों की गणना का उपयोग करके। एक ट्यूरिंग मशीन का उपयोग करता है जो प्रासंगिक प्रमाणों की गणना करता है, और प्रत्येक इनपुट n कॉल f के लिए_n(एन) (जहां एफ_n इस गणना द्वारा n-th फंक्शन है) ट्यूरिंग मशीन का आह्वान करके जो इसे N-TH प्रमाण के अनुसार गणना करता है। ऐसी ट्यूरिंग मशीन के रुकने की गारंटी है यदि प्रमाण सिस्टम ध्वनि है।

अप्रभावी कार्य और अनहोनी समस्याएं

प्रत्येक संगणनीय कार्य की एक परिमित प्रक्रिया होती है जो इसकी गणना करने के नियम पर स्पष्ट, निर्देश देती है। इसके अतिरिक्त, इस प्रक्रिया को अभिकलनात्मक जटिलता द्वारा उपयोग किए जाने वाले परिमित वर्णमाला में एन्कोड किया जाता है, इसलिए एकमात्र गणना करने योग्य कई कार्य हैं। उदाहरण के लिए, कार्यों को बिट्स की एक स्ट्रिंग (वर्णमाला) का उपयोग करके एन्कोड किया जा सकता है $Σ = {0, 1$ })।

वास्तविक संख्या असंख्य हैं इसलिए अधिकांश वास्तविक संख्याएँ गणना योग्य नहीं हैं। प्राकृतिक संख्याओं पर परिमित कार्यों का समुच्चय असंख्य है इसलिए अधिकांश संगणनीय नहीं हैं। इस तरह के कार्यों के ठोस उदाहरण व्यस्त बीवर, कोलमोगोरोव जटिलता, या कोई भी कार्य है जैसे कि चैतिन का स्थिरांक, जो एक गैर-गणना योग्य संख्या के अंकों को उत्पादन करता है।

इसी तरह, प्राकृत संख्याओं के अधिकांश उपसमुच्चय संगणनीय नहीं हैं। हॉल्टिंग की समस्या निर्मित होने वाला पहला ऐसा सेट था। डेविड हिल्बर्ट द्वारा प्रस्तावित एंट्सचेइडुंगस्प्रोबल ने पूछा कि क्या यह निर्धारित करने के लिए एक प्रभावी प्रक्रिया है कौन से गणितीय कथन (प्राकृतिक संख्या के रूप में कोडित) सत्य हैं। ट्यूरिंग और चर्च ने 1930 के दशक में स्वतंत्र रूप से दिखाया कि प्राकृतिक संख्याओं का यह सेट गणना योग्य नहीं है। चर्च-ट्यूरिंग थीसिस के अनुसार, ऐसी कोई प्रभावी प्रक्रिया नहीं है (एल्गोरिदम के साथ) जो इन संगणनाओं को निष्पादित कर सके।

संगणनीयता का विस्तार

सापेक्ष संगणनीयता

किसी फंक्शन की अभिकलन की धारणा को प्राकृतिक संख्याओं a के अनैतिक सेट से संबंधित किया जा सकता है। एक फंक्शन f को a में गणना योग्य माना जाता है (समकक्ष ए-गणना योग्य या a के सापेक्ष गणना योग्य) जब यह गणना योग्य फंक्शन की परिभाषा को संतुष्ट करता है, एक ओरेकल (अभिकलन) के रूप में ए तक पहुंच की अनुमति देने वाले संशोधन। संगणनीय कार्य की अवधारणा के साथ-साथ संगणना के कई अलग-अलग मॉडलों में सापेक्ष संगणनीयता को समकक्ष परिभाषाएं दी जा सकती हैं। यह सामान्यतः एक अतिरिक्त आदिम ऑपरेशन के साथ गणना के मॉडल को पूरक करके पूरा किया जाता है जो पूछता है कि क्या दिया गया पूर्णांक ए का सदस्य है। हम इसके ग्राफ के साथ j की पहचान करके j में गणना योग्य होने के बारे में भी बात कर सकते हैं।

उच्च पुनरावर्ती सिद्धांत

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

अति संगणना

यद्यपि चर्च -ट्रिंग थीसिस में कहा गया है कि संगणनीय कार्यों में एल्गोरिदम के साथ सभी कार्य सम्मलित हैं, ऐसे कार्यों के व्यापक वर्गों पर विचार करना संभव है जो उन आवश्यकताओं को स्थिरता प्रदान करता हैं जो एल्गोरिदम के पास होनी चाहिए। हाइपरकंपुटेशन का क्षेत्र गणना के मॉडल का अध्ययन करता है जो सामान्य ट्यूरिंग संगणना से बाहर जाता है।

यह भी देखें

कम्प्यूटेबल नंबर
प्रभावी विधि
गणना का सिद्धांत
पुनरावर्ती सिद्धांत
ट्यूरिंग डिग्री
अंकगणितीय पदानुक्रम
हाइपरकंपुटेशन
सुपर-पुनरावर्ती एल्गोरिथ्म
अर्धविराम समारोह

संदर्भ

↑ Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second ed.). USA: Elsevier. p. 209. ISBN 0-12-238452-0.
↑ Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second ed.). USA: Elsevier. p. 208,262. ISBN 0-12-238452-0.
↑ C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Studies in Logic and the Foundation of Mathematics, 2000), p. 4
↑ R. Soare, Computability and Recursion (1995). Accessed 9 November 2022.

Cutland, Nigel. Computability. Cambridge University Press, 1980.
Enderton, H.B. Elements of recursion theory. Handbook of Mathematical Logic (North-Holland 1977) pp. 527–566.
Rogers, H. Theory of recursive functions and effective computation (McGraw–Hill 1967).
Turing, A. (1937), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, Volume 42 (1937), p.230–265. Reprinted in M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.

[1] Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second ed.). USA: Elsevier. p. 209. ISBN 0-12-238452-0.

[2] Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second ed.). USA: Elsevier. p. 208,262. ISBN 0-12-238452-0.

[3] C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Studies in Logic and the Foundation of Mathematics, 2000), p. 4

[4] R. Soare, Computability and Recursion (1995). Accessed 9 November 2022.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 {{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= मैथेमेटिशन|मैथेमेटिशन]] अधिकांशतः अनौपचारिक शब्द का प्रभावी ढंग से गणना योग्य उपयोग करते थे। तब से यह शब्द संगणनीय कार्य के साथ पहचाना जाने लगा है। इन कार्यों की प्रभावी संगणनीयता का अर्थ यह नहीं है कि उनकी कुशलता से गणना की जा सकती है। वास्तव में, कुछ प्रभावी रूप से गणना योग्य कार्यों के लिए यह दिखाया जा सकता है कि उनकी गणना करने वाला कोई भी एल्गोरिथम का समय इनपुट की लंबाई के साथ [[घातीय वृद्धि]] से(या [[Index.php?title=सुपरएक्सपोनेंशियली|सुपरएक्सपोनेंशियली]]) को बढ़ाता है। व्यवहार्य संगणनीयता और संगणनात्मक जटिलता के साथ उन क्षेत्र के कार्यों का अध्ययन करते हैं।
-चर्च -ट्यूरिंग थीसिस के अनुसार, कम्प्यूटेबल फ़ंक्शंस बिल्कुल ऐसे कार्य हैं जिनकी गणना एक यांत्रिक गणना डिवाइस का उपयोग करके की जा सकती है, जो समय और भंडारण स्थान की असीमित मात्रा में दी गई है।समान रूप से, इस थीसिस में कहा गया है कि एक फ़ंक्शन कम्प्यूटेशनल है यदि और केवल अगर इसमें एक एल्गोरिथ्म है।ध्यान दें कि इस अर्थ में एक एल्गोरिथ्म को असीमित समय वाले व्यक्ति के चरणों का एक अनुक्रम समझा जाता है और पेन और पेपर की एक असीमित आपूर्ति का पालन किया जा सकता है।
+चर्च -ट्यूरिंग थीसिस के अनुसार, संगणनीय फलन वास्तव में ऐसे कार्य हैं जिनकी गणना एक यांत्रिक गणना उपकरण का उपयोग करके असीमित मात्रा में समय और भंडारण स्थान के साथ की जा सकती है, समतुल्य रूप से, यह थीसिस बताती है कि एक फलन संगणनीय है और एकमात्र इसमें एल्गोरिथम हो। इस अर्थ में एक एल्गोरिथम को असीमित स्थिति के रूप में समझा जाता है।
-ब्लम स्वयंसिद्ध का उपयोग कम्प्यूटेबल फ़ंक्शंस के सेट पर एक अमूर्त [[कम्प्यूटेशनल जटिलता सिद्धांत]] को परिभाषित करने के लिए किया जा सकता है।कम्प्यूटेशनल जटिलता सिद्धांत में, एक कम्प्यूटेबल फ़ंक्शन की जटिलता का निर्धारण करने की समस्या को एक फ़ंक्शन समस्या के रूप में जाना जाता है।
+ब्लम स्वयंसिद्धों का उपयोग संगणनीय कार्य के सेट पर एक अमूर्त [[Index.php?title=संगणनात्मक जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]] को परिभाषित करने के लिए किया जा सकता है। संगणनात्मक जटिलता सिद्धांत में, एक संगणनीय फलन की जटिलता को निर्धारण करने की समस्या को एक कार्य प्रायौगिक के रूप में जाना जाता है।
 == परिभाषा ==
-{{see also|Total Turing machine}}
+{{see also|कुल ट्यूरिंग मशीन}}
-एक फ़ंक्शन की कम्प्यूटिबिलिटी एक अनौपचारिक धारणा है।इसका वर्णन करने का एक तरीका यह कहना है कि एक फ़ंक्शन कम्प्यूटेबल है यदि इसका मूल्य एक प्रभावी विधि द्वारा प्राप्त किया जा सकता है।अधिक कठोरता के साथ, एक फ़ंक्शन <math>f:\mathbb N^k\rightarrow\mathbb N</math>
-यदि और केवल एक प्रभावी प्रक्रिया है, तो कम्प्यूटेशनल है {{mvar|k}}-[[tuple]] <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> इस परिभाषा के साथ समझौते में, इस लेख के शेष यह मानता है कि कम्प्यूटेबल फ़ंक्शंस तर्कों के रूप में कई [[प्राकृतिक संख्या]]ओं को ध्यान में रखते हैं और एक मूल्य का उत्पादन करते हैं जो एक एकल प्राकृतिक संख्या है।
-इस अनौपचारिक विवरण के समकक्षों के रूप में, कई औपचारिक, गणितीय परिभाषाएँ मौजूद हैं।कम्प्यूटेबल फ़ंक्शंस के वर्ग को गणना के कई समकक्ष मॉडल में परिभाषित किया जा सकता है
+किसी कार्य की संगणनीयता एक अनौपचारिक धारणा है। इसका वर्णन करने का एक नियम यह है कि एक कार्य गणना योग्य है यदि इसका मूल्य एक प्रभावी विधि द्वारा प्राप्त किया जा सकता है। अधिक कठोरता के साथ, एक कार्य <math>f:\mathbb N^k\rightarrow\mathbb N</math>
+संगणनीय है यदि एकमात्र कोई प्रभावी प्रक्रिया है, तो अभिकलनात्‍मक है {{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=प्राकृतिक संख्याएँ|प्राकृतिक संख्याएँ]] लेते हैं और एक मूल्य का उत्पादन करते हैं जो एक एकल प्राकृतिक संख्या है।
+इस अनौपचारिक विवरण के समकक्षों के रूप में, कई औपचारिक, गणितीय परिभाषाएँ सम्मलित हैं। संगणनीय कार्य के वर्ग को संगणना के कई समकक्ष मॉडल में परिभाषित किया जा सकता है
 * ट्यूरिंग मशीनें
 * μ- पुनरावर्ती कार्य
 * [[लम्बा कैलकुलस]]
-* पोस्ट मशीनें (पोस्ट -ट्र्यूरिंग मशीन और [[टैग सिस्टम]])।
+* पोस्ट मशीनें (पोस्ट -ट्र्यूरिंग मशीन और [[Index.php?title=टैग मशीन|टैग मशीन]])।
 * रजिस्टर मशीनें
-यद्यपि ये मॉडल कार्यों, उनके इनपुट, और उनके आउटपुट के लिए अलग -अलग अभ्यावेदन का उपयोग करते हैं, अनुवाद किसी भी दो मॉडलों के बीच मौजूद हैं, और इसलिए प्रत्येक मॉडल अनिवार्य रूप से कार्यों के एक ही वर्ग का वर्णन करता है, यह राय को जन्म देता है कि औपचारिक कम्प्यूटरी दोनों प्राकृतिक है और भी नहीं भी हैसँकरा।<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=पूर्ण|पूर्ण]] है।
-उदाहरण के लिए, कोई कम्प्यूटेबल फ़ंक्शंस को μ- पुनरावर्ती कार्यों के रूप में औपचारिक रूप दे सकता है, जो [[आंशिक कार्य]] हैं जो [[प्राकृतिक संख्या]]ओं के परिमित ट्यूपल्स लेते हैं और एक भी प्राकृतिक संख्या (बस ऊपर के रूप में) लौटा देते हैं।वे आंशिक कार्यों के सबसे छोटे वर्ग हैं जिनमें निरंतर, उत्तराधिकारी और प्रक्षेपण कार्य शामिल हैं, और फ़ंक्शन रचना, आदिम पुनरावर्ती फ़ंक्शन और μ ऑपरेटर के तहत [[बंद (गणित)]] है।
+समान रूप से, संगणनीय कार्य को उन कार्यों में औपचारिक रूप दिया जा सकता है, जिसकी गणना एक आदर्श कंप्यूटिंग एजेंट जैसे कि ट्यूरिंग मशीन या रजिस्टर मशीन द्वारा की जा सकती है। औपचारिक रूप से, एक आंशिक फंक्शन <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:\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>।
-== कम्प्यूटेबल फ़ंक्शंस की विशेषताएं ==
+{{main| एल्गोरिथम}}
-{{main|Algorithm}}
+एक संगणनीय कार्य की मूल विशेषता यह है कि कार्य की गणना कैसे करें, यह बताने वाली एक परिमित प्रक्रिया (एक एल्गोरिथम) होनी चाहिए। सूचीबद्ध गणना एक मॉडल प्रक्रिया है और इसका उपयोग कैसे किया जाता है, इसकी व्याख्या अलग -अलग करते हैं, परंतु ये व्याख्या कई गुणों को साझा करती है। तथ्य यह है कि ये मॉडल संगणनीय कार्य के समान वर्ग देते हैं, इस तथ्य से लाभ है कि प्रत्येक मॉडल किसी भी अन्य मॉडलों के लिए यह प्रक्रिया सक्षम है, जितना कि एक [[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 के डोमेन में नहीं है, तो प्रक्रिया हमेशा के लिए चल सकती है, कभी भी रुक नहीं सकती।या यह किसी बिंदु पर अटक सकता है (यानी, इसके निर्देशों में से एक को निष्पादित नहीं किया जा सकता है), लेकिन इसे 'एक्स' पर एफ के लिए एक मूल्य का उत्पादन करने का दिखावा नहीं करना चाहिए।इस प्रकार यदि f ('x') के लिए एक मान कभी भी पाया जाता है, तो यह सही मान होना चाहिए।कंप्यूटिंग एजेंट के लिए गलत परिणामों से सही परिणामों को अलग करने के लिए यह आवश्यक नहीं है क्योंकि प्रक्रिया को सही के रूप में परिभाषित किया गया है यदि और केवल अगर यह एक परिणाम का उत्पादन करता है।
+*यदि प्रक्रिया को k-tuple 'X' दिया जाता है, जो F की डोमेन में नहीं है, तो प्रक्रिया हमेशा के लिए चल सकती है, कभी भी रुक नहीं सकती। या किसी बिंदु पर अटक नहीं सकती है ('अर्थात, इसके निर्देशों में से किसी एक को भी निष्पादित नहीं किया जा सकता है), परंतु इसे 'x' पर f के लिए एक मूल्य का उत्पादन करने का दिखावा नहीं करना चाहिए। इस प्रकार यदि f ('x') के लिए कोई मूल्य कभी पाया जाता है, तो यह सही मूल्य होना चाहिए। कंप्यूटिंग एजेंट के लिए यह आवश्यक नहीं है कि वह सही परिणामों को गलत परिणामों से सही परिणामों से करे चूंकि प्रक्रिया को सही के रूप में परिभाषित किया गया है।
-एंडर्टन एक कम्प्यूटेबल फ़ंक्शन के लिए प्रक्रिया की इन 3 आवश्यकताओं के कई स्पष्टीकरणों को सूचीबद्ध करता है:<!-- must be enumerated for the "#Church–Turing thesis" below-->
+एंडर्टन एक संगणनीय कार्य के लिए प्रक्रिया की इन 3 आवश्यकताओं के कई स्पष्टीकरणों को सूचीबद्ध करता है:<!-- must be enumerated for the "#Church–Turing thesis" below-->
-# प्रक्रिया को सैद्धांतिक रूप से मनमाने ढंग से बड़े तर्कों के लिए काम करना चाहिए।यह नहीं माना जाता है कि तर्क पृथ्वी में परमाणुओं की संख्या से छोटे हैं, उदाहरण के लिए।
+# प्रक्रिया को सैद्धांतिक रूप से मनमाने ढंग से बड़े तर्कों के लिए काम करना चाहिए। यह नहीं माना जाता है कि तर्क पृथ्वी में परमाणुओं की संख्या से कम हैं,
-# प्रक्रिया को आउटपुट का उत्पादन करने के लिए कई चरणों के बाद रुकने की आवश्यकता होती है, लेकिन रुकने से पहले यह कई कदमों को मनमाने ढंग से ले सकता है।कोई समय सीमा नहीं ली जाती है।
+# आउटपुट उत्पन्न करने के लिए प्रक्रिया को कई चरणों मे समाप्त होना आवश्यक है, परंतु रुकने से पहले यह मनमाने ढंग से कई कदम उठा सकता है। इसमे कोई समय सीमा नहीं मानी जाती है।
-# हालांकि प्रक्रिया एक सफल गणना के दौरान केवल भंडारण स्थान की एक परिमित मात्रा का उपयोग कर सकती है, लेकिन उपयोग किए जाने वाले स्थान की मात्रा पर कोई बाध्य नहीं है।यह माना जाता है कि जब भी प्रक्रिया पूछती है, तो अतिरिक्त भंडारण स्थान प्रक्रिया को दिया जा सकता है।
+# यद्यपि प्रक्रिया एक सफल गणना के समय एक सीमित मात्रा में संग्रह स्थान का उपयोग कर सकती है, परंतु उपयोग किए जाने वाले स्थान की मात्रा पर कोई बाध्यता नहीं है। यह माना जाता है कि जब भी कार्यविधि को आवश्यकता होती है, तो अतिरिक्त संग्रह स्थान कार्यविधि को दिया जा सकता है।
-संक्षेप में, इस दृश्य के आधार पर एक फ़ंक्शन कम्प्यूटेबल है यदि:
+संक्षेप में, इस दृश्य के आधार पर एक कार्य की गणना की जा सकती है:
-{{ordered list|list-style-type=lower-alpha
+{{ordered list|list-style-type=कम-अल्फा
-|given an input from its domain, possibly relying on unbounded storage space, it can give the corresponding output by following a procedure (program, algorithm) that is formed by a finite number of exact unambiguous instructions;
+|अपने डोमेन से एक इनपुट दिया गया है, संभवतः असीमित स्टोरेज स्पेस पर भरोसा करते हुए, यह एक प्रक्रिया (प्रोग्राम, एल्गोरिदम) का पालन करके संबंधित आउटपुट दे सकता है जो सटीक स्पष्ट निर्देशों की एक सीमित संख्या से बनता है;
-| it returns such output (halts) in a finite number of steps; and
+|यह इस तरह के आउटपुट (हॉल्ट्स) को सीमित चरणों में लौटाता है; |और यदि कोई इनपुट दिया जाता है जो उसके डोमेन में नहीं है तो भी वह कभी रुकता नहीं है और न ही कभी अटकता है।}}
-| if given an input which is not in its domain it either never halts or it gets stuck.
+अभिकलनात्मक जटिलता अध्ययन का क्षेत्र एक सफल संगणना में अनुमत समय और/या स्थान पर निर्धारित सीमा के साथ कार्य करता है।
-}}
-कम्प्यूटेशनल जटिलता सिद्धांत का क्षेत्र एक सफल गणना में अनुमत समय और/या स्थान पर निर्धारित सीमा के साथ कार्य करता है।
-== कम्प्यूटेबल सेट और संबंध ==
+== संगणनीय सेट और संबंध ==
-एक सेट {{math|<var>A</var>}} प्राकृतिक संख्याओं को कम्प्यूटेबल कहा जाता है (समानार्थी: पुनरावर्ती, निर्णय लेने योग्य) यदि कोई कम्प्यूटरी, कुल फ़ंक्शन है {{math|''f''}} ऐसा कि किसी भी प्राकृतिक संख्या के लिए {{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|<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>}} में नहीं है।
-प्राकृतिक संख्याओं के एक सेट को कम्प्यूटेशनल रूप से enumerable कहा जाता है (समानार्थक शब्द: पुनरावर्ती रूप से enumerable, semidecidable) यदि एक कम्प्यूटेबल फ़ंक्शन है {{math|''f''}} ऐसा कि प्रत्येक संख्या के लिए {{math|<var>n</var>}}, {{math|''f''(<var>n</var>)}} परिभाषित किया गया है [[अगर और केवल अगर]] {{math|<var>n</var>}} सेट में है।इस प्रकार एक सेट कम्प्यूटिक रूप से यदि और केवल अगर यह कुछ कम्प्यूटेबल फ़ंक्शन का डोमेन है।Enumerable शब्द का उपयोग किया जाता है क्योंकि निम्नलिखित एक गैर -रिक्त सबसेट के बराबर हैं {{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>}} योग संगणनीय कार्य की श्रेणी है। यदि {{math|<var>B</var>}} अनंत है तो फलन को [[Index.php?title=इंजेक्शन|इंजेक्शन]] माना जा सकता है।
-अगर एक सेट {{math|<var>B</var>}} एक फ़ंक्शन की सीमा है {{math|''f''}} तब फ़ंक्शन को एक के रूप में देखा जा सकता है
+यदि एक सेट {{math|<var>B</var>}} कार्य {{math|''f''}} की सीमा है तब फंक्शन को {{math|<var>B</var>}} की गणना के रूप में देखा जा सकता है
-की गणना {{math|<var>B</var>}}, क्योंकि सूची {{math|''f''(0), ''f''(1), ...}} का हर तत्व शामिल होगा {{math|<var>B</var>}}।
+चूंकि सूची {{math|''f''(0), ''f''(1), ...}}में {{math|<var>B</var>}} के प्रत्येक तत्व सम्मलित होंगे।
-क्योंकि प्राकृतिक संख्याओं पर प्रत्येक स्वच्छ संबंध को प्राकृतिक संख्याओं के परिमित अनुक्रमों के एक संगत सेट के साथ पहचाना जा सकता है, कम्प्यूटेबल संबंध की धारणाओं और कम्प्यूटेशनल रूप से एन्यूमरेबल संबंध को सेट के लिए उनके एनालॉग्स से परिभाषित किया जा सकता है।
+चूंकि प्राकृतिक संख्याओं पर प्रत्येक परिमित संबंध को प्राकृतिक संख्याओं के परिमित अनुक्रमों के संगत समुच्चय के साथ पहचाना जा सकता है, संगणनीय संबंध और संगणनीय रूप से गणना योग्य संबंध की धारणाओं को सेट के लिए उनके अनुरूपों से परिभाषित किया जा सकता है।
 == औपचारिक भाषाएँ ==
-{{main|Formal language}}कम्प्यूटिबिलिटी थ्योरी (कंप्यूटर साइंस) में, [[औपचारिक भाषा]]ओं पर विचार करना आम है।एक 'वर्णमाला' एक मनमाना सेट है।एक वर्णमाला पर एक 'शब्द' वर्णमाला से प्रतीकों का एक परिमित अनुक्रम है;एक ही प्रतीक का उपयोग एक से अधिक बार किया जा सकता है।उदाहरण के लिए, बाइनरी स्ट्रिंग्स वर्णमाला पर बिल्कुल शब्द हैं {{math|{0, 1} }}।एक भाषा एक निश्चित वर्णमाला पर सभी शब्दों के संग्रह का एक सबसेट है।उदाहरण के लिए, सभी बाइनरी स्ट्रिंग्स का संग्रह जिसमें बिल्कुल 3 वाले होते हैं, बाइनरी वर्णमाला पर एक भाषा है।
+{{main|औपचारिक भाषा}}
+कंप्यूटर विज्ञान में अभिकलन सिद्धांत में, [[Index.php?title=औपचारिक भाषाओं|औपचारिक भाषाओं]] पर विचार करना साधारण है। एक 'वर्णमाला' एक मनमाना सेट है। एक वर्णमाला पर एक 'शब्द' वर्णमाला से प्रतीकों का एक परिमित अनुक्रम है; एक ही चिन्ह का एक से अधिक बार प्रयोग किया जा सकता है। उदाहरण के लिए, बाइनरी स्ट्रिंग्स वर्णमाला{{math|{0, 1} }}पर सटीक शब्द हैं। एक भाषा एक निश्चित वर्णमाला पर सभी शब्दों के संग्रह का एक उपसमुच्चय है। उदाहरण के लिए, सभी बाइनरी श्रृंखला का संग्रह होते हैं, बाइनरी वर्णमाला एक भाषा है।
-एक औपचारिक भाषा की एक प्रमुख संपत्ति यह तय करने के लिए आवश्यक कठिनाई का स्तर है कि कोई दिया गया शब्द भाषा में है या नहीं।इनपुट के रूप में भाषा में एक मनमाना शब्द लेने के लिए एक कम्प्यूटेबल फ़ंक्शन की अनुमति देने के लिए कुछ कोडिंग सिस्टम विकसित किया जाना चाहिए;यह आमतौर पर दिनचर्या माना जाता है।एक भाषा को कम्प्यूटेबल कहा जाता है (समानार्थी: पुनरावर्ती, निर्णय लेने योग्य) यदि कोई कम्प्यूटबल फ़ंक्शन है {{math|''f''}} ऐसा कि प्रत्येक शब्द के लिए {{math|<var>w</var>}} वर्णमाला के ऊपर, {{math|''f''(<var>w</var>) {{=}} 1}} यदि शब्द भाषा में है और {{math|''f''(<var>w</var>) {{=}} 0}} यदि शब्द भाषा में नहीं है।इस प्रकार एक भाषा कम्प्यूटेबल होती है, बस एक ऐसी प्रक्रिया होती है जो सही ढंग से बताने में सक्षम होती है कि क्या मनमाने शब्द भाषा में हैं।
+एक औपचारिक भाषा की एक प्रमुख संपत्ति यह तय करने के लिए एक आवश्यक स्तर है  कि कोई दिया गया शब्द भाषा में है या नहीं।  इनपुट के रूप में भाषा में एक मनमाना शब्द लेने के लिए एक गणना योग्य कार्य की अनुमति देने के लिए कुछ कोडिंग सिस्टम विकसित किया जाना चाहिए;  इसे सामान्यतः नियमित माना जाता है। एक भाषा को संगणनीय कहा जाता है (समानार्थक: पुनरावर्ती, निर्णायक) यदि कोई संगणनीय फलन है जैसे कि वर्णमाला के प्रत्येक शब्द {{math|''f''(<var>w</var>) {{=}} 1}} यदि शब्द भाषा में है और {{math|''f''(<var>w</var>) {{=}} 0}} यदि शब्द भाषा में नहीं है।  इस प्रकार एक भाषा की गणना एकमात्र तभी की जा सकती है जब कोई ऐसी प्रक्रिया हो जो सही ढंग से यह बता सके कि भाषा में अनैतिक शब्द हैं या नहीं।
-एक भाषा कम्प्यूटरीली (समानार्थक शब्द: पुनरावर्ती रूप से enumerable, semidecidable) है, यदि कोई कम्प्यूटरी फ़ंक्शन है {{math|''f''}} ऐसा है कि {{math|''f''(<var>w</var>)}} परिभाषित किया गया है अगर और केवल अगर शब्द {{math|<var>w</var>}} भाषा में है।Enumerable शब्द में समान व्युत्पत्ति होती है, जैसा कि प्राकृतिक संख्याओं के कम्प्यूटिक रूप से enumerable सेट में होता है।
+एक भाषा संगणनीय रूप से गणना योग्य है (समानार्थक: पुनरावर्ती रूप से गणना करने योग्य, अर्धविराम योग्य) यदि कोई संगणनीय कार्य है जैसे कि {{math|''f''(<var>w</var>)}} परिभाषित किया गया है यदि और एकमात्र शब्द {{math|<var>w</var>}} भाषा में है।  गणना योग्य शब्द की व्युत्पत्ति वैसी ही है जैसी प्राकृतिक संख्याओं के संगणनीय रूप से गणना योग्य सेटों में होती है।
 == उदाहरण ==
-निम्नलिखित कार्य कम्प्यूटेशनल हैं:
+निम्नलिखित कार्य गणना योग्य हैं:
-* एक फ़ंक्शन के परिमित डोमेन के साथ प्रत्येक फ़ंक्शन;जैसे, प्राकृतिक संख्याओं का कोई परिमित अनुक्रम।
+* एक परिमित डोमेन के साथ प्रत्येक फंक्शन; उदाहरण के लिए, प्राकृतिक संख्याओं का कोई परिमित क्रम नही है।
-* प्रत्येक निरंतर फ़ंक्शन f: 'n'<sup>K </do> → 'n', f (n (n<sub>1</sub>,...एन<sub>''k''</sub>): = एन।
+* प्रत्येक स्थिर फंक्शन 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>
-* दो नंबरों का सबसे बड़ा आम भाजक
+* दो संख्याओं का सबसे बड़ा सामान्य विभाजक
-* दो नंबरों का एक बेज़ाउट गुणांक
+* दो संख्याओं का बेज़ाउट गुणांक
 * एक संख्या का सबसे छोटा [[मुख्य कारक है]]
-यदि f और g कम्प्यूटेबल हैं, तो वे हैं: f + g, गुणन | f * g, फ़ंक्शन रचना |<math>\color{Blue} f \circ g</math>अगर
+यदि f और g गणना योग्य हैं, तो वे हैं: f + g, गुणन | f * g, फंक्शन रचना |<math>\color{Blue} f \circ g</math>यदि
-f unary ऑपरेशन है, अधिकतम (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 जैसे कि f (n) = 1 यदि दशमलव विस्तार में कम से कम n लगातार fives का एक अनुक्रम है {{Pi}}, और f (n) = 0 अन्यथा, कम्प्यूटेशनल है।(फ़ंक्शन F या तो निरंतर 1 फ़ंक्शन है, जो कम्प्यूटेशनल है, या फिर एक k है जैसे कि f (n) = 1 यदि n <k और f (n) = 0 यदि n ≥ k। ऐसा प्रत्येक फ़ंक्शन कम्प्यूटेशनल है।यह ज्ञात नहीं है कि क्या π के दशमलव विस्तार में मनमाने ढंग से लंबे समय तक फाइव्स हैं, इसलिए हम नहीं जानते कि उन कार्यों में से कौन सी है। फिर भी, हम जानते हैं कि फ़ंक्शन f को कम्प्यूटेशनल होना चाहिए।)
+* फंक्शन 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) की गणना करने के लिए एक तुच्छ एल्गोरिथ्म है;इसी तरह, n के किसी भी मूल्य के लिए, इस तरह के एक तुच्छ एल्गोरिथ्म मौजूद है (भले ही यह कभी भी किसी के द्वारा ज्ञात या उत्पादित नहीं किया जा सकता है) σ (0), σ (1), σ (2), ..., σ की गणना करने के लिएएन)।
+* प्राकृतिक संख्याओं के एक अगणनीय अनुक्रम का प्रत्येक परिमित खंड (जैसे व्यस्त बीवर फंक्शन Σ) संगणनीय है। उदाहरण के लिए, प्रत्येक प्राकृतिक संख्या n के लिए, एक एल्गोरिथम सम्मलित है जो परिमित अनुक्रम σ (0), σ (1), σ (2), ..., σ (n) - इस तथ्य के विपरीत है कि कोई कलन विधि जो पूरे σ- अनुक्रम की गणना करता है, अर्थात् सभी n के लिए σ (n)।इस प्रकार, प्रिंट 0, 1, 4, 6, 13 एक तुच्छ एल्गोरिथ्म है, जो σ (0), σ (1), σ (2), σ (3), σ (4) की गणना करने के लिए एक तुच्छ एल्गोरिथ्म सम्मलित है (भले ही यह कभी भी ज्ञात या किसी के द्वारा निर्मित नहीं हो सकता है) σ (0), σ (1), σ (2), ..., σ n।
 == चर्च -ट्र्यूरिंग थीसिस ==
-{{main|Church–Turing thesis}}
+{{main|चर्च-ट्यूरिंग थीसिस}}
-चर्च -ट्रिंग थीसिस में कहा गया है कि कम्प्यूटेशनल फ़ंक्शंस के #Characteristics सूचीबद्ध तीन गुणों को रखने वाली प्रक्रिया से कम्प्यूटेबल कोई भी फ़ंक्शन एक कम्प्यूटेबल फ़ंक्शन है।क्योंकि इन तीन गुणों को औपचारिक रूप से नहीं कहा गया है, चर्च -ट्यूरिंग थीसिस को साबित नहीं किया जा सकता है।निम्नलिखित तथ्यों को अक्सर थीसिस के लिए सबूत के रूप में लिया जाता है:
-* गणना के कई समान मॉडल ज्ञात हैं, और वे सभी कम्प्यूटेबल फ़ंक्शन (या एक कमजोर संस्करण, कुछ उदाहरणों में) की समान परिभाषा देते हैं।
-* गणना का कोई मजबूत मॉडल जिसे आमतौर पर [[प्रभावी रूप से गणना योग्य]] माना जाता है, प्रस्तावित किया गया है।
-चर्च -ट्राईिंग थीसिस का उपयोग कभी -कभी प्रमाणों में किया जाता है ताकि यह सही हो सके कि गणना के लिए एक प्रक्रिया का ठोस विवरण देकर एक विशेष फ़ंक्शन कम्प्यूटेबल है।यह अनुमति दी जाती है क्योंकि यह माना जाता है कि थीसिस के ऐसे सभी उपयोगों को गणना के कुछ मॉडल में फ़ंक्शन के लिए एक औपचारिक प्रक्रिया लिखने की थकाऊ प्रक्रिया द्वारा हटाया जा सकता है।
+चर्च -ट्रिंग थीसिस में कहा गया है सूचीबद्ध तीन गुणों वाली प्रक्रिया से संगणनीय कोई भी कार्य एक गणना योग्य कार्य है। चूंकि इन तीन गुणों को औपचारिक रूप से नहीं बताया गया है, चर्च -ट्यूरिंग थीसिस को सिद्ध नहीं किया जा सकता है। निम्नलिखित तथ्यों को अधिकांशतः थीसिस के साक्ष्य के रूप में लिया जाता है:
+* अभिकलन के कई समकक्ष मॉडल ज्ञात हैं, और वे सभी संगणनीय फलन (या कुछ उदाहरणों में एक कमजोर संस्करण) की समान परिभाषा देते हैं।
+* संगणना का कोई ठोस मॉडल प्रस्तावित नहीं किया गया है, जिसे सामान्यतः [[प्रभावी रूप से गणना योग्य]] माना जाता है।
+चर्च -ट्राईिंग थीसिस को कभी-कभी सबूतों में प्रयोग किया जाता है इसलिये यह प्रमाणित किया जा सके कि गणना के लिए एक प्रक्रिया का ठोस विवरण देकर एक विशेष कार्य गणना योग्य है। चूंकि यह माना जाता है कि थीसिस के ऐसे सभी उपयोगों को गणना के कुछ मॉडल में फंक्शन के लिए एक औपचारिक प्रक्रिया लिखने की कठिन प्रक्रिया द्वारा हटाया जा सकता है।
 == प्रोवेबिलिटी ==
-एक फ़ंक्शन (या, इसी तरह, एक सेट) को देखते हुए, किसी को न केवल कम्प्यूटेशनल होने पर दिलचस्पी हो सकती है, बल्कि यह भी कि क्या यह एक विशेष प्रूफ सिस्टम (आमतौर पर प्रथम-क्रम लॉजिक [[पीनो अंकगणित]]) में साबित हो सकता है।एक फ़ंक्शन जिसे कम्प्यूटेशनल साबित किया जा सकता है, उसे 'प्रॉमिस टोटल' कहा जाता है।
+फंक्शन एकमात्र गणना होने पर प्रभावित हो सकता है, किन्तु यह एक विशेष प्रमाण प्रणाली में सिद्ध किया जा सकता है (सामान्यतः [[पीनो अंकगणित]] का प्रथम-क्रम ) कार्य जिसे संगणनीय सिद्ध किया जा सकता है, उसे 'प्रॉमिस टोटल' कहा जाता है।
-कुल कार्यों का सेट पुनरावर्ती रूप से समृद्ध है: कोई भी अपने सभी संबंधित प्रमाणों की गणना करके सभी साबित कुल कार्यों की गणना कर सकता है, जो उनकी कम्प्यूटिबिलिटी को साबित करता है।यह प्रमाण प्रणाली के सभी प्रमाणों की गणना और अप्रासंगिक लोगों को अनदेखा करके किया जा सकता है।
+कुल कार्यों का सेट पुनरावर्ती रूप से गणना योग्य है: कोई भी उनके सभी संगत प्रमाणों की गणना करके सभी सिद्ध कुल कार्यों की गणना कर सकता है, जो उनकी संगणना को प्रमाणित करते हैं। यह साक्ष्य प्रणाली के सभी प्रमाणों की गणना करके और अप्रासंगिक लोगों को अप्रत्यक्ष करके किया जा सकता है।
 === पुनरावर्ती परिभाषित कार्यों के संबंध ===
-एक [[पुनरावर्ती परिभाषा]] द्वारा परिभाषित एक फ़ंक्शन में, प्रत्येक मान को अन्य के एक निश्चित प्रथम-क्रम सूत्र द्वारा परिभाषित किया जाता है, पहले एक ही फ़ंक्शन या अन्य कार्यों के परिभाषित मूल्यों, जो केवल स्थिरांक हो सकते हैं।इनमें से एक सबसेट आदिम पुनरावर्ती कार्य है।इस तरह के प्रत्येक कार्य कुल है: इस तरह के एक [[arity]] के लिए | k-ary फ़ंक्शन f, प्रत्येक मान <math>f(n_1, n_2... n_k)</math> परिभाषा का अनुसरण करके गणना की जा सकती है, पुनरावृत्ति, और पुनरावृत्ति की परिमित संख्या के बाद (जैसा कि आसानी से साबित किया जा सकता है), एक स्थिरांक तक पहुंच जाता है।
+एक [[पुनरावर्ती परिभाषा]] द्वारा परिभाषित एक फलन में, प्रत्येक मान को अन्य के एक निश्चित प्रथम-क्रम सूत्र द्वारा परिभाषित किया जाता है, पहले एक ही फंक्शन या अन्य कार्यों के परिभाषित मूल्यों, जो केवल स्थिरांक हो सकते हैं। इनमें से एक सबसेट आदिम पुनरावर्ती कार्य है। इस तरह के प्रत्येक कार्य योग्य है: इस तरह के एक [[arity]] के लिए | k-ary फंक्शन f, प्रत्येक मान <math>f(n_1, n_2... n_k)</math> परिभाषा का अनुसरण करके ओर, पुनरावृत्ति रूप से, और पुनरावृत्ति की परिमित संख्या के बाद (जैसा कि  सरलता से सिद्ध किया जा सकता है), एक स्थिरांक की गणना कर के पहुंचा जा सकता है।
-यह सच नहीं है, क्योंकि प्रत्येक साबित कुल समारोह आदिम पुनरावर्ती नहीं है।वास्तव में, कोई भी सभी आदिम पुनरावर्ती कार्यों की गणना कर सकता है और एक फ़ंक्शन को परिभाषित कर सकता है जैसे कि सभी 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 एक [[विकर्ण]] lemma तर्क द्वारा कुल मिलाकर कुल है, लेकिन आदिम पुनरावर्ती नहीं है: वहाँ एक j था कि g = f था<sub>''j''</sub>, हमें g (j) = en (j, j) +1 = f मिल गया होगा<sub>''j''</sub> (j)+1 = g (j) +1, एक विरोधाभास।(सभी आदिम पुनरावर्ती कार्यों के Gödel संख्याओं को एक आदिम पुनरावर्ती फ़ंक्शन द्वारा गणना की जा सकती है, हालांकि आदिम पुनरावर्ती कार्यों के मान नहीं हो सकते हैं।)
+आक्षेप सत्य नहीं है, चूंकि प्रत्येक प्रमाणित कार्य योग्य आदिम पुनरावर्ती नहीं है। वास्तव ,कोई भी सभी आदिम पुनरावर्ती कार्यों की गणना कर सकता है और एक फंक्शन 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, एक विरोधाभास। (सभी आदिम पुनरावर्ती कार्यों की गोडेल संख्या को एक आदिम पुनरावर्ती कार्य द्वारा गणना की जा सकती है, चूंकि आदिम पुनरावर्ती कार्यों के मान नहीं हो सकते हैं।)
-ऐसा ही एक फ़ंक्शन, जो कुल साबित करने योग्य है, लेकिन आदिम पुनरावर्ती नहीं है, [[एकरमन फ़ंक्शन]] है: चूंकि यह पुनरावर्ती रूप से परिभाषित किया गया है, इसलिए इसकी कम्प्यूटिबिलिटी को साबित करना वास्तव में आसान है (हालांकि, एक समान विकर्ण तर्क भी पुनरावर्ती परिभाषा द्वारा परिभाषित सभी कार्यों के लिए बनाया जा सकता है।; इस प्रकार, कुल कार्य हैं जिन्हें पुनरावर्ती रूप से परिभाषित नहीं किया जा सकता है {{citation needed|date=June 2016}})।
+एक ऐसा कार्य, जो सिद्ध करने योग्य है, परंतु आदिम पुनरावर्ती नहीं है, [[Index.php?title=एकरमन फलन|एकरमन फलन]] है: चूंकि यह पुनरावर्ती रूप से परिभाषित किया गया है, इसकी संगणना को सिद्ध करना वास्तव में सरल है (चूंकि, पुनरावर्ती परिभाषा द्वारा परिभाषित सभी कार्यों के लिए एक समान विकर्ण तर्क भी बनाया जा सकता है ; इस प्रकार, सिद्ध करने योग्य कार्य हैं जिन्हें पुनरावर्ती रूप से परिभाषित नहीं किया जा सकता है {{citation needed|date=June 2016}})।
-=== कुल कार्य जो कुल नहीं हैं ===
+=== योग कार्य जो सिद्ध रूप से योग नहीं हैं ===
-एक [[दृढ़ता]] प्रूफ सिस्टम में, प्रत्येक कुल समग्र समारोह वास्तव में कुल है, लेकिन यह स्पष्ट नहीं है: हर प्रथम-क्रम प्रूफ सिस्टम में जो पर्याप्त रूप से मजबूत और ध्वनि है (मीनो अंकगणित सहित), कोई भी साबित कर सकता है (एक अन्य प्रमाण प्रणाली में)कुल कार्यों का अस्तित्व जो प्रमाण प्रणाली में कुल साबित नहीं किया जा सकता है।
+एक [[Index.php?title=ध्वनि|ध्वनि]] प्रमाण प्रणाली में, प्रत्येक सिद्ध योग कार्य वास्तव में योग है, परंतु इसका विलोम सत्य नहीं है: प्रत्येक प्रथम-क्रम प्रमाण प्रणाली में जो पर्याप्त सुदृढ़ और ध्वनि (पीनो अंकगणित सहित) है, कोई भी (दूसरे प्रमाण प्रणाली में) सिद्ध कर सकता है योग कार्यों का अस्तित्व जो प्रमाण प्रणाली में योग सिद्ध नहीं किया जा सकता है।
-यदि कुल कम्प्यूटेबल फ़ंक्शंस को ट्यूरिंग मशीनों के माध्यम से एन्यूमरेट किया जाता है, जो उन्हें पैदा करता है, तो उपरोक्त कथन को दिखाया जा सकता है, यदि प्रूफ सिस्टम ध्वनि है, तो ऊपर दिए गए एक समान विकर्ण तर्क द्वारा, पहले दिए गए कुल कार्यों की गणना का उपयोग करके।एक ट्यूरिंग मशीन का उपयोग करता है जो प्रासंगिक प्रमाणों की गणना करता है, और प्रत्येक इनपुट n कॉल f के लिए<sub>''n''</sub>(एन) (जहां एफ<sub>''n''</sub> इस गणना द्वारा n-th फ़ंक्शन है) ट्यूरिंग मशीन को आमंत्रित करके जो इसे N-TH प्रूफ के अनुसार गणना करता है।इस तरह की ट्यूरिंग मशीन को रुकने की गारंटी दी जाती है यदि प्रूफ सिस्टम ध्वनि है।
+यदि ट्यूरिंग मशीनों के माध्यम से कुल संगणनीय कार्यों की गणना की जाती है, तो उपरोक्त कथन दिखाया जा सकता है,यदि प्रमाण प्रणाली ध्वनि है, तो एक समान विकर्ण तर्क द्वारा, पहले दिए गए कुल कार्यों की गणना का उपयोग करके। एक ट्यूरिंग मशीन का उपयोग करता है जो प्रासंगिक प्रमाणों की गणना करता है, और प्रत्येक इनपुट n कॉल f के लिए<sub>''n''</sub>(एन) (जहां एफ<sub>''n''</sub> इस गणना द्वारा n-th फंक्शन है) ट्यूरिंग मशीन का आह्वान करके जो इसे N-TH प्रमाण के अनुसार गणना करता है। ऐसी ट्यूरिंग मशीन के रुकने की गारंटी है यदि प्रमाण सिस्टम ध्वनि है।
 == अप्रभावी कार्य और अनहोनी समस्याएं ==
-{{main|List of undecidable problems}}
+{{main|अनिर्णीत समस्याओं की सूची}}
-प्रत्येक कम्प्यूटेबल फ़ंक्शन में एक परिमित प्रक्रिया होती है, जो इसकी गणना करने के तरीके के बारे में स्पष्ट, अस्पष्ट निर्देश देती है।इसके अलावा, इस प्रक्रिया को कम्प्यूटेशनल मॉडल द्वारा उपयोग की जाने वाली परिमित वर्णमाला में एन्कोड किया जाना है, इसलिए केवल कई कम्प्यूटेबल फ़ंक्शन हैं।उदाहरण के लिए, कार्यों को बिट्स की एक स्ट्रिंग (वर्णमाला) का उपयोग करके एन्कोड किया जा सकता है {{math|&Sigma; {{=}} {0, 1}}})।
-वास्तविक संख्या बेशुमार हैं इसलिए अधिकांश वास्तविक संख्या कम्प्यूटेबल नहीं हैं।कम्प्यूटेबल नंबर#गुण देखें।प्राकृतिक संख्याओं पर साहित्यिक कार्यों का सेट बेशुमार है इसलिए अधिकांश कम्प्यूटेबल नहीं हैं।इस तरह के कार्यों के ठोस उदाहरण [[व्यस्त बीवर]], [[कोलमोगोरोव जटिलता]], या किसी भी फ़ंक्शन में हैं जो चेटिन के स्थिरांक जैसे एक गैर -उपलब्ध संख्या के अंकों को आउटपुट करता है।
+प्रत्येक संगणनीय कार्य की एक परिमित प्रक्रिया होती है जो इसकी गणना करने के नियम पर स्पष्ट, निर्देश देती है। इसके अतिरिक्त, इस प्रक्रिया को अभिकलनात्मक जटिलता द्वारा उपयोग किए जाने वाले परिमित वर्णमाला में एन्कोड किया जाता है, इसलिए  एकमात्र गणना करने योग्य कई कार्य हैं। उदाहरण के लिए, कार्यों को बिट्स की एक स्ट्रिंग (वर्णमाला) का उपयोग करके एन्कोड किया जा सकता है {{math|&Sigma; {{=}} {0, 1}}})।
-इसी तरह, प्राकृतिक संख्याओं के अधिकांश सबसेट कम्प्यूटेबल नहीं हैं।रुकने की समस्या का निर्माण किया जाने वाला पहला सेट था।[[डेविड हिल्बर्ट]] द्वारा प्रस्तावित entscheidungsproblem ने पूछा कि क्या यह निर्धारित करने के लिए एक प्रभावी प्रक्रिया है कि कौन से गणितीय कथन (प्राकृतिक संख्या के रूप में कोडित) सत्य हैं।ट्यूरिंग और चर्च ने स्वतंत्र रूप से 1930 के दशक में दिखाया कि प्राकृतिक संख्याओं का यह सेट कम्प्यूटेबल नहीं है।चर्च -ट्यूरिंग थीसिस के अनुसार, कोई प्रभावी प्रक्रिया नहीं है (एक एल्गोरिथ्म के साथ) जो इन संगणनाओं को कर सकता है।
+वास्तविक संख्या असंख्य हैं इसलिए अधिकांश वास्तविक संख्याएँ गणना योग्य नहीं हैं। प्राकृतिक संख्याओं पर परिमित कार्यों का समुच्चय असंख्य है इसलिए अधिकांश संगणनीय नहीं हैं। इस तरह के कार्यों के ठोस उदाहरण [[व्यस्त बीवर]], [[कोलमोगोरोव जटिलता]], या कोई भी कार्य है जैसे कि चैतिन का स्थिरांक, जो एक गैर-गणना योग्य संख्या के अंकों को उत्पादन करता है।
-== कम्प्यूटिबिलिटी का एक्सटेंशन ==
+इसी तरह, प्राकृत संख्याओं के अधिकांश उपसमुच्चय संगणनीय नहीं हैं। हॉल्टिंग की समस्या निर्मित होने वाला पहला ऐसा सेट था। [[डेविड हिल्बर्ट]] द्वारा प्रस्तावित एंट्सचेइडुंगस्प्रोबल ने पूछा कि क्या यह निर्धारित करने के लिए एक प्रभावी प्रक्रिया है कौन से गणितीय कथन (प्राकृतिक संख्या के रूप में कोडित) सत्य हैं। ट्यूरिंग और चर्च ने 1930 के दशक में स्वतंत्र रूप से दिखाया कि प्राकृतिक संख्याओं का यह सेट गणना योग्य नहीं है। चर्च-ट्यूरिंग थीसिस के अनुसार, ऐसी कोई प्रभावी प्रक्रिया नहीं है (एल्गोरिदम के साथ) जो इन संगणनाओं को निष्पादित कर सके।
-=== सापेक्ष कम्प्यूटिबिलिटी ===
+== संगणनीयता का विस्तार ==
-एक फ़ंक्शन की कम्प्यूटिबिलिटी की धारणा प्राकृतिक संख्या ए के एक मनमाना [[सेट (गणित)]] के लिए सापेक्ष कम्प्यूटिबिलिटी हो सकती है। एक फ़ंक्शन f को 'कम्प्यूटेबल इन' (समतुल्य 'ए-कंप्यूप्टेबल' या 'कम्प्यूटेबल सापेक्ष' के सापेक्ष होने के लिए परिभाषित किया गया है)जब यह संशोधनों के साथ एक कम्प्यूटेबल फ़ंक्शन की परिभाषा को संतुष्ट करता है, तो एक [[ओरेकल (कम्प्यूटिबिलिटी)]] के रूप में पहुंच की अनुमति देता है।एक कम्प्यूटेबल फ़ंक्शन की अवधारणा के साथ सापेक्ष कम्प्यूटिबिलिटी को गणना के कई अलग -अलग मॉडलों में समान परिभाषा दी जा सकती है।यह आमतौर पर एक अतिरिक्त आदिम ऑपरेशन के साथ गणना के मॉडल को पूरक करके पूरा किया जाता है जो पूछता है कि क्या दिया गया पूर्णांक ए का सदस्य है। हम अपने ग्राफ के साथ जी की पहचान करके एफ 'कम्प्यूटेबल जी' के बारे में भी बात कर सकते हैं।
+=== सापेक्ष संगणनीयता ===
+किसी फंक्शन की अभिकलन की धारणा को प्राकृतिक संख्याओं a के अनैतिक [[Index.php?title=सेट|सेट]] से संबंधित किया जा सकता है। एक फंक्शन f को a में गणना योग्य माना जाता है (समकक्ष ए-गणना योग्य या a के सापेक्ष गणना योग्य) जब यह गणना योग्य फंक्शन की परिभाषा को संतुष्ट करता है, एक [[Index.php?title=ओरेकल (अभिकलन)|ओरेकल (अभिकलन)]] के रूप में ए तक पहुंच की अनुमति देने वाले संशोधन। संगणनीय कार्य की अवधारणा के साथ-साथ संगणना के कई अलग-अलग मॉडलों में सापेक्ष संगणनीयता को समकक्ष परिभाषाएं दी जा सकती हैं। यह सामान्यतः एक अतिरिक्त आदिम ऑपरेशन के साथ गणना के मॉडल को पूरक करके पूरा किया जाता है जो पूछता है कि क्या दिया गया पूर्णांक ए का सदस्य है। हम इसके ग्राफ के साथ j की पहचान करके j में गणना योग्य होने के बारे में भी बात कर सकते हैं।
 === उच्च पुनरावर्ती सिद्धांत ===
-हाइपररिथिक सिद्धांत उन सेटों का अध्ययन करता है, जिन्हें खाली सेट के [[ट्यूरिंग कूद]] के एक [[कम्प्यूटेबल ऑर्डिनल]] संख्या से गणना की जा सकती है।यह द्वितीय क्रम अंकगणित की भाषा में एक सार्वभौमिक और अस्तित्व के दोनों सूत्र द्वारा परिभाषित सेट के बराबर है और [[अतिशयोक्ति]] के कुछ मॉडल के लिए।इससे भी अधिक सामान्य पुनरावर्ती सिद्धांतों का अध्ययन किया गया है, जैसे कि ई-रिकर्सेशन सिद्धांत जिसमें किसी भी सेट का उपयोग ई-पुनरावर्ती फ़ंक्शन के तर्क के रूप में किया जा सकता है।
+हाइपररिथिक सिद्धांत उन सेटों का अध्ययन करता है, जिन्हें निरर्थक सेट के [[Index.php?title=ट्यूरिंग जंप|ट्यूरिंग जंप]] के [[Index.php?title=संगणनीय क्रमसंख्या|संगणनीय क्रमसंख्या]] से गणना की जा सकती है। यह द्वितीय क्रम अंकगणित की भाषा में और हाइपरकंप्यूटेशन के कुछ मॉडलों के लिए एक सार्वभौमिक और अस्तित्वगत सूत्र दोनों द्वारा परिभाषित सेट के बराबर है। इससे भी अधिक सामान्य पुनरावर्तन सिद्धांतों का अध्ययन किया गया है, जैसे ई-पुनरावर्तन सिद्धांत जिसमें किसी भी सेट को ई-पुनरावर्ती फंक्शन के तर्क के रूप में उपयोग किया जा सकता है
-=== हाइपर-कंप्यूटेशन ===
+=== अति संगणना ===
-यद्यपि चर्च -ट्रिंग थीसिस में कहा गया है कि कम्प्यूटेबल फ़ंक्शंस में एल्गोरिदम के साथ सभी फ़ंक्शन शामिल हैं, लेकिन उन कार्यों के व्यापक वर्गों पर विचार करना संभव है जो उन आवश्यकताओं को आराम देते हैं जो एल्गोरिदम के पास होना चाहिए।हाइपरकंपुटेशन का क्षेत्र गणना के मॉडल का अध्ययन करता है जो सामान्य ट्यूरिंग संगणना से परे जाता है।
+यद्यपि चर्च -ट्रिंग थीसिस में कहा गया है कि संगणनीय कार्यों में एल्गोरिदम के साथ सभी कार्य सम्मलित हैं, ऐसे कार्यों के व्यापक वर्गों पर विचार करना संभव है जो उन आवश्यकताओं को स्थिरता प्रदान करता हैं जो एल्गोरिदम के पास होनी चाहिए। हाइपरकंपुटेशन का क्षेत्र गणना के मॉडल का अध्ययन करता है जो सामान्य ट्यूरिंग संगणना से बाहर जाता है।
 == यह भी देखें ==
@@ Line 161: / Line 165: @@
 {{ComplexityClasses}}
 {{Mathematical logic}}
-[[Category: अभिप्राय सिद्धांत]] [[Category: गणना सिद्धांत]]
-[[Category: Machine Translated Page]]
+[[Category:All articles with unsourced statements]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:Articles with unsourced statements from June 2016]]
+[[Category:Collapse templates]]
 [[Category:Created On 14/02/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Mathematics navigational boxes]]
+[[Category:Navbox orphans]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with empty portal template]]
+[[Category:Pages with script errors]]
+[[Category:Philosophy and thinking navigational boxes]]
+[[Category:Portal-inline template with redlinked portals]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Translated in Hindi]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:अभिप्राय सिद्धांत]]
+[[Category:गणना सिद्धांत]]

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

संगणनीय फलन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 11:16, 23 February 2023

Contents

परिभाषा

संगणनीय फलन की विशेषताएं

संगणनीय सेट और संबंध

औपचारिक भाषाएँ

उदाहरण

चर्च -ट्र्यूरिंग थीसिस

प्रोवेबिलिटी

पुनरावर्ती परिभाषित कार्यों के संबंध

योग कार्य जो सिद्ध रूप से योग नहीं हैं

अप्रभावी कार्य और अनहोनी समस्याएं

संगणनीयता का विस्तार

सापेक्ष संगणनीयता

उच्च पुनरावर्ती सिद्धांत

अति संगणना

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

संगणनीय फलन: Difference between revisions

Latest revision as of 11:16, 23 February 2023

परिभाषा

संगणनीय फलन की विशेषताएं

संगणनीय सेट और संबंध

औपचारिक भाषाएँ

उदाहरण

चर्च -ट्र्यूरिंग थीसिस

प्रोवेबिलिटी

पुनरावर्ती परिभाषित कार्यों के संबंध

योग कार्य जो सिद्ध रूप से योग नहीं हैं

अप्रभावी कार्य और अनहोनी समस्याएं

संगणनीयता का विस्तार

सापेक्ष संगणनीयता

उच्च पुनरावर्ती सिद्धांत

अति संगणना

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories