क्या एक ट्यूरिंग मशीन एक असली डिवाइस या एक काल्पनिक अवधारणा है?

Question

जब मैं ट्यूरिंग मशीनों और पीडीए के बारे में पढ़ रहा हूं, तो मैं सोच रहा था कि पहला कंप्यूटिंग डिवाइस ट्यूरिंग मशीन है।

इसलिए, मैंने सोचा कि ट्यूरिंग मशीन नामक एक व्यावहारिक मशीन मौजूद है और इसके राज्यों को कुछ विशेष उपकरणों (फ़्लिप-फ्लॉप की तरह कहें) द्वारा प्रदर्शित किया जा सकता है और यह चुंबकीय टेप में इनपुट स्वीकार कर सकता है।

इसलिए मैंने संदेह How input string is represented in magnetic tapes? से पूछा। लेकिन जवाब से और मेरी पुस्तक में दिए गए विवरणों से, मुझे पता चला कि ट्यूरिंग मशीन कुछ कल्पित है।

मेरा सवाल है, एक ट्यूरिंग मशीन को व्यावहारिक रूप से कैसे लागू किया जाएगा? उदाहरण के लिए, हमारे वर्तमान प्रोसेसर में वर्तनी त्रुटियों की जांच के लिए इसका उपयोग कैसे किया जाता है।

क्या ट्यूरिंग मशीन पुरानी हैं? या फिर भी उनका उपयोग किया जा रहा है?

Answer 1

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

यह सवाल पूछता है ... क्यों ट्यूरिंग मशीनों का अध्ययन करें? सौभाग्य से, ऐसा करने के कई कारण हैं:

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

2. एल्गोरिदम की परिभाषा को औपचारिक बनाने के लिए। बाइनरी एक एल्गोरिदम क्यों खोजता है जबकि "उत्तर अनुमान लगाएं" कथन नहीं है? इस सवाल का जवाब देने के लिए, हमारे पास औपचारिक मॉडल होना चाहिए कि कंप्यूटर क्या है और एल्गोरिदम का क्या अर्थ है।गणना के मॉडल के रूप में ट्यूरिंग मशीन रखने से हम दृढ़ता से परिभाषित कर सकते हैं कि एल्गोरिदम क्या है। वास्तव में कभी भी प्रारूप में एल्गोरिदम का अनुवाद नहीं करना चाहता, लेकिन ऐसा करने की क्षमता एल्गोरिदम और कम्प्यूटेबिलिटी सिद्धांत के क्षेत्र को एक दृढ़ गणितीय ग्राउंडिंग प्रदान करती है।

3. निर्धारक और नॉनडेटेटिनिस्टिक एल्गोरिदम की परिभाषाओं को औपचारिक बनाने के लिए। शायद कंप्यूटर विज्ञान में सबसे बड़ा खुला प्रश्न अभी प्रश्न है कि पी = एनपी। यह प्रश्न केवल तभी समझ में आता है जब आपके पास पी और एनपी के लिए औपचारिक परिभाषा है, और इन्हें बदले में परिभाषाओं की आवश्यकता होती है यदि निर्धारिती और nndeterministic गणना (हालांकि तकनीकी रूप से उन्हें दूसरे क्रम तर्क का उपयोग करके परिभाषित किया जा सकता है)। ट्यूरिंग मशीन होने के बाद हमें एनपी-पूर्ण समस्याओं को खोजने का एक तरीका प्रदान करने के साथ-साथ एनपी में महत्वपूर्ण समस्याओं के बारे में बात करने की अनुमति मिलती है। उदाहरण के लिए, एसएटी एनपी-पूर्ण है यह सबूत इस तथ्य का उपयोग करता है कि एसएटी का उपयोग ट्यूरिंग मशीन को एन्कोड करने के लिए किया जा सकता है और यह इनपुट पर निष्पादन है।

आशा है कि इससे मदद मिलती है!

Answer 2

यह एक वैचारिक डिवाइस है जो वास्तविक नहीं है (अनंत टेप की आवश्यकता के कारण)। कुछ लोगों ने ट्यूरिंग मशीन के भौतिक अहसास बनाए हैं, लेकिन शारीरिक सीमाओं के कारण यह एक वास्तविक ट्यूरिंग मशीन नहीं है। http://www.youtube.com/watch?v=E3keLeMwfHY

Answer 3

यह एक सैद्धांतिक मशीन, विकिपीडिया

से निम्नलिखित पैरा

एक ट्यूरिंग मशीन एक तालिका के अनुसार एक सैद्धांतिक उपकरण है, जो टेप की एक पट्टी पर प्रतीकों manipulates है:

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

गैर नियतात्मक मशीन (वास्तविक में मौजूद नहीं है) की तरह अन्य मशीनों के साथ-साथ इस मशीन की गणना जटिलता में बहुत उपयोगी होते हैं और साबित होता है कि एक एल्गोरिथ्म एक और की तुलना में कठिन है या एक एल्गोरिथ्म व्याख्या करने योग्य नहीं है .. .etc

Answer 4

ट्यूरिंग मशीन बिल्कुल भौतिक मशीन नहीं हैं, बल्कि वे मूल रूप से वैचारिक मशीन हैं। ट्यूरिंग अवधारणा परिकल्पना है और वास्तविक दुनिया में इसे लागू करना बहुत मुश्किल है क्योंकि हमें छोटे और आसान समाधान के लिए अनंत टेप की भी आवश्यकता होती है।