परिचय
एल्गोरिदम सर्वव्यापी हो गए हैं। वे हमारे आवागमन को अनुकूलित करते हैं, भुगतान की प्रक्रिया करते हैं और इंटरनेट ट्रैफ़िक के प्रवाह का समन्वय करते हैं। ऐसा लगता है कि प्रत्येक समस्या के लिए जिसे सटीक गणितीय शब्दों में व्यक्त किया जा सकता है, एक एल्गोरिदम है जो इसे हल कर सकता है, कम से कम सिद्धांत रूप में।
लेकिन ऐसा नहीं है - कुछ सरल प्रतीत होने वाली समस्याओं को कभी भी एल्गोरिथम से हल नहीं किया जा सकता है। अग्रणी कंप्यूटर वैज्ञानिक एलन ट्यूरिंग साबित ऐसी "अगणनीय" समस्याओं का अस्तित्व लगभग एक सदी पहले, उसी पेपर में था जहाँ उन्होंने इसे तैयार किया था गणना का गणितीय मॉडल जिसने आधुनिक कंप्यूटर विज्ञान का शुभारंभ किया।
ट्यूरिंग ने एक प्रति-सहज ज्ञान युक्त रणनीति का उपयोग करके इस अभूतपूर्व परिणाम को साबित किया: उन्होंने एक ऐसी समस्या को परिभाषित किया जो इसे हल करने के हर प्रयास को अस्वीकार कर देती है।
"मैं आपसे पूछता हूं कि आप क्या कर रहे हैं, और फिर मैं कहता हूं, 'नहीं, मैं कुछ अलग करने जा रहा हूं," कहा राहुल इलंगो, मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी में स्नातक छात्र सैद्धांतिक कंप्यूटर विज्ञान का अध्ययन कर रहा है।
ट्यूरिंग की रणनीति विकर्णीकरण नामक गणितीय तकनीक पर आधारित थी जिसका एक विशिष्ट इतिहास है। यहां उनके प्रमाण के पीछे के तर्क का एक सरलीकृत विवरण दिया गया है।
स्ट्रिंग सिद्धांत
विकर्णीकरण एक सांसारिक समस्या को हल करने के लिए एक चतुर चाल से उत्पन्न होता है जिसमें बिट्स की स्ट्रिंग शामिल होती है, जिनमें से प्रत्येक 0 या 1 हो सकती है। ऐसी स्ट्रिंग्स की एक सूची दी गई है, जो सभी समान रूप से लंबी हैं, क्या आप एक नई स्ट्रिंग उत्पन्न कर सकते हैं जो पर नहीं है सूची?
सबसे सीधी रणनीति प्रत्येक संभावित स्ट्रिंग पर बारी-बारी से विचार करना है। मान लीजिए कि आपके पास पाँच तार हैं, प्रत्येक पाँच बिट लंबा है। 00000 के लिए सूची को स्कैन करके प्रारंभ करें। यदि यह वहां नहीं है, तो आप रुक सकते हैं; यदि ऐसा है, तो आप 00001 पर जाएं और प्रक्रिया को दोहराएं। यह काफी सरल है, लेकिन लंबी स्ट्रिंग्स की लंबी सूची के लिए यह धीमा है।
विकर्णीकरण एक वैकल्पिक दृष्टिकोण है जो लापता स्ट्रिंग को थोड़ा-थोड़ा करके बनाता है। सूची में पहली स्ट्रिंग के पहले बिट से प्रारंभ करें और इसे उल्टा करें - यह आपकी नई स्ट्रिंग का पहला बिट होगा। फिर दूसरी स्ट्रिंग के दूसरे बिट को उल्टा करें और उसे नई स्ट्रिंग के दूसरे बिट के रूप में उपयोग करें, और तब तक दोहराएं जब तक आप सूची के अंत तक नहीं पहुंच जाते। आपके द्वारा फ़्लिप किए गए बिट्स यह सुनिश्चित करते हैं कि नई स्ट्रिंग कम से कम एक स्थान पर मूल सूची की प्रत्येक स्ट्रिंग से भिन्न है। (वे तारों की सूची के माध्यम से एक विकर्ण रेखा भी बनाते हैं, जिससे तकनीक को इसका नाम मिलता है।)
विकर्णीकरण को सूची में प्रत्येक स्ट्रिंग से केवल एक बिट की जांच करने की आवश्यकता होती है, इसलिए यह अक्सर अन्य तरीकों की तुलना में बहुत तेज़ होता है। लेकिन इसकी असली शक्ति इसमें निहित है कि यह अनंत के साथ कितनी अच्छी तरह खेलता है।
“तार अब अनंत हो सकते हैं; सूची अनंत हो सकती है - यह अभी भी काम करती है," कहा रयान विलियम्स, एमआईटी में एक सैद्धांतिक कंप्यूटर वैज्ञानिक।
इस शक्ति का उपयोग करने वाले पहले व्यक्ति जॉर्ज कैंटर थे, जो सेट सिद्धांत के गणितीय उपक्षेत्र के संस्थापक थे। 1873 में, कैंटर ने यह साबित करने के लिए विकर्णीकरण का उपयोग किया कि कुछ अनंत हैं दूसरों से बड़ा. छह दशक बाद, ट्यूरिंग ने कैंटर के विकर्णीकरण के संस्करण को गणना के सिद्धांत में अनुकूलित किया, जिससे इसे एक विशिष्ट विरोधाभासी स्वाद मिला।
सीमा का खेल
ट्यूरिंग उन गणितीय समस्याओं के अस्तित्व को साबित करना चाहते थे जिन्हें कोई एल्गोरिदम हल नहीं कर सकता - यानी, अच्छी तरह से परिभाषित इनपुट और आउटपुट वाली समस्याएं लेकिन इनपुट से आउटपुट तक पहुंचने के लिए कोई आसान प्रक्रिया नहीं। उन्होंने विशेष रूप से निर्णय समस्याओं पर ध्यान केंद्रित करके इस अस्पष्ट कार्य को और अधिक प्रबंधनीय बना दिया, जहां इनपुट 0 और 1 की कोई भी स्ट्रिंग हो सकती है और आउटपुट 0 या 1 हो सकता है।
यह निर्धारित करना कि क्या कोई संख्या अभाज्य है (केवल 1 और स्वयं से विभाज्य) एक निर्णय समस्या का एक उदाहरण है - एक संख्या का प्रतिनिधित्व करने वाली एक इनपुट स्ट्रिंग दी गई है, यदि संख्या अभाज्य है तो सही आउटपुट 1 है और यदि यह नहीं है तो 0 है। एक अन्य उदाहरण सिंटैक्स त्रुटियों (व्याकरण संबंधी गलतियों के समतुल्य) के लिए कंप्यूटर प्रोग्राम की जाँच करना है। वहां, इनपुट स्ट्रिंग्स अलग-अलग प्रोग्रामों के लिए कोड का प्रतिनिधित्व करते हैं - सभी प्रोग्रामों को इस तरह से दर्शाया जा सकता है, क्योंकि वे कंप्यूटर पर इसी तरह संग्रहीत और निष्पादित होते हैं - और लक्ष्य 1 आउटपुट देना है यदि कोड में कोई सिंटैक्स त्रुटि है और यदि नहीं है तो 0 आउटपुट देना है। टी।
एक एल्गोरिदम किसी समस्या को केवल तभी हल करता है जब वह हर संभावित इनपुट के लिए सही आउटपुट उत्पन्न करता है - यदि यह एक बार भी विफल हो जाता है, तो यह उस समस्या के लिए एक सामान्य-उद्देश्य वाला एल्गोरिदम नहीं है। आमतौर पर, आप पहले वह समस्या निर्दिष्ट करेंगे जिसे आप हल करना चाहते हैं और फिर एक एल्गोरिदम ढूंढने का प्रयास करेंगे जो इसे हल करता है। ट्यूरिंग ने, अघुलनशील समस्याओं की तलाश में, इस तर्क को उल्टा कर दिया - उन्होंने सभी संभावित एल्गोरिदम की एक अनंत सूची की कल्पना की और एक जिद्दी समस्या का निर्माण करने के लिए विकर्णीकरण का उपयोग किया जो सूची में प्रत्येक एल्गोरिदम को विफल कर देगा।
20 प्रश्नों के एक धांधली वाले खेल की कल्पना करें, जहां उत्तर देने वाला किसी विशेष वस्तु को ध्यान में रखकर शुरू करने के बजाय प्रत्येक प्रश्न को ना कहने का बहाना खोजता है। खेल के अंत तक, उन्होंने एक वस्तु का वर्णन किया है जो पूरी तरह से उन गुणों से परिभाषित होती है जिनमें उसका अभाव है।
ट्यूरिंग का विकर्णीकरण प्रमाण इस गेम का एक संस्करण है जहां प्रश्न संभावित एल्गोरिदम की अनंत सूची के माध्यम से चलते हैं, बार-बार पूछते हैं, "क्या यह एल्गोरिदम उस समस्या को हल कर सकता है जिसे हम असंगठित साबित करना चाहते हैं?"
विलियम्स ने कहा, "यह एक तरह के 'अनंत प्रश्न' हैं।"
गेम जीतने के लिए, ट्यूरिंग को एक ऐसी समस्या तैयार करने की ज़रूरत थी जहाँ हर एल्गोरिदम का उत्तर 'नहीं' हो। इसका मतलब एक विशेष इनपुट की पहचान करना है जो पहले एल्गोरिदम को गलत उत्तर देता है, दूसरा इनपुट जो दूसरे को विफल बनाता है, इत्यादि। उन्होंने कर्ट गोडेल द्वारा हाल ही में इस्तेमाल की गई एक ट्रिक के समान उन विशेष इनपुट को पाया साबित करना "यह कथन अप्रमाणित है" जैसे स्व-संदर्भित दावे गणित की नींव के लिए परेशानी पैदा करते हैं।
मुख्य अंतर्दृष्टि यह थी कि प्रत्येक एल्गोरिदम (या प्रोग्राम) को 0s और 1s की एक स्ट्रिंग के रूप में दर्शाया जा सकता है। इसका मतलब है, जैसा कि त्रुटि-जांच कार्यक्रम के उदाहरण में है, कि एक एल्गोरिदम किसी अन्य एल्गोरिदम के कोड को इनपुट के रूप में ले सकता है। सिद्धांत रूप में, एक एल्गोरिदम इनपुट के रूप में अपना कोड भी ले सकता है।
इस अंतर्दृष्टि के साथ, हम ट्यूरिंग के प्रमाण की तरह एक अगणनीय समस्या को परिभाषित कर सकते हैं: “एक एल्गोरिदम के कोड का प्रतिनिधित्व करने वाली एक इनपुट स्ट्रिंग दी गई है, आउटपुट 1 यदि वह एल्गोरिदम 0 आउटपुट करता है जब उसका अपना कोड इनपुट होता है; अन्यथा, आउटपुट 0. प्रत्येक एल्गोरिदम जो इस समस्या को हल करने का प्रयास करता है वह कम से कम एक इनपुट पर गलत आउटपुट उत्पन्न करेगा - अर्थात्, अपने स्वयं के कोड के अनुरूप इनपुट। इसका मतलब है कि इस विकृत समस्या को किसी भी एल्गोरिदम द्वारा हल नहीं किया जा सकता है।
नकार क्या नहीं कर सकता
कंप्यूटर वैज्ञानिक अभी तक विकर्णीकरण से नहीं गुजरे थे। 1965 में, ज्यूरिस हार्टमैनिस और रिचर्ड स्टर्न्स ने ट्यूरिंग के तर्क को अपनाया साबित करना कि सभी संगणनीय समस्याएँ समान नहीं बनाई गई हैं - कुछ दूसरों की तुलना में आंतरिक रूप से कठिन हैं। उस परिणाम ने कम्प्यूटेशनल जटिलता सिद्धांत के क्षेत्र को लॉन्च किया, जो कम्प्यूटेशनल समस्याओं की कठिनाई का अध्ययन करता है।
लेकिन जटिलता सिद्धांत ने ट्यूरिंग की विपरीत पद्धति की सीमाओं का भी खुलासा किया। 1975 में, थिओडोर बेकर, जॉन गिल और रॉबर्ट सोलोवे साबित जटिलता सिद्धांत में कई खुले प्रश्नों को केवल विकर्णीकरण द्वारा कभी भी हल नहीं किया जा सकता है। इनमें से प्रमुख प्रसिद्ध पी बनाम एनपी समस्या है, जो पूछती है कि क्या आसानी से जांचने योग्य समाधान वाली सभी समस्याओं को सही सरल एल्गोरिदम के साथ हल करना भी आसान है।
विकर्णीकरण के अंधे धब्बे उच्च स्तर के अमूर्तता का प्रत्यक्ष परिणाम हैं जो इसे इतना शक्तिशाली बनाता है। ट्यूरिंग के प्रमाण में ऐसी कोई भी अगणनीय समस्या शामिल नहीं थी जो व्यवहार में उत्पन्न हो सकती है - इसके बजाय, इसने तुरंत ही ऐसी समस्या गढ़ ली। अन्य विकर्णीकरण प्रमाण वास्तविक दुनिया से समान रूप से अलग हैं, इसलिए वे उन प्रश्नों को हल नहीं कर सकते हैं जहां वास्तविक दुनिया के विवरण मायने रखते हैं।
विलियम्स ने कहा, "वे दूर से गणना करते हैं।" "मैं एक ऐसे व्यक्ति की कल्पना करता हूं जो वायरस से निपट रहा है और कुछ दस्ताने बॉक्स के माध्यम से उन तक पहुंचता है।"
विकर्णीकरण की विफलता एक प्रारंभिक संकेत थी कि पी बनाम एनपी समस्या का समाधान होगा एक लंबी यात्रा. लेकिन अपनी सीमाओं के बावजूद, विकर्णीकरण जटिलता सिद्धांतकारों के शस्त्रागार में प्रमुख उपकरणों में से एक बना हुआ है। 2011 में, विलियम्स ने इसे कई अन्य तकनीकों के साथ मिलकर इस्तेमाल किया साबित करना गणना का एक निश्चित प्रतिबंधित मॉडल कुछ असाधारण रूप से कठिन समस्याओं को हल नहीं कर सका - एक परिणाम जो शोधकर्ताओं को 25 वर्षों तक नहीं मिला था। यह पी बनाम एनपी को हल करने से बहुत दूर था, लेकिन यह अभी भी बड़ी प्रगति का प्रतिनिधित्व करता है।
यदि आप यह साबित करना चाहते हैं कि कुछ संभव नहीं है, तो सिर्फ 'नहीं' कहने की शक्ति को कम मत समझिए।
- एसईओ संचालित सामग्री और पीआर वितरण। आज ही प्रवर्धित हो जाओ।
- प्लेटोडेटा.नेटवर्क वर्टिकल जेनरेटिव एआई। स्वयं को शक्तिवान बनाएं। यहां पहुंचें।
- प्लेटोआईस्ट्रीम। Web3 इंटेलिजेंस। ज्ञान प्रवर्धित। यहां पहुंचें।
- प्लेटोईएसजी. ऑटोमोटिव/ईवीएस, कार्बन, क्लीनटेक, ऊर्जा, पर्यावरण, सौर, कचरा प्रबंधन। यहां पहुंचें।
- प्लेटोहेल्थ। बायोटेक और क्लिनिकल परीक्षण इंटेलिजेंस। यहां पहुंचें।
- चार्टप्राइम. चार्टप्राइम के साथ अपने ट्रेडिंग गेम को उन्नत करें। यहां पहुंचें।
- BlockOffsets. पर्यावरणीय ऑफसेट स्वामित्व का आधुनिकीकरण। यहां पहुंचें।
- स्रोत: https://www.quantamagazine.org/alan-turing-and-the-power-of-negative-thinking-20230905/
- :हैस
- :है
- :नहीं
- :कहाँ
- ][पी
- $यूपी
- 1
- 20
- 2011
- 25
- a
- मतिहीनता
- लेखा
- पूर्व
- एलन
- एलन ट्यूरिंग
- कलन विधि
- एल्गोरिदम रूप से
- एल्गोरिदम
- सब
- अकेला
- भी
- के बीच में
- an
- और
- अन्य
- जवाब
- कोई
- दृष्टिकोण
- हैं
- तर्क
- उठता
- शस्त्रागार
- AS
- पूछना
- At
- बेकर
- आधारित
- BE
- बन
- पीछे
- बिट
- मुक्केबाज़ी
- बनाता है
- लेकिन
- by
- बुलाया
- कैंब्रिज
- कर सकते हैं
- मामला
- सदी
- कुछ
- जाँच
- प्रमुख
- कोड
- जटिलता
- गणना
- कंप्यूटर
- कम्प्यूटर साइंस
- कंप्यूटर्स
- विचार करना
- निर्माण
- शामिल हैं
- विपरीत
- समन्वय
- सही
- इसी
- शिल्प
- बनाया
- व्यवहार
- दशकों
- निर्णय
- परिभाषित
- परिभाषित
- वर्णित
- के बावजूद
- विवरण
- विभिन्न
- कठिनाई
- प्रत्यक्ष
- दूरी
- विशिष्ट
- do
- नहीं करता है
- कर
- dont
- से प्रत्येक
- शीघ्र
- आसानी
- आसान
- भी
- समाप्त
- पर्याप्त
- सुनिश्चित
- पूरी तरह से
- बराबर
- समान रूप से
- बराबर
- त्रुटि
- त्रुटियाँ
- और भी
- प्रत्येक
- की जांच
- उदाहरण
- अनन्य रूप से
- मार डाला
- अस्तित्व
- असाधारण ढंग से
- असफल
- विफल रहता है
- विफलता
- प्रसिद्ध
- दूर
- सुदूर रो
- और तेज
- खेत
- खोज
- प्रथम
- पांच
- फ्लिप
- प्रवाह
- ध्यान केंद्रित
- के लिए
- प्रपत्र
- पाया
- नींव
- संस्थापक
- से
- खेल
- सामान्य उद्देश्य
- उत्पन्न
- मिल
- मिल रहा
- दी
- देते
- लक्ष्य
- जा
- स्नातक
- अभूतपूर्व
- लड़के
- था
- संभालना
- कठिन
- और जोर से
- साज़
- है
- he
- सिर
- हाई
- उसके
- इतिहास
- कैसे
- HTTPS
- i
- पहचान
- आईईईई
- if
- कल्पना करना
- कल्पना
- in
- संकेत
- अनंत
- अनन्तता
- निवेश
- निविष्टियां
- अन्तर्दृष्टि
- बजाय
- संस्थान
- इंटरनेट
- आंतरिक रूप से
- शामिल करना
- IT
- आईटी इस
- खुद
- जॉन
- केवल
- कुंजी
- कर्ट
- बाद में
- शुभारंभ
- कम से कम
- स्तर
- झूठ
- पसंद
- सीमा
- सीमाओं
- सीमाएं
- लाइन
- सूची
- सूचियाँ
- तर्क
- लंबा
- बनाया गया
- पत्रिका
- प्रमुख
- बनाता है
- प्रबंधनीय
- बहुत
- मेसाचुसेट्स
- मेसाचुसेट्स प्रौद्योगिक संस्थान
- गणितीय
- गणित
- बात
- साधन
- मतलब
- तरीका
- तरीकों
- हो सकता है
- मन
- लापता
- गलतियां
- एमआईटी
- आदर्श
- आधुनिक
- अधिक
- अधिकांश
- चाल
- बहुत
- नाम
- यानी
- लगभग
- जरूरत
- की जरूरत है
- नकारात्मक
- कभी नहीँ
- नया
- नहीं
- अभी
- संख्या
- वस्तु
- of
- अक्सर
- on
- एक बार
- ONE
- केवल
- खुला
- ऑप्टिमाइज़ करें
- or
- मूल
- अन्य
- अन्य
- अन्यथा
- हमारी
- उत्पादन
- अपना
- काग़ज़
- विशेष
- भुगतान
- व्यक्ति
- अग्रणी
- जगह
- प्लेटो
- प्लेटो डेटा इंटेलिजेंस
- प्लेटोडाटा
- निभाता
- संभव
- बिजली
- शक्तिशाली
- अभ्यास
- ठीक
- मुख्य
- सिद्धांत
- मुसीबत
- समस्याओं
- प्रक्रिया
- प्रक्रिया
- उत्पादन
- पैदा करता है
- कार्यक्रम
- प्रोग्राम्स
- प्रगति
- प्रमाण
- सबूत
- साबित करना
- साबित
- गुण
- क्वांटमगाज़ी
- प्रश्न
- प्रशन
- बल्कि
- वास्तविक
- असली दुनिया
- हाल ही में
- बाकी है
- दोहराना
- बार बार
- प्रतिनिधित्व
- प्रतिनिधित्व
- का प्रतिनिधित्व
- शोधकर्ताओं
- संकल्प
- हल करने
- प्रतिबंधित
- परिणाम
- प्रकट
- रिचर्ड
- धांधली
- सही
- रॉबर्ट
- रन
- कहा
- वही
- कहना
- कहावत
- स्कैनिंग
- विज्ञान
- वैज्ञानिक
- वैज्ञानिकों
- Search
- दूसरा
- मालूम होता है
- लगता है
- सेट
- सियाम
- समान
- उसी प्रकार
- सरल
- सरलीकृत
- केवल
- के बाद से
- छह
- धीमा
- So
- समाधान ढूंढे
- हल
- हल करती है
- सुलझाने
- कुछ
- कुछ
- विशेष
- स्पॉट
- प्रारंभ
- शुरुआत में
- कथन
- उपजी
- फिर भी
- रुकें
- संग्रहित
- सरल
- स्ट्रेटेजी
- तार
- छात्र
- पढ़ाई
- का अध्ययन
- ऐसा
- वाक्यविन्यास
- लेना
- कार्य
- तकनीक
- टेक्नोलॉजी
- शर्तों
- से
- कि
- RSI
- उन
- फिर
- सैद्धांतिक
- सिद्धांत
- वहाँ।
- इन
- वे
- विचारधारा
- इसका
- उन
- यहाँ
- विफल
- सेवा मेरे
- एक साथ
- उपकरण
- यातायात
- मुसीबत
- <strong>उद्देश्य</strong>
- कोशिश
- ट्यूरिंग
- मोड़
- बदल गया
- देशव्यापी
- जब तक
- उपयोग
- प्रयुक्त
- का उपयोग
- संस्करण
- बनाम
- वायरस
- करना चाहते हैं
- जरूरत है
- था
- मार्ग..
- we
- webp
- कुंआ
- अच्छी तरह से परिभाषित
- क्या
- कब
- या
- कौन कौन से
- कौन
- मर्जी
- विलियम्स
- जीतना
- साथ में
- कार्य
- विश्व
- होगा
- गलत
- साल
- अभी तक
- आप
- आपका
- जेफिरनेट