Variants — multi-tape TM, non-deterministic TM, all equivalent

4.6.14 · Coding › Theory of Computation

WHY karte hain hum variants ki parwah?

KYA badalta hai variants ke beech mein: tapes ki sankhya, heads ki sankhya, tape ki direction, aur yeh ki transitions unique hain (deterministic) ya branching (non-deterministic).
KYU matter karta hai: agar ek chhoti si tweak naya power de deti, toh "computable" ek arbitrary, fragile notion hota. Iske bajaye har reasonable tweak equivalent hai ⇒ computability ki boundary ek real, model-independent cheez hai.
KAISE prove karte hain equivalence: ek simulator banao. Yeh dikhane ke liye ki model $B$ , model $A$ se zyada strong nahi hai, ek $A$ -machine likhte hain jo, $B$ ki description deke, $B$ ke har step ko reproduce kare. Equivalence = simulation dono directions mein.

Variant 1 — Multi-tape TM

Theorem: har multi-tape TM ka ek equivalent single-tape TM hota hai

Worked example Simulation:

$k$ tapes → 1 tape Idea: saare $k$ tapes ko ek tape par side-by-side store karo, delimiter # se alag karke, aur har head position ko symbol ke dotted version se mark karo.

Single tape ka content represent karta hai $# \overset{a}{˙}_{1} a_{2} a_{3} # b_{1} \dot{b}_{2} # \overset{c}{˙}_{1} c_{2} #$ jahan dots ( $\overset{x}{˙}$ ) dikhate hain ki har virtual head kahan baitha hai.

$k$ -tape machine ke ek step ko simulate karne ke liye:

Left→right scan karo saare blocks mein, (finite-state control mein) $k$ dotted symbols record karte hue. Yeh step kyon? Real $δ$ ko saare heads ek saath padhne hote hain; ek sweep unhe gather kar leti hai.
Ab control ko tuple $(\overset{a}{˙}_{1}, \dot{b}_{2}, \overset{c}{˙}_{1})$ pata hai, toh woh $δ$ compute karta hai. Kyon? $δ$ ek finite table hai; jab padhe gaye symbols paas hain, toh naye symbols/moves determined hain.
Doosra sweep: har dotted cell par naya symbol likho aur dot ko move ke hisaab se ek cell left ya right shift karo. Kyon? Yeh simultaneous update apply karta hai.
Agar koi virtual head ek # par move kare (block chhota tha), toh sab kuch right shift karo ek blank insert karne ke liye, us virtual tape ko badhate hue. Kyon? Virtual tapes unbounded hain; ek real tape ko jagah banani padti hai.

Conclusion: single-tape machine wahi outputs produce karta hai, toh woh same language recognize karta hai. ✔

Figure — Variants — multi-tape TM, non-deterministic TM, all equivalent

Variant 2 — Non-deterministic TM (NTM)

Theorem: har NTM ka ek equivalent deterministic TM (DTM) hota hai

Worked example Simulation: NTM → DTM breadth-first search se tree mein

DFS kyon nahi? Galat guess ek infinite non-accepting branch tak le ja sakti hai; DFS wahan hamesha ke liye fansa reh sakta hai aur paas ke accepting branch ko miss kar sakta hai. BFS depth $d + 1$ se pehle depth $d$ ke saare branches explore karta hai, toh finite depth par koi bhi accepting branch eventually mil jaata hai.

Ek 3-tape DTM use karo (hum pehle prove kar chuke hain ki 3-tape ≡ 1-tape):

Tape 1: original input $w$ (read-only, kabhi alter nahi hota). Kyon? Hume har branch ko same input se restart karna hai.
Tape 2: working tape — $w$ ki ek copy jis par hum ek chosen branch simulate karte hain.
Tape 3: current branch ka address: ${1, \dots, b}$ par ek string jahan $b$ kisi bhi $δ$ entry mein choices ki max sankhya hai. String 2 1 3 ka matlab hai "step 1 mein choice 2 lo, step 2 mein choice 1 lo, step 3 mein choice 3 lo."

Loop:

Tape 1 → tape 2 copy karo. Kyon? Is branch ke liye fresh start.
Tape 2 par NTM simulate karo, tape 3 use karke decide karo ki har step mein kaunsi choice lo. Agar tape 3 ka koi digit available choices ki sankhya se zyada hai (invalid branch), toh is branch ko abort karo.
Agar yeh branch accept kare → DTM accept karta hai. Kyon? Ek accepting branch kaafi hai.
Warna tape 3 ko next address par increment karo ( ${1.. b}^{*}$ par lexicographic, shortest first) aur repeat karo. Shortest-first kyon? Yahi BFS order hai jo guarantee karta hai ki hum koi finite accepting branch kabhi skip nahi karte.

Result: DTM accept karta hai iff koi branch accept kare ⇒ same language. ✔

Kyon yeh sab ek model par collapse karte hain

Recall Feynman: ek 12-saal ke bacche ko samjhao

Ek bacche ko socho jo ek maze ek notebook page aur pencil se solve kar raha hai. Ab ek amir bacche ko teen notebook pages do, ya use magically copies mein split hone do jo har ek alag turn try kare. Amir bacche faster khatam karte hain. Lekin yahan cool part hai: ek-page wala baccha copy kar sakta hai jo amir bacche karte hain — ek page par teen chhote boxes draw karo (pretend pages), ya har path ek ek karke try karo, dheere lekin pakka. Toh end mein, jo bhi maze amir bacche solve kar sakte hain, ek-page wala baccha bhi solve kar sakta hai — bas dheere. Same brain power, alag speed. Isi liye saare Turing machines, fancy ho ya plain, bilkul same problems solve kar sakte hain.

Active-recall flashcards

k

-tape TM ka transition function type kya hota hai?

δ : Q \times Γ^{k} \to Q \times Γ^{k} \times {L, R}^{k}

— ek saath

k

symbols padhta hai,

k

likhta hai, saare

k

heads ko independently move karta hai.

Ek single tape

k

tapes ko kaise simulate karta hai?

k

tape contents ko # se alag karke side-by-side store karo, har virtual head ko dotted symbol se mark karo; ek sweep saare heads padhti hai, doosri sweep updates likhti hai aur dots move karti hai, virtual tape badhane ke liye right shift karte hue.

Multi-tape → single-tape simulation mein time slowdown kitna hai?

Quadratic:

O (t (n)^{2})

, kyunki used tape

O (t (n))

lambi hai aur har step mein ~2 full sweeps lagte hain.

Non-deterministic TM ka acceptance rule kya hai?

w

ko accept karo iff computation tree ki kam se kam ek branch accept state tak pahunche.

NTM→DTM simulation mein DFS nahi balki BFS kyon use karna chahiye?

DFS ek infinite non-accepting branch mein girke paas ke accepting branch ko kabhi explore nahi kar sakta; BFS pehle saare depth-

d

nodes explore karta hai, guarantee karta hai ki koi bhi finite accepting branch milegi.

NTM→DTM simulation mein 3rd tape kya store karta hai?

Branch ka "address" —

{1.. b}

par ek string jo batata hai ki har step mein kaunsi choice lo; hum inhe shortest-first (BFS) order mein iterate karte hain.

NTM→DTM simulation ka time cost kya hai aur kyon?

2^{O (t (n))}

, kyunki computation tree mein

b^{t (n)}

tak nodes ho sakte hain aur DTM unhe sab visit kar sakta hai.

Kya non-determinism computational power add karta hai?

Nahi — yeh bilkul wahi languages recognize karta hai jo deterministic TMs karti hain. Yeh efficiency change kar sakta hai, computability kabhi nahi.

TM model ki "robustness" ka kya matlab hai?

Definition mein reasonable changes (tapes, non-determinism, two-way tape) decidable/recognizable languages ki class nahi badlte.

Kaun si famous thesis ko saare variants ke equivalent hone se support milti hai?

Church–Turing thesis: jo bhi effectively computable hai woh ek single-tape deterministic TM se computable hai.

Connections

Turing Machine — formal definition
Church–Turing Thesis
Decidability and Recognizability
Time Complexity and Big-O
P vs NP problem
Non-determinism in Finite Automata (NFA = DFA)
Universal Turing Machine