Turing machines — formal definition, computation, configurations

4.6.13 · Coding › Theory of Computation

1. Formal definition

HAR piece kya karta hai:

$δ (q, a) = (r, b, D)$ ka matlab: state $q$ mein symbol $a$ padhte hue, state $r$ mein switch karo, cell ko $b$ se overwrite karo, phir head ko direction $D$ ( $L$ ya $R$ ) mein ek cell move karo.

2. Configurations — ek snapshot "hum kahan hain?"

3. Ek configuration doosri ko kaise yield karti hai

Maano $δ (q, b) = (r, c, D)$ , head symbol $b$ padh raha hai. $a$ woh symbol hai jo head ke bilkul left mein hai, $u$ baaki left part hai, $v$ baaki right part hai.

Figure — Turing machines — formal definition, computation, configurations

4. Computation, acceptance, aur language

$A = {0^{2^{n}} : n \geq 0}$ ke liye (jinki length power of 2 ho) Idea: baar baar har doosre 0 ko cross off karo. Har pass count ko half karta hai. Accept tab karo jab har pass ek even count chhode jab tak ek akela 0 na bache.

$δ$ behavior ka sketch:

Right sweep karo, har doosre 0 ko cross out karo ( $X$ se replace karo).
- Yeh step kyun? 0s ki sankhya half ho rahi hai; power of two halving ke baad power of two hi rehti hai.
Agar ek pass mein exactly ek 0 dikha → accept. Kyun? $2^{0} = 1$ base case hai.
Agar kabhi odd count $> 1$ dikhe → reject. Kyun? ek odd number $> 1$ power of two nahi hota; halving fail ho jaata hai.
Warna head ko left end par rewind karo aur repeat karo.

0000 input par Trace (4 = $2^{2}$ ):

$q_{0} 0000$ → mark karo, alternate cross karo: tape ban jaati hai 0X0X, 0s ki count = 2 (even, $> 1$ ) → rewind.
Pass 2: 0X0X → cross karke 0XXX, count = 1 → accept. ✓

6. Common mistakes (Steel-man + fix)

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho ek endless kagaz ki patti hai jo boxes mein bata hui hai, aur ek chota robot ek box par baitha hai. Robot ke paas ek tiny notebook hai jisme kuch "moods" (states) hain. Woh apne box ka letter dekhta hai, phir uski rulebook kehti hai: "ise mita do, yeh naya letter likho, aur ek box left ya right khisak jao, aur uss mood mein switch ho jao." Yeh karta rehta hai. Do special moods matlab hain STOP-YES aur STOP-NO. Agar yeh kabhi STOP mood par nahi pahuncha, toh bas khisakta rehta hai hamesha ke liye. Yahi Turing machine hai — aur kamal ki baat yeh hai ki yeh bewaqoof robot woh sab compute kar sakta hai jo koi bhi computer kar sakta hai.

Flashcards

What are the 7 components of a Turing machine?

(Q, Σ, Γ, δ, q_{0}, q_{accept}, q_{reject})

— states, input alphabet, tape alphabet, transition function, start state, accept aur reject states.

What is the type signature of the transition function

δ

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

Why must

Σ \subseteq Γ

and

⊔ \in / Σ

Input tape par rehti hai (isliye

Σ \subseteq Γ

), lekin blank ka matlab hai "yahan koi input nahi" isliye yeh input mein kabhi appear nahi hona chahiye.

What is a configuration

u q v

Ek snapshot: state

q

, head ke left ki tape content

u

, head se shuru hone wali content

v

(

v

ke pehle symbol par head), aage sab blank.

Yield rule for moving right:

u a q b v ⊢

? (given

δ (q, b) = (r, c, R)

)

u a cr v

—

c

likho, head right step kare toh

c

left part mein join ho jaata hai.

Yield rule for moving left:

u a q b v ⊢

? (given

δ (q, b) = (r, c, L)

)

u r a c v

—

c

likho, head

a

par left step kare.

What happens when the head tries to move left off cell 0?

Woh cell 0 par ruk jaata hai (left-edge convention); computation jaari rehti hai.

Difference between Turing-recognizable and Turing-decidable?

Recognizable: koi TM members ko accept karta hai (non-members par loop kar sakta hai). Decidable: ek TM jo hamesha halt kare har input ke liye yes/no deta hai.

What is a decider?

Ek TM jo har input par halt karta hai (kabhi loop nahi karta).

What are the three outcomes of a TM running on input

w

Accept, reject, ya hamesha ke liye loop karna (kabhi halt nahi).

Why are there exactly two halting states?

Taaki machine "yes" ya "no" decide kar sake aur turant ruk sake, bina poori input padhe.

On which domain is

δ

defined?

(Q ∖ {q_{accept}, q_{reject}}) \times Γ

— halting states ke koi outgoing transitions nahi hote.

Connections

Finite Automata — TMs ek writable, infinite, two-way tape add karte hain (FAs read-only, one-way hote hain).
Pushdown Automata — PDAs ke paas stack hoti hai; TMs head movement ke zariye full random-ish access tak generalize karte hain.
Church-Turing Thesis — claim karta hai ki TMs sab effective computation capture karte hain.
Halting Problem — canonical undecidable language; recognizable-but-not-decidable gap mein rehta hai.
Recursively Enumerable Languages / Recursive Languages — yahan define hone wali language classes.
Nondeterministic Turing Machines — same power, possibly faster; ek yield relation se define hote hain, function se nahi.
Multitape Turing Machines — power mein equivalent, cleaner constructions ke liye use hote hain.