चैतीन का स्थिरांक

"ओमेगा संख्या" redirects here. For other uses, see ओमेगा (बहुविकल्पी) § गणित.

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

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

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

उदाहरण

मान लीजिए कि P केवल 5 वैध प्रोग्रामों वाली प्रोग्रामिंग भाषा है। C++ में उनका अनुवाद इस प्रकार है:

P	C++	Halts?
1	#include <iostream> using namespace std; int main() { cout << "Hello, World!"; }	Y
2	#include <iostream> using namespace std; int main() { for (int i = 0; i < 10; i++) { cout << i << endl; } }	Y
3	#include <iostream> using namespace std; int main() { while (true) { cout << "Whee!" << endl; } }	N
4	#include <iostream> using namespace std; int main() { int i = 0; while (true) { cout << i << endl; i++; if (i == 10) { break; } } }	Y
5	#include <iostream> using namespace std; void f() { cout << "f()" << endl; f(); } int main() { f(); }	N

इस स्थिति में 3 प्रोग्राम रुकते हैं और 2 नहीं, इसलिए इस प्रोग्रामिंग भाषा के लिए चैटिन स्थिरांक $\Omega _{P}={\frac {3}{5}}=0.6$ है

पृष्ठभूमि

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

मान लीजिए कि F आंशिक फलन है जो तर्क, सीमित बाइनरी स्ट्रिंग लेता है, और संभवतः आउटपुट के रूप में बाइनरी स्ट्रिंग लौटाता है। फलन F को संगणनीय कार्य कहा जाता है यदि कोई ट्यूरिंग मशीन है जो इसकी गणना करती है (इस अर्थ में कि किसी भी परिमित बाइनरी स्ट्रिंग x और y, F(x) = y के लिए यदि और केवल यदि इनपुट x दिए जाने पर ट्यूरिंग मशीन अपने टेप पर y के साथ रुकती है)।

फलन F को कम्प्यूटेशनल सार्वभौमिकता कहा जाता है यदि निम्नलिखित प्रोपर्टी धारण करती है | एकल वैरीएबल के प्रत्येक गणनीय फलन F के लिए स्ट्रिंग w है जैसे कि सभी x के लिए, F(w x) = F(x); यहां w x दो तारों w और x के संयोजन को दर्शाता है। इसका कारण यह है कि F का उपयोग वैरीएबल के किसी भी गणनीय फलन को अनुकरण करने के लिए किया जा सकता है। अनौपचारिक रूप से, w गणनीय फलन f के लिए स्क्रिप्ट का प्रतिनिधित्व करता है, और F इंटरप्रेटर का प्रतिनिधित्व करता है जो स्क्रिप्ट को उसके इनपुट के उपसर्ग के रूप में पार्स करता है और फिर इसे शेष इनपुट पर निष्पादित करता है।

F के किसी फलन का डोमेन सभी इनपुट p का समुच्चय है जिस पर इसे परिभाषित किया गया है। F के लिए जो सार्वभौमिक हैं, ऐसे p को सामान्यतः प्रोग्राम भाग और डेटा भाग के संयोजन के रूप में और फलन F के लिए एकल प्रोग्राम के रूप में देखा जा सकता है।

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

किसी भी सार्वभौमिक गणनीय फलन का डोमेन गणनीय समुच्चय है, किन्तु कभी भी गणनीय समुच्चय नहीं है। इस प्रकार डोमेन सदैव हॉल्टिंग समस्या के लिए ट्यूरिंग डिग्री वाला होता है।

परिभाषा

मान लीजिए P_F उपसर्ग-मुक्त सार्वभौमिक संगणनीय फलन F का डोमेन है। स्थिरांक Ω_F फिर परिभाषित किया गया है

$\Omega _{F}=\sum _{p\in P_{F}}2^{-|p|}$,

जहाँ $\left|p\right|$ स्ट्रिंग p की लंबाई को दर्शाता है। यह श्रृंखला (गणित) है जिसमें F के डोमेन में प्रत्येक p के लिए सारांश है। इसमें आवश्यकता है कि डोमेन उपसर्ग-मुक्त हो, और क्राफ्ट की असमानता के साथ, यह सुनिश्चित करता है कि यह योग 0 और 1 के मध्य वास्तविक संख्या में परिवर्तित हो जाता है। यदि F संदर्भ से स्पष्ट है तब Ω_F केवल Ω को दर्शाया जा सकता है, चूँकि विभिन्न उपसर्ग-मुक्त सार्वभौमिक गणनीय फलन Ω के विभिन्न मानों को उत्पन्न कर देते हैं।

