Turing Machine in Hindi – ट्यूरिंग मशीन क्या है?

Turing Machine in Hindi 

Turing machine का आविष्कार 1936 में Alan Turing ने किया था. यह एक accepting डिवाइस है जो type 0 grammar द्वारा जनरेट किये गये Recursive Enumerable Language को accept करती है.

ट्यूरिंग मशीन (TM) एक गणितीय मॉडल है जिसमें एक infinite length की tape होती है जो cells में विभाजित रहती है जिस पर input दिया जाता है। इसमें एक head होता है जो input tape को read करता है। एक state register ट्यूरिंग मशीन की state (स्थिति) को store करता है।

input symbol को पढ़ने के बाद, इसे दूसरे symbol से बदल दिया जाता है, जिससे इसकी internal state (आंतरिक स्थिति) बदल जाती है, और यह एक cell से right या left की तरफ बढ़ता है। यदि TM, final state में पहुंच जाता है, तो input string को accept कर लिया जाता है, अन्यथा reject कर दिया जाता है।

Visit these :- Online Salon Booking App & Web

turing machine के विभिन्न features (विशेषताएं) निम्नलिखित हैं:-

1. इसके पास external memory होती है जो कि input के बहुत बड़े sequence को याद रखता है.
2. इसमें unlimited memory की क्षमता होती है।
3. इस मॉडल में एक सुविधा है जिसके द्वारा tape में left या right में स्थित input को आसानी से read किया जा सकता है।
4. यह machine अपने input के आधार पर एक निश्चित output को produce कर सकती है। कभी-कभी यह आवश्यक हो सकता है कि output को produce करने के लिए इसी input का उपयोग किया जाए। इसलिए इस मशीन में, इनपुट और आउटपुट के बीच के अंतर को remove कर दिया गया है। इस प्रकार turing machine के लिए alphabets के एक सामान्य set का प्रयोग किया जा सकता है।

एक Turing Machine को 7 tuple के द्वारा formally describe किया जाता है:- (Q, X, ∑, δ, q0, B, F) जहाँ:-

• Q, states की एक finite set है.
• X, टेप अल्फाबेट है.
• ∑, इनपुट अल्फाबेट है.
• δ, एक transition function है. δ : Q × X → Q × X × {Left_shift, Right_shift}.
• q0, शुरुवाती (initial) state है.
• B, blank symbol है.
• F, final states का समूह (set) है.

Time and Space Complexity of a TM

Turing machine के लिए, time complexity से तात्पर्य tape के move करने की संख्या से है जब कुछ input symbols के लिए मशीन initialize होती है. और space complexity टेप की write की गयी cells की संख्या है.

time complexity

T(n) = O(n log n)

space complexity

S(n) = O(n)

Thanks for watching these page 🙏