चैतीन का स्थिरांक: Difference between revisions

Revision as of 11:41, 2 August 2023

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

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

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

उदाहरण

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


#include <iostream>
using namespace std;

int main() {
	cout << "Hello, World!";
}
#include <iostream>
using namespace std;

int main() {
	for (int i = 0; i < 10; i++) {
		cout << i << endl;
	}
}
#include <iostream>
using namespace std;

int main() {
	while (true) {
		cout << "Whee!" << endl;
	}
}
#include <iostream>
using namespace std;

int main() {
	int i = 0;
	while (true) {
		cout << i << endl;
		i++;
		if (i == 10) {
			break;
		}
	}
}
#include <iostream>
using namespace std;

void f() {
	cout << "f()" << endl;
	f();
}

int main() {
	f();
}

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

पृष्ठभूमि

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

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

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

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

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

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

परिभाषा

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

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

,

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

रुकने की समस्या से संबंध

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

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

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

कैंटर स्पेस 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 \}

.

इनमें से प्रत्येक तार पी_i उपसमुच्चय S निर्धारित करता है_i कैंटर स्थान का; सेट एस_i कैंटर स्पेस में पी से शुरू होने वाले सभी अनुक्रम शामिल हैं_i. ये समुच्चय असंयुक्त हैं क्योंकि P उपसर्ग-मुक्त समुच्चय है। योग

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

सेट के माप का प्रतिनिधित्व करता है

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

.

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

गुण

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

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

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

अगणनीयता

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

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

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

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

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

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

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

सुपर ओमेगा

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

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

यह भी देखें

संदर्भ

↑ mathworld.wolfram.com, Chaitin's Constant. Retrieved 28 May 2012
↑ Calude, Cristian S.; Dinneen, Michael J.; Shu, Chi-Kou (2002). "यादृच्छिकता की झलक की गणना". Experimental Mathematics. 11 (3): 361–370. arXiv:nlin/0112022. doi:10.1080/10586458.2002.10504481. S2CID 8796343.
↑ Downey & Hirschfeldt 2010, Theorem 6.1.3.
↑ Downey & Hirschfeldt 2010, Theorem 5.1.11.
↑ ^5.0 ^5.1 Downey & Hirschfeldt 2010, p. 405.
↑ Downey & Hirschfeldt 2010, pp. 228–229.
↑ Calude, Cristian S.; Hertling, Peter H.; Khoussainov, Bakhadyr; Wang, Yongge (1998), "Recursively Enumerable Reals and Chaitin Ω numbers" (PDF), STACS 98, Springer Berlin Heidelberg, vol. 1373, pp. 596–606, Bibcode:1998LNCS.1373..596C, doi:10.1007/bfb0028594, ISBN 978-3-540-64230-5, S2CID 5493426, archived (PDF) from the original on 2004-01-19, retrieved 2022-03-20
↑ Barmpalias, G. and Dowe D.L. (2012). "उपसर्ग-मुक्त मशीन की सार्वभौमिकता की संभावना". Philosophical Transactions of the Royal Society A. 370 (1): 3488–3511 (Theme Issue 'The foundations of computation, physics and mentality: the Turing legacy' compiled and edited by Barry Cooper and Samson Abramsky). Bibcode:2012RSPTA.370.3488B. doi:10.1098/rsta.2011.0319. PMID 22711870.

उद्धृत कार्य

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

[2] ttps://ideone.com/nef7Wl

[3] ttps://ideone.com/9C8E4X

[4] ttps://ideone.com/pZsRfo

[5] ttps://ideone.com/sHZzHp

[6] ttps://ideone.com/gNG1jS

[1] thworld.wolfram.com, Chaitin's Constant. Retrieved 28 May 2012

[7] Calude, Cristian S.; Dinneen, Michael J.; Shu, Chi-Kou (2002). "यादृच्छिकता की झलक की गणना". Experimental Mathematics. 11 (3): 361–370. arXiv:nlin/0112022. doi:10.1080/10586458.2002.10504481. S2CID 8796343.

[FOOTNOTEDowneyHirschfeldt2010Theorem_6.1.3-8] Downey & Hirschfeldt 2010, Theorem 6.1.3.

[FOOTNOTEDowneyHirschfeldt2010Theorem_5.1.11-9] Downey & Hirschfeldt 2010, Theorem 5.1.11.

[FOOTNOTEDowneyHirschfeldt2010405-10] 5.0 ^5.1 Downey & Hirschfeldt 2010, p. 405.

[FOOTNOTEDowneyHirschfeldt2010228–229-11] Downey & Hirschfeldt 2010, pp. 228–229.

[12] Calude, Cristian S.; Hertling, Peter H.; Khoussainov, Bakhadyr; Wang, Yongge (1998), "Recursively Enumerable Reals and Chaitin Ω numbers" (PDF), STACS 98, Springer Berlin Heidelberg, vol. 1373, pp. 596–606, Bibcode:1998LNCS.1373..596C, doi:10.1007/bfb0028594, ISBN 978-3-540-64230-5, S2CID 5493426, archived (PDF) from the original on 2004-01-19, retrieved 2022-03-20

[13] Barmpalias, G. and Dowe D.L. (2012). "उपसर्ग-मुक्त मशीन की सार्वभौमिकता की संभावना". Philosophical Transactions of the Royal Society A. 370 (1): 3488–3511 (Theme Issue 'The foundations of computation, physics and mentality: the Turing legacy' compiled and edited by Barry Cooper and Samson Abramsky). Bibcode:2012RSPTA.370.3488B. doi:10.1098/rsta.2011.0319. PMID 22711870.

[1]

[program 1]

[program 2]

[program 3]

[program 4]

