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

"Enumerable set" redirects here. For the set-theoretic concept, see Countable set.

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

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

या, समकक्ष,

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

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

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

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

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

समतुल्य फॉर्मूलेशन

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

सेमीसाइडिबिलिटी :

* समुच्चय 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}}$$

गणनीयता :

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

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

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

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

* पूर्णांक गुणांक और चर 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).$$

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

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

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.