Unknown
Turing Machine (TM) एक accepting device है इसका अविष्कार Alan Turing ने 1936 में किया था इसका उपयोग Recursive Enumerable Languages को स्वीकार करने के लिए किया जाता है
Turing machine (TM) एक mathematical model है जिसमे infinite length का tape होता है | जिस पर read write operation performed किये जाते है tape में infinite cells होते है या तो input symbol होता है या एक spacial symbol होता है जिसे blank कहा जाता है इसमें Head Pointer भी होता है जो वर्तमान में read किये जाने वाले cell को point करता है और यह दोनों दिशाओ में move हो सकता है
Turing Machine (TM) को 7 tuple के साथ describe किया जाता है |
Q : Finite set of states है
X : एक tape alphabet है
∑ : एक input alphabet है
δ : एक transition function है (δ : Q × X → Q × X ×) {Left Shift , Right Shift }
Q0 : initial state है
B : एक blank symbol है
F : set of final states है
Turing machine M = (Q, X, ∑, δ, q0, B, F) with
Q = {q0, q1, q2, qf}
X = {a, b}
∑ = {1}
q0 = {q0}
B = blank symbol
F = {qf }
|
|
|
|
||||
A | 1Rq1 | 1Lq0 | 1Lqf | ||||
B |
|
1Rq1 | 1Rqf |