ट्यूरिंग मशीन परिचय

ट्यूरिंग मशीन एक स्वीकार करने वाला उपकरण है जो टाइप 0 व्याकरण द्वारा उत्पन्न भाषाओं (पुनरावर्ती असंख्य सेट) को स्वीकार करता है। इसका आविष्कार 1936 में एलन ट्यूरिंग ने किया था।

परिभाषा

ट्यूरिंग मशीन (टीएम) एक गणितीय मॉडल है जिसमें एक अनंत लंबाई की टेप होती है जो कोशिकाओं में विभाजित होती है जिस पर इनपुट दिया जाता है। इसमें एक सिर होता है जो इनपुट टेप को पढ़ता है। एक राज्य रजिस्टर ट्यूरिंग मशीन की स्थिति को संग्रहीत करता है। एक इनपुट प्रतीक को पढ़ने के बाद, इसे दूसरे प्रतीक से बदल दिया जाता है, इसकी आंतरिक स्थिति को बदल दिया जाता है, और यह एक कोशिका से दाएं या बाएं स्थानांतरित होता है। यदि TM अंतिम स्थिति में पहुंच जाता है, तो इनपुट स्ट्रिंग को स्वीकार कर लिया जाता है, अन्यथा अस्वीकार कर दिया जाता है।

एक टीएम को औपचारिक रूप से 7-ट्यूपल (क्यू, एक्स, δ, δ, q ₀ , B, F के रूप में वर्णित किया जा सकता है ) -

• Q राज्यों का एक समुच्चय है

• X टेप वर्णमाला है

• ∑ इनपुट वर्णमाला है

• δएक संक्रमण समारोह है; X: Q × X → Q × X × {Left_shift, Right_shift}।

• q₀ प्रारंभिक अवस्था है

• B रिक्त प्रतीक है

• F अंतिम राज्यों का सेट है

पिछले ऑटोमेटन के साथ तुलना

निम्न तालिका इस बात की तुलना करती है कि ट्यूरिंग मशीन, फिनाइट ऑटोमेटन और पुशडाउन ऑटोमैटन से कैसे भिन्न है।

मशीन	स्टैक डेटा संरचना	नियतात्मक?
परिमित ऑटोमोटन	NA	हाँ
पुशडाउन ऑटोमेटन	पहले आउट में अंतिम (LIFO)	नहीं
ट्यूरिंग मशीन	अनंत टेप	हाँ

ट्यूरिंग मशीन का उदाहरण

ट्यूरिंग मशीन M = (Q, X, machine, q, q ₀ , B, F) के साथ

• Q = {q ₀ , q ₁ , q ₂ , q _f }
• X = {a, b}
• 1 = {1}
• q ₀ = {q ₀ }
• ब = खाली प्रतीक
• F = {q _f }

by द्वारा दिया गया है -

टेप वर्णमाला प्रतीक	वर्तमान स्थिति 'q 0 '	वर्तमान स्थिति 'q 1 '	वर्तमान स्थिति 'q 2 '
ए	१ रक १	१ लक ०	1 एल एफ
ख	१ लक २	१ रक १	1Rq च

यहां संक्रमण 1Rq _{1 का} अर्थ है कि लेखन प्रतीक 1 है, टेप सही चलता है, और अगला राज्य q _{1 है} । इसी तरह, संक्रमण ₁ एल _{2 2 का} अर्थ है कि लेखन प्रतीक 1 है, टेप बाईं ओर चलता है, और अगला राज्य q _{2 है} ।

ट्यूरिंग मशीन का समय और स्थान जटिलता

ट्यूरिंग मशीन के लिए, समय की जटिलता टेप चालों की संख्या के माप को संदर्भित करती है जब मशीन को कुछ इनपुट प्रतीकों के लिए प्रारंभ किया जाता है और अंतरिक्ष जटिलता लिखे गए टेप की कोशिकाओं की संख्या होती है।

समय जटिलता सभी उचित कार्य -

T(n) = O(n log n)

टीएम की अंतरिक्ष जटिलता -

S(n) = O(n)