हाल्टिंग समस्या से संबंध

Ω के पहले N बिट्स को जानने के पश्चात्, कोई N तक के आकार के सभी प्रोग्रामो के लिए हॉल्टिंग समस्या की गणना कर सकता है। मान लें कि प्रोग्राम p जिसके लिए हॉल्टिंग समस्या हल की जानी है वह N बिट लंबा है। डोवेटेलिंग (कंप्यूटर विज्ञान) फैशन में, सभी लंबाई के सभी प्रोग्राम तब तक चलाए जाते हैं, जब तक कि इन पहले N बिट्स से मेल खाने के लिए संयुक्त रूप से पर्याप्त प्रायिकता का योगदान करने के लिए पर्याप्त मात्रा में रुकना संवृत नही हो जाता है। यदि प्रोग्राम p अभी तक नहीं रुका है, तब यह कभी नहीं रुकता है, क्योंकि हाल्टिंग प्रायिकता में इसका योगदान पहले N बिट्स को प्रभावित करता है। इस प्रकार, p के लिए हाल्टिंग समस्या हल हो जाती है।

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

प्रायिकता के रूप में व्याख्या

कैंटर समिष्ट 0s और 1s के सभी अनंत अनुक्रमों का संग्रह है। कैंटर समिष्ट पर सामान्य प्रायिकता माप के अनुसार कैंटर समिष्ट के निश्चित उपसमुच्चय के माप सिद्धांत के रूप में हाल्टिंग प्रायिकता की व्याख्या की जा सकती है। यह इस व्याख्या से है कि हाल्टिंग प्रायिकता अपना नाम लेती हैं।

कैंटर समिष्ट पर प्रायिकता माप, जिसे कभी-कभी फेयर-कॉइन माप भी कहा जाता है, जिसको परिभाषित किया गया है जिससे किसी भी बाइनरी स्ट्रिंग x के लिए x से प्रारंभ होने वाले अनुक्रमों के समुच्चय का माप 2^−|x| होता है. इसका तात्पर्य यह है कि प्रत्येक प्राकृतिक संख्या n के लिए, कैंटर समिष्ट में अनुक्रमों का समुच्चय f (n) = 1 का माप 1/2 है, और अनुक्रमों का समुच्चय जिसका nवाँ अवयव 0 है, जिसका माप 1/2 भी है।

मान लीजिए कि F उपसर्ग-मुक्त सार्वभौमिक संगणनीय फलन है। F के डोमेन P में बाइनरी स्ट्रिंग्स का अनंत समुच्चय होता है

$P=\{p_{1},p_{2},\ldots \}$.

इनमें से प्रत्येक तार p_i उपसमुच्चय S_i निर्धारित करता है कैंटर समिष्ट का समुच्चय s_i कैंटर समिष्ट में p_i से प्रारंभ होने वाले सभी अनुक्रम सम्मिलित हैं. यह समुच्चय असंयुक्त हैं क्योंकि P उपसर्ग-मुक्त समुच्चय है।

$\sum _{p\in P}2^{-|p|}$

समुच्चय के माप का प्रतिनिधित्व करता है

$\bigcup _{i\in \mathbb {N} }S_{i}$.

इस प्रकार, Ω_F इस प्रायिकता का प्रतिनिधित्व करता है कि 0s और 1s का यादृच्छिक रूप से चयनित अनंत अनुक्रम बिट स्ट्रिंग (कुछ सीमित लंबाई की) इससे प्रारंभ होता है जो F के डोमेन में है। यही कारण है कि Ω_F हाल्टिंग प्रायिकता कहलाती है |

गुण

प्रत्येक चैतीन स्थिरांक Ω में निम्नलिखित गुण होते हैं |

