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

hello दोस्तों! आज हम इस आर्टिकल में What is Turing Machine in Hindi (ट्यूरिंग मशीन क्या है?) के बारें में पढेंगे. तथा इसके features के बारें में जानेंगे. यह theory of computation (TOC) का एक important टॉपिक है तो चलिए start करते हैं:-

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 कर दिया जाता है।

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, ∑, δ, q₀, B, F) जहाँ:-

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

इसे भी पढ़ें:- finite automata क्या है?

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)

• pushdown automata किसे कहते है?
• mealy और Moore मशीन को पढ़िए.

निवेदन:- अगर आपके लिए यह पोस्ट helpful रही हो तो इसे अपने दोस्तों के साथ share कीजिये, जिससे कि उन्हें भी हेल्प हो जाए. और आपको इस post में कुछ सुधार करना है या कोई अन्य question पूछना है तो कमेंट के द्वारा बता सकते है. thanks.