एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम: Difference between revisions

Latest revision as of 12:15, 4 August 2023

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

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

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

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

समस्त मार्टिन-लोफ यादृच्छिक (द्विचर) अनुक्रमों की श्रेणी को सीमा या एमएलआर के माध्यम से दर्शाया गया है।

इतिहास

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

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

तीन सामान्य परिभाषाएँ

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

'एल्गोरिथमिक जटिलता' (चैटिन 1969, श्नोर 1973, लेविन 1973): एल्गोरिथम जटिलता (जिसे उपसर्ग-मुक्त एल्गोरिथम जटिलता या कार्य आकार जटिलता के रूप में भी जाना जाता है) को परिमित अनुक्रम (अक्षरों या द्विचर अंकों का) की एल्गोरिथम संपीड्यता पर निचली सीमा के रूप में विचार करा जा सकता है। यह ऐसे प्रत्येक अनुक्रम को प्राकृतिक संख्या K(w) प्रदान करता है, जो सहज रूप से, कंप्यूटर कार्य की न्यूनतम लंबाई को मापता है (कुछ निश्चित कार्यरचना भाषा में लिखा गया है) जो कोई इनपुट नहीं लेता है और प्रवाह पर आउटपुट w देता है। जटिलता को उपसर्ग-मुक्त होना आवश्यक है: कार्य (0 और 1 का अनुक्रम) के पश्चात् 0s की अनंत शृंखला होती है, और कार्यरचना की लंबाई (यह मानते हुए कि यह रुकती है) में कार्य के दाईं ओर शून्य की संख्या सम्मिलित होती है, जिसे विश्वव्यापी ट्यूरिंग यंत्र अध्यन करता है। अतिरिक्त आवश्यकता की आवश्यकता है क्योंकि हम लंबाई चयन कर सकते हैं, जैसे कि लंबाई उप-शृंखला के बारे में जानकारी को चिन्हित करती है। एक प्राकृतिक संख्या c और अनुक्रम w को देखते हुए हम कहते हैं कि यदि $K(w)\geq |w|-c$ . है तो w, c-असंपीड्य है।

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

रचनात्मक शून्य आवरण (मार्टिन-लोफ 1966): यह मार्टिन-लोफ की मूल परिभाषा है। परिमित द्विचर शृंखला w के लिए हम C_w को w माध्यम से उत्पन्न बेलन को निरूपित करने देते हैं। यह w से प्रारंभ होने वाले समस्त अनंत अनुक्रमों का समुच्चय है, जो कैंटर अंतराल में मूल विवृत समुच्चय है। w के माध्यम से उत्पन्न बेलन का उत्पाद माप (गणित) μ(C_w) 2^−|w| के रूप में परिभाषित किया गया है। प्रगायक अंतराल का प्रत्येक विवृत उपसमुच्चय असंयुक्त मूलभूत विवृत समुच्चय के गणनीय अनुक्रम का संघ है, और विवृत समुच्चय का माप ऐसे किसी भी अनुक्रम के उपायों का योग है। प्रभावी विवृत समुच्चय विवृत समुच्चयों है जो द्विचर शृंखला के पुनरावर्ती गणना योग्य अनुक्रम के माध्यम से निर्धारित मूलभूत विवृत समुच्चय के अनुक्रम का संघ है। रचनात्मक शून्य आवरण या प्रभावी माप 0 समुच्चय, प्रभावी विवृत समुच्चयों का पुनरावर्ती रूप से गणना योग्य अनुक्रम ^{$U_{i}$ है, जैसे कि प्रत्येक प्राकृतिक संख्या के लिए ^{$U_{i+1}\subseteq U_{i}$ और ^{$\mu (U_{i})\leq 2^{-i}$ एवं i.प्रत्येक प्रभावी शून्य आवरण माप 0 का $G_{\delta }$ समुच्चय निर्धारित करता है, अर्थात् समुच्चय ^{$U_{i}$ का प्रतिच्छेदन है।}}}}

एक अनुक्रम को मार्टिन-लोफ यादृच्छिक के रूप में परिभाषित किया गया है यदि यह रचनात्मक शून्य आवरण के माध्यम से निर्धारित किसी भी

G_{\delta }

समुच्चय में सम्मलित नहीं है।

रचनात्मक मार्टिंगेल्स (श्नर 1971): मार्टिंगेल (संभाव्यता सिद्धांत) कार्य है $d:\{0,1\}^{*}\to [0,\infty )$ ऐसा है कि, समस्त परिमित श्रृंखला w के लिए, $d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2$ , जिस स्थान पर $a^{\smallfrown }b$ श्रृंखला a और b का संयोजन है। इसे निष्पक्षता की स्थिति कहा जाता है: यदि मार्टिंगेल को शर्त की रणनीति के रूप में देखा जाता है, तब उपरोक्त शर्त के लिए आवश्यक है कि शर्त उचित बाधाओं के विरुद होनी चाहिए। मार्टिंगेल डी को अनुक्रम S पर 'सफल' माना जाता है यदि $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ जिस स्थान पर $S\upharpoonright n$ S के पूर्व n बिंदु हैं। मार्टिंगेल डी रचनात्मक है (जिसे अशक्त रूप से गणना योग्य अल्प अर्ध-गणना के रूप में भी जाना जाता है) यदि कोई गणना योग्य कार्य ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ उपस्थित है, जैसे कि समस्त परिमित द्विचर शृंखला के लिए w है