• यह एल्गोरिथम यादृच्छिकता है (जिसे मार्टिन-लोफ यादृच्छिक या 1-यादृच्छिक भी कहा जाता है)। इसका कारण यह है कि Ω के पहले n बिट्स को आउटपुट करने वाला सबसे छोटा प्रोग्राम कम से कम n - O(1) आकार का होना चाहिए। ऐसा इसलिए है, क्योंकि गोल्डबैक उदाहरण की तरह, वह n बिट्स हमें यह पता लगाने में सक्षम बनाते हैं कि अधिकतम n लंबाई वाले सभी प्रोग्रामों में से कौन सा प्रोग्राम रुकता है।
• इसके परिणामस्वरूप, यह सामान्य संख्या है, जिसका अर्थ है कि इसके अंक समान रूप से वितरित हैं जैसे कि वह उचित सिक्का उछालकर उत्पन्न हुए हों।
• यह गणनीय संख्या नहीं है | ऐसा कोई गणनीय फलन नहीं है जो इसके द्विआधारी विस्तार की गणना करता है, जैसा कि नीचे वैरीएबल्चा की गई है।
• परिमेय संख्याओं q का समुच्चय इस प्रकार है कि q < Ω गणनीय समुच्चय है | ऐसी प्रोपर्टी वाली वास्तविक संख्या को लेफ्ट-सी.ई. कहा जाता है। पुनरावर्तन सिद्धांत में वास्तविक संख्या है |
• परिमेय संख्याओं का समुच्चय q इस प्रकार है कि q > Ω गणनीय नहीं है। (कारण: इस प्रोपर्टी के साथ प्रत्येक बाएं-सी.ई. वास्तविक गणनीय है, जो Ω नहीं है।)
• Ω अंकगणितीय संख्या है |
• यह ट्यूरिंग हाल्टिंग समस्या के सामान्य है और इस प्रकार अंकगणितीय पदानुक्रम के स्तर $\Delta _{2}^{0}$ पर है।

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

अगणनीयता

वास्तविक संख्या को गणनीय कहा जाता है यदि कोई एल्गोरिदम है, जो n दिया गया है, संख्या के पहले n अंक लौटाता है। यह प्रोग्राम के अस्तित्व के सामान है जो वास्तविक संख्या के अंकों की गणना करता है।

हाल्टिंग कोई प्रायिकता गणनीय नहीं है। इस तथ्य का प्रमाण एल्गोरिदम पर निर्भर करता है, जो Ω के पहले n अंक दिए जाने पर, n तक की लंबाई के प्रोग्रामो के लिए ट्यूरिंग की हाल्टिंग समस्या को हल करता है। चूंकि हाल्टिंग समस्या अनिर्णीत समस्या है, इसलिए Ω की गणना नहीं की जा सकती है।

एल्गोरिथम निम्नानुसार आगे बढ़ता है। इस प्रकार Ω और ak ≤ n के पहले n अंकों को देखते हुए, एल्गोरिथ्म F के डोमेन की गणना करता है जब तक कि डोमेन के पर्याप्त अवयव नहीं मिल जाते हैं जिससे वह जिस प्रायिकता का प्रतिनिधित्व करते हैं वह 2^−(k+1) के अन्दर होता है इस प्रकार जिसका Ω बिंदु के पश्चात्, लंबाई k का कोई भी अतिरिक्त प्रोग्राम डोमेन में नहीं हो सकता है, क्योंकि इनमें से प्रत्येक 2^−k जोड़ देता है जो असंभव है। इस प्रकार डोमेन में लंबाई k की स्ट्रिंग्स का समुच्चय वास्तव में पहले से ही गणना की गई ऐसी स्ट्रिंग्स का समुच्चय है।

एल्गोरिथम यादृच्छिकता

वास्तविक संख्या यादृच्छिक होती है यदि वास्तविक संख्या का प्रतिनिधित्व करने वाला द्विआधारी अनुक्रम एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम है। कैलुडे, हर्टलिंग, खुसैनोव और वांग ने दिखाया कि पुनरावर्ती रूप से गणनीय वास्तविक संख्या एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम है यदि और केवल यदि यह चैतिन की Ω संख्या है।

प्रायिकताओं को रोकने के लिए अपूर्णता प्रमेय

Main article: चैतिन की अपूर्णता प्रमेय

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

सुपर ओमेगा

