अनिर्णीत समस्याओं की सूची: Difference between revisions
From Vigyanwiki
m (8 revisions imported from alpha:अनिर्णीत_समस्याओं_की_सूची) |
No edit summary |
||
| Line 97: | Line 97: | ||
*[https://mathoverflow.net/q/11540 Discussion] at [[MathOverflow]] | *[https://mathoverflow.net/q/11540 Discussion] at [[MathOverflow]] | ||
{{DEFAULTSORT:Undecidable Problems}} | {{DEFAULTSORT:Undecidable Problems}} | ||
[[Category:Articles with hatnote templates targeting a nonexistent page|Undecidable Problems]] | |||
[[Category:CS1 errors|Undecidable Problems]] | |||
[[Category: | [[Category:Created On 15/05/2023|Undecidable Problems]] | ||
[[Category:Created On 15/05/2023]] | [[Category:Lua-based templates|Undecidable Problems]] | ||
[[Category:Vigyan Ready]] | [[Category:Machine Translated Page|Undecidable Problems]] | ||
[[Category:Pages with script errors|Undecidable Problems]] | |||
[[Category:Templates Vigyan Ready|Undecidable Problems]] | |||
[[Category:Templates that add a tracking category|Undecidable Problems]] | |||
[[Category:Templates that generate short descriptions|Undecidable Problems]] | |||
[[Category:Templates using TemplateData|Undecidable Problems]] | |||
[[Category:अनिर्णीत समस्याएं| अनिर्णीत समस्याएं]] | |||
[[Category:गणित से संबंधित सूचियाँ|Undecidable Problems]] | |||
[[Category:संगणना का सिद्धांत|*]] | |||
[[Category:संगणनीयता सिद्धांत|*]] | |||
[[Category:समस्याओं की सूची|Undecidable Problems]] | |||
Revision as of 10:00, 12 June 2023
कम्प्यूटेबिलिटी संगणनीयता सिद्धांत, अनिर्णीत समस्या एकल प्रकार की कम्प्यूटेशनल समस्या है जिसके लिए हां/नहीं में उत्तर की आवश्यकता होती है, किन्तु जहां संभवतः कोई कंप्यूटर प्रोग्राम नहीं हो सकता है जो सदैव सही उत्तर देता है; अर्थात, कोई भी संभावित कार्यक्रम कभी-कभी गलत उत्तर देगा या बिना कोई उत्तर दिए सदैव के लिए चलेगा। अधिक औपचारिक रूप से, अनिर्णीत समस्या ऐसी समस्या है जिसकी भाषा [[पुनरावर्ती सबसेट]] नहीं है; लेख देखें निर्णायक भाषा। कई अनिर्णीत समस्याएं अनगिनत सेट हैं, इसलिए नीचे दी गई सूची आवश्यक रूप से अधूरी है। चूंकि अनिर्णायक भाषाएँ पुनरावर्ती भाषाएँ नहीं हैं, वे एलन ट्यूरिंग पहचानने योग्य भाषाओं के उपसमुच्चय हो सकती हैं: अर्थात, ऐसी अनिर्णनीय भाषाएँ पुनरावर्ती गणना योग्य हो सकती हैं।
कई, यदि अधिकांश नहीं, तो गणित में अनिर्णीत समस्याओं को शब्द समस्या (गणित) के रूप में प्रस्तुत किया जा सकता है: यह निर्धारित करना कि प्रतीकों के दो भिन्न-भिन्न तार (किसी गणितीय अवधारणा या वस्तु को कूटबद्ध करना) वस्तु का प्रतिनिधित्व करते हैं या नहीं करते हैं।
स्वयंसिद्ध गणित में अनिर्वचनीयता के लिए, ZFC में अनिर्णीत कथनों की सूची देखें।
तर्क में समस्या
- हिल्बर्ट की निर्णय समस्या
- दूसरे क्रम के लैम्ब्डा कैलकुलस (या समतुल्य) के लिए अनुमान टाइप और प्रकार की जाँच करें।[1]
- यह निर्धारित करना कि क्या रेखांकन के तर्क में प्रथम क्रम के वाक्य को परिमित अप्रत्यक्ष ग्राफ द्वारा अनुभव किया जा सकता है।[2]
- ट्रैखटेनब्रॉट का प्रमेय - परिमित संतुष्टि अनिर्णीत है।
- प्रथम आदेश हॉर्न क्लॉज की संतुष्टि है।
अमूर्त मशीनों के विषय में समस्या
- रुकने की समस्या (यह निर्धारित करना कि क्या ट्यूरिंग मशीन किसी दिए गए इनपुट पर रुकती है) और मृत्यु दर (कम्प्यूटेबिलिटी सिद्धांत) (यह निर्धारित करना कि क्या यह प्रत्येक प्रारंभिक विन्यास के लिए रुकता है)।
- यह निर्धारित करना कि क्या ट्यूरिंग मशीन व्यस्त बीवर है, गैर-कम्प्यूटेबिलिटी (अर्थात, समान संख्या में राज्यों और प्रतीकों के साथ ट्यूरिंग मशीनों को रोकने के मध्य सबसे लंबे समय तक चलने वाली है)।
- राइस की प्रमेय कहती है कि आंशिक कार्यों के सभी गैर-तुच्छ गुणों के लिए, यह अनिर्णीत है कि दी गई मशीन उस संपत्ति के साथ आंशिक फ़ंक्शन की गणना करती है या नहीं करती है।
- मिन्स्की मशीन के लिए रुकने की समस्या परिमित-राज्य ऑटोमेटन जिसमें कोई इनपुट नहीं है और दो काउंटर हैं जिन्हें बढ़ाया जा सकता है, घटाया जा सकता है और शून्य के लिए परीक्षण किया जा सकता है।
- गैर-नियतात्मक पुशडाउन ऑटोमेटन की सार्वभौमिकता: यह निर्धारित करना कि क्या सभी शब्द स्वीकार किए जाते हैं।
- समस्या यह है कि टैग प्रणाली रुकता है या नहीं रुकता है।
मेट्रिसेस के विषय में समस्या
- नश्वर मैट्रिक्स समस्या: निर्धारण, पूर्णांक प्रविष्टियों के साथ n × n मैट्रिक्स का परिमित सेट दिया गया है, क्या उन्हें किसी क्रम में गुणा किया जा सकता है, संभवतः पुनरावृत्ति के साथ, शून्य मैट्रिक्स प्राप्त करने के लिए यह छह या अधिक 3 × 3 मैट्रिक्स के सेट या दो 15 × 15 मैट्रिक्स के सेट के लिए अनिर्णीत माना जाता है।[3]
- यह निर्धारित करना कि क्या गैर-नकारात्मक पूर्णांक प्रविष्टियों के साथ ऊपरी त्रिकोणीय 3 × 3 मैट्रिसेस का परिमित सेट मुक्त अर्धसमूह उत्पन्न करता है।
- यह निर्धारित करना कि पूर्णांक मेट्रिसेस के दो सूक्ष्म रूप से उत्पन्न उपसमूहों में सामान्य तत्व है या नहीं है।
मिश्रित समूह सिद्धांत में समस्याएं-
टोपोलॉजी में समस्याएं
- यह निर्धारित करना कि क्या दो परिमित सरल परिसर होमियोमॉर्फिक हैं।
- यह निर्धारित करना कि क्या परिमित सरल परिसर कई गुना (होमियोमॉर्फिक) है।
- यह निर्धारित करना कि परिमित सरल परिसर का मौलिक समूह तुच्छ है या नहीं है।
- यह निर्धारित करना कि क्या दो गैर-सरल रूप से जुड़े 5-कई गुना होमोमोर्फिक हैं, या यदि 5-कई गुना S5 के लिए होमोमोर्फिक है।[4]
विश्लेषण में समस्याएं
- कुछ वर्गों में कार्यों के लिए, निर्धारण की समस्या: क्या दो कार्य समान हैं, शून्य-समतुल्यता समस्या के रूप में जाना जाता है (रिचर्डसन की प्रमेय देखें);[5] फंक्शन के शून्य; क्या किसी फलन का अनिश्चित समाकल भी कक्षा में है।[6] इन समस्याओं के कुछ उपवर्ग निर्णायक हैं। उदाहरण के लिए, किसी भी फ़ंक्शन के प्राथमिक एकीकरण के लिए प्रभावी निर्णय प्रक्रिया है जो पारलौकिक प्राथमिक फ़ंक्शंस के कार्य से संबंधित है, रिस्क एल्गोरिथम।
- यह निर्धारित करने की समस्या कि प्राथमिक मेरोमॉर्फिक फ़ंक्शन का निश्चित समोच्च एकाधिक अभिन्न प्रत्येक स्थान वास्तविक विश्लेषणात्मक मैनिफोल्ड पर शून्य है, जिस पर यह विश्लेषणात्मक है, मटियासेविच के प्रमेय का हिल्बर्ट की दसवीं समस्या को समाधान करने का परिणाम है।[6]
- फार्म के साधारण अंतर समीकरण के समाधान के डोमेन का निर्धारण
- जहाँ x Rn में सदिश है, p(t, x) t और x में बहुपदों का सदिश है, और (t0, x0) Rn+1 से संबंधित है।[7]
औपचारिक भाषाओं और व्याकरण के विषय में समस्याएं
- पोस्ट पत्राचार समस्या।
- यह निर्धारित करना कि क्या कोई संदर्भ-मुक्त व्याकरण सभी संभव तार उत्पन्न करता है, या यदि यह अस्पष्ट है।
- दो संदर्भ-मुक्त व्याकरण दिए गए हैं, यह निर्धारित करते हुए कि क्या वे स्ट्रिंग्स का सेट उत्पन्न करते हैं, या क्या कोई दूसरे द्वारा उत्पन्न स्ट्रिंग्स का सबसेट उत्पन्न करता है, या क्या कोई स्ट्रिंग है जो दोनों उत्पन्न करते हैं।
अन्य समस्याएं
- यह निर्धारित करने की समस्या कि क्या वांग टाइल्स का दिया गया सेट विमान को टाइल कर सकता है।
- स्ट्रिंग की कोलमोगोरोव जटिलता को निर्धारित करने की समस्या है।
- हिल्बर्ट की दसवीं समस्या: डायोफैंटाइन समीकरण (बहुभिन्नरूपी बहुपद समीकरण) का समाधान पूर्णांकों में है या नहीं, यह निर्धारित करने की समस्या है।
- यह निर्धारित करना कि तर्कसंगत निर्देशांक के साथ दिया गया प्रारंभिक बिंदु आवधिक है, या क्या यह किसी दिए गए विवृत सेट के आकर्षण के बेसिन में स्थित है, दो आयामों में खंड-रेखीय पुनरावृत्त मानचित्र में, या तीन आयामों में खंड-रेखीय प्रवाह में है।[8]
- यह निर्धारित करना कि λ-गणना सूत्र का सामान्य रूप है या नहीं है।
- कॉनवे का गेम ऑफ लाइफ इस पर कि क्या प्रारंभिक प्रतिरूप और दूसरा प्रतिरूप दिया गया है, क्या पश्चात वाला प्रतिरूप कभी भी प्रारंभिक प्रतिरूप से प्रकट हो सकता है।
- नियम 110 - संपत्ति X से जुड़े अधिकांश प्रश्न पश्चात में प्रकट हो सकते हैं, यह अनिर्णीत है।
- यह निर्धारित करने की समस्या कि क्या क्वांटम यांत्रिक प्रणाली में वर्णक्रमीय अंतर (भौतिकी)भौतिकी है।[9][10]
- सूचना-स्थिर परिमित राज्य मशीन चैनल की क्षमता का ज्ञात करना है।[11]
- नेटवर्क कोडिंग में, यह निर्धारित करना कि नेटवर्क सॉल्व करने योग्य है या नहीं।[12][13]
- यह निर्धारित करना कि किसी खिलाड़ी के पास मैजिक: द गैदरिंग के गेम में जीतने की रणनीति है या नहीं है।
- आंशिक रूप से देखने योग्य मार्कोव निर्णय प्रक्रिया में योजना।
- भूमिकर को ध्यान में रखते हुए गंतव्य से दूसरे गंतव्य तक हवाई यात्रा की योजना बनाने की समस्या।
- परावर्तक या अपवर्तक वस्तुओं की 3-आयामी प्रणाली के लिए किरण अनुरेखण (ग्राफिक्स) समस्या में, यह निर्धारित करना कि क्या किरण किसी दिए गए स्थान और दिशा से प्रारम्भ होकर अंततः निश्चित बिंदु तक पहुँचती है।
यह भी देखें
टिप्पणियाँ
- ↑ Wells, J. B. (1993). "दूसरे क्रम के लैम्ब्डा-कैलकुलस में टाइपेबिलिटी और टाइप चेकिंग समतुल्य और अनिर्णीत हैं". Tech. Rep. 93-011. Comput. Sci. Dept., Boston Univ.: 176–185. CiteSeerX 10.1.1.31.3590.
- ↑ Trahtenbrot, B. A. (1950). "सीमित डोमेन के लिए निर्णय समस्या के लिए एल्गोरिदम की असंभवता". Doklady Akademii Nauk SSSR. New Series. 70: 569–572. MR 0033784.
- ↑ Cassaigne, Julien; Halava, Vesa; Harju, Tero; Nicolas, Francois (2014). "मैट्रिक्स मृत्यु दर, शून्य-इन-द-कॉर्नर समस्याओं, और अधिक के लिए सख्त अनिश्चितता सीमा". arXiv:1404.0644 [cs.DM].
- ↑ Stillwell, John (1993), Classical Topology and Combinatorial Group Theory, Graduate Texts in Mathematics, vol. 72, Springer, p. 247, ISBN 9780387979700.
- ↑ Keith O. Geddes, Stephen R. Czapor, George Labahn, Algorithms for Computer Algebra, ISBN 0585332479, 2007, p. 81ff
- ↑ 6.0 6.1 Stallworth, Daniel T. and Fred W. Roush An Undecidable Property of Definite Integrals Proceedings of the American Mathematical Society Volume 125, Number 7, July 1997, Pages 2147-2148
- ↑ Graça, Daniel S.; Buescu, Jorge; Campagnolo, Manuel L. (21 March 2008). "परिभाषा के क्षेत्र की सीमा बहुपद ODEs के लिए अनिर्णीत है". Electronic Notes in Theoretical Computer Science. 202: 49–57. doi:10.1016/j.entcs.2008.03.007.
- ↑ Moore, Cristopher (1990), "Unpredictability and undecidability in dynamical systems" (PDF), Physical Review Letters, 64 (20): 2354–2357, Bibcode:1990PhRvL..64.2354M, doi:10.1103/PhysRevLett.64.2354, PMID 10041691.
- ↑ Cubitt, Toby S.; Perez-Garcia, David; Wolf, Michael M. (2015). "वर्णक्रमीय अंतराल की अनिश्चितता". Nature. 528 (7581): 207–211. arXiv:1502.04135. Bibcode:2015Natur.528..207C. doi:10.1038/nature16059. PMID 26659181. S2CID 4451987.
- ↑ Bausch, Johannes; Cubitt, Toby S.; Lucia, Angelo; Perez-Garcia, David (17 August 2020). "एक आयाम में स्पेक्ट्रल गैप की अनिश्चितता". Physical Review X. 10 (3): 031038. Bibcode:2020PhRvX..10c1038B. doi:10.1103/PhysRevX.10.031038.
- ↑ Elkouss, D.; Pérez-García, D. (2018). "स्मृति प्रभाव एक संचार चैनल की संचरण क्षमता को अगणनीय बना सकते हैं". Nature Communications. 9 (1): 1149. doi:10.1038/s41467-018-03428-0. PMC 5861076. PMID 29559615.
- ↑ Li, C. T. (2023). "नेटवर्क कोडिंग, सशर्त सूचना असमानताओं और सशर्त स्वतंत्रता निहितार्थ की अनिश्चितता". IEEE Transactions on Information Theory: 1. arXiv:2205.11461. doi:10.1109/TIT.2023.3247570.
- ↑ Kühne, L.; Yashfe, G. (2022). "सी-अरेंजमेंट्स द्वारा मैट्रोइड्स की प्रतिनिधित्व क्षमता अनिर्णीत है". Israel Journal of Mathematics. 252: 1-53. arXiv:1912.06123. doi:10.1007/s11856-022-2345-z. S2CID 209324252.
ग्रन्थसूची
- Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. Appendix C includes impossibility of algorithms deciding if a grammar contains ambiguities, and impossibility of verifying program correctness by an algorithm as example of Halting Problem.
- Halava, Vesa (1997). "Decidable and undecidable problems in matrix theory". TUCS technical report. 127. Turku Centre for Computer Science. CiteSeerX 10.1.1.31.5792.
{{cite journal}}: Cite journal requires|journal=(help) - Moret, B. M. E.; H. D. Shapiro (1991). Algorithms from P to NP, volume 1 - Design and Efficiency. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms."
- Weinberger, Shmuel (2005). Computers, rigidity, and moduli. Princeton, NJ: Princeton University Press. Discusses undecidability of the word problem for groups, and of various problems in topology.
अग्रिम पठन
- Poonen, Bjorn (2 April 2012), Undecidable problems: a sampler, arXiv:1204.0299, Bibcode:2012arXiv1204.0299P