${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ समस्त धनात्मक पूर्णांक के लिए t है
$\lim _{t\to \infty }{\widehat {d}}(w,t)=d(w).$ : अनुक्रम मार्टिन-लोफ यादृच्छिक है और यदि कोई रचनात्मक मार्टिंगेल सफल नहीं होता है।

परिभाषाओं की व्याख्या

कोल्मोगोरोव जटिलता लक्षण वर्णन अंतर्ज्ञान को व्यक्त करता है कि यादृच्छिक अनुक्रम असंपीड़ित है: उपसर्ग से बहुत कम कार्य के माध्यम से कोई उपसर्ग नहीं बनाया जा सकता है।

अशक्त आवरण लक्षण वर्णन अंतर्ज्ञान बताता है कि यादृच्छिक वास्तविक संख्या में ऐसी कोई गुण नहीं होनी चाहिए जो असामान्य हो। प्रत्येक माप 0 समुच्चय को असामान्य गुण के रूप में माना जा सकता है। अनुक्रम के लिए बिना माप 0 समुच्चय के बिना संभव नहीं है, क्योंकि प्रत्येक एक-बिंदु समुच्चय में माप 0 है। मार्टिन-लोफ का विचार परिभाषा को 0 समुच्चयों को मापने के लिए सीमित करना था जो प्रभावी रूप से वर्णित हैं; एक प्रभावी शून्य आवरण की परिभाषा प्रभावी रूप से वर्णित माप 0 समुच्चयों का गणनीय संग्रह निर्धारित करती है और अनुक्रम को यादृच्छिक होने के लिए परिभाषित करती है यदि यह इनमें से किसी विशेष माप 0 समुच्चय में नहीं है। चूंकि माप 0 समुच्चय के गणनीय संग्रह के संबंध का माप 0 है, इसलिए यह परिभाषा तत्काल प्रमेय की ओर ले जाती है, कि यादृच्छिक अनुक्रमों का माप 1 समुच्चय है। ध्यान दें कि यदि हम वास्तविक संख्याओं के अंतराल [0,1] के साथ द्विचर अनुक्रमों के कैंटर अंतराल की अभिज्ञान करते हैं, तब कैंटर अंतराल पर माप लेबेसेग माप से सहमत है।मार्टिंगेल लक्षण वर्णन अंतर्ज्ञान बताता है कि कोई भी प्रभावी प्रक्रिया यादृच्छिक अनुक्रम के सट्टेबाजी से चलन करने में सक्षम नहीं होनी चाहिए। मार्टिंगेल डी शर्त की रणनीति है। d एक परिमित शृंखला w का अध्यन करता है और आगामी योजना पर चलन करता है। यह अपने प्रचलन के कुछ अंश पर शर्त लगाता है कि आगामी अंश 0 होगा, और उसके पश्चात् का शेष चलन होगा कि आगामी अंश 1 होगा। d उस अंश पर लगाए गए मुद्रा को दोगुना कर देता है जो वास्तव में घटित हुआ था और वह शेष को लुप्त कर देता है। d(w) शृंखला w को देखने के पश्चात् उसके पास उपस्थित राशि है। चूँकि शृंखला w को देखने के पश्चात् लगाई गई अंश की गणना d(w), d(w0), और d(w1) के मानों से की जा सकती है, इसके पास उपस्थित धनराशि की गणना करना अंश की गणना करने के सामान्य है। मार्टिंगेल लक्षण वर्णन कहता है कि किसी भी कंप्यूटर के माध्यम से प्रयुक्त की जाने वाली कोई भी शर्त की रणनीति (रचनात्मक रणनीतियों के अशक्त अर्थों में भी, जो आवश्यक रूप से संगणनीय नहीं हैं) यादृच्छिक अनुक्रम पर धनराशि की शर्त कर सकती है।

मार्टिन-लोफ यादृच्छिक अनुक्रमों के गुण और उदाहरण

चैटिन स्थिरांक की स्थिरांक की संभावना Ω यादृच्छिक अनुक्रम का उदाहरण है।
रैंड^c (रैंड का पूरक (समुच्चय सिद्धांत)) समस्त अनंत अनुक्रमों के समुच्चय का माप (गणित) 0 उप-समुच्चय है। यह इस तथ्य से निहित है कि प्रत्येक रचनात्मक शून्य आवरण में माप 0 समुच्चय सम्मिलित होता है, मात्र गणनीय रचनात्मक शून्य आवरण होते हैं, और माप 0 समुच्चय के गणनीय संघ में माप 0 होता है। इसका तात्पर्य है कि रैंड समस्त अनंत क्रम के समुच्चय का माप 1 उप-समुच्चय है।
प्रत्येक यादृच्छिक क्रम सामान्य संख्या है।
रैंड^c का रचनात्मक अशक्त आवरण है। इसका कारण यह है कि यादृच्छिकता के लिए समस्त प्रभावी परीक्षण (अर्थात्, रचनात्मक शून्य आवरण), एक रूप में, यादृच्छिकता के लिए इस सार्वभौमिक परीक्षण के माध्यम से सम्मिलित हैं, क्योंकि कोई भी अनुक्रम जो यादृच्छिकता के लिए इस एकल परीक्षा को उत्तीर्ण करता है, यादृच्छिकता के लिए समस्त परीक्षणों को पारित करेगा। (मार्टिन-लोफ 1966)
एक सार्वभौमिक रचनात्मक मार्टिंगेल 'डी' है। यह मार्टिंगेल इस रूप में सार्वभौमिक है कि, किसी रचनात्मक मार्टिंगेल डी को देखते हुए, यदि d अनुक्रम पर सफल होता है, तब 'd' उस क्रम पर भी सफल होता है। इस प्रकार, रैंड में प्रत्येक क्रम पर 'd' सफल होता है^c (किन्तु, चूंकि d रचनात्मक है, यह रैंड में बिना किसी क्रम के सफल होता है)। (श्नोर 1971)
वर्ग रैंड , कैंटर अंतराल का $\Sigma _{2}^{0}$ उपसमुच्चय है जिस स्थान पर $\Sigma _{2}^{0}$ अंकगणितीय पदानुक्रम के दूसरे स्तर को संदर्भित करता है। ऐसा इसलिए है क्योंकि अनुक्रम S रैंड में है और मात्र यदि सार्वभौमिक प्रभावी अशक्त आवरण में कुछ विवृत समुच्चय है जिसमें S सम्मिलित नहीं है; इस गुण को $\Sigma _{2}^{0}$ सूत्र के माध्यम से परिभाषित किया जा सकता है।
एक यादृच्छिक क्रम है जो $\Delta _{2}^{0}$ है, अर्थात्, स्थिरांक समस्या के लिए दैवज्ञ के सापेक्ष गणना योग्य है।। (श्नोरर 1971) चैतीन Ω ऐसे अनुक्रम का उदाहरण है।
कोई यादृच्छिक अनुक्रम निर्णायकता (तर्क), संगणनीय रूप से गणना योग्य, या सह-गणना योग्य नहीं है। चूँकि यह अंकगणितीय पदानुक्रम के $\Delta _{1}^{0}$ , $\Sigma _{1}^{0}$ , और $\Pi _{1}^{0}$ स्तरों के अनुरूप हैं, इसका अर्थ है कि $\Delta _{2}^{0}$ अंकगणितीय पदानुक्रम में सबसे निचला स्तर है जिस स्थान पर यादृच्छिक अनुक्रम प्राप्त करे जा सकते हैं।
प्रत्येक क्रम कुछ यादृच्छिक अनुक्रम के लिए परिगणन रूपांतरित है। (कुचेरा 1985/1989, पेटर जीएसी। जीएसी 1986)। इस प्रकार इच्छानुसार से उच्च परिगणन उपाधि के यादृच्छिक क्रम हैं।

सापेक्ष यादृच्छिकता

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

सापेक्ष यादृच्छिकता से संबंधित महत्वपूर्ण परिणाम मिचेल वैन लैंबलजेन प्रमेय है, जिसमें कहा गया है कि यदि C, A और B से बना अनुक्रम है, तो A के पूर्व अंश को जोड़कर करके, B का प्रथम अंश, A का दूसरा अंश, A का दूसरा अंश B, और इसी तरह, पुनः C एल्गोरिदमिक रूप से यादृच्छिक है और मात्र यदि A एल्गोरिदमिक रूप से यादृच्छिक है, और B एल्गोरिदमिक रूप से A के सापेक्ष यादृच्छिक है। एक निकट संबंधी परिणाम यह है कि यदि A और B दोनों स्वयं यादृच्छिक हैं, तब A यादृच्छिक सापेक्ष है B यदि मात्र B एवं A के सापेक्ष यादृच्छिक है।

मार्टिन-लोफ यादृच्छिकता से अधिक शक्तिशाली

सापेक्ष यादृच्छिकता हमें प्रथम धारणा देती है जो मार्टिन-लोफ यादृच्छिकता से अधिक शक्तिशाली है, जो कि कुछ निश्चित दैवज्ञ A के सापेक्ष यादृच्छिकता है। किसी भी दैवज्ञ के लिए, यह कम से कम उतना ही शक्तिशाली है, और अधिकांश दैवज्ञ के लिए, यह दृढता से शक्तिशाली है, क्योंकि मार्टिन-लोफ यादृच्छिक अनुक्रम होंगे जो दैवज्ञ A के सापेक्ष यादृच्छिक नहीं हैं। महत्वपूर्ण दैवज्ञ को अधिकांशतः स्थिरांक समस्या $\emptyset '$ और नौवीं व्यतिक्रम दैवज्ञ $\emptyset ^{(n)}$ माना जाता है, क्योंकि यह दैवज्ञ स्वाभाविक रूप से उत्पन्न होने वाले विशिष्ट प्रश्नों का उत्तर देने में सक्षम होते हैं। एक क्रम जो दैवज्ञ $\emptyset ^{(n-1)}$ के सापेक्ष यादृच्छिक है उसे n-यादृच्छिक कहा जाता है। अनुक्रम 1-यादृच्छिक है, इसलिए, यदि और मात्र यह मार्टिन-लोफ यादृच्छिक है। अनुक्रम जो प्रत्येक n के लिए n-यादृच्छिक होता है, अंकगणितीय रूप से यादृच्छिक कहलाता है। अधिक जटिल गुणों पर विचार करते समय कभी-कभी n-यादृच्छिक अनुक्रम उत्पन्न होते हैं। उदाहरण के लिए, मात्र चयनित $\Delta _{2}^{0}$ अनेक सेट हैं, इसलिए कोई सोच सकता है कि यह गैर-यादृच्छिक होने चाहिए। चूंकि, स्थिरांक की संभावना Ω $\Delta _{2}^{0}$ और 1-यादृच्छिक है; 2-यादृच्छिकता तक पहुंचने के पश्चात् ही यादृच्छिक समुच्चय का $\Delta _{2}^{0}$ होना असंभव है।

मार्टिन-लोफ यादृच्छिकता से अशक्त

इसके अतिरिक्त, यादृच्छिकता की अनेक धारणाएँ हैं जो मार्टिन-लोफ़ यादृच्छिकता से अशक्त हैं। इनमें से कुछ अशक्त 1-यादृच्छिकता, श्नोरर यादृच्छिकता, गणना योग्य यादृच्छिकता, आंशिक गणना योग्य यादृच्छिकता हैं। योंगगे वांग ने दिखाया ^[2] कि श्नोरर यादृच्छिकता संगणनीय यादृच्छिकता से भिन्न है। इसके अतिरिक्त, कोल्मोगोरोव-लवलैंड यादृच्छिकता को मार्टिन-लोफ यादृच्छिकता से अधिक शक्तिशाली नहीं माना जाता है, किन्तु यह ज्ञात नहीं है कि यह वास्तव में अशक्त है या नहीं है। यादृच्छिकता वर्णक्रम के विपरीत बिंदु पर K-नगण्य समुच्चय की धारणा है। ये समुच्चय यादृच्छिक-विरोधी हैं क्योंकि सभी प्रारंभिक खंड प्रत्येक प्रारंभिक खंड w के लिए लघुगणकीय रूप से संपीड़ित $K(w)\leq K(|w|)+b$ हैं, किन्तु वे गणना योग्य नहीं हैं।

यह भी देखें

संदर्भ

↑ Jean-Paul Delahaye, Randomness, Unpredictability and Absence of Order, in Philosophy of Probability, p. 145–167, Springer 1993.
↑ Yongge Wang: Randomness and Complexity. PhD Thesis, 1996, http://webpages.uncc.edu/yonwang/papers/thesis.pdf

आगे की पढाई

Downey, Rod; Hirschfeldt, Denis R.; Nies, André; Terwijn, Sebastiaan A. (2006). "Calibrating Randomness". The Bulletin of Symbolic Logic. 12 (3/4): 411–491. CiteSeerX 10.1.1.135.4162. doi:10.2178/bsl/1154698741. Archived from the original on 2016-02-02.
Gács, Péter (1986). "Every sequence is reducible to a random one" (PDF). Information and Control. 70 (2/3): 186–192. doi:10.1016/s0019-9958(86)80004-3.
Kučera, A. (1985). "Measure, Π⁰
₁-classes and complete extensions of PA". Recursion Theory Week. Lecture Notes in Mathematics. Vol. 1141. Springer-Verlag. pp. 245–259. doi:10.1007/BFb0076224. ISBN 978-3-540-39596-6.

Kučera, A. (1989). "On the use of diagonally nonrecursive functions". Studies in Logic and the Foundations of Mathematics. Vol. 129. North-Holland. pp. 219–239.

Levin, L. (1973). "On the notion of a random sequence". Soviet Mathematics - Doklady. 14: 1413–1416.

Li, M.; Vitanyi, P. M. B. (1997). An Introduction to Kolmogorov Complexity and its Applications (Second ed.). Berlin: Springer-Verlag.

Martin-Löf, P. (1966). "The definition of random sequences". Information and Control. 9 (6): 602–619. doi:10.1016/s0019-9958(66)80018-9.
Nies, André (2009). Computability and randomness. Oxford Logic Guides. Vol. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034.

Schnorr, C. P. (1971). "A unified approach to the definition of a random sequence". Mathematical Systems Theory. 5 (3): 246–258. doi:10.1007/BF01694181. S2CID 8931514.

Schnorr, Claus P. (1973). "Process complexity and effective random tests". Journal of Computer and System Sciences. 7 (4): 376–388. doi:10.1016/s0022-0000(73)80030-3.

Chaitin, Gregory J. (1969). "On the Length of Programs for Computing Finite Binary Sequences: Statistical Considerations". Journal of the ACM. 16 (1): 145–159. doi:10.1145/321495.321506. S2CID 8209877.

Ville, J. (1939). Etude critique de la notion de collectif. Paris: Gauthier-Villars.

[1] Jean-Paul Delahaye, Randomness, Unpredictability and Absence of Order, in Philosophy of Probability, p. 145–167, Springer 1993.

[2] Yongge Wang: Randomness and Complexity. PhD Thesis, 1996, http://webpages.uncc.edu/yonwang/papers/thesis.pdf

[1]

[2]

@@ Line 1: / Line 1: @@
 {{distinguish-redirect|एल्गोरिथम यादृच्छिकता|यादृच्छिक एल्गोरिदम}}
-सहज रूप से एक एल्गोरिदमिक रूप से [[यादृच्छिक अनुक्रम]] (या यादृच्छिक अनुक्रम) द्विचर अंकों का एक अनुक्रम है जो सार्वभौमिक  परिगणन  उपकरण  (उपसर्ग-मुक्त या नहीं) पर संचालन  वाले किसी भी एल्गोरिदम के लिए यादृच्छिक प्रतीत होता है। धारणा को किसी भी परिमित वर्णमाला (जैसे दशमलव अंक) पर अनुक्रमों के अनुरूप प्रयुक्त किया जा सकता है। [[एल्गोरिथम सूचना सिद्धांत]] में यादृच्छिक अनुक्रम अध्ययन की प्रमुख  उद्देश्य उपलब्ध हैं।
+सहज रूप से एल्गोरिदमिक रूप से [[यादृच्छिक अनुक्रम]] (या यादृच्छिक अनुक्रम) द्विचर अंकों का एक अनुक्रम है, जो सार्वभौमिक परिगणन उपकरण (उपसर्ग-मुक्त या नहीं) पर संचालन वाले किसी भी एल्गोरिदम के लिए यादृच्छिक प्रतीत होता है। धारणा को किसी भी परिमित वर्णमाला (जैसे दशमलव अंक) पर अनुक्रमों के अनुरूप प्रयुक्त किया जा सकता है। [[एल्गोरिथम सूचना सिद्धांत]] में यादृच्छिक अनुक्रम अध्ययन की प्रमुख उद्देश्य उपलब्ध हैं।
-जैसा कि कभी-कभी विभिन्न प्रकार के एल्गोरिदम पर विचार किया जाता है, उनके संचालन  के समय पर विशिष्ट सीमाओं वाले एल्गोरिदम से लेकर एल्गोरिदम तक जो [[ओरेकल मशीन]] से प्रश्न पूछ सकते हैं, यह यादृच्छिकता की विभिन्न धारणाएं हैं। इनमें से सबसे आम को मार्टिन-लोफ यादृच्छिकता (k-यादृच्छिकता या 1-यादृच्छिकता) के रूप में जाना जाता है, किन्तु यादृच्छिकता के शक्तिशाली और अशक्त रूप भी उपस्थित हैं। जब "एल्गोरिथम  रूप से यादृच्छिक" शब्द का उपयोग स्पष्टीकरण के बिना किसी विशेष एकल (परिमित या अनंत) अनुक्रम को संदर्भित करने के लिए किया जाता है, तो सामान्यतः पर इसका अर्थ "असंपीड़ित" माना जाता है या स्थितियों में अनुक्रम अनंत होता है और उपसर्ग एल्गोरिदमिक रूप से यादृच्छिक (अर्थात k-असंपीड़ित) होता है। "मार्टिन-लोफ-चैतिन रैंडम" है।
+जैसा कि कभी-कभी विभिन्न प्रकार के एल्गोरिदम पर विचार किया जाता है, उनके संचालन के समय पर विशिष्ट सीमाओं वाले एल्गोरिदम से लेकर एल्गोरिदम तक जो [[ओरेकल मशीन|दैवज्ञ यंत्र]] से प्रश्न सकते हैं, यह यादृच्छिकता की विभिन्न धारणाएं हैं। इनमें से सबसे आम को मार्टिन-लोफ यादृच्छिकता (k-यादृच्छिकता या 1-यादृच्छिकता) के रूप में जाना जाता है, किन्तु यादृच्छिकता के शक्तिशाली और अशक्त रूप भी उपस्थित हैं। जब "एल्गोरिथम रूप से यादृच्छिक" शब्द का उपयोग स्पष्टीकरण के बिना किसी विशेष एकल (परिमित या अनंत) अनुक्रम को संदर्भित करने के लिए किया जाता है, तो सामान्यतः पर इसका अर्थ "असंपीड़ित" माना जाता है या स्थितियों में अनुक्रम अनंत होता है और उपसर्ग एल्गोरिदमिक रूप से यादृच्छिक (अर्थात k-असंपीड़ित) होता है। "मार्टिन-लोफ-चैतिन रैंडम" है।
-एल्गोरिथम यादृच्छिकता और प्रसंभाव्य  यादृच्छिकता के मध्य  स्पष्ट करना महत्वपूर्ण है। एल्गोरिथम यादृच्छिकता के विपरीत, जिसे संगणनीय (और इस प्रकार नियतात्मक) प्रक्रियाओं के लिए परिभाषित किया गया है, प्रसंभाव्य  यादृच्छिकता को  सामान्यतः एक अनुक्रम का  गुण कहा जाता है जो एक स्वतंत्रता (संभाव्यता सिद्धांत) के माध्यम से  उत्पन्न होने वाली प्राथमिकता है (या इसका परिणाम है) समान रूप से यह  वितरण समसंभाव्य प्रसंभाव्य  प्रक्रिया है।
+एल्गोरिथम यादृच्छिकता और प्रसंभाव्य यादृच्छिकता के मध्य स्पष्ट करना महत्वपूर्ण है। एल्गोरिथम यादृच्छिकता के विपरीत, जिसे संगणनीय (और इस प्रकार नियतात्मक) प्रक्रियाओं के लिए परिभाषित किया गया है, प्रसंभाव्य यादृच्छिकता को सामान्यतः अनुक्रम का गुण कहा जाता है जो स्वतंत्रता (संभाव्यता सिद्धांत) के माध्यम से उत्पन्न होने वाली प्राथमिकता है (या इसका परिणाम है) समान रूप से यह वितरण समसंभाव्य प्रसंभाव्य प्रक्रिया है।
-क्योंकि द्विचर अंकों के अनंत अनुक्रमों को इकाई अंतराल में वास्तविक संख्याओं के साथ निर्धारित  करा जा सकता है, यादृच्छिक द्विचर अनुक्रमों को   अधिकांशतः  (एल्गोरिथमिक रूप से) यादृच्छिक वास्तविक संख्या कहा जाता है। इसके अतिरिक्त, अनंत द्विचर अनुक्रम प्राकृतिक संख्याओं के समुच्चय के विशिष्ट कार्यों के अनुरूप होते हैं; इसलिए उन अनुक्रमों को प्राकृतिक संख्याओं के समुच्चय के रूप में देखा जा सकता है।
+क्योंकि द्विचर अंकों के अनंत अनुक्रमों को इकाई अंतराल में वास्तविक संख्याओं के साथ निर्धारित करा जा सकता है, यादृच्छिक द्विचर अनुक्रमों को अधिकांशतः (एल्गोरिथमिक रूप से) यादृच्छिक वास्तविक संख्या कहा जाता है। इसके अतिरिक्त, अनंत द्विचर अनुक्रम प्राकृतिक संख्याओं के समुच्चय के विशिष्ट कार्यों के अनुरूप होते हैं; इसलिए उन अनुक्रमों को प्राकृतिक संख्याओं के समुच्चय के रूप में देखा जा सकता है।
-समस्त  मार्टिन-लोफ यादृच्छिक (द्विचर) अनुक्रमों की श्रेणी को सीमा  या एमएलआर के माध्यम से  दर्शाया गया है।
+समस्त मार्टिन-लोफ यादृच्छिक (द्विचर) अनुक्रमों की श्रेणी को सीमा या एमएलआर के माध्यम से दर्शाया गया है।
 == इतिहास ==
-एक यादृच्छिक अनुक्रम की प्रथम  उपयुक्त परिभाषा 1966 में पर मार्टिन-लोफ के माध्यम से  दी गई थी। इससे पूर्व  [[रिचर्ड वॉन मिसेस]] जैसे शोधकर्ताओं ने एक यादृच्छिक अनुक्रम को परिभाषित करने के लिए एक [[यादृच्छिकता परीक्षण]] की धारणा को औपचारिक रूप देने का प्रयास किया था, जो कि यादृच्छिकता के लिए समस्त  परीक्षणों को पारित करता है। चूंकि, एक यादृच्छिकता परीक्षण की स्पष्ट  धारणा अस्पष्ट त्याग  रह  गई थी। मार्टिन-लोफ की प्रमुख अंतर्दृष्टि यादृच्छिकता के लिए एक परीक्षण की धारणा को औपचारिक रूप से परिभाषित करने के लिए अभिकलन के सिद्धांत का उपयोग करना था। यह संभाव्यता में यादृच्छिकता के विचार के विपरीत है; उस सिद्धांत में, नमूना स्थान का कोई विशेष तत्व यादृच्छिक नहीं कहा जा सकता है।
+एक यादृच्छिक अनुक्रम की प्रथम उपयुक्त परिभाषा 1966 में पर मार्टिन-लोफ के माध्यम से दी गई थी। इससे पूर्व [[रिचर्ड वॉन मिसेस]] जैसे शोधकर्ताओं ने यादृच्छिक अनुक्रम को परिभाषित करने के लिए [[यादृच्छिकता परीक्षण]] की धारणा को औपचारिक रूप देने का प्रयास किया था, जो कि यादृच्छिकता के लिए समस्त परीक्षणों को पारित करता है। चूंकि, यादृच्छिकता परीक्षण की स्पष्ट धारणा अस्पष्ट त्याग दी गई थी। मार्टिन-लोफ की प्रमुख अंतर्दृष्टि यादृच्छिकता के लिए परीक्षण की धारणा को औपचारिक रूप से परिभाषित करने के लिए अभिकलन के सिद्धांत का उपयोग करना था। यह संभाव्यता में यादृच्छिकता के विचार के विपरीत है; उस सिद्धांत में, नमूना स्थान का कोई विशेष तत्व यादृच्छिक नहीं कहा जा सकता है।
-इसकी स्थापना के पश्चात् से, मार्टिन-लोफ यादृच्छिकता को  आँकड़े संपीड़न, यादृच्छिकता परीक्षणों और कठनाई के संदर्भ में अनेक समकक्ष विशेषताओं को स्वीकार करने के लिए दिखाया गया है-जो मूल परिभाषा के लिए अल्प बाह्य  समानता रखते हैं, किन्तु इनमें से प्रत्येक गुणों की हमारी सहज धारणा को संतुष्ट करता है जैसे यादृच्छिक अनुक्रम होना चाहिए: यादृच्छिक अनुक्रम असंगत होना चाहिए, उन्हें यादृच्छिकता के लिए सांख्यिकीय परीक्षण पास करना चाहिए, और उन पर पैसा लगाना कठिनाई होना चाहिए। मार्टिन-लोफ यादृच्छिकता की इन अनेक परिभाषाओं का अस्तित्व, और संगणना के विभिन्न मॉडलों के अनुसार  इन परिभाषाओं की स्थिरता, इस बात का प्रमाण देती है कि मार्टिन-लोफ यादृच्छिकता गणित की एक मौलिक गुण है और मार्टिन-लोफ के विशेष मॉडल की दुर्घटना नहीं है। थीसिस कि मार्टिन-लोफ यादृच्छिकता की परिभाषा सही ढंग से यादृच्छिकता की सहज धारणा को पकड़ती है, मार्टिन-लोफ-चैटिन थीसिस कहलाती है; यह कुछ सीमा  तक चर्च- परिगणन  थीसिस के समान है।<ref>[[Jean-Paul Delahaye]], [https://books.google.com/books?id=EDoXdoz-qYQC&pg=PA145&source=gbs_toc_r&cad=0_0 Randomness, Unpredictability and Absence of Order], in ''Philosophy of Probability'', p. 145–167, Springer 1993.</ref>{{explain|reason=Similar in what way? In that both theorems concern Turing machines and/or computability?|date=June 2021}}
+इसकी स्थापना के पश्चात् से मार्टिन-लोफ यादृच्छिकता को आँकड़े संपीड़न, यादृच्छिकता परीक्षणों और कठनाई के संदर्भ में अनेक समकक्ष विशेषताओं को स्वीकार करने के लिए दिखाया गया है। जो मूल परिभाषा के लिए अल्प बाह्य समानता रखते हैं, किन्तु इनमें से प्रत्येक गुणों की हमारी सहज धारणा को संतुष्ट करता है, जैसे यादृच्छिक अनुक्रम होना चाहिए: यादृच्छिक अनुक्रम असंगत होना चाहिए, उन्हें यादृच्छिकता के लिए सांख्यिकीय परीक्षण उत्तीर्ण करना चाहिए, और उन पर पैसे का दांव लगाना कठिन होना चाहिए। मार्टिन-लोफ यादृच्छिकता की इन अनेक परिभाषाओं का अस्तित्व और संगणना के विभिन्न रचनाओं के अनुसार इन परिभाषाओं की स्थिरता इस बात का प्रमाण देती है, कि मार्टिन-लोफ यादृच्छिकता गणित की मौलिक गुण है और मार्टिन-लोफ के विशेष रचना की संयोग नहीं है। शोध प्रबन्ध कि मार्टिन-लोफ यादृच्छिकता की परिभाषा सही रूप से यादृच्छिकता की सहज धारणा को ग्रहण करती है, मार्टिन-लोफ-चैटिन शोध प्रबन्ध कहलाती है, यह कुछ सीमा तक चर्च- परिगणन शोध प्रबन्ध के समान है।<ref>[[Jean-Paul Delahaye]], [https://books.google.com/books?id=EDoXdoz-qYQC&pg=PA145&source=gbs_toc_r&cad=0_0 Randomness, Unpredictability and Absence of Order], in ''Philosophy of Probability'', p. 145–167, Springer 1993.</ref>
+== तीन सामान्य परिभाषाएँ ==
+मार्टिन-लोफ की यादृच्छिक अनुक्रम की मूल परिभाषा रचनात्मक शून्य आवरण के संदर्भ में थी, उन्होंने अनुक्रम को यादृच्छिक होने के लिए परिभाषित किया यदि यह ऐसे किसी आवरण में समाहित नहीं है। [[ग्रेगरी चैतिन]], [[लियोनिद लेविन]] और [[क्लॉस-पीटर Schnorr|क्लॉस-पीटर श्नोरर]] ने [[कोलमोगोरोव जटिलता|एल्गोरिथम जटिलता]] के संदर्भ में लक्षण वर्णन सिद्ध किया कि यह अनुक्रम यादृच्छिक है यदि इसके प्रारंभिक खंडों की संपीडनशीलता पर समान सीमा है। श्नॉर ने मार्टिंगेल (संभाव्यता सिद्धांत) के संदर्भ में तीसरी समकक्ष परिभाषा दी है। ली और वितानी की किताब ''[http://homepages.cwi.nl/~paulv/kolmogorov.html एन इंट्रोडक्शन टू कोलोगोरोव कॉम्प्लेक्सिटी एंड इट्स एप्लिकेशन]'' इन विचारों का मानक परिचय है।
-== तीन समकक्ष परिभाषाएँ ==
+* 'एल्गोरिथमिक जटिलता' (चैटिन 1969, श्नोर 1973, लेविन 1973): एल्गोरिथम जटिलता (जिसे उपसर्ग-मुक्त एल्गोरिथम जटिलता या कार्य आकार जटिलता के रूप में भी जाना जाता है) को परिमित अनुक्रम (अक्षरों या द्विचर अंकों का) की एल्गोरिथम संपीड्यता पर निचली सीमा के रूप में विचार करा जा सकता है। यह ऐसे प्रत्येक अनुक्रम को प्राकृतिक संख्या K(w) प्रदान करता है, जो सहज रूप से, कंप्यूटर कार्य की न्यूनतम लंबाई को मापता है (कुछ निश्चित कार्यरचना भाषा में लिखा गया है) जो कोई इनपुट नहीं लेता है और प्रवाह पर आउटपुट w देता है। जटिलता को उपसर्ग-मुक्त होना आवश्यक है: कार्य (0 और 1 का अनुक्रम) के पश्चात् 0s की अनंत शृंखला होती है, और कार्यरचना की लंबाई (यह मानते हुए कि यह रुकती है) में कार्य के दाईं ओर शून्य की संख्या सम्मिलित होती है, जिसे विश्वव्यापी ट्यूरिंग यंत्र अध्यन करता है। अतिरिक्त आवश्यकता की आवश्यकता है क्योंकि हम लंबाई चयन कर सकते हैं, जैसे कि लंबाई उप-शृंखला के बारे में जानकारी को चिन्हित करती है। एक प्राकृतिक संख्या c और अनुक्रम w को देखते हुए हम कहते हैं कि यदि <math>K(w) \geq |w| - c </math>. है तो w, c-असंपीड्य है।
+: एक अनंत अनुक्रम S मार्टिन-लोफ़ यादृच्छिक है और मात्र यदि कोई स्थिरांक c है, जैसे कि S के सभी परिमित [[उपसर्ग (कंप्यूटर विज्ञान)]] c-असंपीड्य हैं।
-मार्टिन-लोफ की एक यादृच्छिक अनुक्रम की मूल परिभाषा रचनात्मक नल कवर के संदर्भ में थी; उन्होंने एक अनुक्रम को यादृच्छिक होने के लिए परिभाषित किया यदि यह ऐसे किसी आवरण में समाहित नहीं है। [[ग्रेगरी चैतिन]], [[लियोनिद लेविन]] और [[क्लॉस-पीटर Schnorr]] ने [[कोलमोगोरोव जटिलता]] के संदर्भ में एक लक्षण वर्णन सिद्ध किया: एक अनुक्रम यादृच्छिक है यदि इसके प्रारंभिक खंडों की संपीडनशीलता पर एक समान सीमा है। श्नॉर ने मार्टिंगेल (संभाव्यता सिद्धांत) के संदर्भ में तीसरी समकक्ष परिभाषा दी। ली और वितानी की किताब [http://homepages.cwi.nl/~paulv/kolmogorov.html कोलमोगोरोव कॉम्प्लेक्सिटी एंड इट्स एप्लिकेशन का एक परिचय] इन विचारों का मानक परिचय है।
+*रचनात्मक शून्य आवरण (मार्टिन-लोफ 1966): यह मार्टिन-लोफ की मूल परिभाषा है। परिमित द्विचर शृंखला w के लिए हम C<sub>w</sub> को w माध्यम से उत्पन्न बेलन को निरूपित करने देते हैं। यह w से प्रारंभ होने वाले समस्त अनंत अनुक्रमों का समुच्चय है, जो [[कैंटर स्पेस|कैंटर अंतराल]] में मूल विवृत समुच्चय है। w के माध्यम से उत्पन्न बेलन का उत्पाद माप (गणित) μ(C<sub>w</sub>) 2<sup>−|''w''|</sup> के रूप में परिभाषित किया गया है। प्रगायक अंतराल का प्रत्येक विवृत उपसमुच्चय असंयुक्त मूलभूत विवृत समुच्चय के गणनीय अनुक्रम का संघ है, और विवृत समुच्चय का माप ऐसे किसी भी अनुक्रम के उपायों का योग है। प्रभावी विवृत समुच्चय विवृत समुच्चयों है जो द्विचर शृंखला के पुनरावर्ती गणना योग्य अनुक्रम के माध्यम से निर्धारित मूलभूत विवृत समुच्चय के अनुक्रम का संघ है। रचनात्मक शून्य आवरण या प्रभावी माप 0 समुच्चय, प्रभावी विवृत समुच्चयों का पुनरावर्ती रूप से गणना योग्य अनुक्रम <sup><math>U_i</math> है, जैसे कि प्रत्येक प्राकृतिक संख्या के लिए <sup><math>U_{i+1} \subseteq U_i</math> और <sup><math>\mu (U_i) \leq 2^{-i}</math> एवं i.प्रत्येक प्रभावी शून्य आवरण माप 0 का <math>G_\delta</math> समुच्चय निर्धारित करता है, अर्थात् समुच्चय <sup><math>U_i</math> का प्रतिच्छेदन है।
+: एक अनुक्रम को मार्टिन-लोफ यादृच्छिक के रूप में परिभाषित किया गया है यदि यह रचनात्मक शून्य आवरण के माध्यम से निर्धारित किसी भी <math>G_\delta</math> समुच्चय में सम्मलित नहीं है।
-* 'एल्गोरिथमिक जटिलता' (चैटिन 1969, श्नोर 1973, लेविन 1973): एल्गोरिथम जटिलता (जिसे (उपसर्ग-मुक्त) कोलमोगोरोव जटिलता या प्रोग्राम-साइज़ जटिलता के रूप में भी जाना जाता है) को परिमित की एल्गोरिथम संपीड्यता पर एक निचली सीमा के रूप में सोचा जा सकता है। अनुक्रम (अक्षरों या द्विचर अंकों का)। यह ऐसे प्रत्येक अनुक्रम w को एक प्राकृतिक संख्या K(w) प्रदान करता है, जो सहजता से, एक कंप्यूटर प्रोग्राम की न्यूनतम लंबाई को मापता है (कुछ निश्चित प्रोग्रामिंग भाषा में लिखा गया है) जो कोई इनपुट नहीं लेता है और रन होने पर आउटपुट w करेगा। उपसर्ग-मुक्त होने के लिए जटिलता आवश्यक है: कार्यक्रम (0 और 1 का एक क्रम) 0s की एक अनंत स्ट्रिंग के माध्यम से  पीछा किया जाता है, और कार्यक्रम की लंबाई (इसे रोकते हुए) के दाईं ओर शून्य की संख्या सम्मिलित  होती है प्रोग्राम जिसे यूनिवर्सल  परिगणन  मशीन पढ़ती है। अतिरिक्त आवश्यकता की आवश्यकता है क्योंकि हम एक लंबाई चुन सकते हैं जैसे कि लंबाई सबस्ट्रिंग के बारे में जानकारी को कोड करती है। एक प्राकृतिक संख्या c और एक अनुक्रम w को देखते हुए, हम कहते हैं कि w 'c-incompressible' है, यदि <math>K(w) \geq |w| - c </math>.
+* रचनात्मक मार्टिंगेल्स (श्नर 1971): मार्टिंगेल (संभाव्यता सिद्धांत) कार्य है <math>d:\{0,1\}^*\to[0,\infty)</math> ऐसा है कि, समस्त परिमित श्रृंखला w के लिए, <math>d(w) = (d(w^\smallfrown 0) + d(w^\smallfrown 1))/2</math>, जिस स्थान पर <math>a^\smallfrown b</math> श्रृंखला a और b का संयोजन है। इसे निष्पक्षता की स्थिति कहा जाता है: यदि मार्टिंगेल को शर्त की रणनीति के रूप में देखा जाता है, तब उपरोक्त शर्त के लिए आवश्यक है कि शर्त उचित बाधाओं के विरुद होनी चाहिए। मार्टिंगेल डी को अनुक्रम S पर 'सफल' माना जाता है यदि <math>\limsup_{n\to\infty} d(S \upharpoonright n) = \infty,</math> जिस स्थान पर <math>S \upharpoonright n</math> S के पूर्व n बिंदु हैं। मार्टिंगेल डी रचनात्मक है (जिसे अशक्त रूप से गणना योग्य अल्प अर्ध-गणना के रूप में भी जाना जाता है) यदि कोई गणना योग्य कार्य <math>\widehat{d}:\{0,1\}^*\times\N\to{\mathbb{Q}}</math> उपस्थित है, जैसे कि समस्त परिमित द्विचर शृंखला के लिए w है
-: एक अनंत अनुक्रम एस मार्टिन-लोफ यादृच्छिक है यदि और केवल यदि एक निरंतर सी है जैसे कि एस के समस्त  परिमित [[उपसर्ग (कंप्यूटर विज्ञान)]] सी-असंपीड़ित हैं।
+# <math>\widehat{d}(w,t) \leq \widehat{d}(w,t+1) < d(w),</math> समस्त धनात्मक पूर्णांक के लिए t है
+# <math>\lim_{t\to\infty} \widehat{d}(w,t) = d(w).</math> : अनुक्रम मार्टिन-लोफ यादृच्छिक है और यदि कोई रचनात्मक मार्टिंगेल सफल नहीं होता है।
-* 'कंस्ट्रक्टिव नल कवर' (मार्टिन-लोफ 1966): यह मार्टिन-लोफ की मूल परिभाषा है। एक परिमित द्विचर स्ट्रिंग w के लिए हम C<sub>w</sub>डब्ल्यू 'के माध्यम से  उत्पन्न सिलेंडर' निरूपित करें। यह डब्ल्यू से प्रारंभ  होने वाले समस्त  अनंत अनुक्रमों का समुच्चय है, जो [[कैंटर स्पेस]] में एक मूल खुला समुच्चय है। 'उत्पाद माप (गणित)' μ(C<sub>w</sub>) w के माध्यम से  उत्पन्न सिलेंडर को 2 के रूप में परिभाषित किया गया है<sup>-|व|</सुप>. कैंटर स्पेस का प्रत्येक खुला उपसमुच्चय असंयुक्त मूल खुले समुच्चयों के एक गणनीय अनुक्रम का संघ है, और एक खुले समुच्चय का माप ऐसे किसी अनुक्रम के उपायों का योग है। एक प्रभावी ओपन समुच्चय एक ओपन समुच्चय है जो द्विचर स्ट्रिंग्स के पुनरावर्ती गणना योग्य अनुक्रम के माध्यम से  निर्धारित मूलभूतओपन समुच्चय के अनुक्रम का संघ है। एक रचनात्मक नल कवर या प्रभावी उपाय 0 समुच्चय एक पुनरावर्ती गणना योग्य अनुक्रम है <math>U_i</math> ऐसे प्रभावी खुले समुच्चयों की <math>U_{i+1} \subseteq U_i</math> और <math>\mu (U_i) \leq 2^{-i}</math> प्रत्येक प्राकृतिक संख्या के लिए मैं। प्रत्येक प्रभावी नल कवर जी-डेल्टा समुच्चय निर्धारित करता है<math>G_\delta</math> माप 0 का समुच्चय, अर्थात् समुच्चय का प्रतिच्छेदन <math>U_i</math>.
-: एक अनुक्रम को मार्टिन-लोफ रैंडम के रूप में परिभाषित किया जाता है यदि यह किसी में निहित नहीं है <math>G_\delta</math> एक रचनात्मक नल कवर के माध्यम से  निर्धारित समुच्चय।
-* 'कंस्ट्रक्टिव मार्टिंगेल्स' (श्नोर 1971): ए मार्टिंगेल (संभाव्यता सिद्धांत) एक कार्य है <math>d:\{0,1\}^*\to[0,\infty)</math> ऐसा है कि, समस्त  परिमित तार w के लिए, <math>d(w) = (d(w^\smallfrown 0) + d(w^\smallfrown 1))/2</math>, कहाँ पे <math>a^\smallfrown b</math> तार a और b का संयोजन है। इसे निष्पक्षता की स्थिति कहा जाता है: यदि मार्टिंगेल को सट्टेबाजी की रणनीति के रूप में देखा जाता है, तब  उपरोक्त शर्त के लिए आवश्यक है कि सट्टेबाज उचित बाधाओं के खिलाफ खेले। एक मार्टिंगेल डी को अनुक्रम एस पर 'सफल' कहा जाता है यदि <math>\limsup_{n\to\infty} d(S \upharpoonright n) = \infty,</math> कहाँ पे <math>S \upharpoonright n</math> एस के पूर्व  एन बिट्स हैं। एक मार्टिंगेल डी 'रचनात्मक' है (जिसे 'अशक्त गणना योग्य', 'कम अर्ध-गणना योग्य' के रूप में भी जाना जाता है) यदि कोई गणना योग्य कार्य उपस्थित है <math>\widehat{d}:\{0,1\}^*\times\N\to{\mathbb{Q}}</math> ऐसा है कि, समस्त  परिमित द्विचर स्ट्रिंग्स के लिए w
-# <math>\widehat{d}(w,t) \leq \widehat{d}(w,t+1) < d(w),</math> समस्त  धनात्मक पूर्णांक टी के लिए,
-# <math>\lim_{t\to\infty} \widehat{d}(w,t) = d(w).</math> : एक अनुक्रम मार्टिन-लोफ यादृच्छिक है यदि और केवल यदि कोई रचनात्मक मार्टिंगेल सफल नहीं होता है।
 == परिभाषाओं की व्याख्या ==
-कोल्मोगोरोव जटिलता लक्षण वर्णन अंतर्ज्ञान को व्यक्त करता है कि एक यादृच्छिक अनुक्रम असंपीड़ित है: उपसर्ग से बहुत कम प्रोग्राम के माध्यम से  कोई उपसर्ग नहीं बनाया जा सकता है।
+कोल्मोगोरोव जटिलता लक्षण वर्णन अंतर्ज्ञान को व्यक्त करता है कि यादृच्छिक अनुक्रम असंपीड़ित है: उपसर्ग से बहुत कम कार्य के माध्यम से कोई उपसर्ग नहीं बनाया जा सकता है।
-अशक्त आवरण लक्षण वर्णन अंतर्ज्ञान बताता है कि एक यादृच्छिक वास्तविक संख्या में ऐसी कोई गुण नहीं होनी चाहिए जो असामान्य हो। प्रत्येक माप 0 समुच्चय को एक असामान्य गुण के रूप में माना जा सकता है। अनुक्रम के लिए बिना माप के 0 समुच्चय में झूठ बोलना संभव नहीं है, क्योंकि प्रत्येक एक-बिंदु समुच्चय में माप 0 है। मार्टिन-लोफ का विचार परिभाषा को 0 समुच्चयों को मापने के लिए सीमित करना था जो प्रभावी रूप से वर्णित हैं; एक प्रभावी नल कवर की परिभाषा प्रभावी रूप से वर्णित माप 0 समुच्चयों का एक गणनीय संग्रह निर्धारित करती है और अनुक्रम को यादृच्छिक होने के लिए परिभाषित करती है यदि यह इनमें से किसी विशेष माप 0 समुच्चय में नहीं है। चूंकि माप 0 समुच्चय के एक गणनीय संग्रह के मिलन का माप 0 है, इसलिए यह परिभाषा तुरंत प्रमेय की ओर ले जाती है कि यादृच्छिक अनुक्रमों का एक माप 1 समुच्चय है। ध्यान दें कि यदि हम वास्तविक संख्याओं के अंतराल [0,1] के साथ द्विचर अनुक्रमों के कैंटर स्पेस की पहचान करते हैं, तब  कैंटर स्पेस पर माप लेबेसेग माप से सहमत है।
-ज़रेबंद लक्षण वर्णन अंतर्ज्ञान बताता है कि कोई भी प्रभावी प्रक्रिया एक यादृच्छिक अनुक्रम के खिलाफ पैसे की सट्टेबाजी करने में सक्षम नहीं होनी चाहिए। मार्टिंगेल डी एक सट्टेबाजी की रणनीति है। d एक परिमित स्ट्रिंग w पढ़ता है और अगले बिट पर पैसा लगाता है। यह अपने पैसे के कुछ अंश पर शर्त लगाता है कि अगला बिट 0 होगा, और उसके पश्चात् का शेष पैसा होगा कि अगला बिट 1 होगा। d उस पैसे को दोगुना कर देता है जो वास्तव में हुआ था, और यह बाकी को खो देता है। d(w) वह राशि है जो स्ट्रिंग w को देखने के पश्चात् उसके पास होती है। चूँकि स्ट्रिंग w को देखने के पश्चात् लगाई गई बेट की गणना d(w), d(w0), और d(w1) के मानों से की जा सकती है, इसके पास उपस्थित धनराशि की गणना करना बेट की गणना करने के सामान्य है। ज़रेबंद लक्षण वर्णन कहता है कि किसी भी कंप्यूटर के माध्यम से  प्रयुक्त की जाने वाली कोई भी सट्टेबाजी की रणनीति (रचनात्मक रणनीतियों के अशक्त अर्थों में भी, जो आवश्यक रूप से संगणनीय नहीं हैं) एक यादृच्छिक अनुक्रम पर पैसे की सट्टेबाजी कर सकती है।
+अशक्त आवरण लक्षण वर्णन अंतर्ज्ञान बताता है कि यादृच्छिक वास्तविक संख्या में ऐसी कोई गुण नहीं होनी चाहिए जो असामान्य हो। प्रत्येक माप 0 समुच्चय को असामान्य गुण के रूप में माना जा सकता है। अनुक्रम के लिए बिना माप 0 समुच्चय के बिना संभव नहीं है, क्योंकि प्रत्येक एक-बिंदु समुच्चय में माप 0 है। मार्टिन-लोफ का विचार परिभाषा को 0 समुच्चयों को मापने के लिए सीमित करना था जो प्रभावी रूप से वर्णित हैं; एक प्रभावी शून्य आवरण की परिभाषा प्रभावी रूप से वर्णित माप 0 समुच्चयों का गणनीय संग्रह निर्धारित करती है और अनुक्रम को यादृच्छिक होने के लिए परिभाषित करती है यदि यह इनमें से किसी विशेष माप 0 समुच्चय में नहीं है। चूंकि माप 0 समुच्चय के गणनीय संग्रह के संबंध का माप 0 है, इसलिए यह परिभाषा तत्काल प्रमेय की ओर ले जाती है, कि यादृच्छिक अनुक्रमों का माप 1 समुच्चय है। ध्यान दें कि यदि हम वास्तविक संख्याओं के अंतराल [0,1] के साथ द्विचर अनुक्रमों के कैंटर अंतराल की अभिज्ञान करते हैं, तब कैंटर अंतराल पर माप लेबेसेग माप से सहमत है।मार्टिंगेल लक्षण वर्णन अंतर्ज्ञान बताता है कि कोई भी प्रभावी प्रक्रिया यादृच्छिक अनुक्रम के सट्टेबाजी से चलन करने में सक्षम नहीं होनी चाहिए। मार्टिंगेल डी शर्त की रणनीति है। d एक परिमित शृंखला w का अध्यन करता है और आगामी योजना पर चलन करता है। यह अपने प्रचलन के कुछ अंश पर शर्त लगाता है कि आगामी अंश 0 होगा, और उसके पश्चात् का शेष चलन होगा कि आगामी अंश 1 होगा। d उस अंश पर लगाए गए मुद्रा को दोगुना कर देता है जो वास्तव में घटित हुआ था और वह शेष को लुप्त कर देता है। d(w) शृंखला w को देखने के पश्चात् उसके पास उपस्थित राशि है। चूँकि शृंखला w को देखने के पश्चात् लगाई गई अंश की गणना d(w), d(w0), और d(w1) के मानों से की जा सकती है, इसके पास उपस्थित धनराशि की गणना करना अंश की गणना करने के सामान्य है। मार्टिंगेल लक्षण वर्णन कहता है कि किसी भी कंप्यूटर के माध्यम से प्रयुक्त की जाने वाली कोई भी शर्त की रणनीति (रचनात्मक रणनीतियों के अशक्त अर्थों में भी, जो आवश्यक रूप से संगणनीय नहीं हैं) यादृच्छिक अनुक्रम पर धनराशि की शर्त कर सकती है।
 == मार्टिन-लोफ यादृच्छिक अनुक्रमों के गुण और उदाहरण ==
-*चैटिन स्थिरांक|चैटिन की रुकने की संभावना Ω एक यादृच्छिक अनुक्रम का एक उदाहरण है।
+*चैटिन स्थिरांक की स्थिरांक की संभावना Ω यादृच्छिक अनुक्रम का उदाहरण है।
-* रैंड<sup>c</sup> (रैंड का [[पूरक (सेट सिद्धांत)|पूरक (समुच्चय सिद्धांत)]]) समस्त  अनंत अनुक्रमों के समुच्चय का एक माप (गणित) 0 उप-समुच्चय है। यह इस तथ्य से निहित है कि प्रत्येक रचनात्मक शून्य कवर में माप 0 समुच्चय सम्मिलित  होता है, केवल [[गणनीय]] रचनात्मक शून्य कवर होते हैं, और माप 0 समुच्चय के एक गणनीय संघ में माप 0 होता है। इसका तात्पर्य है कि RAND एक माप 1 समुच्चय का उप-समुच्चय है समस्त  अनंत क्रम।
+* रैंड<sup>c</sup> (रैंड का [[पूरक (सेट सिद्धांत)|पूरक (समुच्चय सिद्धांत)]]) समस्त अनंत अनुक्रमों के समुच्चय का माप (गणित) 0 उप-समुच्चय है। यह इस तथ्य से निहित है कि प्रत्येक रचनात्मक शून्य आवरण में माप 0 समुच्चय सम्मिलित होता है, मात्र [[गणनीय]] रचनात्मक शून्य आवरण होते हैं, और माप 0 समुच्चय के गणनीय संघ में माप 0 होता है। इसका तात्पर्य है कि रैंड समस्त अनंत क्रम के समुच्चय का माप 1 उप-समुच्चय है।
-* हर यादृच्छिक क्रम [[सामान्य संख्या]] है।
+* प्रत्येक यादृच्छिक क्रम [[सामान्य संख्या]] है।
-* रैंड का एक रचनात्मक अशक्त आवरण है<sup>सी</sup>. इसका कारणयह है कि यादृच्छिकता के लिए समस्त  प्रभावी परीक्षण (अर्थात्, रचनात्मक नल कवर), एक मायने में, यादृच्छिकता के लिए इस सार्वभौमिक परीक्षण के माध्यम से  सम्मिलित हैं, क्योंकि कोई भी अनुक्रम जो यादृच्छिकता के लिए इस एकल परीक्षा को पास करता है, यादृच्छिकता के लिए समस्त  परीक्षणों को पारित करेगा। (मार्टिन-लोफ 1966)
+* रैंड<sup>c</sup> का रचनात्मक अशक्त आवरण है। इसका कारण यह है कि यादृच्छिकता के लिए समस्त प्रभावी परीक्षण (अर्थात्, रचनात्मक शून्य आवरण), एक रूप में, यादृच्छिकता के लिए इस सार्वभौमिक परीक्षण के माध्यम से सम्मिलित हैं, क्योंकि कोई भी अनुक्रम जो यादृच्छिकता के लिए इस एकल परीक्षा को उत्तीर्ण करता है, यादृच्छिकता के लिए समस्त परीक्षणों को पारित करेगा। (मार्टिन-लोफ 1966)
-* एक सार्वभौमिक रचनात्मक मार्टिंगेल 'डी' है। यह मार्टिंगेल इस मायने में सार्वभौमिक है कि, किसी रचनात्मक मार्टिंगेल डी को देखते हुए, यदि डी अनुक्रम पर सफल होता है, तब  'डी' उस क्रम पर भी सफल होता है। इस प्रकार, रैंड में हर क्रम पर 'डी' सफल होता है<sup>c</sup> (लेकिन, चूंकि d रचनात्मक है, यह RAND में बिना किसी क्रम के सफल होता है)। (श्नोर 1971)
+* एक सार्वभौमिक रचनात्मक मार्टिंगेल 'डी' है। यह मार्टिंगेल इस रूप में सार्वभौमिक है कि, किसी रचनात्मक मार्टिंगेल डी को देखते हुए, यदि d अनुक्रम पर सफल होता है, तब 'd' उस क्रम पर भी सफल होता है। इस प्रकार, रैंड में प्रत्येक क्रम पर 'd' सफल होता है<sup>c</sup> (किन्तु, चूंकि d रचनात्मक है, यह रैंड में बिना किसी क्रम के सफल होता है)। (श्नोर 1971)
-* वर्ग रैंड एक है <math>\Sigma^0_2</math> कैंटर स्पेस का उप-समुच्चय, जहां <math>\Sigma^0_2</math> [[अंकगणितीय पदानुक्रम]] के दूसरे स्तर को संदर्भित करता है। ऐसा इसलिए है क्योंकि एक अनुक्रम S RAND में है यदि और केवल यदि सार्वभौमिक प्रभावी अशक्त आवरण में कुछ खुला समुच्चय है जिसमें S सम्मिलित  नहीं है; इस गुण को a के माध्यम से  परिभाषित किया जा सकता है <math>\Sigma^0_2</math> सूत्र।
+* वर्ग रैंड , कैंटर अंतराल का <math>\Sigma^0_2</math> उपसमुच्चय है जिस स्थान पर <math>\Sigma^0_2</math> [[अंकगणितीय पदानुक्रम]] के दूसरे स्तर को संदर्भित करता है। ऐसा इसलिए है क्योंकि अनुक्रम S रैंड में है और मात्र यदि सार्वभौमिक प्रभावी अशक्त आवरण में कुछ विवृत समुच्चय है जिसमें S सम्मिलित नहीं है; इस गुण को <math>\Sigma^0_2</math> सूत्र के माध्यम से परिभाषित किया जा सकता है।
-* एक यादृच्छिक क्रम है जो है <math>\Delta^0_2</math>, अर्थात्, हॉल्टिंग समस्या के लिए एक ऑरेकल के सापेक्ष संगणनीय। (Schnorr 1971) Chaitin's Chaitin's constant|Ω ऐसे अनुक्रम का एक उदाहरण है।
+* एक यादृच्छिक क्रम है जो <math>\Delta^0_2</math> है, अर्थात्, स्थिरांक समस्या के लिए दैवज्ञ के सापेक्ष गणना योग्य है।। (श्नोरर 1971) चैतीन Ω ऐसे अनुक्रम का उदाहरण है।
-* कोई यादृच्छिक अनुक्रम [[निर्णायकता (तर्क)]], संगणनीय रूप से [[गणना योग्य]], या संगणनीय रूप से गणना योग्य | सह-गणना योग्य-गणनीय नहीं है। चूंकि यह इसके अनुरूप हैं <math>\Delta_1^0</math>, <math>\Sigma_1^0</math>, और <math>\Pi_1^0</math> अंकगणितीय पदानुक्रम के स्तर, इसका कारणहै कि <math>\Delta_2^0</math> अंकगणितीय पदानुक्रम में सबसे निचला स्तर है जहाँ यादृच्छिक क्रम पाया जा सकता है।
+* कोई यादृच्छिक अनुक्रम [[निर्णायकता (तर्क)]], संगणनीय रूप से [[गणना योग्य]], या सह-गणना योग्य नहीं है। चूँकि यह अंकगणितीय पदानुक्रम के <math>\Delta_1^0</math>, <math>\Sigma_1^0</math>, और <math>\Pi_1^0</math> स्तरों के अनुरूप हैं, इसका अर्थ है कि <math>\Delta_2^0</math> अंकगणितीय पदानुक्रम में सबसे निचला स्तर है जिस स्थान पर यादृच्छिक अनुक्रम प्राप्त करे जा सकते हैं।
-* हर क्रम कुछ यादृच्छिक अनुक्रम के लिए  [[ट्यूरिंग रिड्यूसिबल|परिगणन  रिड्यूसिबल]] है। (कुचेरा 1985/1989, पेटर जीएसी। जीएसी 1986)। इस प्रकार इच्छानुसारसे उच्च  [[ट्यूरिंग डिग्री|परिगणन  डिग्री]] के यादृच्छिक क्रम हैं।
+* प्रत्येक क्रम कुछ यादृच्छिक अनुक्रम के लिए [[ट्यूरिंग रिड्यूसिबल|परिगणन रूपांतरित]] है। (कुचेरा 1985/1989, पेटर जीएसी। जीएसी 1986)। इस प्रकार इच्छानुसार से उच्च [[ट्यूरिंग डिग्री|परिगणन उपाधि]] के यादृच्छिक क्रम हैं।
 == सापेक्ष यादृच्छिकता ==
-जैसा कि मार्टिन-लोफ यादृच्छिक अनुक्रम की प्रत्येक समतुल्य परिभाषा कुछ  परिगणन  मशीन के माध्यम से  गणना योग्य है, पर आधारित है, कोई स्वाभाविक रूप से पूछ सकता है कि  परिगणन  ऑरेकल मशीन के माध्यम से  गणना योग्य क्या है। एक निश्चित ओरेकल ए के लिए, एक अनुक्रम बी जो न केवल यादृच्छिक है किन्तु कि वास्तव में, ए के सापेक्ष संगणनीयता के लिए समकक्ष परिभाषाओं को संतुष्ट करता है (उदाहरण के लिए, कोई मार्टिंगेल जो ऑरैकल ए के सापेक्ष रचनात्मक है, बी पर सफल होता है) को यादृच्छिक रिश्तेदार कहा जाता है ए के लिए। दो अनुक्रम, जबकि स्वयं यादृच्छिक होते हैं, उनमें बहुत समान जानकारी हो सकती है, और इसलिए कोई भी दूसरे के सापेक्ष यादृच्छिक नहीं होगा। किसी भी समय एक अनुक्रम से दूसरे अनुक्रम में  [[ट्यूरिंग कमी|परिगणन  कमी]] होती है, दूसरा क्रम पूर्व  के सापेक्ष यादृच्छिक नहीं हो सकता है, जैसे कि गणनीय अनुक्रम स्वयं गैर-यादृच्छिक होते हैं; विशेष रूप से, इसका अर्थ है कि चैटिन का स्थिरांक|चैटिन का Ω हॉल्टिंग समस्या के सापेक्ष यादृच्छिक नहीं है।
+जैसा कि मार्टिन-लोफ यादृच्छिक अनुक्रम की प्रत्येक समतुल्य परिभाषा कुछ परिगणन यंत्र के माध्यम से गणना योग्य है, और आधारित है, कोई स्वाभाविक रूप से प्रश्न कर सकता है कि परिगणन दैवज्ञ यंत्र के माध्यम से गणना क्या योग्य है। निश्चित दैवज्ञ A के लिए, अनुक्रम B जो न मात्र यादृच्छिक है किन्तु कि वास्तव में, A के सापेक्ष संगणनीयता के लिए समकक्ष परिभाषाओं को संतुष्ट करता है (उदाहरण के लिए, कोई मार्टिंगेल जो दैवज्ञ A के सापेक्ष रचनात्मक है, B पर सफल होता है) को यादृच्छिक A के लिए सापेक्ष कहा जाता है। दो अनुक्रम, जबकि स्वयं यादृच्छिक होते हैं, उनमें बहुत समान जानकारी हो सकती है, और इसलिए कोई भी दूसरे के सापेक्ष यादृच्छिक नहीं होता है। किसी भी समय अनुक्रम से दूसरे अनुक्रम में [[ट्यूरिंग कमी|परिगणन कमी]] होती है, दूसरा क्रम पूर्व के सापेक्ष यादृच्छिक नहीं हो सकता है, जैसे कि गणनीय अनुक्रम स्वयं गैर-यादृच्छिक होते हैं; विशेष रूप से, इसका अर्थ है कि चैटिन का Ω स्थिरांक समस्या के सापेक्ष यादृच्छिक नहीं है।
-सापेक्ष यादृच्छिकता से संबंधित एक महत्वपूर्ण परिणाम मिचेल वैन लैंबलजेन प्रमेय है, जिसमें कहा गया है कि यदि सी ए और बी से बना अनुक्रम है, ए के पूर्व  बिट को इंटरलीविंग करके, बी का पहला बिट, ए का दूसरा बिट, ए का दूसरा बिट बी, और इसी तरह, फिर सी एल्गोरिदमिक रूप से यादृच्छिक है यदि और केवल यदि ए एल्गोरिदमिक रूप से यादृच्छिक है, और बी एल्गोरिदमिक रूप से ए के सापेक्ष यादृच्छिक है। एक निकट संबंधी परिणाम यह है कि यदि ए और बी दोनों स्वयं यादृच्छिक हैं, तब  ए यादृच्छिक सापेक्ष है बी यदि और केवल यदि बी ए के सापेक्ष यादृच्छिक है।
+सापेक्ष यादृच्छिकता से संबंधित महत्वपूर्ण परिणाम मिचेल वैन लैंबलजेन प्रमेय है, जिसमें कहा गया है कि यदि C, A और B से बना अनुक्रम है, तो A के पूर्व अंश को जोड़कर करके, B का प्रथम अंश, A का दूसरा अंश, A का दूसरा अंश B, और इसी तरह, पुनः C एल्गोरिदमिक रूप से यादृच्छिक है और मात्र यदि A एल्गोरिदमिक रूप से यादृच्छिक है, और B एल्गोरिदमिक रूप से A के सापेक्ष यादृच्छिक है। एक निकट संबंधी परिणाम यह है कि यदि A और B दोनों स्वयं यादृच्छिक हैं, तब A यादृच्छिक सापेक्ष है B यदि मात्र B एवं A के सापेक्ष यादृच्छिक है।
 == मार्टिन-लोफ यादृच्छिकता से अधिक शक्तिशाली ==
-सापेक्ष यादृच्छिकता हमें प्रथम  धारणा देती है जो मार्टिन-लोफ यादृच्छिकता से अधिक शक्तिशाली  है, जो कि कुछ निश्चित ऑरेकल ए के सापेक्ष यादृच्छिकता है। किसी भी ऑरेकल के लिए, यह कम से कम उतना ही शक्तिशाली  है, और अधिकांश ऑरेकल के लिए, यह सख्ती से शक्तिशाली  है, क्योंकि वहाँ होगा मार्टिन-लोफ रैंडम सीक्वेंस बनें जो कि ऑरेकल ए के सापेक्ष रैंडम नहीं हैं। महत्वपूर्ण ऑरेकल को   अधिकांशतः  हॉल्टिंग प्रॉब्लम माना जाता है, <math>\emptyset '</math>, और nth जंप ऑरेकल, <math>\emptyset^{(n)}</math>, क्योंकि यह दैवज्ञ विशिष्ट प्रश्नों का उत्तर देने में सक्षम हैं जो स्वाभाविक रूप से उत्पन्न होते हैं। एक क्रम जो ऑरेकल के सापेक्ष यादृच्छिक है <math>\emptyset^{(n-1)}</math> एन-यादृच्छिक कहा जाता है; एक अनुक्रम 1-यादृच्छिक है, इसलिए, यदि और केवल यदि यह मार्टिन-लोफ यादृच्छिक है। एक अनुक्रम जो प्रत्येक n के लिए n-यादृच्छिक होता है, अंकगणितीय रूप से यादृच्छिक कहलाता है। अधिक जटिल गुणों पर विचार करते समय कभी-कभी एन-यादृच्छिक अनुक्रम उत्पन्न होते हैं। उदाहरण के लिए, केवल गिने-चुने ही बहुत से हैं <math>\Delta^0_2</math> समुच्चय, इसलिए कोई सोच सकता है कि यह गैर-यादृच्छिक होना चाहिए। चूंकि, हॉल्टिंग प्रायिकता चैटिन का स्थिरांक|Ω है <math>\Delta^0_2</math> और 1-यादृच्छिक; यह 2-यादृच्छिकता तक पहुँचने के पश्चात् ही होता है कि एक यादृच्छिक समुच्चय होना असंभव है <math>\Delta^0_2</math>.
+सापेक्ष यादृच्छिकता हमें प्रथम धारणा देती है जो मार्टिन-लोफ यादृच्छिकता से अधिक शक्तिशाली है, जो कि कुछ निश्चित दैवज्ञ A के सापेक्ष यादृच्छिकता है। किसी भी दैवज्ञ के लिए, यह कम से कम उतना ही शक्तिशाली है, और अधिकांश दैवज्ञ के लिए, यह दृढता से शक्तिशाली है, क्योंकि मार्टिन-लोफ यादृच्छिक अनुक्रम होंगे जो दैवज्ञ A के सापेक्ष यादृच्छिक नहीं हैं। महत्वपूर्ण दैवज्ञ को अधिकांशतः स्थिरांक समस्या <math>\emptyset '</math> और नौवीं व्यतिक्रम दैवज्ञ <math>\emptyset^{(n)}</math> माना जाता है, क्योंकि यह दैवज्ञ स्वाभाविक रूप से उत्पन्न होने वाले विशिष्ट प्रश्नों का उत्तर देने में सक्षम होते हैं। एक क्रम जो दैवज्ञ <math>\emptyset^{(n-1)}</math> के सापेक्ष यादृच्छिक है उसे n-यादृच्छिक कहा जाता है। अनुक्रम 1-यादृच्छिक है, इसलिए, यदि और मात्र यह मार्टिन-लोफ यादृच्छिक है। अनुक्रम जो प्रत्येक n के लिए n-यादृच्छिक होता है, अंकगणितीय रूप से यादृच्छिक कहलाता है। अधिक जटिल गुणों पर विचार करते समय कभी-कभी n-यादृच्छिक अनुक्रम उत्पन्न होते हैं। उदाहरण के लिए, मात्र चयनित <math>\Delta^0_2</math> अनेक सेट हैं, इसलिए कोई सोच सकता है कि यह गैर-यादृच्छिक होने चाहिए। चूंकि, स्थिरांक की संभावना Ω <math>\Delta^0_2</math> और 1-यादृच्छिक है; 2-यादृच्छिकता तक पहुंचने के पश्चात् ही यादृच्छिक समुच्चय का <math>\Delta^0_2</math> होना असंभव है।
 == मार्टिन-लोफ यादृच्छिकता से अशक्त ==
-इसके अतिरिक्त, यादृच्छिकता की अनेक धारणाएँ हैं जो मार्टिन-लोफ़ यादृच्छिकता से कमज़ोर हैं। इनमें से कुछ अशक्त 1-रैंडमनेस, श्नोरर रैंडमनेस, कंप्यूटेबल रैंडमनेस, आंशिक कंप्यूटेबल रैंडमनेस हैं। योंगगे वांग ने दिखाया <ref>Yongge Wang: Randomness and Complexity. PhD Thesis, 1996, http://webpages.uncc.edu/yonwang/papers/thesis.pdf</ref> कि Schnorr यादृच्छिकता संगणनीय यादृच्छिकता से भिन्न है। इसके अतिरिक्त, कोल्मोगोरोव-लवलैंड यादृच्छिकता को मार्टिन-लोफ यादृच्छिकता से अधिक शक्तिशाली  नहीं माना जाता है, किन्तु यह ज्ञात नहीं है कि यह वास्तव में अशक्त है या नहीं।
+इसके अतिरिक्त, यादृच्छिकता की अनेक धारणाएँ हैं जो मार्टिन-लोफ़ यादृच्छिकता से अशक्त हैं। इनमें से कुछ अशक्त 1-यादृच्छिकता, श्नोरर यादृच्छिकता, गणना योग्य यादृच्छिकता, आंशिक गणना योग्य यादृच्छिकता हैं। योंगगे वांग ने दिखाया <ref>Yongge Wang: Randomness and Complexity. PhD Thesis, 1996, http://webpages.uncc.edu/yonwang/papers/thesis.pdf</ref> कि श्नोरर यादृच्छिकता संगणनीय यादृच्छिकता से भिन्न है। इसके अतिरिक्त, कोल्मोगोरोव-लवलैंड यादृच्छिकता को मार्टिन-लोफ यादृच्छिकता से अधिक शक्तिशाली नहीं माना जाता है, किन्तु यह ज्ञात नहीं है कि यह वास्तव में अशक्त है या नहीं है। यादृच्छिकता वर्णक्रम के विपरीत बिंदु पर [[के-तुच्छ सेट|K-नगण्य समुच्चय]] की धारणा है। ये समुच्चय यादृच्छिक-विरोधी हैं क्योंकि सभी प्रारंभिक खंड प्रत्येक प्रारंभिक खंड w के लिए लघुगणकीय रूप से संपीड़ित <math>K(w) \leq K(|w|) + b </math> हैं, किन्तु वे गणना योग्य नहीं हैं।
-यादृच्छिकता स्पेक्ट्रम के विपरीत छोर पर [[के-तुच्छ सेट|के-तुच्छ समुच्चय]] की धारणा है। यहसमुच्चय एंटी-रैंडम हैं क्योंकि समस्त  प्रारंभिक खंड लघुगणकीय रूप से संकुचित होते हैं (अर्थात, <math>K(w) \leq K(|w|) + b </math> प्रत्येक प्रारंभिक खंड w के लिए), किन्तु वह गणना योग्य नहीं हैं।
 == यह भी देखें ==
 * यादृच्छिक क्रम
 *ग्रेगरी चैटिन
-* [[स्टोकेस्टिक्स|प्रसंभाव्य ्स]]
+* [[स्टोकेस्टिक्स|प्रसंभाव्यस]]
 * [[मोंटे कार्लो विधि]]
-* के-तुच्छ समुच्चय
+* k-नगण्य समुच्चय
 * [[सार्वभौमिकता संभावना]]
 * [[सांख्यिकीय यादृच्छिकता]]
@@ Line 159: / Line 153: @@
   | location = Paris
   | year = 1939}}
-[[Category: अनियमितता]] [[Category: एल्गोरिथम सूचना सिद्धांत]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
 [[Category:Created On 27/01/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Missing redirects]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:अनियमितता]]
+[[Category:एल्गोरिथम सूचना सिद्धांत]]

Anonymous

Search

एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 12:15, 4 August 2023

Contents

इतिहास

तीन सामान्य परिभाषाएँ

परिभाषाओं की व्याख्या

मार्टिन-लोफ यादृच्छिक अनुक्रमों के गुण और उदाहरण

सापेक्ष यादृच्छिकता

मार्टिन-लोफ यादृच्छिकता से अधिक शक्तिशाली

मार्टिन-लोफ यादृच्छिकता से अशक्त

यह भी देखें

संदर्भ

आगे की पढाई

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम: Difference between revisions

Latest revision as of 12:15, 4 August 2023

इतिहास

तीन सामान्य परिभाषाएँ

परिभाषाओं की व्याख्या

मार्टिन-लोफ यादृच्छिक अनुक्रमों के गुण और उदाहरण

सापेक्ष यादृच्छिकता

मार्टिन-लोफ यादृच्छिकता से अधिक शक्तिशाली

मार्टिन-लोफ यादृच्छिकता से अशक्त

यह भी देखें

संदर्भ

आगे की पढाई

Navigation

Wiki tools

Page tools

Other projects

Categories