| अवस्था | पढ़ना | लिखना | चाल | अगली अवस्था |
|---|
ट्यूरिंग मशीन सिम्युलेटर
ट्यूरिंग मशीन सबसे सरल संभव कंप्यूटर है: एक हेड जो अंतहीन टेप का एक प्रतीक पढ़ता है, एक प्रतीक लिखता है, एक सेल बाएँ या दाएँ चलता है और अपनी अवस्था बदलता है, यह सब नियमों की एक छोटी तालिका के अनुसार। एलन ट्यूरिंग ने 1936 में इसका आविष्कार किया, और आपका कंप्यूटर जो कुछ भी करता है, वह सिद्धांत रूप में इसी तरह किया जा सकता है। अपने नियम लिखें या कोई उदाहरण लोड करें, चलाएँ दबाएँ और टेप को कदम-दर-कदम बदलते देखें, नीचे उसके पूरे इतिहास के आरेख के साथ। कोई प्रोग्राम चुनें या अपना प्रोग्राम लिखें, इनपुट दर्ज करें और चलाएँ दबाएँ, या एक-एक नियम का पालन देखने के लिए एक कदम दबाएँ; पीछे एक कदम वापस ले लेता है। प्रोग्राम की हर पंक्ति एक नियम है: अवस्था, पढ़ा गया प्रतीक, लिखा जाने वाला प्रतीक, चाल (L, R या बिना चाल के लिए N) और अगली अवस्था, जैसे A 0 -> 1 R B। खाली सेल के लिए _ का उपयोग करें। मशीन पहले नियम की अवस्था में, इनपुट के पहले प्रतीक पर शुरू होती है, और H, accept या reject में पहुँचने पर या जब कोई नियम लागू न हो, तब रुकती है। आरेख हर कदम के बाद का टेप ऊपर से नीचे की ओर दिखाता है।
यह कैसे काम करता है
- कोई उदाहरण प्रोग्राम चुनें या A 0 -> 1 R B जैसे नियम लिखें, हर पंक्ति में एक, और इनपुट टाइप करें।
- हेड को चलते देखने के लिए चलाएँ दबाएँ, या एक-एक नियम का पालन देखने के लिए एक कदम दबाएँ; पीछे एक कदम वापस ले लेता है।
- टाइलों में अवस्था, कदम और टेप पर प्रतीक पढ़ें, और आरेख में टेप का इतिहास देखें।
मशीन कैसे काम करती है
हर क्षण मशीन कुछ अवस्थाओं में से किसी एक में होती है और उसका हेड टेप के एक सेल पर होता है। उस अवस्था और हेड के नीचे के प्रतीक का नियम तीन बातें बताता है: सेल में कौन-सा प्रतीक लिखना है, बाएँ चलना है, दाएँ या बिल्कुल नहीं, और आगे किस अवस्था में जाना है। पूरी मशीन बस इतनी ही है। यह तब रुकती है जब किसी रुकने वाली अवस्था, जैसे H, accept या reject, तक पहुँचती है, या जब कोई नियम लागू नहीं होता। किसी बाइनरी संख्या में 1 जोड़ने वाले प्रोग्राम को ऐसे केवल नौ नियम चाहिए।
बिज़ी बीवर
खाली टेप पर शुरू की गई n अवस्थाओं वाली कौन-सी मशीन रुकने से पहले सबसे ज़्यादा 1 लिखती है? तिबोर रादो ने 1962 में यह प्रश्न पूछा। चैंपियनों को बिज़ी बीवर कहा जाता है, और वे किसी भी ऐसे फ़ंक्शन से तेज़ बढ़ते हैं जिसकी गणना कंप्यूटर कर सकता है। दो अवस्थाएँ 6 कदमों में 4 बार 1 देती हैं, तीन अवस्थाएँ 6 बार 1, चार अवस्थाएँ 107 कदमों में 13 बार 1। 1989 में मिला पाँच अवस्थाओं वाला चैंपियन 4,71,76,870 कदमों में 4,098 बार 1 लिखता है, और 2024 में एक ऑनलाइन सहयोग ने कंप्यूटर से जाँचे गए गणित द्वारा सिद्ध किया कि रुकने वाली पाँच अवस्थाओं की कोई और मशीन इससे अधिक देर नहीं चलती।
अक्सर पूछे जाने वाले प्रश्न
मैं नियम कैसे लिखूँ?
हर पंक्ति में एक नियम: वर्तमान अवस्था, वह जो प्रतीक पढ़ती है, लिखा जाने वाला प्रतीक, चाल (L, R या N) और अगली अवस्था, जैसे A 0 -> 1 R B। तीर और कॉमा वैकल्पिक हैं। खाली सेल के लिए _ और टिप्पणी के लिए # का उपयोग करें। मशीन पहले नियम की अवस्था में शुरू होती है; H या halt नाम की अगली अवस्था उसे रोक देती है, और accept और reject उसे एक निर्णय के साथ रोकते हैं।
क्या ट्यूरिंग मशीन सचमुच कुछ भी गणना कर सकती है?
पर्याप्त टेप और समय मिलने पर, वह सब कुछ जिसकी गणना कोई भी कंप्यूटर कर सकता है: यही चर्च–ट्यूरिंग थीसिस है। ट्यूरिंग मशीन की कोई मेमोरी सीमा नहीं होती, इसलिए इस अर्थ में वह किसी भी वास्तविक कंप्यूटर से अधिक शक्तिशाली है, हालाँकि बहुत धीमी। वह जो नहीं कर सकती, वह है हर प्रश्न का उत्तर देना: ट्यूरिंग ने सिद्ध किया कि कोई भी मशीन हर प्रोग्राम और इनपुट के लिए यह तय नहीं कर सकती कि वह प्रोग्राम रुकेगा या नहीं।
काउंटर कभी क्यों नहीं रुकता?
उसके नियम कभी किसी रुकने वाली अवस्था तक नहीं ले जाते। वह टेप के दाएँ छोर पर एक बाइनरी संख्या में लगातार 1 जोड़ता है और वापस चलता है, इसलिए संख्या हमेशा बढ़ती रहती है। ट्यूरिंग की हॉल्टिंग समस्या कहती है कि कोई सामान्य विधि हर मशीन के लिए यह नहीं बता सकती कि वह रुकेगी या नहीं; इस सरल काउंटर के लिए आप यह देख सकते हैं, लेकिन केवल छह अवस्थाओं वाली कुछ मशीनों के बारे में अभी तक कोई नहीं जानता।
पाँच अवस्थाओं वाला बिज़ी बीवर यहाँ 4.7 करोड़ कदम कैसे चल सकता है?
टेप को एक सघन ऐरे के रूप में संग्रहीत किया जाता है जो दोनों दिशाओं में बढ़ता है, और सबसे तेज़ सेटिंग में ऐप स्क्रीन के दो अपडेट के बीच लाखों कदम चलाता है, इसलिए पूरा रन आधुनिक ब्राउज़र में कुछ ही सेकंड लेता है। आरेख केवल पहले 400 कदम दर्ज करता है, क्योंकि 4.7 करोड़ पंक्तियों का चित्र किसी भी स्क्रीन पर नहीं समाएगा।
क्या कुछ सर्वर पर भेजा जाता है?
नहीं। प्रोग्राम आपके ब्राउज़र में चलता है, और आपका प्रोग्राम और इनपुट इसी ब्राउज़र के लोकल स्टोरेज में रहते हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