अभिकलनात्‍मक गणनीय सेट

"गणना योग्य समुच्चय" redirects here. For सेट-सैद्धांतिक अवधारणा, see गणनीय समुच्चय.

संगणनीयता सिद्धांत में, प्राकृतिक संख्याओं के एक समुच्चय एस को 'कम्प्यूटेशनल इन्युमरेबल(अभिकलनात्‍मक गणनीय) (सी.ई.)', 'रिकर्सिवली इन्युमरेबल(पुनरावर्ती रूप से गणनीय) (आर.ई.)', 'सेमीडेसिडेबल'(अर्द्धनिर्णय योग्य), 'आंशिक रूप से निर्णायक', 'लिस्टेबल', 'सूची योग्य, सिद्ध या ट्यूरिंग-पहचानने योग्य' कहा जाता है। अगर:

• एक कलन विधि है जैसे कि इनपुट नंबरों का समुच्चय जिसके लिए कलन विधि रुकता है, बिल्कुल एस है।

या, समकक्ष,

• एस के सदस्यों के लिए एक गणना कलन विधि है। इसका मतलब है कि इसका निर्गम एस के सभी सदस्यों की एक सूची है: एस₁, एस₂, एस₃, ... . यदि एस अनंत है, तो यह कलन विधि हमेशा के लिए चलेगा।

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

अभिकलनात्‍मक जटिलता सिद्धांत में, जटिलता वर्ग जिसमें सभी गणनात्मक गणना योग्य समुच्चय आरई (जटिलता) हैं। पुनरावर्तन सिद्धांत में, सी.ई. का जालक (क्रम) समावेशन के तहत समुच्चय को दर्शाया गया है ${\mathcal {E}}$.

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

प्राकृतिक संख्याओं के एक समुच्चय एस को 'अभिकलनात्‍मक गणनीय' कहा जाता है, यदि कोई आंशिक संगणनीय कार्य जिसका डोमेन बिल्कुल एस है, जिसका अर्थ है कि कार्य को परिभाषित किया गया है और केवल अगर इसका इनपुट एस का सदस्य है।

समतुल्य सूत्रीकरण

निम्नलिखित प्राकृतिक संख्याओं के समुच्चय एस के समतुल्य गुण हैं:

अर्धनिर्णायकता :

* समुच्चय S संगणनीय रूप से गणना योग्य है। अर्थात्, S एक आंशिक संगणनीय फलन का प्रांत (सह-श्रेणी) है।

* समुच्चय S है $\Sigma _{1}^{0}$ (अंकगणितीय पदानुक्रम का जिक्र करते हुए)।

* एक आंशिक संगणनीय कार्य f है जैसे कि:

$$f(x)={\begin{cases}1&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{cases}}$$

गणनीयता :

* समुच्चय एस आंशिक गणना योग्य फ़ंक्शन की सीमा है।

* समुच्चय एस कुल गणना योग्य फ़ंक्शन या खाली की सीमा है। यदि एस अनंत है, तो कार्य अंतःक्षेपक के रूप में चुना जा सकता है।

* समुच्चय एस एक आदिम पुनरावर्ती कार्य या खाली की सीमा है। भले ही एस अनंत है, इस मामले में मूल्यों की पुनरावृत्ति आवश्यक हो सकती है।

डायोफैंटाइन :

* पूर्णांक गुणांक और चर x, a, b, c, d, e, f, g, h, i के साथ एक बहुपद p है, जो प्राकृतिक संख्याओं से अधिक है

$$x\in S\Leftrightarrow \exists a,b,c,d,e,f,g,h,i\ (p(x,a,b,c,d,e,f,g,h,i)=0).$$

(इस परिभाषा में बाध्य चर की संख्या अब तक सबसे अच्छी तरह से ज्ञात है; हो सकता है कि सभी डायोफैंटाइन समुच्चयों को परिभाषित करने के लिए कम संख्या का उपयोग किया जा सके।)

* पूर्णांक से पूर्णांक तक एक बहुपद है जैसे कि समुच्चय एस में इसकी सीमा में गैर-ऋणात्मक संख्याएँ होती हैं।

Dovetailing (कंप्यूटर विज्ञान) की तकनीक द्वारा अर्ध-निर्णायकता और गणनीयता की समानता प्राप्त की जा सकती है।

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

A computable enumeration of the set of all Turing machines halting on a fixed input: Simulate all Turing machines (enumerated on vertical axis) step by step (horizontal axis), using the shown diagonalization scheduling. If a machine terminates, print its number. This way, the number of each terminating machine is eventually printed. In the example, the algorithm prints "9, 13, 4, 15, 12, 18, 6, 2, 8, 0, ..."