जैसा कि ऊपर उल्लेख किया गया है, ग्रेगरी चैटिन के स्थिरांक Ω के पहले n बिट्स इस अर्थ में यादृच्छिक या असंपीड़ित हैं कि हम n-O(1) बिट्स से कम वाले हॉल्टिंग एल्गोरिदम द्वारा उनकी गणना नहीं कर सकते हैं। चूँकि , छोटे किन्तु कभी न रुकने वाले एल्गोरिदम पर विचार करें जो सभी संभावित प्रोग्रामो को व्यवस्थित रूप से सूचीबद्ध करता और चलाता है | जब भी यह उनमें से रुकता है तब इसकी प्रायिकता आउटपुट में जुड़ जाती है | यह (शून्य से प्रारंभ) होता हैं। इस प्रकार सीमित समय के पश्चात् आउटपुट के पहले n बिट्स कभी नहीं परिवर्तित होते है (इससे कोई प्रभाव नहीं पड़ता कि यह समय स्वयं हॉल्टिंग प्रोग्राम द्वारा गणनीय नहीं है)। जिससे छोटा नॉन-हॉल्टिंग एल्गोरिदम है जिसका आउटपुट (परिमित समय के पश्चात्) Ω के पहले N बिट्स पर परिवर्तित होता है। दूसरे शब्दों में, Ω के गणनीय प्रथम n बिट्स इस अर्थ में अत्यधिक संपीड़ित हैं कि वह बहुत ही छोटे एल्गोरिथ्म द्वारा सीमा-गणनीय हैं | वह गणना एल्गोरिदम के समुच्चय के संबंध में यादृच्छिक नहीं हैं। जुरगेन श्मिडहुबर (2000) ने सीमा-गणनीय सुपर Ω का निर्माण किया था, जो अर्थ में मूल सीमा-गणनीय Ω की तुलना में बहुत अधिक यादृच्छिक है, क्योंकि कोई भी किसी भी गणना करने वाले गैर-रोक एल्गोरिथ्म द्वारा सुपर Ω को महत्वपूर्ण रूप से संपीड़ित नहीं कर सकता है।

वैकल्पिक सुपर Ω के लिए, उपसर्ग-मुक्त कोड या उपसर्ग-मुक्त यूनिवर्सल ट्यूरिंग मशीन (UTM) की सार्वभौमिकता प्रायिकता अर्थात्, प्रायिकता यह है कि यह तब भी सार्वभौमिक रहता है जब इसका प्रत्येक इनपुट (बाइनरी स्ट्रिंग के रूप में) यादृच्छिक बाइनरी स्ट्रिंग द्वारा उपसर्ग किया जाता है जिसको ऑरेकल वाली मशीन की हाल्टिंग समस्या के तीसरे पुनरावृत्ति के रूप में देखा जा सकता है (अर्थात, $O^{(3)}$ट्यूरिंग जंप का उपयोग करता हैं)।

यह भी देखें

• अपूर्णता प्रमेय
• कोलमोगोरोव सम्मिश्रता

संदर्भ

उद्धृत कार्य

• Calude, Cristian S. (2002). सूचना और यादृच्छिकता: एक एल्गोरिथम परिप्रेक्ष्य (second ed.). Springer. ISBN 3-540-43466-6.
• Calude, Cristian S.; Dinneen, Michael J.; Shu, Chi-Kou (2001). यादृच्छिकता की झलक की गणना (PDF). arXiv:nlin/0112022. Bibcode:2001nlin.....12022C. Archived (PDF) from the original on 2004-12-05.
• Downey, R.; Hirschfeldt, D. (2010). एल्गोरिथम यादृच्छिकता और जटिलता. Springer-Verlag.
• Li, Ming; Vitányi, Paul (1997). कोलमोगोरोव जटिलता और उसके अनुप्रयोगों का एक परिचय. Springer. परिचय अध्याय पूर्ण-पाठ।
• Schmidhuber, Jürgen (2002). "सामान्यीकृत कोलमोगोरोव जटिलताओं के पदानुक्रम और सीमा में गणना योग्य अनगिनत सार्वभौमिक उपाय". International Journal of Foundations of Computer Science. 13 (4): 587–612. doi:10.1142/S0129054102001291. प्रीप्रिंट: हर चीज़ के एल्गोरिथम सिद्धांत (arXiv: क्वांट-ph/ 0011122)

बाहरी संबंध

• Aspects of Chaitin's Omega Survey article discussing recent advances in the study of Chaitin's Omega.
• Omega and why maths has no TOEs article based on one written by Gregory Chaitin which appeared in the August 2004 edition of Mathematics Today, on the occasion of the 50th anniversary of Alan Turing's death.
• The Limits of Reason, Gregory Chaitin, originally appeared in Scientific American, March 2006.
• Limit-computable Super Omega more random than Omega and generalizations of algorithmic information, by Jürgen Schmidhuber