संगणना के मॉडल
कई औपचारिक ढाँचे यह परिभाषित करते हैं कि संगणना का क्या अर्थ है, लैम्डा कैलकुलस के फ़ंक्शन-पुनर्लेखन से लेकर बूलियन सर्किट और क्वांटम सिस्टम तक, और उनकी शक्ति की तुलना करने से पता चलता है कि कौन से मॉडल समतुल्य हैं और कौन से वास्तव में भिन्न हैं।
Definition
संगणना का एक मॉडल एक सटीक अमूर्त ढाँचा है जो यह निर्दिष्ट करता है कि कौन से ऑपरेशन अनुमत हैं और संगणना कैसे आगे बढ़ती है; विभिन्न मॉडल कार्यों के एक ही वर्ग की गणना कर सकते हैं फिर भी संक्षिप्तता, समानांतरता, या उन संसाधनों में भिन्न हो सकते हैं जिन्हें वे स्पष्ट करते हैं।
Scope
यह क्षेत्र लैम्डा कैलकुलस और कार्यात्मक मॉडल, पुनरावर्ती फ़ंक्शन और रजिस्टर मशीन, बूलियन सर्किट और सर्किट जटिलता, और क्वांटम संगणना को शामिल करता है, यह जाँचते हुए कि प्रत्येक मॉडल एल्गोरिदम को कैसे व्यक्त करता है, चर्च-ट्यूरिंग थीसिस के माध्यम से उनकी संगणनीयता शक्ति कैसे संबंधित है, और उनकी दक्षता कैसे भिन्न हो सकती है।
Sub-topics
Core questions
- संगणना की धारणा को औपचारिक रूप देने के विभिन्न तरीके क्या हैं?
- कौन से मॉडल उन कार्यों में समतुल्य हैं जिनकी वे गणना कर सकते हैं, और क्यों?
- दक्षता, समानांतरता, या भौतिक प्राप्यता के मायने रखने पर मॉडल कैसे भिन्न होते हैं?
- क्या क्वांटम संगणना जैसा भौतिक रूप से प्रेरित मॉडल शास्त्रीय दक्षता से अधिक हो सकता है?
Key theories
- चर्च-ट्यूरिंग थीसिस के तहत समतुल्यता
- लैम्डा कैलकुलस, पुनरावर्ती फ़ंक्शन, रजिस्टर मशीनें, और ट्यूरिंग मशीनें सभी कार्यों के एक ही वर्ग की गणना करती हैं, वह अभिसरण जो संगणना की पहचान को ट्यूरिंग संगणनीयता के साथ आधार बनाता है।
- दक्षता में विचलन
- जो मॉडल संगणनीयता पर सहमत होते हैं, वे संसाधनों पर तेज़ी से भिन्न हो सकते हैं: सर्किट समानांतर और गैर-समान संगणना को उजागर करते हैं, और क्वांटम मॉडल गति में वृद्धि की पेशकश करते प्रतीत होते हैं, इसलिए मॉडल का चुनाव जटिलता के लिए बहुत मायने रखता है, भले ही वह संगणनीयता के लिए न हो।
Clinical relevance
विभिन्न मॉडल वास्तविक संगणना के विभिन्न पहलुओं को प्रकाशित करते हैं: लैम्डा कैलकुलस कार्यात्मक प्रोग्रामिंग भाषाओं का सैद्धांतिक आधार है, सर्किट हार्डवेयर और समानांतर संगणना का मॉडल करते हैं, रजिस्टर मशीनें पारंपरिक प्रोसेसर को दर्शाती हैं, और क्वांटम मॉडल उभरते क्वांटम हार्डवेयर और एल्गोरिदम के डिजाइन का मार्गदर्शन करते हैं।
History
1930 के दशक में चर्च के लैम्डा कैलकुलस, गोडेल और क्लीने के पुनरावर्ती फ़ंक्शन, और ट्यूरिंग की मशीनों को प्रस्तावित किया गया था और फिर समतुल्य दिखाया गया था। बाद के मॉडल ने नए आयाम जोड़े: सर्किट जटिलता ने समानांतर और हार्डवेयर संगणना को औपचारिक रूप दिया, और फेनमैन के 1982 के क्वांटम सिमुलेशन के प्रस्ताव ने संगणना के क्वांटम मॉडल को जन्म दिया।
Key figures
- Alonzo Church
- Alan Turing
- Stephen Kleene
- Richard Feynman
Related topics
Seminal works
- church1936
- sipser2013
- aroraBarak2009
Frequently asked questions
- यदि वे समान कार्यों की गणना करते हैं तो कई मॉडलों का अध्ययन क्यों करें?
- समतुल्यता केवल इस बात के लिए मान्य है कि सिद्धांत रूप में क्या गणना की जा सकती है। विभिन्न मॉडल विभिन्न चीजों को व्यक्त करना या विश्लेषण करना आसान बनाते हैं: लैम्डा कैलकुलस कार्यात्मक प्रोग्रामिंग को स्पष्ट करता है, सर्किट समानांतरता और हार्डवेयर लागतों को प्रकट करते हैं, और क्वांटम मॉडल भौतिक घटनाओं को पकड़ते हैं, इसलिए प्रत्येक विभिन्न प्रश्नों के लिए सही लेंस है।
- क्या संगणना के सभी मॉडल समतुल्य हैं?
- सभी उचित शास्त्रीय मॉडल कार्यों के एक ही वर्ग की गणना करते हैं, जो चर्च-ट्यूरिंग थीसिस का समर्थन करते हैं। लेकिन वे दक्षता में बहुत भिन्न हो सकते हैं, और जो मॉडल विभिन्न संसाधनों का उपयोग करते हैं, जैसे कि क्वांटम सुपरपोजिशन, वे समान कार्यों की गणना करते हुए भी कुछ समस्याओं को तेज़ी से हल कर सकते हैं।