उदाहरण

• प्रत्येक संगणनीय समुच्चय संगणनीय रूप से गणना योग्य है, लेकिन यह सच नहीं है कि प्रत्येक गणना योग्य समुच्चय गणना योग्य है। संगणनीय समुच्चयों के लिए, कलन विधि को यह भी बताना चाहिए कि क्या कोई इनपुट समुच्चय में नहीं है - यह संगणनीय रूप से गणना योग्य समुच्चयों के लिए आवश्यक नहीं है।
• एक पुनरावर्ती गणना योग्य भाषा एक औपचारिक भाषा का एक संगणनीय रूप से गणना योग्य उपसमुच्चय है।
• प्रभावी रूप से प्रस्तुत स्वयंसिद्ध प्रणाली में सभी सिद्ध वाक्यों का समुच्चय एक संगणनीय रूप से गणना योग्य समुच्चय है।
• मटियासेविच के प्रमेय में कहा गया है कि प्रत्येक संगणनीय रूप से गणना योग्य समुच्चय एक डायोफैंटाइन समुच्चय है (विपरीत तुच्छ रूप से सत्य है)।
• सरल समुच्चय संगणनीय रूप से गणना योग्य हैं लेकिन गणना योग्य नहीं हैं।
• रचनात्मक समुच्चय गणना योग्य हैं लेकिन गणना योग्य नहीं हैं।
• कोई भी उत्पादक समुच्चय 'नहीं' गणना योग्य है।
• गोडेल नंबरिंग दी गई $\phi$ संगणनीय कार्यों की, समुच्चय $\{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}$ (कहाँ $\langle i,x\rangle$ कैंटर पेयरिंग फंक्शन है और $\phi _{i}(x)\downarrow$ दर्शाता है $\phi _{i}(x)$ परिभाषित किया गया है) संगणनीय रूप से गणना योग्य है (cf. एक निश्चित x के लिए चित्र)। यह समुच्चय हॉल्टिंग समस्या को एनकोड करता है क्योंकि यह उन इनपुट पैरामीटर्स का वर्णन करता है जिसके लिए प्रत्येक ट्यूरिंग मशीन रुकती है।
• गोडेल नंबरिंग दी गई $\phi$ संगणनीय कार्यों की, समुच्चय $\{\left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\}$ गणना योग्य है। यह समुच्चय फ़ंक्शन मान तय करने की समस्या को कूटबद्ध करता है।
• प्राकृतिक संख्याओं से प्राकृतिक संख्याओं में एक आंशिक फ़ंक्शन f को देखते हुए, f एक आंशिक संगणनीय फ़ंक्शन है यदि और केवल यदि f का ग्राफ, यानी सभी जोड़े का समुच्चय $\langle x,f(x)\rangle$ ऐसा है कि f(x) परिभाषित है, संगणनीय रूप से गणना योग्य है।

गुण

यदि ए और बी संगणनीय रूप से गणना योग्य समुच्चय हैं तो ए ∩ बी, ए ∪ बी और ए × बी (कैंटर पेयरिंग फ़ंक्शन के साथ एकल प्राकृतिक संख्या में मैप की गई प्राकृतिक संख्याओं की क्रमबद्ध जोड़ी के साथ) संगणनीय रूप से गणना योग्य समुच्चय हैं। आंशिक संगणनीय फ़ंक्शन के तहत एक संगणनीय रूप से गणना योग्य समुच्चय का पूर्वाभास एक संगणनीय रूप से गणना योग्य समुच्चय है।

एक समुच्चय $T$ सह-कम्प्यूटेशनल-गणनीय या सह-सी.ई. कहा जाता है। यदि इसका पूरक (समुच्चय सिद्धांत) $\mathbb {N} \setminus T$ गणना योग्य है। समतुल्य रूप से, एक समुच्चय सह-आर है। अगर और केवल अगर यह स्तर पर है $\Pi _{1}^{0}$ अंकगणितीय पदानुक्रम का। सह-कम्प्यूटेशनल-गणनीय समुच्चय की जटिलता वर्ग को सह-आरई निरूपित किया जाता है।

एक समुच्चय A संगणनीय समुच्चय है यदि और केवल यदि A और A का पूरक दोनों गणना योग्य हैं।

कम्प्यूटेशनल रूप से गणना योग्य समुच्चय के कुछ जोड़े प्रभावी रूप से वियोज्य हैं और कुछ नहीं हैं।

टिप्पणियाँ

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

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

यह भी देखें

• आरई (जटिलता)
• पुनरावर्ती गणना योग्य भाषा
• अंकगणितीय पदानुक्रम

संदर्भ

• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1.
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7.
• Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.