[program 5]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
 {{Short description|Halting probability of  a random computer program}}
 {{redirect|Omega number||Omega (disambiguation)#Mathematics}}
-{{Use dmy dates|date=December 2020}}
-{{More footnotes|date=November 2011}}
-[[एल्गोरिथम सूचना सिद्धांत]] के [[कंप्यूटर विज्ञान]] उपक्षेत्र में, एक चैतिन स्थिरांक (चैतिन ओमेगा संख्या)<ref>[[mathworld.wolfram.com]], [http://mathworld.wolfram.com/ChaitinsConstant.html Chaitin's Constant]. Retrieved 28 May 2012</ref> या रुकने की [[संभावना]] एक [[वास्तविक संख्या]] है, जो अनौपचारिक रूप से, इस संभावना का प्रतिनिधित्व करती है कि एक यादृच्छिक रूप से निर्मित कार्यक्रम रुक जाएगा। ये संख्याएँ [[ग्रेगरी चैटिन]] के कारण एक निर्माण से बनी हैं।
-हालाँकि रुकने की अनंत संभावनाएँ हैं, एन्कोडिंग प्रोग्राम की प्रत्येक विधि के लिए एक, उन्हें संदर्भित करने के लिए अक्षर Ω का उपयोग करना आम बात है जैसे कि केवल एक ही हो। क्योंकि Ω उपयोग किए गए प्रोग्राम एन्कोडिंग पर निर्भर करता है, किसी विशिष्ट एन्कोडिंग का संदर्भ न देते हुए इसे कभी-कभी चैतिन का निर्माण कहा जाता है।
-प्रत्येक रुकने की संभावना एक [[सामान्य संख्या]] और ट्रान्सेंडैंटल संख्या वास्तविक संख्या है जो [[गणना योग्य संख्या]] नहीं है, जिसका अर्थ है कि इसके अंकों की गणना करने के लिए कोई [[कलन विधि]] नहीं है। प्रत्येक रुकने की संभावना एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम है|मार्टिन-लोफ यादृच्छिक, जिसका अर्थ है कि कोई एल्गोरिदम भी नहीं है जो विश्वसनीय रूप से इसके अंकों का अनुमान लगा सके।
+[[एल्गोरिथम सूचना सिद्धांत]] के [[कंप्यूटर विज्ञान]] उपक्षेत्र में, चैतिन स्थिरांक (चैतिन ओमेगा संख्या)<ref>[[mathworld.wolfram.com]], [http://mathworld.wolfram.com/ChaitinsConstant.html Chaitin's Constant]. Retrieved 28 May 2012</ref> या रुकने की [[संभावना]] [[वास्तविक संख्या]] है, जो अनौपचारिक रूप से, इस संभावना का प्रतिनिधित्व करती है कि यादृच्छिक रूप से निर्मित कार्यक्रम रुक जाएगा। ये संख्याएँ [[ग्रेगरी चैटिन]] के कारण निर्माण से बनी हैं।
+हालाँकि रुकने की अनंत संभावनाएँ हैं, एन्कोडिंग प्रोग्राम की प्रत्येक विधि के लिए एक, उन्हें संदर्भित करने के लिए अक्षर Ω का उपयोग करना आम बात है जैसे कि केवल ही हो। क्योंकि Ω उपयोग किए गए प्रोग्राम एन्कोडिंग पर निर्भर करता है, किसी विशिष्ट एन्कोडिंग का संदर्भ न देते हुए इसे कभी-कभी चैतिन का निर्माण कहा जाता है।
+प्रत्येक रुकने की संभावना [[सामान्य संख्या]] और ट्रान्सेंडैंटल संख्या वास्तविक संख्या है जो [[गणना योग्य संख्या]] नहीं है, जिसका अर्थ है कि इसके अंकों की गणना करने के लिए कोई [[कलन विधि]] नहीं है। प्रत्येक रुकने की संभावना एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम है|मार्टिन-लोफ यादृच्छिक, जिसका अर्थ है कि कोई एल्गोरिदम भी नहीं है जो विश्वसनीय रूप से इसके अंकों का अनुमान लगा सके।
 == उदाहरण ==
-मान लीजिए कि P केवल 5 वैध प्रोग्रामों वाली एक प्रोग्रामिंग भाषा है। [[C++]] में उनका अनुवाद इस प्रकार है:
+मान लीजिए कि P केवल 5 वैध प्रोग्रामों वाली प्रोग्रामिंग भाषा है। [[C++]] में उनका अनुवाद इस प्रकार है:
 {| class="wikitable"
 ! ''P'' !! C++ !! Halts?
@@ Line 82: / Line 82: @@
 == पृष्ठभूमि ==
-रुकने की संभावना की परिभाषा एक उपसर्ग-मुक्त सार्वभौमिक गणना योग्य फ़ंक्शन के अस्तित्व पर निर्भर करती है। ऐसा फ़ंक्शन, सहज रूप से, एक प्रोग्रामिंग भाषा को इस संपत्ति के साथ दर्शाता है कि किसी भी वैध प्रोग्राम को किसी अन्य वैध प्रोग्राम के उचित विस्तार के रूप में प्राप्त नहीं किया जा सकता है।
+रुकने की संभावना की परिभाषा उपसर्ग-मुक्त सार्वभौमिक गणना योग्य फ़ंक्शन के अस्तित्व पर निर्भर करती है। ऐसा फ़ंक्शन, सहज रूप से, प्रोग्रामिंग भाषा को इस संपत्ति के साथ दर्शाता है कि किसी भी वैध प्रोग्राम को किसी अन्य वैध प्रोग्राम के उचित विस्तार के रूप में प्राप्त नहीं किया जा सकता है।
-मान लीजिए कि ''एफ'' एक आंशिक फ़ंक्शन है जो एक तर्क, एक सीमित बाइनरी स्ट्रिंग लेता है, और संभवतः आउटपुट के रूप में एक बाइनरी स्ट्रिंग लौटाता है। फ़ंक्शन ''F'' को [[संगणनीय कार्य]] कहा जाता है यदि कोई [[ट्यूरिंग मशीन]] है जो इसकी गणना करती है (इस अर्थ में कि किसी भी परिमित बाइनरी स्ट्रिंग ''x'' और ''y'', ''F(x) = y'' के लिए यदि और केवल यदि इनपुट ''x'' दिए जाने पर ट्यूरिंग मशीन अपने टेप पर ''y'' के साथ रुकती है)।
+मान लीजिए कि ''एफ'' आंशिक फ़ंक्शन है जो तर्क, सीमित बाइनरी स्ट्रिंग लेता है, और संभवतः आउटपुट के रूप में बाइनरी स्ट्रिंग लौटाता है। फ़ंक्शन ''F'' को [[संगणनीय कार्य]] कहा जाता है यदि कोई [[ट्यूरिंग मशीन]] है जो इसकी गणना करती है (इस अर्थ में कि किसी भी परिमित बाइनरी स्ट्रिंग ''x'' और ''y'', ''F(x) = y'' के लिए यदि और केवल यदि इनपुट ''x'' दिए जाने पर ट्यूरिंग मशीन अपने टेप पर ''y'' के साथ रुकती है)।
-फ़ंक्शन ''एफ'' को [[कम्प्यूटेशनल सार्वभौमिकता]] कहा जाता है यदि निम्नलिखित संपत्ति धारण करती है: एक एकल चर के प्रत्येक गणना योग्य फ़ंक्शन ''एफ'' के लिए एक स्ट्रिंग ''डब्ल्यू'' है जैसे कि सभी ''एक्स'' के लिए, ''एफ''(''डब्ल्यू'' ''एक्स'') = ''एफ''(''एक्स''); यहां ''w'' ''x'' दो तारों ''w'' और ''x'' के संयोजन को दर्शाता है। इसका मतलब यह है कि ''एफ'' का उपयोग एक चर के किसी भी गणना योग्य फ़ंक्शन को अनुकरण करने के लिए किया जा सकता है। अनौपचारिक रूप से, ''w'' गणना योग्य फ़ंक्शन ''f'' के लिए एक स्क्रिप्ट का प्रतिनिधित्व करता है, और ''F'' एक दुभाषिया का प्रतिनिधित्व करता है जो स्क्रिप्ट को उसके इनपुट के उपसर्ग के रूप में पार्स करता है और फिर इसे शेष इनपुट पर निष्पादित करता है।
+फ़ंक्शन ''एफ'' को [[कम्प्यूटेशनल सार्वभौमिकता]] कहा जाता है यदि निम्नलिखित संपत्ति धारण करती है: एकल चर के प्रत्येक गणना योग्य फ़ंक्शन ''एफ'' के लिए स्ट्रिंग ''डब्ल्यू'' है जैसे कि सभी ''एक्स'' के लिए, ''एफ''(''डब्ल्यू'' ''एक्स'') = ''एफ''(''एक्स''); यहां ''w'' ''x'' दो तारों ''w'' और ''x'' के संयोजन को दर्शाता है। इसका मतलब यह है कि ''एफ'' का उपयोग चर के किसी भी गणना योग्य फ़ंक्शन को अनुकरण करने के लिए किया जा सकता है। अनौपचारिक रूप से, ''w'' गणना योग्य फ़ंक्शन ''f'' के लिए स्क्रिप्ट का प्रतिनिधित्व करता है, और ''F'' दुभाषिया का प्रतिनिधित्व करता है जो स्क्रिप्ट को उसके इनपुट के उपसर्ग के रूप में पार्स करता है और फिर इसे शेष इनपुट पर निष्पादित करता है।
 ''F'' के [[किसी फ़ंक्शन का डोमेन]] सभी इनपुट ''p'' का सेट है जिस पर इसे परिभाषित किया गया है। ''एफ'' के लिए जो सार्वभौमिक हैं, ऐसे ''पी'' को आम तौर पर प्रोग्राम भाग और डेटा भाग के संयोजन के रूप में और फ़ंक्शन ''एफ'' के लिए एकल प्रोग्राम के रूप में देखा जा सकता है।
-फ़ंक्शन ''F'' को उपसर्ग-मुक्त कहा जाता है यदि इसके डोमेन में ''p'', ''p'' कोई दो तत्व नहीं हैं जैसे कि ''p'' ''p'' का उचित विस्तार है। इसे इस प्रकार दोहराया जा सकता है: ''एफ'' का डोमेन परिमित बाइनरी स्ट्रिंग्स के सेट पर एक [[उपसर्ग-मुक्त कोड]] (तात्कालिक कोड) है। उपसर्ग-मुक्तता को लागू करने का एक सरल तरीका उन मशीनों का उपयोग करना है जिनके इनपुट का साधन एक बाइनरी स्ट्रीम है जिससे बिट्स को एक समय में पढ़ा जा सकता है। धारा का कोई अंत मार्कर नहीं है; इनपुट का अंत तब निर्धारित होता है जब सार्वभौमिक मशीन अधिक बिट्स को पढ़ना बंद करने का निर्णय लेती है, और शेष बिट्स को स्वीकृत स्ट्रिंग का हिस्सा नहीं माना जाता है। यहां, अंतिम पैराग्राफ में उल्लिखित कार्यक्रम की दो अवधारणाओं के बीच अंतर स्पष्ट हो जाता है; एक को कुछ व्याकरण द्वारा आसानी से पहचाना जा सकता है, जबकि दूसरे को पहचानने के लिए मनमानी गणना की आवश्यकता होती है।
+फ़ंक्शन ''F'' को उपसर्ग-मुक्त कहा जाता है यदि इसके डोमेन में ''p'', ''p'' कोई दो तत्व नहीं हैं जैसे कि ''p'' ''p'' का उचित विस्तार है। इसे इस प्रकार दोहराया जा सकता है: ''एफ'' का डोमेन परिमित बाइनरी स्ट्रिंग्स के सेट पर [[उपसर्ग-मुक्त कोड]] (तात्कालिक कोड) है। उपसर्ग-मुक्तता को लागू करने का सरल तरीका उन मशीनों का उपयोग करना है जिनके इनपुट का साधन बाइनरी स्ट्रीम है जिससे बिट्स को समय में पढ़ा जा सकता है। धारा का कोई अंत मार्कर नहीं है; इनपुट का अंत तब निर्धारित होता है जब सार्वभौमिक मशीन अधिक बिट्स को पढ़ना बंद करने का निर्णय लेती है, और शेष बिट्स को स्वीकृत स्ट्रिंग का हिस्सा नहीं माना जाता है। यहां, अंतिम पैराग्राफ में उल्लिखित कार्यक्रम की दो अवधारणाओं के बीच अंतर स्पष्ट हो जाता है; को कुछ व्याकरण द्वारा आसानी से पहचाना जा सकता है, जबकि दूसरे को पहचानने के लिए मनमानी गणना की आवश्यकता होती है।
-किसी भी सार्वभौमिक गणना योग्य फ़ंक्शन का डोमेन एक [[गणना योग्य सेट]] है, लेकिन कभी भी गणना योग्य सेट नहीं है। डोमेन हमेशा हॉल्टिंग समस्या के लिए [[ट्यूरिंग डिग्री]] वाला होता है।
+किसी भी सार्वभौमिक गणना योग्य फ़ंक्शन का डोमेन [[गणना योग्य सेट]] है, लेकिन कभी भी गणना योग्य सेट नहीं है। डोमेन हमेशा हॉल्टिंग समस्या के लिए [[ट्यूरिंग डिग्री]] वाला होता है।
 == परिभाषा ==
-चलो पी<sub>F</sub> एक उपसर्ग-मुक्त सार्वभौमिक संगणनीय फ़ंक्शन F का डोमेन बनें। स्थिरांक Ω<sub>F</sub> फिर परिभाषित किया गया है
+चलो पी<sub>F</sub> उपसर्ग-मुक्त सार्वभौमिक संगणनीय फ़ंक्शन F का डोमेन बनें। स्थिरांक Ω<sub>F</sub> फिर परिभाषित किया गया है
 :<math>\Omega_F = \sum_{p \in P_F} 2^{-|p|}</math>,
-कहाँ <math>\left|p\right|</math> एक स्ट्रिंग पी की लंबाई को दर्शाता है। यह एक [[श्रृंखला (गणित)]] है जिसमें एफ के डोमेन में प्रत्येक पी के लिए एक सारांश है। आवश्यकता है कि डोमेन उपसर्ग-मुक्त हो, क्राफ्ट की असमानता के साथ, यह सुनिश्चित करता है कि यह योग 0 और 1 के बीच एक वास्तविक संख्या में परिवर्तित हो जाता है। यदि एफ संदर्भ से स्पष्ट है तो Ω<sub>F</sub> केवल Ω को दर्शाया जा सकता है, हालांकि विभिन्न उपसर्ग-मुक्त सार्वभौमिक गणना योग्य फ़ंक्शन Ω के विभिन्न मानों को जन्म देते हैं।
+कहाँ <math>\left|p\right|</math> स्ट्रिंग पी की लंबाई को दर्शाता है। यह [[श्रृंखला (गणित)]] है जिसमें एफ के डोमेन में प्रत्येक पी के लिए सारांश है। आवश्यकता है कि डोमेन उपसर्ग-मुक्त हो, क्राफ्ट की असमानता के साथ, यह सुनिश्चित करता है कि यह योग 0 और 1 के बीच वास्तविक संख्या में परिवर्तित हो जाता है। यदि एफ संदर्भ से स्पष्ट है तो Ω<sub>F</sub> केवल Ω को दर्शाया जा सकता है, हालांकि विभिन्न उपसर्ग-मुक्त सार्वभौमिक गणना योग्य फ़ंक्शन Ω के विभिन्न मानों को जन्म देते हैं।
 ==रुकने की समस्या से संबंध==
@@ Line 105: / Line 105: @@
 == संभाव्यता के रूप में व्याख्या ==
-[[कैंटर स्पेस]] 0s और 1s के सभी अनंत अनुक्रमों का संग्रह है। कैंटर स्पेस पर सामान्य [[संभाव्यता माप]] के तहत कैंटर स्पेस के एक निश्चित उपसमुच्चय के [[माप सिद्धांत]] के रूप में एक रुकने की संभावना की व्याख्या की जा सकती है। यह इस व्याख्या से है कि रुकने की संभावनाएँ अपना नाम लेती हैं।
+[[कैंटर स्पेस]] 0s और 1s के सभी अनंत अनुक्रमों का संग्रह है। कैंटर स्पेस पर सामान्य [[संभाव्यता माप]] के तहत कैंटर स्पेस के निश्चित उपसमुच्चय के [[माप सिद्धांत]] के रूप में रुकने की संभावना की व्याख्या की जा सकती है। यह इस व्याख्या से है कि रुकने की संभावनाएँ अपना नाम लेती हैं।
 कैंटर स्पेस पर संभाव्यता माप, जिसे कभी-कभी फेयर-कॉइन माप भी कहा जाता है, को परिभाषित किया गया है ताकि किसी भी बाइनरी स्ट्रिंग x के लिए x से शुरू होने वाले अनुक्रमों के सेट का माप 2 हो<sup>−|x|</sup>. इसका तात्पर्य यह है कि प्रत्येक प्राकृतिक संख्या n के लिए, कैंटर स्पेस में अनुक्रमों का सेट f (n) = 1 का माप 1/2 है, और अनुक्रमों का सेट जिसका nवाँ तत्व 0 है, का माप 1/2 भी है।
-मान लीजिए कि F एक उपसर्ग-मुक्त सार्वभौमिक संगणनीय फलन है। F के डोमेन P में बाइनरी स्ट्रिंग्स का एक अनंत सेट होता है
+मान लीजिए कि F उपसर्ग-मुक्त सार्वभौमिक संगणनीय फलन है। F के डोमेन P में बाइनरी स्ट्रिंग्स का अनंत सेट होता है
 :<math>P = \{p_1,p_2,\ldots\}</math>.
-इनमें से प्रत्येक तार पी<sub>''i''</sub> एक उपसमुच्चय S निर्धारित करता है<sub>''i''</sub> कैंटर स्थान का; सेट एस<sub>''i''</sub> कैंटर स्पेस में पी से शुरू होने वाले सभी अनुक्रम शामिल हैं<sub>''i''</sub>. ये समुच्चय असंयुक्त हैं क्योंकि P एक उपसर्ग-मुक्त समुच्चय है। योग
+इनमें से प्रत्येक तार पी<sub>''i''</sub> उपसमुच्चय S निर्धारित करता है<sub>''i''</sub> कैंटर स्थान का; सेट एस<sub>''i''</sub> कैंटर स्पेस में पी से शुरू होने वाले सभी अनुक्रम शामिल हैं<sub>''i''</sub>. ये समुच्चय असंयुक्त हैं क्योंकि P उपसर्ग-मुक्त समुच्चय है। योग
 :<math>\sum_{p \in P} 2^{-|p|}</math>
 सेट के माप का प्रतिनिधित्व करता है
 :<math>\bigcup_{i \in \mathbb{N}} S_i</math>.
-इस प्रकार, Ω<sub>''F''</sub> इस संभावना का प्रतिनिधित्व करता है कि 0s और 1s का एक यादृच्छिक रूप से चयनित अनंत अनुक्रम एक बिट स्ट्रिंग (कुछ सीमित लंबाई की) से शुरू होता है जो F के डोमेन में है। यही कारण है कि Ω<sub>''F''</sub> रुकने की संभावना कहलाती है.
+इस प्रकार, Ω<sub>''F''</sub> इस संभावना का प्रतिनिधित्व करता है कि 0s और 1s का यादृच्छिक रूप से चयनित अनंत अनुक्रम बिट स्ट्रिंग (कुछ सीमित लंबाई की) से शुरू होता है जो F के डोमेन में है। यही कारण है कि Ω<sub>''F''</sub> रुकने की संभावना कहलाती है.
 == गुण ==
@@ Line 122: / Line 122: @@
 * यह [[एल्गोरिथम यादृच्छिकता]] है (जिसे मार्टिन-लोफ यादृच्छिक या 1-यादृच्छिक भी कहा जाता है)।{{sfn|Downey|Hirschfeldt|2010|loc=Theorem 6.1.3}} इसका मतलब यह है कि Ω के पहले n बिट्स को आउटपुट करने वाला सबसे छोटा प्रोग्राम कम से कम n - O(1) आकार का होना चाहिए। ऐसा इसलिए है, क्योंकि गोल्डबैक उदाहरण की तरह, वे n बिट्स हमें यह पता लगाने में सक्षम बनाते हैं कि अधिकतम n लंबाई वाले सभी प्रोग्रामों में से कौन सा प्रोग्राम रुकता है।
-* परिणामस्वरूप, यह एक सामान्य संख्या है, जिसका अर्थ है कि इसके अंक समान रूप से वितरित हैं जैसे कि वे एक उचित सिक्का उछालकर उत्पन्न हुए हों।
+* परिणामस्वरूप, यह सामान्य संख्या है, जिसका अर्थ है कि इसके अंक समान रूप से वितरित हैं जैसे कि वे उचित सिक्का उछालकर उत्पन्न हुए हों।
-* यह एक गणना योग्य संख्या नहीं है; ऐसा कोई गणना योग्य फ़ंक्शन नहीं है जो इसके द्विआधारी विस्तार की गणना करता हो, जैसा कि नीचे चर्चा की गई है।
+* यह गणना योग्य संख्या नहीं है; ऐसा कोई गणना योग्य फ़ंक्शन नहीं है जो इसके द्विआधारी विस्तार की गणना करता हो, जैसा कि नीचे चर्चा की गई है।
 * परिमेय संख्याओं q का समुच्चय इस प्रकार है कि q < Ω गणना योग्य समुच्चय है;{{sfn|Downey|Hirschfeldt|2010|loc=Theorem 5.1.11}} ऐसी संपत्ति वाली वास्तविक संख्या को लेफ्ट-सी.ई. कहा जाता है। पुनरावर्तन सिद्धांत में वास्तविक संख्या.
 * परिमेय संख्याओं का समुच्चय ''q'' इस प्रकार है कि ''q'' > Ω गणना योग्य नहीं है। (कारण: इस संपत्ति के साथ प्रत्येक बाएं-सी.ई. वास्तविक गणना योग्य है, जो Ω नहीं है।)
-* Ω एक [[अंकगणितीय संख्या]] है.
+* Ω [[अंकगणितीय संख्या]] है.
 * यह रुकने की समस्या के लिए ट्यूरिंग डिग्री है और इस प्रकार स्तर पर है <math>\Delta^0_2</math> [[अंकगणितीय पदानुक्रम]] का.
-रुकने की समस्या के समतुल्य ट्यूरिंग वाला प्रत्येक सेट रुकने की संभावना नहीं है। एक तुल्यता संबंध # तुल्यता संबंधों की तुलना तुल्यता संबंध, सोलोवे तुल्यता, का उपयोग वाम-सी.ई. के बीच रुकने की संभावनाओं को चिह्नित करने के लिए किया जा सकता है। वास्तविक।{{sfn|Downey|Hirschfeldt|2010|p=405}} कोई यह दिखा सकता है कि [0,1] में एक वास्तविक संख्या एक चैतिन स्थिरांक है (अर्थात कुछ उपसर्ग-मुक्त सार्वभौमिक गणना योग्य फ़ंक्शन की रुकने की संभावना) यदि और केवल यदि इसे छोड़ दिया जाए। और एल्गोरिदमिक रूप से यादृच्छिक।{{sfn|Downey|Hirschfeldt|2010|p=405}} Ω कुछ [[निश्चित वास्तविक संख्या]] एल्गोरिदमिक रूप से यादृच्छिक संख्याओं में से एक है और सबसे प्रसिद्ध एल्गोरिदमिक रूप से यादृच्छिक संख्या है, लेकिन यह सभी एल्गोरिदमिक रूप से यादृच्छिक संख्याओं के लिए बिल्कुल भी विशिष्ट नहीं है।{{sfn|Downey|Hirschfeldt|2010|pp=228–229}}
+रुकने की समस्या के समतुल्य ट्यूरिंग वाला प्रत्येक सेट रुकने की संभावना नहीं है। तुल्यता संबंध # तुल्यता संबंधों की तुलना तुल्यता संबंध, सोलोवे तुल्यता, का उपयोग वाम-सी.ई. के बीच रुकने की संभावनाओं को चिह्नित करने के लिए किया जा सकता है। वास्तविक।{{sfn|Downey|Hirschfeldt|2010|p=405}} कोई यह दिखा सकता है कि [0,1] में वास्तविक संख्या चैतिन स्थिरांक है (अर्थात कुछ उपसर्ग-मुक्त सार्वभौमिक गणना योग्य फ़ंक्शन की रुकने की संभावना) यदि और केवल यदि इसे छोड़ दिया जाए। और एल्गोरिदमिक रूप से यादृच्छिक।{{sfn|Downey|Hirschfeldt|2010|p=405}} Ω कुछ [[निश्चित वास्तविक संख्या]] एल्गोरिदमिक रूप से यादृच्छिक संख्याओं में से है और सबसे प्रसिद्ध एल्गोरिदमिक रूप से यादृच्छिक संख्या है, लेकिन यह सभी एल्गोरिदमिक रूप से यादृच्छिक संख्याओं के लिए बिल्कुल भी विशिष्ट नहीं है।{{sfn|Downey|Hirschfeldt|2010|pp=228–229}}
 ==अगणनीयता==
-एक वास्तविक संख्या को गणना योग्य कहा जाता है यदि कोई एल्गोरिदम है, जो n दिया गया है, संख्या के पहले n अंक लौटाता है। यह एक प्रोग्राम के अस्तित्व के बराबर है जो वास्तविक संख्या के अंकों की गणना करता है।
+एक वास्तविक संख्या को गणना योग्य कहा जाता है यदि कोई एल्गोरिदम है, जो n दिया गया है, संख्या के पहले n अंक लौटाता है। यह प्रोग्राम के अस्तित्व के बराबर है जो वास्तविक संख्या के अंकों की गणना करता है।
-रुकने की कोई संभावना गणना योग्य नहीं है। इस तथ्य का प्रमाण एक एल्गोरिदम पर निर्भर करता है, जो Ω के पहले n अंक दिए जाने पर, n तक की लंबाई के कार्यक्रमों के लिए ट्यूरिंग की रुकने की समस्या को हल करता है। चूंकि रुकने की समस्या [[अनिर्णीत समस्या]] है, इसलिए Ω की गणना नहीं की जा सकती।
+रुकने की कोई संभावना गणना योग्य नहीं है। इस तथ्य का प्रमाण एल्गोरिदम पर निर्भर करता है, जो Ω के पहले n अंक दिए जाने पर, n तक की लंबाई के कार्यक्रमों के लिए ट्यूरिंग की रुकने की समस्या को हल करता है। चूंकि रुकने की समस्या [[अनिर्णीत समस्या]] है, इसलिए Ω की गणना नहीं की जा सकती।
 एल्गोरिथम निम्नानुसार आगे बढ़ता है। Ω और ak ≤ n के पहले n अंकों को देखते हुए, एल्गोरिथ्म F के डोमेन की गणना करता है जब तक कि डोमेन के पर्याप्त तत्व नहीं मिल जाते हैं ताकि वे जिस संभावना का प्रतिनिधित्व करते हैं वह 2 के भीतर हो<sup>−(k+1)</sup> का Ω. इस बिंदु के बाद, लंबाई k का कोई भी अतिरिक्त प्रोग्राम डोमेन में नहीं हो सकता है, क्योंकि इनमें से प्रत्येक 2 जोड़ देगा<sup>−k</sup>माप तक, जो असंभव है। इस प्रकार डोमेन में लंबाई k की स्ट्रिंग्स का सेट वास्तव में पहले से ही गणना की गई ऐसी स्ट्रिंग्स का सेट है।
 == एल्गोरिथम यादृच्छिकता ==
-एक वास्तविक संख्या यादृच्छिक होती है यदि वास्तविक संख्या का प्रतिनिधित्व करने वाला द्विआधारी अनुक्रम एक [[एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम]] है। कैलुडे, हर्टलिंग, खुसैनोव और वांग ने दिखाया<ref>{{Citation |last1=Calude |first1=Cristian S. |title=Recursively Enumerable Reals and Chaitin &Omega; numbers |date=1998 |url=https://www.cs.auckland.ac.nz/~cristian/samplepapers/omegastacs.pdf |archive-url=https://web.archive.org/web/20040119142843/http://www.cs.auckland.ac.nz/~cristian/samplepapers/omegastacs.pdf |archive-date=2004-01-19 |url-status=live |work=[[Symposium on Theoretical Aspects of Computer Science|STACS 98]] |volume=1373 |pages=596–606 |publisher=Springer Berlin Heidelberg |doi=10.1007/bfb0028594 |isbn=978-3-540-64230-5 |access-date=2022-03-20 |last2=Hertling |first2=Peter H. |last3=Khoussainov |first3=Bakhadyr |last4=Wang |first4=Yongge|bibcode=1998LNCS.1373..596C |s2cid=5493426 }}</ref> कि पुनरावर्ती रूप से गणना योग्य वास्तविक संख्या एक एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम है यदि और केवल यदि यह चैतिन की Ω संख्या है।
+एक वास्तविक संख्या यादृच्छिक होती है यदि वास्तविक संख्या का प्रतिनिधित्व करने वाला द्विआधारी अनुक्रम [[एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम]] है। कैलुडे, हर्टलिंग, खुसैनोव और वांग ने दिखाया<ref>{{Citation |last1=Calude |first1=Cristian S. |title=Recursively Enumerable Reals and Chaitin &Omega; numbers |date=1998 |url=https://www.cs.auckland.ac.nz/~cristian/samplepapers/omegastacs.pdf |archive-url=https://web.archive.org/web/20040119142843/http://www.cs.auckland.ac.nz/~cristian/samplepapers/omegastacs.pdf |archive-date=2004-01-19 |url-status=live |work=[[Symposium on Theoretical Aspects of Computer Science|STACS 98]] |volume=1373 |pages=596–606 |publisher=Springer Berlin Heidelberg |doi=10.1007/bfb0028594 |isbn=978-3-540-64230-5 |access-date=2022-03-20 |last2=Hertling |first2=Peter H. |last3=Khoussainov |first3=Bakhadyr |last4=Wang |first4=Yongge|bibcode=1998LNCS.1373..596C |s2cid=5493426 }}</ref> कि पुनरावर्ती रूप से गणना योग्य वास्तविक संख्या एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम है यदि और केवल यदि यह चैतिन की Ω संख्या है।
 ==संभावनाओं को रोकने के लिए अपूर्णता प्रमेय ==
 {{Main|Chaitin's incompleteness theorem}}
-[[प्राकृतिक संख्या]]ओं के लिए प्रत्येक विशिष्ट सुसंगत रूप से प्रभावी रूप से प्रस्तुत [[स्वयंसिद्ध प्रणाली]] के लिए, जैसे कि [[पीनो अभिगृहीत]], एक निरंतर एन मौजूद है जैसे कि एनथ के बाद Ω का कोई भी बिट उस प्रणाली के भीतर 1 या 0 साबित नहीं किया जा सकता है। स्थिरांक N इस बात पर निर्भर करता है कि [[औपचारिक प्रणाली]] को प्रभावी ढंग से कैसे दर्शाया जाता है, और इस प्रकार यह सीधे तौर पर स्वयंसिद्ध प्रणाली की जटिलता को प्रतिबिंबित नहीं करता है। यह अपूर्णता परिणाम गोडेल की अपूर्णता प्रमेय के समान है जिसमें यह दर्शाता है कि अंकगणित के लिए कोई भी सुसंगत औपचारिक सिद्धांत पूर्ण नहीं हो सकता है।
+[[प्राकृतिक संख्या]]ओं के लिए प्रत्येक विशिष्ट सुसंगत रूप से प्रभावी रूप से प्रस्तुत [[स्वयंसिद्ध प्रणाली]] के लिए, जैसे कि [[पीनो अभिगृहीत]], निरंतर एन मौजूद है जैसे कि एनथ के बाद Ω का कोई भी बिट उस प्रणाली के भीतर 1 या 0 साबित नहीं किया जा सकता है। स्थिरांक N इस बात पर निर्भर करता है कि [[औपचारिक प्रणाली]] को प्रभावी ढंग से कैसे दर्शाया जाता है, और इस प्रकार यह सीधे तौर पर स्वयंसिद्ध प्रणाली की जटिलता को प्रतिबिंबित नहीं करता है। यह अपूर्णता परिणाम गोडेल की अपूर्णता प्रमेय के समान है जिसमें यह दर्शाता है कि अंकगणित के लिए कोई भी सुसंगत औपचारिक सिद्धांत पूर्ण नहीं हो सकता है।
 ==सुपर ओमेगा ==
-जैसा कि ऊपर उल्लेख किया गया है, ग्रेगरी चैटिन के स्थिरांक Ω के पहले n बिट्स इस अर्थ में यादृच्छिक या असंपीड़ित हैं कि हम n-O(1) बिट्स से कम वाले हॉल्टिंग एल्गोरिदम द्वारा उनकी गणना नहीं कर सकते हैं। हालाँकि, छोटे लेकिन कभी न रुकने वाले एल्गोरिदम पर विचार करें जो सभी संभावित कार्यक्रमों को व्यवस्थित रूप से सूचीबद्ध और चलाता है; जब भी उनमें से एक रुकता है तो इसकी संभावना आउटपुट में जुड़ जाती है (शून्य से प्रारंभ)। सीमित समय के बाद आउटपुट के पहले n बिट्स कभी नहीं बदलेंगे (इससे कोई फर्क नहीं पड़ता कि यह समय स्वयं एक हॉल्टिंग प्रोग्राम द्वारा गणना योग्य नहीं है)। तो एक छोटा नॉन-हॉल्टिंग एल्गोरिदम है जिसका आउटपुट (परिमित समय के बाद) Ω के पहले एन बिट्स पर परिवर्तित होता है। दूसरे शब्दों में, Ω के [[गणनीय]] प्रथम n बिट्स इस अर्थ में अत्यधिक संपीड़ित हैं कि वे एक बहुत ही छोटे एल्गोरिथ्म द्वारा सीमा-गणना योग्य हैं; वे गणना एल्गोरिदम के सेट के संबंध में यादृच्छिक नहीं हैं। जुरगेन श्मिडहुबर (2000) ने एक सीमा-गणना योग्य सुपर Ω का निर्माण किया, जो एक अर्थ में मूल सीमा-गणना योग्य Ω की तुलना में बहुत अधिक यादृच्छिक है, क्योंकि कोई भी किसी भी गणना करने वाले गैर-रोक एल्गोरिथ्म द्वारा सुपर Ω को महत्वपूर्ण रूप से संपीड़ित नहीं कर सकता है।
+जैसा कि ऊपर उल्लेख किया गया है, ग्रेगरी चैटिन के स्थिरांक Ω के पहले n बिट्स इस अर्थ में यादृच्छिक या असंपीड़ित हैं कि हम n-O(1) बिट्स से कम वाले हॉल्टिंग एल्गोरिदम द्वारा उनकी गणना नहीं कर सकते हैं। हालाँकि, छोटे लेकिन कभी न रुकने वाले एल्गोरिदम पर विचार करें जो सभी संभावित कार्यक्रमों को व्यवस्थित रूप से सूचीबद्ध और चलाता है; जब भी उनमें से रुकता है तो इसकी संभावना आउटपुट में जुड़ जाती है (शून्य से प्रारंभ)। सीमित समय के बाद आउटपुट के पहले n बिट्स कभी नहीं बदलेंगे (इससे कोई फर्क नहीं पड़ता कि यह समय स्वयं हॉल्टिंग प्रोग्राम द्वारा गणना योग्य नहीं है)। तो छोटा नॉन-हॉल्टिंग एल्गोरिदम है जिसका आउटपुट (परिमित समय के बाद) Ω के पहले एन बिट्स पर परिवर्तित होता है। दूसरे शब्दों में, Ω के [[गणनीय]] प्रथम n बिट्स इस अर्थ में अत्यधिक संपीड़ित हैं कि वे बहुत ही छोटे एल्गोरिथ्म द्वारा सीमा-गणना योग्य हैं; वे गणना एल्गोरिदम के सेट के संबंध में यादृच्छिक नहीं हैं। जुरगेन श्मिडहुबर (2000) ने सीमा-गणना योग्य सुपर Ω का निर्माण किया, जो अर्थ में मूल सीमा-गणना योग्य Ω की तुलना में बहुत अधिक यादृच्छिक है, क्योंकि कोई भी किसी भी गणना करने वाले गैर-रोक एल्गोरिथ्म द्वारा सुपर Ω को महत्वपूर्ण रूप से संपीड़ित नहीं कर सकता है।
-वैकल्पिक सुपर Ω के लिए, उपसर्ग-मुक्त कोड|उपसर्ग-मुक्त [[यूनिवर्सल ट्यूरिंग मशीन]] (UTM) की सार्वभौमिकता संभावना{{Snd}} अर्थात्, संभावना यह है कि यह तब भी सार्वभौमिक रहता है जब इसका प्रत्येक इनपुट ([[बाइनरी स्ट्रिंग]] के रूप में) एक यादृच्छिक बाइनरी स्ट्रिंग द्वारा उपसर्ग किया जाता है{{Snd}} को ऑरेकल वाली मशीन की रुकने की समस्या के तीसरे पुनरावृत्ति के रूप में देखा जा सकता है (यानी, <math>O^{(3)}</math>[[ट्यूरिंग जंप]] का उपयोग करके)।<ref>{{cite journal |author=Barmpalias, G. and Dowe D.L. |title=उपसर्ग-मुक्त मशीन की सार्वभौमिकता की संभावना|journal=Philosophical Transactions of the Royal Society A |volume=370 |issue=1 | pages=3488–3511 (Theme Issue 'The foundations of computation, physics and mentality: the Turing legacy' compiled and edited by Barry Cooper and Samson Abramsky) |date=2012 |doi=10.1098/rsta.2011.0319|pmid=22711870 |bibcode=2012RSPTA.370.3488B |doi-access=free }}</ref>
+वैकल्पिक सुपर Ω के लिए, उपसर्ग-मुक्त कोड|उपसर्ग-मुक्त [[यूनिवर्सल ट्यूरिंग मशीन]] (UTM) की सार्वभौमिकता संभावना{{Snd}} अर्थात्, संभावना यह है कि यह तब भी सार्वभौमिक रहता है जब इसका प्रत्येक इनपुट ([[बाइनरी स्ट्रिंग]] के रूप में) यादृच्छिक बाइनरी स्ट्रिंग द्वारा उपसर्ग किया जाता है{{Snd}} को ऑरेकल वाली मशीन की रुकने की समस्या के तीसरे पुनरावृत्ति के रूप में देखा जा सकता है (यानी, <math>O^{(3)}</math>[[ट्यूरिंग जंप]] का उपयोग करके)।<ref>{{cite journal |author=Barmpalias, G. and Dowe D.L. |title=उपसर्ग-मुक्त मशीन की सार्वभौमिकता की संभावना|journal=Philosophical Transactions of the Royal Society A |volume=370 |issue=1 | pages=3488–3511 (Theme Issue 'The foundations of computation, physics and mentality: the Turing legacy' compiled and edited by Barry Cooper and Samson Abramsky) |date=2012 |doi=10.1098/rsta.2011.0319|pmid=22711870 |bibcode=2012RSPTA.370.3488B |doi-access=free }}</ref>

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

v t e अपरिमेय संख्या
चेटिन ( $Ω$ )* Liouville* प्राइम ( $ρ$ )* ओमेगा* काहेन* 2 का लघुगणक* गॉस ( $G$ )* 2 की बारहवीं जड़* apéry's ( $ζ (3)$ )* प्लास्टिक $ρ$ )* 2 का वर्गमूल* सुपरगोल्डन अनुपात ( $ψ$ )* erdős -borwein ( $E$ )* गोल्डन अनुपात ( $φ$ )* 3 का वर्गमूल* 5 का वर्गमूल* चांदी का अनुपात ( $δ S$ )* 6 का वर्गमूल* 7 का वर्गमूल* यूलर ( $e$ )* Pi ( $π$ )
सिज़ोफ्रेनिक ट्रांसेंडेंटल त्रिकोणमितीय* सिज़ोफ्रेनिक ट्रांसेंडेंटल त्रिकोणमितीय सिज़ोफ्रेनिक ट्रांसेंडेंटल त्रिकोणमितीयसिज़ोफ्रेनिक नंबर
...-->

Anonymous

Search

चैतीन का स्थिरांक: Difference between revisions

Namespaces

More

Page actions

Revision as of 11:41, 2 August 2023

Contents

उदाहरण

टिप्पणियाँ

पृष्ठभूमि

परिभाषा

रुकने की समस्या से संबंध

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

गुण

अगणनीयता

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

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

सुपर ओमेगा

यह भी देखें

संदर्भ

उद्धृत कार्य

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

चैतीन का स्थिरांक: Difference between revisions

Revision as of 11:41, 2 August 2023

उदाहरण

टिप्पणियाँ

पृष्ठभूमि

परिभाषा

रुकने की समस्या से संबंध

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

गुण

अगणनीयता

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

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

सुपर ओमेगा

यह भी देखें

संदर्भ

उद्धृत कार्य

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories