এই পর্বে যা শিখবেন
- Hilbert-এর সিদ্ধান্ত-সমস্যা থেকে Turing-এর ১৯৩৬ সালের মডেল কেন এল, আর tape, head, নিয়ন্ত্রণের ভূমিকা
- Turing machine-এর formal 7-tuple সংজ্ঞা, বাঁ প্রান্তের নিয়ম, transition সারণি আর state diagram পড়া
- Configuration u q v, ⊢, গ্রহণ-বর্জন-loop এই তিন ফল, আর decider বনাম recognizer-এর প্রথম ধারণা
- anbncn আর {w#w}-এর যন্ত্র নকশা, সঠিকতার প্রমাণ আর move গোনা
- Python-এ step cap-সহ simulator চালিয়ে brute force যাচাই, আর Sipser-এর তিন স্তরের বর্ণনায় উত্তর লেখা
১ · Hilbert-এর প্রশ্ন থেকে Turing-এর যন্ত্র — tape, head আর নিয়মের তালিকা
এতদিন যত যন্ত্র দেখেছেন, সবগুলোর স্মৃতি কোনো না কোনোভাবে সীমিত। DFA-র স্মৃতি শুধু state. পর্ব ৩২-এর PDA পেল একটি সীমাহীন stack, কিন্তু দেখতে পায় শুধু ওপরের চিহ্ন। পর্ব ৩৬-এ প্রমাণ হয়েছে, anbncn = {ε, abc, aabbcc, …} কোনো PDA চেনে না। এবার আমরা এমন একটি যন্ত্র দেখব, যার স্মৃতিতে কোনো সীমা নেই, আর যা স্মৃতির যেকোনো জায়গায় গিয়ে পড়তে ও লিখতে পারে। গণনার তত্ত্বের বাকি অর্ধেক, অর্থাৎ computability আর complexity, এই যন্ত্রের ওপর দাঁড়িয়ে।
ইতিহাস: ১৯২৮ সালে David Hilbert আর Wilhelm Ackermann-এর logic-এর বইয়ে একটি প্রশ্ন স্পষ্ট রূপ পায়, যা Entscheidungsproblem নামে পরিচিত: এমন কোনো যান্ত্রিক পদ্ধতি আছে কি, যা প্রথম-ক্রম logic-এর যেকোনো সূত্র দেখে বলে দেবে সেটি সর্বত্র সত্য কি না? “না” বলতে হলে আগে বলতে হয় “যান্ত্রিক পদ্ধতি” মানে ঠিক কী। Alan Turing তাঁর বিখ্যাত প্রবন্ধ “On Computable Numbers, with an Application to the Entscheidungsproblem” ১৯৩৬ সালে London Mathematical Society-তে জমা দেন; প্রবন্ধটি ১৯৩৬–৩৭ সালে ছাপা হয়। প্রায় একই সময়ে Alonzo Church আলাদা পথে (λ-calculus দিয়ে) একই নেতিবাচক উত্তরে পৌঁছান, আর Emil Post ১৯৩৬ সালে Turing-এর খুব কাছাকাছি একটি মডেল প্রকাশ করেন। “Turing machine” নামটি Church-এর ১৯৩৭ সালের একটি review থেকে প্রচলিত হয় বলে সাধারণত বলা হয়। পুরো গল্প আর মডেলগুলোর সমতা পর্ব ৪৭-এ।
Turing-এর মূল চিন্তা ছিল একজন মানুষ হিসাবকারীর কাজ খুঁটিয়ে দেখা। ভাবুন, পুরোনো দিনের একজন হিসাবরক্ষক একটি লম্বা খাতায় যোগ-বিয়োগ করছেন। খাতা ঘরে ঘরে ভাগ করা, প্রতিটি ঘরে একটি চিহ্ন। তিনি একসঙ্গে একটি বা অল্প কয়েকটি ঘর দেখেন। তাঁর মাথায় থাকে সসীম কয়েকটি “মনের অবস্থা” (“এখন হাতে ১ আছে”, “এখন বাঁয়ে ফিরছি”)। প্রতিটি মুহূর্তে তিনি যা দেখছেন আর মনের অবস্থা মিলিয়ে ঠিক করেন: এই ঘরে কী লিখবেন, কোন দিকে সরবেন, আর মনের নতুন অবস্থা কী হবে। খাতা ফুরিয়ে গেলে নতুন পাতা জুড়ে দেন। Turing যুক্তি দেন, যেকোনো যান্ত্রিক হিসাব এই কয়েকটি সরল কাজে ভাঙা যায়।
রেলস্টেশনের একজন টিকিট-পরীক্ষককে কল্পনা করুন, যিনি একটি লম্বা বগির সারির পাশে হাঁটছেন। তাঁর হাতে একটি চক। প্রতিটি বগির দরজায় তিনি একটি চিহ্ন দেখেন, চাইলে মুছে নতুন চিহ্ন দেন, তারপর এক বগি সামনে বা পেছনে যান। তাঁর পকেটে একটি ছোট নিয়মের কার্ড, যেমন: “অবস্থা ‘খুঁজছি’ আর দরজায় ‘খালি’ লেখা থাকলে: ‘ভরা’ লেখা, এক বগি সামনে”। কার্ডটি সসীম, কিন্তু সারি যত লম্বা ইচ্ছা হতে পারে, আর চকের দাগ তাঁর বাড়তি স্মৃতি। এটিই Turing machine: চকের দাগ হলো tape-এ লেখা, পরীক্ষক হলো head, কার্ড হলো transition function.
যন্ত্রটির তিন অংশ নিচের ছবিতে।
Turing machine-এর তিন অংশ
ডানে অসীম tape; শুরুতে input বাঁ প্রান্ত থেকে, বাকি সব ঘরে blank ␣. Head প্রথম ঘরে, নিয়ন্ত্রণ start state q0-এ।
একটি বড় পার্থক্য খেয়াল করুন। DFA আর PDA input পড়া শেষ হলেই থামে, তাই তাদের computation সবসময় সসীম। Turing machine-এর কোনো “input শেষ” মুহূর্ত নেই: head ইচ্ছামতো ঘোরে, তাই যন্ত্রটি থামে শুধু তখন, যখন একটি বিশেষ accept বা reject state-এ ঢোকে। কখনো না ঢুকলে চিরকাল চলতে থাকে। এই তৃতীয় সম্ভাবনাটি, “loop”, পুরো computability তত্ত্বের কেন্দ্রে। ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৫-এ Turing machine-এর একটি সংক্ষিপ্ত পরিচয় আছে; এখানে আমরা সংজ্ঞা, configuration আর প্রমাণে অনেক গভীরে যাব।
২ · Formal definition — M = (Q, Σ, Γ, δ, q0, qaccept, qreject)
এই কোর্স Sipser-এর রীতি মানে। দুটি নতুন উপাদান আছে: tape alphabet Γ, যাতে input-এর চিহ্ন ছাড়াও যন্ত্রের নিজের লেখার চিহ্ন (যেমন দাগ দেওয়া X) থাকে, আর blank চিহ্ন ␣, যা tape-এর ফাঁকা ঘর বোঝায়।
একটি Turing machine হলো সাতটি জিনিসের tuple M = (Q, Σ, Γ, δ, q0, qaccept, qreject), যেখানে Q, Σ, Γ সসীম set আর
১. Q হলো state-এর set;
২. Σ হলো input alphabet, আর ␣ ∉ Σ;
৩. Γ হলো tape alphabet, যেখানে ␣ ∈ Γ আর Σ ⊆ Γ;
৪. δ: Q′ × Γ → Q × Γ × {L, R} হলো transition function, যেখানে Q′ = Q \ {qaccept, qreject};
৫. q0 ∈ Q হলো start state;
৬. qaccept ∈ Q হলো accept state;
৭. qreject ∈ Q হলো reject state, আর qreject ≠ qaccept.
δ(q, a) = (r, b, D) পড়ুন এভাবে: “state q-তে head-এর নিচে a থাকলে, সেখানে b লিখুন, state r-এ যান, আর head এক ঘর D দিকে সরান (L = বাঁয়ে, R = ডানে)।” δ একটি function, তাই প্রতিটি অবস্থায় ঠিক একটি পদক্ষেপ: যন্ত্রটি deterministic. State diagram-এ এই নিয়ম লেখা হয় q থেকে r-এ একটি তীরে a → b, R. চিহ্ন না বদলালে (b = a) সংক্ষেপে a → R. দুটি halting state থেকে কোনো নিয়ম নেই: সেখানে পৌঁছালেই যন্ত্র থামে।
এই কোর্সের রীতি: (১) tape শুধু ডানে অসীম; বাঁ দিকে একটি প্রথম ঘর আছে। (২) শুরুতে input w = w1w2…wn প্রথম n ঘরে, বাকি সব ঘরে ␣, head প্রথম ঘরে। Σ-তে ␣ নেই বলে প্রথম ␣-ই input-এর শেষ চিহ্নিত করে। (৩) প্রথম ঘরে থাকা অবস্থায় L নির্দেশ এলে head জায়গায় থাকে, যন্ত্র ভেঙে পড়ে না। (৪) ছবি বা সারণিতে কোনো (state, চিহ্ন) জোড়ের নিয়ম না দেখালে ধরে নিন, সেটি qreject-এ যায়। এতে ছবি পরিষ্কার থাকে, কিন্তু সংজ্ঞায় δ সবসময় পূর্ণ।
এবার পুরো একটি যন্ত্র, যা অংশ ৪-এ বিস্তারিত বোঝানো হবে। M1 = (Q, {a, b, c}, Γ, δ, q0, qaccept, qreject), যেখানে Q = {q0, q1, q2, q3, q4, q5, qaccept, qreject} আর Γ = {a, b, c, X, Y, Z, ␣}. X, Y, Z হলো দাগ-কাটা a, b, c. প্রতিটি ঘরে (পরের state, লেখা চিহ্ন, দিক); “—” মানে qreject. কোডে qaccept লেখা হবে qacc.
| state | a | b | c | X | Y | Z | ␣ |
|---|---|---|---|---|---|---|---|
| q0 | q1, X, R | — | — | — | q4, Y, R | — | qacc, ␣, R |
| q1 | q1, a, R | q2, Y, R | — | — | q1, Y, R | — | — |
| q2 | — | q2, b, R | q3, Z, L | — | — | q2, Z, R | — |
| q3 | q3, a, L | q3, b, L | — | q0, X, R | q3, Y, L | q3, Z, L | — |
| q4 | — | — | — | — | q4, Y, R | q5, Z, R | — |
| q5 | — | — | — | — | — | q5, Z, R | qacc, ␣, R |
একই যন্ত্রের state diagram নিচে। প্রথমবার পড়লে শুধু ওপরের সারিটি দেখুন: q0 → q1 → q2 → q3 → q0 একটি চক্র, যার প্রতিটি পাক একটি a, একটি b আর একটি c কাটে।
M1: anbncn-এর Turing machine
তীরে “পড়া → লেখা, দিক”; লেখা না বদলালে “পড়া → দিক”. দেখানো হয়নি এমন সব নিয়ম qreject-এ যায়।
অন্য বইয়ের রীতি: Hopcroft–Motwani–Ullman (HMU)-তে tape দুই দিকেই অসীম, blank লেখা হয় B, accept state-এর একটি set F থাকে, আর আলাদা reject state নেই: কোনো নিয়ম না থাকলে যন্ত্র থামে, আর থামার সময় F-এ থাকলে গ্রহণ। কিছু বইয়ে head-এর তৃতীয় বিকল্প S (জায়গায় থাকা) আছে। এই সব রূপভেদের ক্ষমতা হুবহু সমান: একটি থেকে অন্যটিতে অনুকরণ করা যায়, প্রমাণ পর্ব ৪৫-এ। ফাঁকা string-এর জন্য কিছু বইয়ে λ লেখা হয়; এই কোর্সে সবসময় ε.
৩ · Configuration আর computation — u q v, ⊢ আর তিনটি সম্ভাব্য ফল
PDA-র এক মুহূর্তের পূর্ণ অবস্থা ছিল (state, বাকি input, stack). Turing machine-এর ক্ষেত্রে তিনটি জিনিস লাগে: বর্তমান state, পুরো tape-এর লেখা, আর head-এর অবস্থান। এগুলো এক লাইনে লেখার চমৎকার একটি রীতি আছে।
M-এর একটি configuration লেখা হয় u q v, যেখানে u, v ∈ Γ∗ আর q ∈ Q. অর্থ: tape-এ বাঁ থেকে uv লেখা, তার পরে সব ␣; state q; head v-এর প্রথম চিহ্নের ওপর (v = ε হলে head একটি ␣-এর ওপর)। a, b, c ∈ Γ আর u, v ∈ Γ∗ হলে এক ধাপের yields সম্পর্ক ⊢:
ua qi bv ⊢ u qj acv যদি δ(qi, b) = (qj, c, L)
ua qi bv ⊢ uac qj v যদি δ(qi, b) = (qj, c, R)
বাঁ প্রান্তে: qi bv ⊢ qj cv যদি দিক L (head জায়গায় থাকে), আর qi bv ⊢ c qj v যদি দিক R. ডান প্রান্তে u a qi-কে u a qi ␣ ধরা হয়।
কয়েকটি বিশেষ configuration-এর নাম আছে। Input w-এর start configuration হলো q0 w. State qaccept থাকলে accepting configuration, qreject থাকলে rejecting configuration; দুটিই halting configuration, কারণ সেখান থেকে আর কোনো ধাপ নেই। উদাহরণ: M1-এ δ(q1, b) = (q2, Y, R), তাই configuration X a q1 bbcc থেকে পরের ধাপ X a Y q2 bcc. Head এক ঘর ডানে সরল, আর পুরোনো b-এর জায়গায় এখন Y.
Input w-এর ওপর M গ্রহণ করে, যদি configuration-এর একটি ক্রম C1, C2, …, Ck থাকে যেখানে C1 = q0 w, প্রতিটি Ci ⊢ Ci+1, আর Ck একটি accepting configuration. একইভাবে Ck rejecting হলে M w-কে বর্জন করে। কোনোটিই না হলে, অর্থাৎ ক্রমটি কখনো halting configuration-এ পৌঁছায় না, তখন M w-এ loop করে। M যে language recognize করে: L(M) = {w ∈ Σ∗ : M w গ্রহণ করে}.
তিনটি ফলের পার্থক্যই পরের পুরো মডিউলের বিষয়। যে যন্ত্র প্রতিটি input-এ থামে (গ্রহণ বা বর্জন), তাকে বলে decider; decider M যদি L(M) = L দেয়, তবে M L-কে decide করে, আর L একটি decidable language. কোনো TM L-কে recognize করলে (কিছু input-এ loop করলেও) L Turing-recognizable. পর্ব ০৫-এ এই দুই ধারণার পূর্বাভাস দেখেছেন; পূর্ণ আলোচনা পর্ব ৫০-এ, আর কোন language recognizable অথচ decidable নয়, তা পর্ব ৫১-এ।
Loop দেখতে কেমন? নিচের ছোট যন্ত্র Mloop-এর input alphabet {a, b}: δ(q0, a) = (qaccept, a, R), δ(q0, b) = (q1, b, R), আর q1-এ যেকোনো চিহ্ন x-এর জন্য δ(q1, x) = (q0, x, L). বাকি সব (যেমন q0-তে ␣) qreject. Simulator কখনো চিরকাল চালানো যায় না, তাই আমরা সবসময় একটি step cap রাখি: সর্বোচ্চ কয়টি move চালানো হবে। Cap-এ পৌঁছানো মানে “এখনো উত্তর নেই”, “loop করে” নয়।
1q0 : a → R (qacc)2q0 : b → R (q1)3q1 : a, b, ␣ → L (q0)4বাকি সব → qrej5(তুলনা) q0 : ␣ → R (q0)
| configuration | |
| input | |
| move |
- শুরু। Input ba, start configuration q0 ba: state q0, head প্রথম ঘরে (b-এর ওপর)।
- প্রথম move. δ(q0, b) = (q1, b, R): b-ই লেখা হলো, head ডানে। Configuration b q1 a.
- দ্বিতীয় move. δ(q1, a) = (q0, a, L): head বাঁয়ে ফিরল। Configuration আবার q0 ba, move 0-এর হুবহু একই। যন্ত্রটি deterministic, তাই এখান থেকে একই দুই ধাপ বারবার ঘটবে: Mloop ba-তে loop করে।
- Step cap. Simulator-এ cap = 6 রাখলে move 6-এ আবার q0 ba-তে থেমে বলে “cap-এ থামানো হলো”। এটি কোনো রায় নয়; cap না থাকলে program-টি নিজেই চিরকাল চলত।
- বাকি দুই ফল। ab-তে প্রথম move-এই δ(q0, a) দিয়ে a qacc b: গৃহীত। ε-তে head-এর নিচে ␣, যার নিয়ম নেই, তাই ␣ qrej ␣: বর্জিত। তাই L(Mloop) = {a দিয়ে শুরু হওয়া string}, আর Mloop decider নয়।
- Loop মানেই পুনরাবৃত্তি নয়। এখানে configuration ফিরে আসায় loop চেনা সহজ ছিল। কিন্তু ধরুন অন্য একটি যন্ত্রের নিয়ম q0 : ␣ → R (q0); সেটি ε পেলে চিরকাল ডানে হাঁটে, আর প্রতিটি configuration নতুন (␣ q0 ␣, ␣␣ q0 ␣, …)। সাধারণভাবে “এই যন্ত্র কি কখনো থামবে?” প্রশ্নের কোনো algorithm নেই, পর্ব ৫১-এর halting problem.
একটি সূক্ষ্ম কথা: L(Mloop) = {a দিয়ে শুরু হওয়া string} একটি decidable language, যদিও Mloop নিজে decider নয়। “b পেলে সরাসরি qreject” নিয়মের আরেকটি যন্ত্র সব input-এ থামে আর একই language দেয়। Decidability হলো language-এর ধর্ম: অন্তত একটি decider থাকলেই চলে। একটি নির্দিষ্ট যন্ত্র loop করলে language সম্পর্কে কিছু প্রমাণ হয় না।
৪ · প্রথম যন্ত্র: anbncn — দাগ কেটে কেটে মেলানো
একটি PDA a গুনতে stack ভরে, b-এর সঙ্গে মেলাতে খালি করে, তারপর c-এর জন্য আর কিছু থাকে না। Turing machine-এর সমস্যা নেই: সে input-এর ওপরেই দাগ দিতে পারে আর বারবার ফিরে আসতে পারে। কৌশলটির নাম crossing off (দাগ কাটা)। বাজারের ফর্দ মেলানোর মতো: তিনটি তালিকায় একটি করে জিনিস কেটে দিন, শুরুতে ফিরে আবার একটি করে, যতক্ষণ না কোনো তালিকা আগে ফুরায়।
উচ্চ-স্তরের বর্ণনা। M1 = “input w-এর ওপর: (১) সবচেয়ে বাঁয়ের না-কাটা a-কে X করুন; (২) ডানে গিয়ে প্রথম না-কাটা b-কে Y করুন; (৩) আরও ডানে গিয়ে প্রথম না-কাটা c-কে Z করুন; (৪) বাঁয়ে ফিরে শেষ X-এর ঠিক ডানে আসুন, আর আবার (১) থেকে; (৫) a আর না থাকলে, অর্থাৎ X-এর পরে Y দেখলে, যাচাই করুন বাকি tape ঠিক Y…YZ…Z, তারপর ␣. হলে গ্রহণ, না হলে কোনো ধাপে প্রত্যাশিত চিহ্ন না পেলে বর্জন।” অংশ ২-এর সারণি ঠিক এটিকেই state দিয়ে লেখে: q0 a কাটে, q1 b খোঁজে, q2 c খোঁজে, q3 বাঁয়ে ফেরে, q4 আর q5 শেষ যাচাই করে।
1q0 : a → X, R (q1)2q1 : a, Y → R ; b → Y, R (q2)3q2 : b, Z → R ; c → Z, L (q3)4q3 : a, b, Y, Z → L ; X → R (q0)5q0 : Y → R (q4) ; q4 : Y → R ; Z → R (q5)6q5 : Z → R ; ␣ → R (qacc)
| u q v | |
| move নম্বর | |
| কাটা X, Y, Z |
- শুরু। q0 aabbcc: head প্রথম ঘরে, নিচে a.
- a কাটা। δ(q0, a) = (q1, X, R). Configuration X q1 abbcc. q1-এর কাজ: a আর Y পেরিয়ে প্রথম b খোঁজা।
- b কাটা। q1 একটি a পেরিয়ে (move 2) b পেল, সেটিকে Y করে ডানে: XaY q2 bcc (move 3).
- c কাটা, ফেরা শুরু। q2 একটি b পেরিয়ে c পেল, Z লিখে বাঁয়ে সরল: XaY q3 bZc (move 5). এবার q3 a, b, Y, Z পেরিয়ে বাঁয়ে হাঁটবে।
- পাক ১ শেষ। q3 X দেখে ডানে সরে q0-তে: X q0 aYbZc (move 9). প্রতিটি তালিকা থেকে একটি করে কাটা হয়েছে; head এখন শেষ X-এর ঠিক ডানে।
- পাক ২. আবার একই কাজ: a → X, তারপর Y পেরিয়ে b → Y, তারপর Z পেরিয়ে c → Z: XXYY q3 ZZ (move 14). সব চিহ্ন এখন কাটা।
- a ফুরিয়েছে। q3 ফিরে আসে, আর move 18-এ XX q0 YYZZ: q0-এর নিচে Y. মানে কোনো a বাকি নেই; δ(q0, Y) = (q4, Y, R) শেষ যাচাইয়ে পাঠায়।
- শেষ যাচাই। q4 Y পেরিয়ে Z-তে q5, q5 Z পেরিয়ে ␣ পেল: XXYYZZ q5 ␣ (move 22). কোথাও কোনো না-কাটা চিহ্ন নেই।
- গ্রহণ। δ(q5, ␣) = (qacc, ␣, R): move 23-এ accepting configuration. সূত্র 4n2 + 3n + 1-এ n = 2 বসালে 16 + 6 + 1 = 23.
বাতিল string কীভাবে আটকায়? aabbc-তে দ্বিতীয় পাকে q2 Z পেরিয়ে c খুঁজতে গিয়ে ␣ পায় (configuration XXYYZ q2 ␣), যার নিয়ম নেই: move 14-এ বর্জন। abcabc-তে প্রথম পাকের পরে tape XYZabc; q0 Y দেখে যাচাইয়ে যায়, আর q5 Z-এর পরে a পায়: বর্জন। এখন যন্ত্রটি যে সব ক্ষেত্রে ঠিক, তা প্রমাণ করা যাক।
M1 একটি decider, আর L(M1) = {anbncn : n ≥ 0}. আরও, anbncn-এ M1 ঠিক 4n2 + 3n + 1টি move-এ গ্রহণ করে।
প্রমাণ: w-এর ওপর যেকোনো computation নিন। একটি “পাক” মানে q0-তে ঢোকা থেকে পরের বার q0-তে ঢোকা পর্যন্ত।
- M1 শুধু a-এর ওপর X, b-এর ওপর Y আর c-এর ওপর Z লেখে; অন্য সব নিয়ম পড়া চিহ্নটিই আবার লেখে। তাই যেকোনো মুহূর্তে tape-এ X → a, Y → b, Z → c বসালে মূল input w ফিরে আসে। — সারণি দেখে; invariant I1
- যে পাক q0-তে ফিরে আসে, তাতে ঠিক একটি X, একটি Y আর একটি Z লেখা হয় (q0, q1, q2-তে একবার করে)। তাই প্রতিবার q0-তে ঢোকার সময় #X = #Y = #Z. — invariant I2, পাক-সংখ্যার ওপর induction
- q3 বাঁয়ে হাঁটে প্রথম X পর্যন্ত, অর্থাৎ ডান দিক থেকে প্রথম X, তারপর এক ঘর ডানে q0. তাই q0 সবসময় শেষ X-এর ঠিক ডানের ঘরে, আর সব X মিলে tape-এর একটি একটানা শুরু-অংশ। — invariant I3
- গ্রহণ দুই জায়গায় হতে পারে। (ক) q0-তে ␣: প্রথম পাকের পরে X-এর ডানে অন্তত একটি Y আর একটি Z থাকে, তাই q0 ␣ দেখে শুধু শুরুতে, যখন w = ε. (খ) q5-এ ␣: তখন q0 Y দেখেছে, আর q4, q5 যাচাই করেছে যে শেষ X-এর পরের অংশ YmZp␣, যেখানে m, p ≥ 1. — সারণিতে qacc-এ যাওয়ার মাত্র দুটি নিয়ম
- (খ)-তে I3 অনুযায়ী tape = XkYmZp, আর I2 অনুযায়ী k = m = p. I1 দিয়ে w = akbkck. তাই L(M1) ⊆ {anbncn}. — ১–৪ মিলিয়ে
- উল্টো দিক: w = anbncn হলে পাক i-এর শুরুতে tape = Xi−1an−i+1Yi−1bn−i+1Zi−1cn−i+1, আর প্রতিটি খোঁজা চিহ্ন ঠিক জায়গায় পাওয়া যায়। n পাকের পরে q0 Y দেখে, আর যাচাই সফল। — i-এর ওপর induction
- Move গোনা (0 থেকে ঘর গুনে): পাক i শুরু হয় ঘর i − 1-এ। ডানে প্রথম b (ঘর n + i − 1) পর্যন্ত n move, b → Y-তে 1, প্রথম c (ঘর 2n + i − 1) পর্যন্ত n − 1, c → Z-তে বাঁয়ে 1, ঘর i − 1-এর X পর্যন্ত 2n − 1, তারপর ডানে 1: মোট 4n + 1. n পাকে 4n2 + n, আর শেষ যাচাইয়ে ঘর n থেকে ঘর 3n-এর ␣ পর্যন্ত 2n move আর গ্রহণের 1টি। যোগফল 4n2 + 3n + 1. — সরাসরি গোনা
- Decider: head কখনো প্রথম ␣-এর পরে যায় না (q1 আর q2 ␣ পেলে বর্জন করে), তাই একটি পাক বড়জোর 2|w| + 2 move. প্রতিটি সম্পূর্ণ পাক তিনটি input চিহ্ন কাটে, তাই পাক বড়জোর |w|/3 + 1টি, আর শেষ যাচাই বড়জোর |w| + 1 move. সব input-এ M1 থামে। ∎ — সসীম সীমা
লক্ষ করুন, ধাপ ৮-এর সীমা |w|-এর বর্গের মতো বাড়ে। একটি tape-এর যন্ত্রে বারবার আসা-যাওয়ার এই খরচ এড়ানো যায় না বলে জানা আছে (আরও গভীরে দেখুন), আর একাধিক tape পেলে তা রৈখিক হয়ে যায় (পর্ব ৪৫)। Move গোনা, অর্থাৎ time, পর্ব ৫৭-এ complexity-র মূল একক হবে।
৫ · Python-এ TM simulator — configuration ছাপা, step cap আর brute force
সংজ্ঞাটি সরাসরি কোডে নামানো যায়। Tape একটি list, head একটি index, δ একটি dict: (state, চিহ্ন) থেকে (পরের state, লেখা চিহ্ন, দিক)। নিয়মগুলো সারণির মতোই এক লাইনে একটি করে লেখা হয়েছে; “=” মানে পড়া চিহ্নটিই আবার লেখা। Dict-এ না থাকা জোড় qreject-এ যায়, বাঁ প্রান্তে L মানে জায়গায় থাকা, আর cap সর্বোচ্চ move-সংখ্যা: এর বেশি চালানো হয় না।
B = "␣" # the blank symbol
def T(text): # one line per rule: state symbols next write move
d = {}
for line in text.strip().splitlines():
q, syms, r, b, mv = line.split()
for s in syms.split(","): # "=" means: write the same symbol
d[(q, s)] = (r, s if b == "=" else b, mv)
return d
def run(M, w, cap=10_000, show=False):
tape, q, h = list(w) or [B], M["q0"], 0
for step in range(cap + 1):
if show: print(f"{step:3}: " + f"{''.join(tape[:h])} {q} {''.join(tape[h:])}".strip())
if q in ("qacc", "qrej"): return q, step
if step == cap: return "stopped by cap", step
q, tape[h], mv = M["d"].get((q, tape[h]), ("qrej", tape[h], "R"))
h = h + 1 if mv == "R" else max(h - 1, 0) # left end: stay put
if h == len(tape): tape.append(B)
ANBNCN = {"q0": "q0", "d": T("""
q0 a q1 X R
q0 Y q4 = R
q0 ␣ qacc = R
q1 a,Y q1 = R
q1 b q2 Y R
q2 b,Z q2 = R
q2 c q3 Z L
q3 a,b,Y,Z q3 = L
q3 X q0 = R
q4 Y q4 = R
q4 Z q5 = R
q5 Z q5 = R
q5 ␣ qacc = R""")}
LOOP = {"q0": "q0", "d": T("q0 a qacc = R\nq0 b q1 = R\nq1 a,b,␣ q0 = L")}
print("abc:"); run(ANBNCN, "abc", show=True)
for w in ["aabbcc", "aabbc", "abcabc", ""]: print(f"{w or 'ε':7} -> {run(ANBNCN, w)}")
print("LOOP on ba ->", run(LOOP, "ba", cap=1000))আসল আউটপুট (ব্রাউজারের Python):
abc:
0: q0 abc
1: X q1 bc
2: XY q2 c
3: X q3 YZ
4: q3 XYZ
5: X q0 YZ
6: XY q4 Z
7: XYZ q5 ␣
8: XYZ␣ qacc ␣
aabbcc -> ('qacc', 23)
aabbc -> ('qrej', 14)
abcabc -> ('qrej', 8)
ε -> ('qacc', 1)
LOOP on ba -> ('stopped by cap', 1000)
প্রথম অংশে abc-এর পুরো computation, প্রতিটি লাইন একটি configuration u q v. Move 3-এ “X q3 YZ”: c-কে Z লিখে head বাঁয়ে Y-এর ওপর। Move 4-এ “q3 XYZ”: head প্রথম ঘরে X-এর ওপর। Move 5-এ X দেখে ডানে q0. Move 7-এ head tape-এর লেখা অংশের বাইরে, তাই v = ␣. n = 1-এ সূত্র 4 + 3 + 1 = 8 move. তারপর চারটি ফল: aabbcc ২৩ move-এ গৃহীত, যা stepper-এর সঙ্গে মেলে; aabbc আর abcabc অংশ ৪-এ বলা জায়গায় বর্জিত; ε একটি move-এ গৃহীত (n = 0). শেষ লাইনে Mloop ১০০০ move পর্যন্ত চলেও থামেনি, তাই simulator শুধু বলছে “cap-এ থামানো”: এটি কোনো রায় নয়।
কয়েকটি উদাহরণে চালানো প্রমাণ নয়, কিন্তু ভুল ধরার সবচেয়ে সস্তা উপায় হলো brute force: ছোট দৈর্ঘ্যের সব string-এ যন্ত্র চালিয়ে language-এর সংজ্ঞার সঙ্গে মেলানো। পরের ব্লক আগের ব্লকের run আর T ব্যবহার করে (একই namespace), অংশ ৬-এর {w#w} যন্ত্রটিও যোগ করে, আর দুই যন্ত্রকে দৈর্ঘ্য ০ থেকে ৯ পর্যন্ত প্রতিটি string-এ পরীক্ষা করে। সঙ্গে move-সংখ্যা মেলায় সূত্রের সঙ্গে।
from itertools import product
WW = {"q0": "q0", "d": T("""
q0 0 q1 x R
q0 1 q2 x R
q0 # q7 = R
q1 0,1 q1 = R
q1 # q3 = R
q2 0,1 q2 = R
q2 # q4 = R
q3 x q3 = R
q3 0 q5 x L
q4 x q4 = R
q4 1 q5 x L
q5 0,1,x q5 = L
q5 # q6 = L
q6 0,1 q6 = L
q6 x q0 = R
q7 x q7 = R
q7 ␣ qacc = R""")}
in_abc = lambda w: w == "a" * (len(w) // 3) + "b" * (len(w) // 3) + "c" * (len(w) // 3)
in_ww = lambda w: w.count("#") == 1 and w.split("#")[0] == w.split("#")[1]
for name, M, sigma, inL in [("anbncn", ANBNCN, "abc", in_abc), ("w#w", WW, "01#", in_ww)]:
words = ["".join(t) for k in range(10) for t in product(sigma, repeat=k)]
out = {w: run(M, w) for w in words}
acc = [w for w in words if out[w][0] == "qacc"]
wrong = [w for w in words if (out[w][0] == "qacc") != inL(w)]
capped = [w for w in words if out[w][0] not in ("qacc", "qrej")]
print(f"{name}: {len(words)} strings, {len(acc)} accepted, wrong {len(wrong)},"
f" cap hit {len(capped)}, max moves {max(o[1] for o in out.values())}")
print("a^n b^n c^n moves:", [run(ANBNCN, "a" * n + "b" * n + "c" * n)[1] for n in range(1, 9)])
print("4n^2 + 3n + 1 :", [4 * n * n + 3 * n + 1 for n in range(1, 9)])
moves = {k: {run(WW, "".join(t) + "#" + "".join(t))[1] for t in product("01", repeat=k)}
for k in range(1, 6)}
print("w#w moves by |w| :", moves, " 2(k+1)^2:", [2 * (k + 1) ** 2 for k in range(1, 6)])আসল আউটপুট (ব্রাউজারের Python):
anbncn: 29524 strings, 4 accepted, wrong 0, cap hit 0, max moves 46
w#w: 29524 strings, 31 accepted, wrong 0, cap hit 0, max moves 50
a^n b^n c^n moves: [8, 23, 46, 77, 116, 163, 218, 281]
4n^2 + 3n + 1 : [8, 23, 46, 77, 116, 163, 218, 281]
w#w moves by |w| : {1: {8}, 2: {18}, 3: {32}, 4: {50}, 5: {72}} 2(k+1)^2: [8, 18, 32, 50, 72]
তিন চিহ্নের alphabet-এ দৈর্ঘ্য ০ থেকে ৯ পর্যন্ত (310 − 1)/2 = 29524টি string. M1 ঠিক ৪টি গ্রহণ করে (ε, abc, aabbcc, aaabbbccc), {w#w}-এর যন্ত্র ৩১টি (দৈর্ঘ্য 2k + 1-এ 2kটি, k = 0 থেকে 4: 1 + 2 + 4 + 8 + 16), আর কোথাও সংজ্ঞার সঙ্গে অমিল নেই। “cap hit 0” গুরুত্বপূর্ণ: কোনো input-এ cap ছোঁয়নি, অর্থাৎ পরীক্ষিত প্রতিটি string-এ যন্ত্র নিজেই থেমেছে, যা উপপাদ্য ৪.১-এর decider-দাবির সঙ্গে মেলে (প্রমাণ নয়, সমর্থন)। Move-সংখ্যা 8, 23, 46, … হুবহু 4n2 + 3n + 1. {w#w}-এ |w| = k হলে প্রতিটি w-এর move-সংখ্যা একই, 2(k + 1)2: যন্ত্রের চলাফেরা চিহ্ন 0 না 1 তার ওপর নির্ভর করে না। দুটিই বর্গের হারে বাড়ে।
৬ · বাজারঘরের যন্ত্র: {w#w} — দুটি order ID কি এক?
বাজারঘরের ফেরত-ব্যবস্থায় একটি যাচাই আছে: গ্রাহকের পাঠানো ফর্মে order ID দুবার লেখা থাকে, মাঝে একটি #, আর দুটি হুবহু এক হতে হবে। সরল রূপে, binary ID-র জন্য language
এটি context-free নয় (প্রমাণ পর্ব ৩৬-এর ধাঁচে; ww-এর মতোই)। Turing machine-এর কৌশল আঁকাবাঁকা পথে মেলানো, Sipser-এর বইয়ের প্রথম উদাহরণ M1-এর মতো। এখানে state-এর নাম q0 থেকে শুরু: “# -এর বাঁয়ের প্রথম না-কাটা চিহ্ন পড়ুন আর x দিয়ে কাটুন; চিহ্নটি 0 না 1, তা state-এ মনে রাখুন (q1 বা q2); # পেরিয়ে ডানে প্রথম না-কাটা চিহ্ন দেখুন; মিললে x দিয়ে কাটুন, না মিললে বর্জন; বাঁয়ে ফিরে আবার। বাঁ দিকের সব কাটা হলে (q0 # দেখলে) যাচাই করুন ডান দিকেও শুধু x, তারপর ␣।”
| state | ভূমিকা | নিয়ম |
|---|---|---|
| q0 | বাঁয়ের পরের চিহ্ন কাটা | 0 → x, R (q1); 1 → x, R (q2); # → R (q7) |
| q1 / q2 | 0 / 1 মনে রেখে # পর্যন্ত | 0, 1 → R; # → R (q3 / q4) |
| q3 / q4 | ডানে মেলানো | x → R; 0 / 1 → x, L (q5) |
| q5 | # পর্যন্ত বাঁয়ে | 0, 1, x → L; # → L (q6) |
| q6 | শেষ x পর্যন্ত বাঁয়ে | 0, 1 → L; x → R (q0) |
| q7 | ডানে সব কাটা? | x → R; ␣ → R (qacc) |
লক্ষ করুন, “কোন চিহ্ন বহন করছি” তথ্যটি tape-এ নয়, state-এ রাখা হয়েছে: q1 মানে “0 নিয়ে যাচ্ছি”, q2 মানে “1 নিয়ে যাচ্ছি”। Alphabet বড় হলে (যেমন order ID-তে ০–৯) প্রতিটি অঙ্কের জন্য আলাদা state লাগবে, কিন্তু সংখ্যাটি সসীমই থাকে। নিচের stepper 01#01-এ যন্ত্রের পুরো ১৮টি move-এর মূল মুহূর্তগুলো দেখায়।
1q0 : 0 → x, R (q1) ; 1 → x, R (q2)2q1, q2 : 0, 1 → R ; # → R (q3, q4)3q3, q4 : x → R ; 0/1 → x, L (q5)4q5 : 0, 1, x → L ; # → L (q6)5q6 : 0, 1 → L ; x → R (q0)6q0 : # → R (q7) ; q7 : x → R ; ␣ → R (qacc)
| u q v | |
| move নম্বর | |
| state-এ মনে রাখা |
- শুরু। q0 01#01. বাঁয়ের অংশ 01, ডানের অংশ 01.
- প্রথম চিহ্ন কাটা। δ(q0, 0) = (q1, x, R): 0-কে x করা হলো, আর state q1 মনে রাখছে “0”. Configuration x q1 1#01.
- # পেরোনো। q1 1 পেরিয়ে # পায় আর q3-তে ডানে: x1# q3 01 (move 3). q3 মানে “ডান অংশে একটি 0 খুঁজছি”।
- মিলল। ডানের প্রথম না-কাটা চিহ্ন 0, মিলেছে: x লিখে বাঁয়ে, x1 q5 #x1 (move 4). মিল না হলে (1 থাকলে) q3-এর নিয়ম নেই, তাই বর্জন।
- বাঁয়ে ফেরা। q5 # পেরিয়ে q6 (move 5), q6 1 পেরিয়ে বাঁয়ে: q6 x1#x1 (move 6), head প্রথম ঘরের x-এর ওপর।
- পাক ২ শুরু। δ(q6, x) = (q0, x, R): x q0 1#x1 (move 7). Head বাঁয়ের অংশের পরের না-কাটা চিহ্নে।
- দ্বিতীয় মিল। 1 কাটা হয়ে q2 (“1 মনে রাখছি”), # পেরিয়ে q4, ডানের x পেরিয়ে 1 পেল, x লিখে বাঁয়ে: xx# q5 xx (move 11).
- বাঁ অংশ শেষ। q5 আর q6 ফিরে এসে xx q0 #xx (move 14): q0-এর নিচে #. মানে বাঁয়ের সব চিহ্ন কাটা।
- শেষ যাচাই। q7 ডানে x পেরিয়ে ␣ পেল: xx#xx q7 ␣ (move 17). ডান অংশে কোনো না-কাটা চিহ্ন নেই, অর্থাৎ ডান অংশ বাঁয়ের চেয়ে লম্বা নয়।
- গ্রহণ। δ(q7, ␣) = (qacc, ␣, R), move 18 = 2(k + 1)2 যেখানে k = |w| = 2. 01#00 হলে move 10-এ q4-এর নিচে 0 থাকত, যার নিয়ম নেই: বর্জন।
একই যন্ত্র এবার অন্য চোখে দেখুন। নিচের JavaScript ব্লক tape-টি ঘর ধরে ছাপে, head-এর ঘর [ ] বন্ধনীর ভেতরে, পাশে state. প্রথমে 1#1-এর প্রতিটি move, তারপর কয়েকটি input-এর শুধু ফল, আর শেষে Mloop ba-তে cap = 6 দিয়ে। এখানেও step cap বাধ্যতামূলক: cap ছাড়া Mloop browser-এর tab আটকে দিত।
// Tape animator: the head's cell is shown in [ ]. Missing rule = reject.
// Rule format "state,read": [next, write, move]; "_" is the blank.
const WW = { start: "q0", rules: {
"q0,0": ["q1","x","R"], "q0,1": ["q2","x","R"], "q0,#": ["q7","#","R"],
"q1,0": ["q1","0","R"], "q1,1": ["q1","1","R"], "q1,#": ["q3","#","R"],
"q2,0": ["q2","0","R"], "q2,1": ["q2","1","R"], "q2,#": ["q4","#","R"],
"q3,x": ["q3","x","R"], "q3,0": ["q5","x","L"],
"q4,x": ["q4","x","R"], "q4,1": ["q5","x","L"],
"q5,0": ["q5","0","L"], "q5,1": ["q5","1","L"], "q5,x": ["q5","x","L"],
"q5,#": ["q6","#","L"], "q6,0": ["q6","0","L"], "q6,1": ["q6","1","L"],
"q6,x": ["q0","x","R"], "q7,x": ["q7","x","R"], "q7,_": ["qacc","_","R"] } };
const LOOP = { start: "q0", rules: { "q0,a": ["qacc","a","R"],
"q0,b": ["q1","b","R"], "q1,a": ["q0","a","L"], "q1,b": ["q0","b","L"],
"q1,_": ["q0","_","L"] } };
function animate(M, w, cap, quiet) {
const tape = w ? w.split("") : ["_"];
let q = M.start, h = 0, step = 0;
for (; step <= cap; step++) {
if (!quiet) console.log(String(step).padStart(3) + " " + q.padEnd(5) +
tape.map((s, i) => i === h ? `[${s}]` : ` ${s} `).join(""));
if (q === "qacc" || q === "qrej") break;
if (step === cap) { console.log(` ${w}: STOPPED by the cap of ${cap} moves (no verdict)`); return; }
const r = M.rules[q + "," + tape[h]] || ["qrej", tape[h], "R"];
[q, tape[h]] = r;
h = r[2] === "R" ? h + 1 : Math.max(h - 1, 0); // left end: stay put
if (h === tape.length) tape.push("_");
}
console.log(` ${w || "ε"}: ${q === "qacc" ? "ACCEPT" : "REJECT"} after ${step} moves`);
}
animate(WW, "1#1", 100);
for (const w of ["01#01", "01#00", "0#01", "011#011"]) animate(WW, w, 100, true);
animate(LOOP, "ba", 6);আসল আউটপুট (ব্রাউজারের JavaScript):
0 q0 [1] # 1
1 q2 x [#] 1
2 q4 x # [1]
3 q5 x [#] x
4 q6 [x] # x
5 q0 x [#] x
6 q7 x # [x]
7 q7 x # x [_]
8 qacc x # x _ [_]
1#1: ACCEPT after 8 moves
01#01: ACCEPT after 18 moves
01#00: REJECT after 11 moves
0#01: REJECT after 8 moves
011#011: ACCEPT after 32 moves
0 q0 [b] a
1 q1 b [a]
2 q0 [b] a
3 q1 b [a]
4 q0 [b] a
5 q1 b [a]
6 q0 [b] a
ba: STOPPED by the cap of 6 moves (no verdict)
1#1-এ head-এর যাত্রা স্পষ্ট দেখা যায়: ডানে (move 0–2), মিলিয়ে বাঁয়ে (3–4), আবার ডানে যাচাই (5–8). Move 7-এ head লেখা অংশের বাইরে চলে যায়, তাই tape-এ নতুন একটি “_” (blank) যুক্ত হয়: tape দরকার মতো ডানে বাড়ে। 01#01 আর 011#011-এর move-সংখ্যা 18 আর 32, সূত্র 2(k + 1)2-এর সঙ্গে মেলে। 01#00 move 11-এ বর্জিত: move 10-এ q4 (“1 খুঁজছি”) 0 পায়, আর সেখানে নিয়ম নেই। 0#01 move 8-এ বর্জিত: বাঁয়ের সব চিহ্ন কাটার পরে q7 ডানে একটি না-কাটা 1 পায়। শেষে Mloop একই দুই configuration-এর মধ্যে দোল খায়, আর cap ৬-এ থামানো হয়, কোনো রায় ছাড়া।
৭ · তিন স্তরের বর্ণনা, state diagram আর decider বনাম recognizer
M1-এর সারণিতে ৬টি state আর ১৮টি নিয়ম। পর্ব ৪৪-এর যন্ত্রগুলোতে আরও বেশি থাকবে, আর পর্ব ৪৮-এর universal machine-এর পূর্ণ সারণি কেউ হাতে লেখে না। তাই Sipser তিন স্তরের বর্ণনা ব্যবহার করেন, আর পরীক্ষায় প্রশ্ন যে স্তর চায়, উত্তর সেই স্তরে দিতে হয়।
১. Formal description
পুরো 7-tuple: Q, Σ, Γ, প্রতিটি δ-নিয়ম (সারণি বা state diagram). সবচেয়ে নির্ভুল, সবচেয়ে লম্বা। ছোট যন্ত্র আর “transition সারণি দিন” প্রশ্নে।
২. Implementation description
বাংলায় বা ইংরেজিতে, কিন্তু head আর tape-এর ভাষায়: “ডানে গিয়ে প্রথম না-কাটা b-কে Y করুন, তারপর বাঁয়ে শেষ X পর্যন্ত ফিরুন”. State-এর নাম নেই, কিন্তু যেকোনো দক্ষ পাঠক এ থেকে সারণি বানাতে পারেন।
৩. High-level description
Algorithm-এর ভাষায়, tape-এর বিবরণ ছাড়া: “w-এ a, b, c-এর সংখ্যা গুনে তুলনা করুন, আর ক্রম a∗b∗c∗ কি না দেখুন”. পর্ব ৫০ থেকে প্রায় সব যন্ত্র এভাবে লেখা হবে।
Input-এর রীতি
High-level বর্ণনা শুরু হয় “M = ‘input ⟨G⟩-এর ওপর: …’” দিয়ে। কোনো বস্তু (graph, DFA, আরেকটি TM) input হলে তার encoding ⟨·⟩ (পর্ব ০৫)। যন্ত্রটি প্রথমে যাচাই করে input একটি বৈধ encoding কি না।
এই তিন স্তর আসলে একটি প্রতিশ্রুতির ওপর দাঁড়িয়ে: high-level বর্ণনার প্রতিটি ধাপ (গোনা, তুলনা, কপি, খোঁজা) একটি Turing machine-এ অনুবাদ করা যায়। এই মডিউলের বাকি পর্বগুলো সেই প্রতিশ্রুতির ভিত্তি গড়ে: পর্ব ৪৪-এ copy, compare, increment-এর মতো subroutine, পর্ব ৪৫-এ একাধিক tape, আর পর্ব ৪৭-এ Church–Turing thesis, যা বলে “যেকোনো algorithm” আর “কোনো Turing machine” একই জিনিস। Thesis-টি একটি দাবি, প্রমাণিত theorem নয়, কারণ “algorithm”-এর কোনো আগের গাণিতিক সংজ্ঞা নেই।
State diagram আঁকার তিনটি ফাঁদ: (১) ␣ ভুলে যাওয়া: input-এর শেষ চেনার একমাত্র উপায় ␣ পড়া, আর ε-এর ক্ষেত্রে প্রথম ঘরেই ␣. (২) বাঁ প্রান্তে আছেন কি না, যন্ত্র নিজে জানে না; Sipser-এর রীতিতে L দিলে head সেখানেই থাকে, তাই “বাঁয়ে হাঁটতে থাকুন যতক্ষণ না শুরুতে পৌঁছান” কাজ করে না। শুরুর ঘরে একটি বিশেষ চিহ্ন (যেমন X বা $) লিখে রাখুন, যেমন M1-এর q3 X খোঁজে। (৩) “দেখানো হয়নি = reject” রীতি মনে রাখুন, আর উল্টোভাবে খেয়াল রাখুন, কোনো দরকারি নিয়ম বাদ পড়ে বৈধ input বর্জিত হচ্ছে কি না।
Decider বনাম recognizer, আবার। M1 আর {w#w}-এর যন্ত্র দুটিই decider: উপপাদ্য ৪.১ আর একই ধরনের যুক্তি দেখায়, প্রতিটি পাক অন্তত একটি নতুন চিহ্ন কাটে আর প্রতিটি পাক সসীম। কিন্তু অনেক স্বাভাবিক যন্ত্র recognizer মাত্র। বাজারঘরের একটি কল্পিত প্রশ্ন ভাবুন: “একটি discount-script, যা যেকোনো order-এর ওপর চলে, কোনো একটি order-এ কি কখনো ঋণাত্মক মোট দেয়?” যন্ত্রটি order একে একে চেষ্টা করে, পেলে “হ্যাঁ” বলে থামে; না পেলে চিরকাল খুঁজতে থাকে। “হ্যাঁ”-এর ক্ষেত্রে উত্তর আসে, “না”-এর ক্ষেত্রে কখনো না। এমন প্রশ্নের অনেকগুলো আসলে কোনো decider-এ নেওয়া যায় না, যার প্রমাণ পর্ব ৫১–৫৩-এ। এই পর্বের জন্য মনে রাখুন: recognize = “হ্যাঁ হলে একসময় বলে”; decide = “সবসময় একসময় বলে, হ্যাঁ বা না”।
৮ · PDA যা পারে না, TM তা কেন পারে — আর একটি সত্যিকারের library-তে যাচাই
anbncn আর {w#w} দুটিই non-context-free, অথচ Turing machine দুটিকেই সহজে decide করল। কোন ক্ষমতাটি পার্থক্য গড়ল? তিনটি জিনিস একসঙ্গে: (১) লেখা: input-এর ওপরেই দাগ দেওয়া যায়, তাই কোন চিহ্ন “খরচ” হয়েছে তা মনে রাখতে আলাদা স্মৃতি লাগে না; (২) দুই দিকে চলা: একই input বারবার পড়া যায়; (৩) যেকোনো ঘরে পৌঁছানো: stack-এর মতো ওপরেরটা তুলে ফেলে নিচেরটা দেখতে হয় না, আর কিছু হারায়ও না। পর্ব ৩২-এর শেষে দেখেছেন, দুটি stack মিলে একটি tape অনুকরণ করে; একটি দুই-stack PDA আর একটি TM সমান ক্ষমতার।
| যন্ত্র | স্মৃতি | চেনে | উদাহরণ যা পারে না |
|---|---|---|---|
| DFA / NFA | শুধু state | regular (Type 3) | anbn |
| PDA | একটি stack | context-free (Type 2) | anbncn, w#w |
| LBA | input-এর সমান tape | context-sensitive (Type 1) | diagonalization দিয়ে পাওয়া কিছু decidable language |
| TM decider | অসীম tape, সবসময় থামে | decidable | halting problem (পর্ব ৫১) |
| TM (যেকোনো) | অসীম tape | Turing-recognizable (Type 0) | ATM-এর complement (পর্ব ৫১) |
M1 আসলে input-এর বাইরে মাত্র একটি ␣ ঘর ছোঁয়। এমন যন্ত্র, যার head input-এর সীমার ভেতরে থাকে, হলো linear bounded automaton, আর এরা ঠিক context-sensitive language চেনে (পর্ব ০৬-এর মানচিত্রে Type 1). তাই anbncn context-sensitive. Decidable language-গুলো Chomsky hierarchy-র কোনো Type নয়; এরা Type 1 আর Type 0-এর মাঝখানে বসে।
একটি সত্যিকারের library দিয়ে যাচাই। নিজের simulator-এ ভুল থাকতে পারে, তাই একই দুটি যন্ত্র একটি স্বাধীন library-তে চালানো হলো। automata-lib একটি Python library (MIT licence), যার DTM class একটি deterministic Turing machine. এর রীতি HMU-র মতো: tape দুই দিকে অসীম, আলাদা reject state নেই (নিয়ম না থাকলে থামে আর বর্জন), আর accept state-এর একটি set. তাই আমাদের সারণি থেকে শুধু qrej বাদ দিলেই চলে। Library-টিতে কোনো network বা usage-reporting কোড নেই। ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে script-টির মূল অংশ:
from automata.tm.dtm import DTM
def table(text): # same "state symbols next write move" lines
tr = {}
for line in text.strip().splitlines():
q, syms, r, b, mv = line.split()
for s in syms.split(","):
tr.setdefault(q, {})[s] = (r, s if b == "=" else b, mv)
return tr
anbncn = DTM(states={"q0", "q1", "q2", "q3", "q4", "q5", "qacc"},
input_symbols={"a", "b", "c"},
tape_symbols={"a", "b", "c", "X", "Y", "Z", "_"},
transitions=table(ANBNCN_RULES), # the 13 lines of tm_sim.py
initial_state="q0", blank_symbol="_", final_states={"qacc"})
# ww = DTM(...) and loop = DTM(...) are built the same way
for name, M, sigma, inL in [("anbncn", anbncn, "abc", lang_abc),
("w#w", ww, "01#", lang_ww)]:
words = ["".join(t) for k in range(9) for t in product(sigma, repeat=k)]
acc = [w for w in words if M.accepts_input(w)]
agree = all(M.accepts_input(w) == inL(w) for w in words)
print(f"{name}: {len(words)} strings, {len(acc)} accepted, agree: {agree}")
steps = list(anbncn.read_input_stepwise("aabbcc"))
print("aabbcc: configurations", len(steps), "moves", len(steps) - 1)
print("last:", steps[-1])
print("loop on 'ba', first 5 configurations (generator, cut by islice):")
for c in islice(loop.read_input_stepwise("ba"), 5): # a generator: we cap it
print(" ", c.state, "".join(c.tape.tape), "head", c.tape.current_position)সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12.13):
~/bazarghar-toc$ uv run python run_dtm.py
automata-lib 9.2.0
anbncn: 9841 strings, 3 accepted, agree: True
w#w: 9841 strings, 15 accepted, agree: True
aabbcc: configurations 24 moves 23
last: TMConfiguration('qacc', TMTape('XXYYZZ__', '_', 7))
loop on 'ba', first 5 configurations (generator, cut by islice):
q0 ba head 0
q1 ba head 1
q0 ba head 0
q1 ba head 1
q0 ba head 0
Library দৈর্ঘ্য ৮ পর্যন্ত ৯৮৪১টি string-এ দুই যন্ত্রকেই সংজ্ঞার সঙ্গে একমত পায় (library ধীর বলে এখানে দৈর্ঘ্য ৯ নয়, ৮)। aabbcc-তে ২৪টি configuration, অর্থাৎ ২৩টি move, যা আমাদের stepper আর simulator-এর সঙ্গে হুবহু মেলে; শেষ tape XXYYZZ, তারপর blank. শেষ অংশটি সবচেয়ে শিক্ষণীয়: library-র accepts_input-এর কোনো step cap নেই, তাই Mloop-কে ba দিলে সেটি কখনো ফিরত না। read_input_stepwise একটি generator, তাই islice দিয়ে প্রথম ৫টি configuration নিয়ে আমরা নিজেরাই cap বসিয়েছি। যেকোনো TM-tool ব্যবহারের আগে দেখে নিন, সেটি নিজে থামায় কি না।
আরও গভীরে: M1-এর 4n2 + 3n + 1 move নিছক নকশার দুর্বলতা নয়। এক tape-এর যন্ত্রে palindrome বা {w#w}-এর মতো language-এর জন্য সময় অন্তত n2-এর অনুপাতে লাগে; এটি ১৯৬০-এর দশকে “crossing sequence” কৌশলে প্রমাণিত (F. C. Hennie-র নামে পরিচিত)। আরও আশ্চর্য একটি ফল, যা Hartmanis (১৯৬৮) আর তার আগে Trakhtenbrot-এর নামে উল্লেখ করা হয়: এক tape-এর যে যন্ত্র o(n log n) সময়ে চলে, সে শুধু regular language চেনে। দুটি tape পেলে {w#w} রৈখিক সময়ে হয় (পর্ব ৪৫), তাই “কতটা সময়” প্রশ্নে মডেলের খুঁটিনাটি গুরুত্বপূর্ণ, যদিও “পারে কি না” প্রশ্নে নয়; এই ভেদ পর্ব ৪৭-এর extended Church–Turing thesis-এর কেন্দ্রে।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Turing machine-এর formal definition দিন। M = (Q, Σ, Γ, δ, q0, qaccept, qreject), ␣ ∈ Γ \ Σ, δ: Q′ × Γ → Q × Γ × {L, R}.
- anbncn-এর TM নকশা করুন আর abc-এর configuration-ক্রম লিখুন। দাগ কাটার চক্র; q0 abc ⊢ X q1 bc ⊢ XY q2 c ⊢ X q3 YZ ⊢ ⋯, মোট ৮ move.
- Configuration u q v-এর অর্থ কী? Tape uv (তারপর ␣), state q, head v-এর প্রথম চিহ্নে।
- Decider আর recognizer-এর পার্থক্য কী? Decider সব input-এ থামে; recognizer language-এর বাইরের input-এ loop করতে পারে।
- TM কেন PDA-র চেয়ে শক্তিশালী? লিখতে পারে আর দুই দিকে চলে; anbncn TM-এ decidable, কিন্তু CFL নয়।
৯ · AI-এর যুগে Turing machine নকশা
AI assistant-কে “anbncn-এর Turing machine দাও” বললে সুন্দর একটি সারণি আসে, প্রায়ই এক বা দুটি গোপন ভুলসহ। সবচেয়ে সাধারণ ভুল: “সব a কাটা হয়ে গেলে গ্রহণ” লিখে শেষ যাচাইয়ের ধাপ বাদ দেওয়া, ␣ বা ε-এর নিয়ম ভুলে যাওয়া, বাঁ প্রান্ত চেনার কোনো উপায় না রাখা, আর loop করতে পারে এমন যন্ত্রকে “decider” বলা। নিচের ব্লকে একটি এমন খসড়া (AI-এর উত্তরের ধাঁচে বানানো উদাহরণ) দৈর্ঘ্য ৮ পর্যন্ত সংজ্ঞার সঙ্গে মেলানো হয়েছে; ব্লকটি নিজের ছোট simulator নিয়ে স্বয়ংসম্পূর্ণ, আর cap ছুঁলে চুপ না থেকে error তোলে।
from itertools import product
def accepts(rules, w, cap=5000): # tiny TM runner; missing rule = reject
tape, q, h = list(w) or ["_"], "q0", 0
for _ in range(cap):
if q == "qacc": return True
if (q, tape[h]) not in rules: return False
q, tape[h], mv = rules[(q, tape[h])]
h = h + 1 if mv == "R" else max(h - 1, 0)
if h == len(tape): tape.append("_")
raise RuntimeError(f"cap reached on {w!r}")
def rules(text):
d = {}
for line in text.strip().splitlines():
q, syms, r, b, mv = line.split()
for s in syms.split(","): d[(q, s)] = (r, s if b == "=" else b, mv)
return d
CORE = """q0 a q1 X R\nq1 a,Y q1 = R\nq1 b q2 Y R\nq2 b,Z q2 = R
q2 c q3 Z L\nq3 a,b,Y,Z q3 = L\nq3 X q0 = R\nq0 _ qacc = R"""
# AI draft: "all a's are crossed off, so accept" -- no final check pass
draft = rules(CORE + "\nq0 Y qacc = R")
fixed = rules(CORE + "\nq0 Y q4 = R\nq4 Y q4 = R\nq4 Z q5 = R\nq5 Z q5 = R\nq5 _ qacc = R")
def in_abc(w):
k = len(w) // 3
return w == "a" * k + "b" * k + "c" * k
words = ["".join(t) for k in range(9) for t in product("abc", repeat=k)]
for name, R in [("AI draft", draft), ("fixed ", fixed)]:
extra = [w for w in words if accepts(R, w) and not in_abc(w)]
missing = [w for w in words if in_abc(w) and not accepts(R, w)]
print(f"{name}: extra {len(extra)} {extra[:5]} missing {len(missing)}")আসল আউটপুট (ব্রাউজারের Python):
AI draft: extra 565 ['abbc', 'abca', 'abcb', 'abcc', 'abbbc'] missing 0
fixed : extra 0 [] missing 0
খসড়াটি কোনো anbncn বাদ দেয় না (missing 0), তাই শুধু “aabbcc দিয়ে পরীক্ষা করলাম, কাজ করছে” বললে ভুলটি ধরা পড়ত না। কিন্তু ৫৬৫টি বাড়তি string গৃহীত। abbc নিন: প্রথম পাকে a → X, প্রথম b → Y, c → Z, tape XYbZ; ফিরে এসে q0 Y দেখে সরাসরি গ্রহণ, অথচ একটি b না-কাটা রয়ে গেছে। abca-তে শেষে একটি বাড়তি a, abcc-তে বাড়তি c: সবই একই কারণে। দ্বিতীয় লাইনে অংশ ২-এর q4, q5 যোগ করলে extra আর missing দুটিই শূন্য। শিক্ষা: TM যাচাই মানে extra (বাড়তি গ্রহণ) আর missing (বাদ পড়া) দুটি তালিকাই দেখা।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| শেষ যাচাই নেই: “a ফুরালে গ্রহণ”, ফলে বাড়তি b বা c থাকলেও গৃহীত | দৈর্ঘ্য ৮–৯ পর্যন্ত brute force-এ extra তালিকা দেখুন; abbc, abcc-র মতো “একটি বেশি” string হাতে চালান |
| ␣ আর ε-এর নিয়ম নেই, বা input-এর শেষ চেনার উপায় নেই | ε, দৈর্ঘ্য ১ আর শেষ চিহ্ন বাদ দেওয়া string-এ trace লিখুন |
| “বাঁ প্রান্ত পর্যন্ত বাঁয়ে যান” — অথচ যন্ত্র প্রান্ত চেনে না | প্রথম ঘরে চিহ্ন বসানো আছে কি না দেখুন; সারণিতে বাঁয়ে হাঁটার state কোন চিহ্নে থামে, তা খুঁজুন |
| Loop করতে পারে এমন যন্ত্রকে “decider” বলা, বা simulator-এ cap না রাখা | প্রতিটি পাক কিছু একটা কমায় কি না দেখুন (যেমন না-কাটা চিহ্নের সংখ্যা); simulator-এ সবসময় cap, আর cap hit সংখ্যা ছাপুন |
| “Church–Turing thesis প্রমাণিত theorem” বা ভুল সাল ও নাম | Thesis একটি দাবি (পর্ব ৪৭); সাল আর উৎস Sipser বা Hopcroft–Motwani–Ullman-এ মিলিয়ে নিন |
AI-কে কাজে লাগানোর ভালো উপায়: যন্ত্রের সঙ্গে তিন স্তরের বর্ণনা, ছোট input-এর configuration-ক্রম আর একটি brute-force কোড চাওয়া, যা আপনি নিজে চালাবেন।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Turing একজন মানুষ হিসাবকারীর কাজ বিশ্লেষণ করে মডেলটি বানিয়েছিলেন। এই বিশ্লেষণ কেন এত বিশ্বাসযোগ্য মনে হয়েছিল, আর মডেলের সীমাগুলো (সসীম state, এক ঘর দেখা) কেন যুক্তিসংগত?
১৯৩০-এর দশকের শুরুতে “কার্যকর পদ্ধতি” (effective procedure) ধারণার কয়েকটি গাণিতিক রূপ প্রস্তাবিত হয়েছিল: Church আর Kleene-এর λ-definable function, Gödel আর Herbrand-এর ধারণা থেকে আসা general recursive function. পরে দেখা গেল এগুলো একই function-শ্রেণি দেয়, কিন্তু একটি প্রশ্ন থেকে যাচ্ছিল: এই সংজ্ঞাগুলো যে সব যান্ত্রিক পদ্ধতি ধরে, তার পক্ষে যুক্তি কী? Turing-এর ১৯৩৬ সালের প্রবন্ধের একটি বড় অংশ ঠিক এই প্রশ্নের উত্তর দেয়, আর উত্তরটি গণিতের সূত্র থেকে নয়, একজন মানুষ কাগজে-কলমে কী করেন তার বিশ্লেষণ থেকে।
তাঁর যুক্তির ধাপগুলো মোটামুটি এরকম। মানুষের মনোযোগ সীমিত, তাই একসঙ্গে সসীম কয়েকটি চিহ্নই দেখা যায়; যেকোনো বড় দৃষ্টি-ক্ষেত্রকে এক ঘর করে দেখার ধাপে ভাঙা যায়। চিহ্নের ধরন সসীম, কারণ দুটি চিহ্ন খুব কাছাকাছি হলে আলাদা করা যায় না। মনের অবস্থাও সসীম, কারণ অসীম সূক্ষ্ম পার্থক্য আলাদা করে ধরে রাখা যায় না; বাড়তি স্মৃতি দরকার হলে মানুষ কাগজে লিখে রাখেন। প্রতিটি ধাপে পরিবর্তন সামান্য: একটি চিহ্ন বদলানো আর মনোযোগ কাছের একটি ঘরে সরানো। এই সীমাগুলো মেনে নিলে যা বাকি থাকে, তা-ই Turing machine.
এই কারণেই বলা হয়, Gödel Turing-এর বিশ্লেষণকে বিশেষভাবে বিশ্বাসযোগ্য মনে করতেন, যদিও আগের সমতুল্য সংজ্ঞাগুলো নিয়ে তাঁর দ্বিধা ছিল। এখানে সূক্ষ্ম পার্থক্যটি খেয়াল করুন: Turing প্রমাণ করেননি যে প্রতিটি যান্ত্রিক পদ্ধতি এই মডেলে ধরা পড়ে; তিনি একটি দার্শনিক বিশ্লেষণ দিয়েছেন। সেজন্যই Church–Turing thesis একটি thesis, theorem নয় (পর্ব ৪৭)। আজকের দৃষ্টিতে সীমাগুলো আরও স্বাভাবিক লাগে: একটি CPU একবারে সসীম bit পড়ে, সসীম নির্দেশের তালিকা মানে, আর মেমরি থেকে পড়ে-লেখে।
মূল উপলব্ধি: Turing machine-এর শক্তি তার সরলতায়; প্রতিটি সীমা একজন হিসাবকারীর বাস্তব সীমা থেকে এসেছে, তাই মডেলটিকে “যান্ত্রিক গণনা”-র সংজ্ঞা হিসেবে মেনে নেওয়া সহজ হয়েছিল।
প্র ০২বিভিন্ন বইয়ে Turing machine-এর সংজ্ঞা আলাদা: এক দিকে বা দুই দিকে অসীম tape, reject state বা “নিয়ম না থাকলে থামা”, S নড়াচড়া আছে বা নেই। এই পার্থক্য কেন ক্ষমতা বদলায় না, আর কোথায় বদলায়?
প্রতিটি রূপভেদের জন্য একটি অনুকরণ (simulation) দেখালেই ক্ষমতার সমতা প্রমাণ হয়। “নিয়ম না থাকলে থামা” রীতি থেকে Sipser-এর রীতিতে যেতে প্রতিটি অনুপস্থিত (state, চিহ্ন) জোড়কে qreject-এ পাঠান; উল্টো দিকে qreject-কে এমন state বানান, যার কোনো নিয়ম নেই আর যা F-এ নেই। S (জায়গায় থাকা) নড়াচড়া চাইলে একটি R আর তার পরে একটি L দিয়ে, মাঝে একটি বাড়তি state রেখে, একই ফল পাওয়া যায়। দুই দিকে অসীম tape-কে এক দিকের tape-এ ভাঁজ করে আনা যায়: প্রতিটি ঘরে দুটি “track”, একটিতে ডান অর্ধেক, অন্যটিতে বাঁ অর্ধেক উল্টো ক্রমে। এর বিস্তারিত পর্ব ৪৫-এ।
প্রতিটি ক্ষেত্রে অনুকরণকারী যন্ত্র মূল যন্ত্রের প্রতিটি ধাপ সসীম কয়েকটি ধাপে করে, আর একই input গ্রহণ, বর্জন বা loop করে। তাই recognizable আর decidable language-এর শ্রেণি একই থাকে। এই দৃঢ়তা (robustness) Turing machine মডেলের সবচেয়ে বড় গুণগুলোর একটি: খুঁটিনাটি বদলালেও “কী গণনা করা যায়” প্রশ্নের উত্তর বদলায় না। এই দৃঢ়তাই Church–Turing thesis-এর পক্ষে একটি পরোক্ষ প্রমাণ হিসেবে দেখা হয়।
কিন্তু সময়ের হিসাবে কিছু রূপভেদ গুরুত্বপূর্ণ। S নড়াচড়া বা দুই দিকের tape সময় বড়জোর একটি ধ্রুবক গুণ বাড়ায়। একাধিক tape থেকে এক tape-এ অনুকরণে সময় বর্গ হতে পারে, আর অংশ ৮-এর আরও গভীরে বক্সে দেখেছেন, এক tape-এ কিছু language-এর জন্য বর্গ সময় সত্যিই লাগে। Nondeterministic যন্ত্রের deterministic অনুকরণ (পর্ব ৪৬) জানা পদ্ধতিতে exponential সময় নেয়, আর এর চেয়ে ভালো সম্ভব কি না, সেটিই P বনাম NP-এর একটি রূপ, যা এখনো অজানা। Complexity-তে তাই মডেলের বিবরণ ঠিক করে বলতে হয়, অন্তত polynomial পার্থক্য পর্যন্ত।
মূল উপলব্ধি: “গণনা করা যায় কি না” প্রশ্নে সব যুক্তিসংগত Turing machine রূপভেদ সমান; “কত দ্রুত” প্রশ্নে রূপভেদের দাম আছে, আর সেই দামের হিসাবই complexity তত্ত্ব।
প্র ০৩Simulator-এ একটি step cap বসালেই কি loop-এর সমস্যা মিটে যায়? cap ছুঁয়ে ফেলা যন্ত্রকে “loop করে” বলে রায় দেওয়া কেন ভুল?
Step cap একটি প্রকৌশলের সুরক্ষা, গাণিতিক উত্তর নয়। ধরুন cap দশ লাখ move. একটি যন্ত্র দশ লাখ এক নম্বর move-এ থামতে পারে; cap তাকে ভুলভাবে “loop করে” বলে দেবে। কোনো নির্দিষ্ট সংখ্যা সব যন্ত্রের জন্য যথেষ্ট হতে পারে না, কারণ খুব ছোট যন্ত্রও অবিশ্বাস্য দীর্ঘ সময় চলে তারপর থামতে পারে। এর সবচেয়ে বিখ্যাত উদাহরণ Busy Beaver: n-state-এর যন্ত্রগুলোর মধ্যে যেটি থামে আর সবচেয়ে বেশি move নেয়, তার move-সংখ্যা n-এর সঙ্গে যেকোনো গণনাযোগ্য function-এর চেয়ে দ্রুত বাড়ে। মাত্র ৫টি state-এর যন্ত্রের জন্য এই সংখ্যাটি (৪,৭১,৭৬,৮৭০) ২০২৪ সালে bbchallenge নামের একটি সহযোগী প্রকল্প যন্ত্র-যাচাই করা প্রমাণ দিয়ে নিশ্চিত করেছে; বিস্তারিত পর্ব ৫৫-এ।
উল্টো দিকে, configuration ফিরে আসা দেখে loop ধরা যায়, যেমন Mloop-এ। Deterministic যন্ত্রে একই configuration দুবার এলে সেটি চিরকাল ঘুরবে, এটি নিশ্চিত। কিন্তু অংশ ৩-এর stepper-এর শেষ ধাপে দেখেছেন, ডানে অনন্তকাল হাঁটা যন্ত্রের configuration কখনো ফেরে না। এমন সব ক্ষেত্র ধরার একটি সাধারণ পদ্ধতি থাকলে halting problem decidable হতো, আর পর্ব ৫১-এ প্রমাণ হবে তা নয়। তবে একটি বিশেষ ক্ষেত্রে পদ্ধতি আছে: যে যন্ত্র tape-এর একটি নির্দিষ্ট সসীম অংশের বাইরে যায় না (যেমন LBA), তার configuration সসীম সংখ্যক, তাই একটি গোনা সীমার পরে পুনরাবৃত্তি নিশ্চিত, আর loop ধরা যায়।
তাই এই পর্বের সব কোড তিন রকম উত্তর দেয়: গৃহীত, বর্জিত, আর “cap-এ থামানো, রায় নেই”। Brute force-এ “cap hit 0” ছাপা হয় এই কারণেই: তবেই বলা যায় পরীক্ষিত সব input-এ যন্ত্র নিজে থেমেছে। বাস্তবের সফটওয়্যারে timeout-এর ভূমিকা একই: বাজারঘরের সার্ভার কোনো request-এ ৩০ সেকেন্ড পরে কাজ বন্ধ করে, কারণ “এটি কি কখনো শেষ হবে?” প্রশ্নের নিশ্চিত উত্তর সাধারণভাবে পাওয়া যায় না।
মূল উপলব্ধি: Step cap আমাদের program-কে বাঁচায়, কিন্তু loop-এর প্রশ্নের উত্তর দেয় না; “cap ছুঁয়েছে” আর “কখনো থামবে না” আলাদা দাবি, আর দ্বিতীয়টি সাধারণভাবে যাচাই করা অসম্ভব।
প্র ০৪বাস্তবের কোনো কম্পিউটারে অসীম tape নেই। তাহলে Turing machine কি অবাস্তব মডেল? অসীম tape ধরে নেওয়া কেন সঠিক বিমূর্ততা?
প্রথমে খেয়াল করুন, সংজ্ঞায় tape অসীম, কিন্তু কোনো থেমে যাওয়া computation কখনো অসীম ঘর ব্যবহার করে না। k move-এ head বড়জোর k + 1টি আলাদা ঘর ছোঁয়, আর বাকি সব ঘর ␣ থাকে। তাই আরও সঠিক বর্ণনা হলো “tape দরকার মতো বাড়ে”, ঠিক যেমন অংশ ৬-এর JavaScript simulator ডানে একটি করে “_” যোগ করে। বাস্তবের কম্পিউটারও তা-ই করে: মেমরি ফুরালে disk, disk ফুরালে আরেকটি disk, cloud-এ আরেকটি সার্ভার। কোনো নির্দিষ্ট সীমা মডেলে বসালে প্রতিটি algorithm-এর বর্ণনায় সেই সীমা ঢুকে যেত, যা algorithm-এর ধারণার অংশ নয়।
দ্বিতীয় কারণ গাণিতিক। একটি নির্দিষ্ট মেমরি-সীমার যন্ত্র আসলে একটি বিশাল finite automaton, আর তার সম্পর্কে প্রায় সব প্রশ্ন নীতিগতভাবে decidable: সব configuration তালিকা করে দেখা যায়। কিন্তু সেই তালিকার দৈর্ঘ্য মেমরির bit-সংখ্যার ঘাতের হারে বাড়ে, তাই এই “decidability” কোনো কাজে আসে না। অসীম tape ধরে নিলেই আমরা সঠিক প্রশ্নগুলো করতে পারি: কোন সমস্যা কোনো পরিমাণ মেমরি দিয়েই সমাধান হয় না, আর কোন সমস্যায় input-এর আকারের সঙ্গে কতটা মেমরি লাগে। দ্বিতীয় প্রশ্নটি space complexity (পর্ব ৬৪), যেখানে মেমরি গোনা হয় input-এর দৈর্ঘ্যের function হিসেবে।
মাঝামাঝি একটি মডেলও আছে, যা এই পর্বে দেখেছেন: linear bounded automaton, যার tape input-এর সমান। M1 প্রায় এমন যন্ত্র, আর এমন যন্ত্রের সব প্রশ্ন সহজ নয়: “এই LBA কি কোনো string গ্রহণ করে?” প্রশ্নটি undecidable বলে জানা আছে, যদিও একটি নির্দিষ্ট input-এ গ্রহণ করে কি না, তা decidable. অর্থাৎ সীমা বসালেও সব কঠিনতা চলে যায় না।
মূল উপলব্ধি: অসীম tape মানে অসীম মেমরি ব্যবহার নয়, বরং “মেমরি কখনো কৃত্রিমভাবে ফুরায় না”; এই বিমূর্ততাই algorithm-কে কম্পিউটারের নির্দিষ্ট মাপ থেকে আলাদা করে ভাবতে দেয়।
প্র ০৫M1-এর move-সংখ্যা 4n2 + 3n + 1, অথচ একটি সাধারণ Python program a, b, c গুনে রৈখিক সময়ে একই উত্তর দেয়। এই ব্যবধান Turing machine মডেলের দুর্বলতা, না অন্য কিছু?
Python program-টি এমন একটি যন্ত্রে চলে, যার মেমরিতে যেকোনো ঠিকানায় এক ধাপে পৌঁছানো যায় (random access), আর একটি গোনার variable-এ একটি সংখ্যা এক ধাপে বাড়ে। এক tape-এর Turing machine-এ দুটিই নেই: দূরের ঘরে যেতে প্রতিটি মাঝের ঘর পেরোতে হয়, আর একটি বড় সংখ্যা রাখতে অনেকগুলো ঘর লাগে। M1-এর প্রতিটি পাক প্রায় পুরো input পেরিয়ে আসে-যায়, তাই n পাকে প্রায় 4n2. অংশ ৫-এর brute force-এ এই বর্গের বৃদ্ধি সরাসরি দেখা গেছে।
এটি কি শুধু M1-এর নকশার দোষ? আংশিক। anbncn-এর জন্য এক tape-এ আরও চতুর পদ্ধতি আছে: বারবার প্রতি দুটি a-এর একটি কেটে সংখ্যাগুলোর binary অঙ্ক তুলনা করলে প্রায় n log n move লাগে, যা Sipser {0k1k}-এর জন্য দেখান। কিন্তু অংশ ৮-এর আরও গভীরে বক্সে দেখেছেন, এক tape-এ n log n-এর চেয়ে কম সময়ে শুধু regular language চেনা যায়, আর {w#w}-এর মতো language-এ বর্গ সময় এড়ানো যায় না। অর্থাৎ ব্যবধানের একটি অংশ মডেলের নিজস্ব।
তবে এই ব্যবধান “ছোট” অর্থে: এক tape-এর যন্ত্র, বহু tape-এর যন্ত্র আর random-access machine একে অপরকে polynomial খরচে অনুকরণ করতে পারে। তাই “polynomial সময়ে সমাধানযোগ্য” (class P, পর্ব ৫৭) প্রশ্নের উত্তর এই মডেলগুলোর যেকোনোটিতে একই। Complexity তত্ত্ব তাই সচেতনভাবে polynomial পার্থক্য উপেক্ষা করে মোটা দাগের প্রশ্ন করে; আর সূক্ষ্ম প্রশ্নে (রৈখিক না বর্গ) মডেল ঠিক করে বলে নেয়, যেমন fine-grained complexity (পর্ব ৭২)। প্রোগ্রামারের জন্য শিক্ষা: Big-O বিশ্লেষণে আমরা নীরবে একটি random-access মডেল ধরে নিই, আর সেটি বদলালে উত্তর বদলাতে পারে।
মূল উপলব্ধি: এক tape-এর Turing machine “কী গণনা করা যায়” প্রশ্নের জন্য নিখুঁত, কিন্তু “ঠিক কত দ্রুত” প্রশ্নে polynomial খরচ যোগ করে; complexity তত্ত্ব এই খরচকে মেনে নিয়েই P-এর মতো দৃঢ় শ্রেণি সংজ্ঞায়িত করে।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। tm_sim.py ব্লকে নিজের যন্ত্র লিখে run(M, w, show=True) দিয়ে, আর tm_check.py-এর ধাঁচে brute force করে উত্তর যাচাইও করতে পারেন।
-
নকশা: Σ = {a, b}-এর ওপর EQ = {w : w-এ a আর b-এর সংখ্যা সমান}-এর জন্য একটি decider Turing machine নকশা করুন। প্রথমে implementation-level বর্ণনা, তারপর transition-এর তালিকা দিন। বাঁ প্রান্ত যন্ত্র কীভাবে চিনবে?
বর্ণনা: “বাঁ থেকে প্রথম না-কাটা চিহ্ন খুঁজুন। না পেলে (␣) গ্রহণ। a পেলে সেটি কেটে ডানে প্রথম না-কাটা b খুঁজে কাটুন; b পেলে উল্টোটা। জোড়া না পেলে (␣) বর্জন। বাঁ প্রান্তে ফিরে আবার।” বাঁ প্রান্ত চেনার জন্য প্রথম ঘরের চিহ্নটি x-এর বদলে $ দিয়ে কাটা হয়।
নিয়ম (start state qs, না দেখানো সব নিয়ম qreject): qs: a → $, R (q1); b → $, R (q2); ␣ → R (qacc). q0: x → R; a → x, R (q1); b → x, R (q2); ␣ → R (qacc). q1 (b খুঁজছে): a, x → R; b → x, L (q3). q2 (a খুঁজছে): b, x → R; a → x, L (q3). q3: a, b, x → L; $ → R (q0).
প্রতিটি পাক দুটি না-কাটা চিহ্ন কাটে, আর প্রতিটি পাক সসীম, তাই যন্ত্রটি decider. abba-তে configuration-ক্রম: qs abba ⊢ $ q1 bba ⊢ q3 $xba ⊢ $ q0 xba ⊢ $x q0 ba ⊢ $xx q2 a ⊢ $x q3 xx ⊢ … ⊢ $xxx q0 ␣ ⊢ $xxx␣ qacc ␣, মোট ১৩ move. aab-তে শেষে $xx q1 ␣: জোড়ার b নেই, বর্জন। Scratch-এর simulator-এ দৈর্ঘ্য ১০ পর্যন্ত ২০৪৭টি string-এ যন্ত্র সংজ্ঞার সঙ্গে হুবহু মিলেছে, গৃহীত ৩৫১টি (1 + 2 + 6 + 20 + 70 + 252), আর কোনো input-এ cap ছোঁয়নি।
-
প্রমাণ (ভুল খুঁজুন): একজন শিক্ষার্থী লিখেছেন: “Mloop (q0: a → R দিয়ে গ্রহণ, b → R দিয়ে q1; q1: যেকোনো চিহ্নে L দিয়ে q0; বাকি সব বর্জন) ba-তে চিরকাল চলে। অতএব Mloop-এর language, অর্থাৎ a দিয়ে শুরু হওয়া string-এর set, decidable নয়।” যুক্তির ভুল কোথায়? ঠিক উপসংহার কী আর তার প্রমাণ দিন।
ভুল: Decidability একটি language-এর ধর্ম: “কোনো decider আছে যা L decide করে”। একটি নির্দিষ্ট যন্ত্র loop করলে শুধু প্রমাণ হয় যে সেই যন্ত্রটি decider নয়। “কোনো decider নেই” দেখাতে সব সম্ভাব্য যন্ত্র নিয়ে যুক্তি লাগে (পর্ব ৫১-এর diagonalization-এর মতো)।
ঠিক উপসংহার: L = {a দিয়ে শুরু হওয়া string} decidable. প্রমাণ: M′-এর নিয়ম δ(q0, a) = (qaccept, a, R), বাকি সব (b আর ␣) qreject. ১. প্রতিটি input-এ M′ ঠিক একটি move করে halting state-এ যায়, তাই M′ decider. ২. প্রথম চিহ্ন a হলে গ্রহণ, নইলে বর্জন, তাই L(M′) = L. ∎ সঙ্গে খেয়াল করুন, L(Mloop) = L(M′), কিন্তু শুধু M′ decider: একই language-এর decider আর অ-decider দুই রকম recognizer থাকতে পারে।
-
Trace আর ফল অনুমান: অংশ ৬-এর {w#w} যন্ত্রে input 10#1 দিন। পুরো configuration-ক্রম লিখুন, কোন move-এ কী কারণে যন্ত্রটি থামে বলুন। তারপর কোড না চালিয়ে অনুমান করুন, M1 a5b5c5-এ কয়টি move নেবে।
q0 10#1 ⊢ x q2 0#1 ⊢ x0 q2 #1 ⊢ x0# q4 1 ⊢ x0 q5 #x ⊢ x q6 0#x ⊢ q6 x0#x ⊢ x q0 0#x ⊢ xx q1 #x ⊢ xx# q3 x ⊢ xx#x q3 ␣ ⊢ xx#x␣ qrej ␣.
প্রথম পাকে 1 মিলেছে। দ্বিতীয় পাকে q1 “0 নিয়ে যাচ্ছে”, q3 ডানের x পেরিয়ে একটি 0 খোঁজে, কিন্তু ␣ পায়: ডান অংশ ছোট। q3-এর ␣-এর নিয়ম নেই, তাই move 11-এ বর্জন। tm_sim.py-এ
run(WW, "10#1", show=True)ঠিক এই ১২টি লাইন দেয় (move 0 থেকে 11).a5b5c5: 4 · 25 + 3 · 5 + 1 = 116 move. tm_check.py-এর move-তালিকার পঞ্চম সংখ্যাটিও 116.
-
Configuration-এর নিয়ম: একটি TM-এ δ(q5, 0) = (q6, 1, L) আর δ(q6, 1) = (q7, 1, R). Configuration (ক) 01 q5 0x আর (খ) q5 0x থেকে দুই ধাপের configuration-ক্রম লিখুন। (খ)-তে head কোথায় থাকে, আর কেন?
(ক) 01 q5 0x ⊢ 0 q6 11x ⊢ 01 q7 1x. প্রথম ধাপে head-এর নিচের 0-কে 1 লিখে বাঁয়ে সরা: আগের ঘরের 1 এখন head-এর নিচে, তাই u = 0, v = 11x. দ্বিতীয় ধাপে 1 পড়ে 1 লিখে ডানে।
(খ) q5 0x ⊢ q6 1x ⊢ 1 q7 x. প্রথম ধাপে head প্রথম ঘরে, তাই L নির্দেশ এলেও head জায়গায় থাকে; শুধু 0 বদলে 1 হয়। দ্বিতীয় ধাপে head সেই 1-এর ওপরেই, δ(q6, 1) খাটে আর head ডানে সরে। এটি সংজ্ঞা ৩.১-এর বাঁ প্রান্তের নিয়ম; HMU-র দুই দিকে অসীম tape-এ head সত্যিই বাঁয়ে একটি ␣-এর ওপর যেত।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমanbncn-এর crossing-off Turing machine-এর কাজগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- শেষ X-এর ডানের a-কে X দিয়ে কাটা
- ডানে গিয়ে প্রথম না-কাটা b-কে Y করা
- আরও ডানে গিয়ে প্রথম না-কাটা c-কে Z করা
- বাঁয়ে হেঁটে শেষ X পর্যন্ত ফিরে আসা
- X-এর পরে Y দেখলে বাকি tape Y…YZ…Z␣ কি না যাচাই
- যাচাই সফল হলে accept state-এ যাওয়া
একটি Turing machine-এ δ(q2, b) = (q2, b, R). Configuration XaY q2 bcc থেকে এক ধাপে কোন configuration আসে?
- XaY q2 Ybcc
- XaYb q2 cc
- Xa q2 Ybcc
- XaYY q2 cc
Sipser রীতির একটি Turing machine (ডানে অসীম tape) configuration q5 0x-এ আছে, আর δ(q5, 0) = (q6, 1, L). পরের configuration কোনটি?
- q6 ␣1x
- 1 q6 x
- q6 1x
- যন্ত্রটি বর্জন করে
Turing machine M কোনো language L recognize করে, অর্থাৎ L(M) = L, কিন্তু M decider কি না জানা নেই। কোন বিবৃতিটি অবশ্যই সত্য?
- M প্রতিটি input-এ থামে
- L decidable নয়
- L-এর কিছু string-এ M loop করে
- L-এর বাইরের কোনো string M গ্রহণ করে না
{anbncn : n ≥ 0} একটি Turing machine decide করে, কিন্তু কোনো pushdown automaton চেনে না। এর মূল কারণ কোনটি?
- TM tape-এ লিখতে আর দুই দিকে চলতে পারে, PDA input একবারই পড়ে আর stack শুধু ওপর থেকে দেখে
- TM-এর state অসীম, PDA-র সসীম
- TM nondeterministic, PDA deterministic
- PDA-র stack-এর আকার সীমিত
এক tape-এর crossing-off Turing machine anbncn-এ প্রতি পাকে একটি a, একটি b আর একটি c কাটে, আর প্রতি পাকে বাঁ প্রান্ত থেকে ডানের c পর্যন্ত গিয়ে ফেরে। n বাড়লে এর move-সংখ্যা কীভাবে বাড়ে?
- n-এর রৈখিক হারে
- n-এর বর্গের হারে
- 2n-এর হারে
- n যা-ই হোক, ধ্রুবক
Sipser-এর তিন স্তরের বর্ণনার কোনটি “implementation-level description”?
- Q, Σ, Γ আর δ-এর সব নিয়মসহ পূর্ণ সারণি
- “a, b আর c গুনে তিনটি সংখ্যা তুলনা করুন”
- “ডানে গিয়ে প্রথম না-কাটা b-কে Y করুন, তারপর বাঁয়ে শেষ X পর্যন্ত ফিরুন”
- q0 abc ⊢ X q1 bc ⊢ XY q2 c-এর মতো configuration-ক্রম
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Turing machine = ডানে অসীম tape + head + সসীম নিয়ন্ত্রণ: M = (Q, Σ, Γ, δ, q0, qaccept, qreject), δ: Q′ × Γ → Q × Γ × {L, R}; বাঁ প্রান্তে L মানে জায়গায় থাকা।
- Configuration u q v: tape uv, state q, head v-এর প্রথম চিহ্নে; শুরু q0 w; এক ধাপ ⊢.
- তিন ফল: গ্রহণ, বর্জন, loop. সব input-এ থামলে decider; L decidable মানে অন্তত একটি decider আছে।
- Crossing off আর zig-zag: anbncn 4n2 + 3n + 1 move-এ, {w#w} 2(k + 1)2 move-এ; সঠিকতা invariant দিয়ে, decider-দাবি “প্রতি পাকে কিছু কমে” দিয়ে।
- Simulator-এ সবসময় step cap; “cap ছুঁয়েছে” রায় নয়। বর্ণনার তিন স্তর: formal, implementation, high-level.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৩৬ · Context-free language-এর pumping lemma আর Ogden-এর lemmaপটভূমিanbncn কেন কোনো PDA চেনে না, যা এই পর্বের প্রথম যন্ত্র decide করে।
- পর্ব ৩২ · Pushdown automaton — stack-সহ automatonফিরে দেখুনConfiguration, ⊢ আর দুই-stack যন্ত্র = Turing machine.
- পর্ব ০৬ · Chomsky hierarchy-র মানচিত্র — চার শ্রেণির language আর machineমানচিত্রType 0 আর Type 1, LBA আর decidable language-এর জায়গা।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৪৪ Turing machine নকশা।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৫ — Turing machine-এর পরিচয়পাশের ট্র্যাকTuring machine, computability আর halting problem-এর সংক্ষিপ্ত পরিচয়।
- DSA · P বনাম NPপাশের ট্র্যাকAlgorithm-এর দিক থেকে সময়ের হিসাব, যা পর্ব ৫৭-এ Turing machine-এর move গোনায় নামবে।