ट्यूरिंग मशीन क्या है?
सन 1936 में एलन ट्यूरिंग ने सबसे सरल कंप्यूटर की कल्पना की। इसके चार हिस्से हैं।
- फीता (tape): बहुत लंबी पट्टी जिसमें खाने हैं। हर खाने में एक चिह्न होता है (जैसे 0, 1 या खाली)।
- सिर (head): यह एक खाने पर रहता है। चिह्न पढ़ता है और नया चिह्न लिख सकता है।
- अवस्था (state): मशीन की छोटी याद, जैसे "अभी मैं दाईं ओर जा रही हूँ"।
- नियम तालिका: नियमों की सूची: इस अवस्था में, यह चिह्न पढ़ा, तो यह लिखो, बाएँ या दाएँ चलो और इस अवस्था में जाओ।
मशीन नियमों को एक-एक करके मानती है और रुकने वाली (halt) अवस्था में रुक जाती है। तब फीते पर जो लिखा है, वही उत्तर है।
उदाहरण: द्विआधारी संख्या में 1 जोड़ना
फीते पर 01011 है। हमें 01100 चाहिए।
| अवस्था | पढ़ा | लिखा | चाल | अगली अवस्था |
|---|---|---|---|---|
| go (दाएँ) | 0 या 1 | वही | दाएँ | go |
| go | खाली | खाली | बाएँ | carry |
| carry (हासिल) | 1 | 0 | बाएँ | carry |
| carry | 0 या खाली | 1 | रुको | halt |
"carry में 1 पढ़ा तो 0 लिखो" वही है जो हम हाथ से जोड़ने में करते हैं: 1 + 1 = 10, 0 लिखो और 1 हासिल बाईं ओर ले जाओ।
चर्च–ट्यूरिंग थीसिस
लोगों ने कंप्यूटिंग के और भी मॉडल बनाए। अलोंज़ो चर्च ने फलनों (lambda calculus) से एक मॉडल बनाया, और बाद में असली प्रोग्रामिंग भाषाएँ आईं। हर बार पता चला कि ये सब ट्यूरिंग मशीन के बराबर शक्तिशाली हैं।
चर्च–ट्यूरिंग थीसिस कहती है: अगर कोई समस्या साफ़ क्रमवार विधि (एल्गोरिदम) से हल हो सकती है, तो उसे ट्यूरिंग मशीन भी हल कर सकती है।
इसे थीसिस कहते हैं, प्रमेय नहीं, क्योंकि "साफ़ क्रमवार विधि" एक विचार है, गणित की सटीक परिभाषा नहीं। इसलिए इसे सिद्ध नहीं किया जा सकता। पर लगभग 90 साल में कोई विपरीत उदाहरण नहीं मिला।
इसका एक नतीजा: कुछ काम किसी भी मशीन से कंप्यूट नहीं हो सकते। सबसे मशहूर है रुकने की समस्या (halting problem): कोई प्रोग्राम हर दूसरे प्रोग्राम के लिए हमेशा सही नहीं बता सकता कि वह रुकेगा या हमेशा चलता रहेगा।
जटिलता विश्लेषण: चरण गिनना
एल्गोरिदम सिर्फ़ सही होना काफ़ी नहीं, उसे काफ़ी तेज़ भी होना चाहिए। समय जटिलता पूछती है: इनपुट का आकार n हो, तो कितने चरण लगेंगे? हम छोटी बातें छोड़कर मुख्य बढ़त रखते हैं, Big O से।
| चरण | नाम | n दुगुना हो तो |
|---|---|---|
| n | O(n) रैखिक | लगभग 2 गुना |
| n² | O(n²) द्विघात | लगभग 4 गुना |
| 2ⁿ | O(2ⁿ) घातांकी | वर्ग हो जाता है! बेकार |
हमारी 1 जोड़ने वाली मशीन में लगभग 2n + 1 चरण लगते हैं, इसलिए यह O(n) है। स्थान जटिलता इस्तेमाल हुई मेमोरी गिनती है, जैसे फीते के खाने।
वर्ग P उन समस्याओं का है जिनका बहुपद समय (n, n², n³ …) वाला एल्गोरिदम है। क्या हर वह समस्या जिसका उत्तर जाँचना आसान है, हल करना भी आसान है (P vs NP)? यह आज भी खुला प्रश्न है।
करके देखो: खुद ट्यूरिंग मशीन बनो
कागज़ की पट्टी लो और 7 डिब्बे बनाओ। बीच के पाँच डिब्बों में 0 1 1 0 1 लिखो। पहले अंक पर सिक्का रखो। सिर्फ़ ऊपर की नियम तालिका मानो। हर चाल पर अवस्था बोलो और चाल गिनो। फिर 3D में संख्या 13 चुनकर "चलाओ" दबाओ। पहले चरण का अंदाज़ा लगाओ, फिर जाँचो।
मुख्य सूत्र और परिभाषाएँ
- ट्यूरिंग मशीन = फीता + सिर + अवस्था + नियम तालिका
- एक चाल: (अवस्था, चिह्न) → (नया चिह्न, बाएँ/दाएँ, नई अवस्था)
- 1 जोड़ने वाली मशीन: n बिट के लिए लगभग 2n + 1 चरण = O(n)
- बढ़त का क्रम: O(1) < O(log n) < O(n) < O(n²) < O(2ⁿ)
- चर्च–ट्यूरिंग थीसिस: एल्गोरिदम ⇔ ट्यूरिंग मशीन से कंप्यूटेबल
हल किए गए उदाहरण
1. फीते पर 0 1 0 0 1 (9) है। 1 जोड़ने वाली मशीन चलाओ। अंत में फीता क्या होगा और कितने चरण लगेंगे?
सिर 5 अंकों पर दाईं ओर चलता है, हर अंक पर एक चरण (5 चरण), फिर खाली खाने पर (1 चरण), फिर बाएँ: अंतिम अंक 1 है, वह 0 बनता है और सिर बाएँ चलता है (1 चरण); अगला अंक 0 है, वह 1 बनता है और मशीन रुक जाती है (1 चरण)। अंतिम फीता 0 1 0 1 0 = 10। कुल 8 चरण।
2. एक एल्गोरिदम में 3n + 5 चरण लगते हैं। उसका Big O क्या है?
स्थिरांक 5 और गुणक 3 छोड़ दो। यह O(n) है।
3. एक एल्गोरिदम में n² चरण लगते हैं। n = 10 के लिए 100 चरण। n = 30 के लिए कितने?
30² = 900 चरण। n तीन गुना हुआ तो चरण 3² = 9 गुना हुए।
4. एक विधि में 2ⁿ चरण लगते हैं। कंप्यूटर 10⁹ चरण प्रति सेकंड करता है। क्या n = 60 संभव है?
2⁶⁰ लगभग 1.15 × 10¹⁸ चरण है। समय = 1.15 × 10¹⁸ / 10⁹ = 1.15 × 10⁹ सेकंड, यानी लगभग 36 साल। इसलिए n = 60 व्यावहारिक नहीं है।
5. ट्यूरिंग मशीन "go" अवस्था में खाली खाना पढ़ती है। तालिका के अनुसार वह क्या करेगी?
वह खाली लिखेगी, बाईं ओर चलेगी और "carry" अवस्था में जाएगी।
6. क्या एक साधारण लैपटॉप ऐसी समस्या हल कर सकता है जो कोई ट्यूरिंग मशीन नहीं कर सकती?
नहीं। चर्च–ट्यूरिंग थीसिस के अनुसार लैपटॉप जो भी एल्गोरिदम चलाता है, वह ट्यूरिंग मशीन पर भी चल सकता है। लैपटॉप बस तेज़ है।
आम गलतियाँ
- ट्यूरिंग मशीन को खरीदी जा सकने वाली असली मशीन समझना। यह कंप्यूटिंग को समझने का एक विचार है।
- "चर्च–ट्यूरिंग थीसिस सिद्ध हो चुकी है" कहना। यह सिद्ध नहीं हो सकती, क्योंकि "एल्गोरिदम" की परिभाषा अनौपचारिक है।
- सोचना कि तेज़ कंप्यूटर खराब एल्गोरिदम को ठीक कर देगा। 2ⁿ वाली विधि 1000 गुना तेज़ कंप्यूटर पर भी बेकार रहती है।
- सिर्फ़ इनपुट का आकार गिनना, चरण नहीं। जटिलता यह है कि इनपुट बढ़ने पर चरण कैसे बढ़ते हैं।