এই পর্বে যা শিখবেন
- Multi-tape Turing machine-এর formal সংজ্ঞা, আর {w#w}-এর জন্য একটি linear-সময়ের 2-tape যন্ত্র
- এক tape-এ multi-tape যন্ত্র নকল করার নির্মাণ, তার সঠিকতার প্রমাণ আর O(t2) সময়ের প্রমাণ
- Multi-track, stay-put, দুই দিকে অসীম tape আর ছোট alphabet কেন একই শক্তি দেয়, আর প্রতিটির নকলের খরচ
- Enumerator-এর সংজ্ঞা আর “recognizable ⇔ enumerable” উপপাদ্যের প্রমাণ, dovetailing-সহ
- কোন পরিবর্তন শক্তি বাড়ায় না, কোনটি কমায়, আর RAM বা দুই stack-এর যন্ত্র কোথায় বসে
১ · কেন রূপভেদ — একটি মডেল কতটা শক্ত
পর্ব ৪৩-এ আপনি মূল মডেলটি দেখেছেন: একটি tape, যা ডান দিকে অসীম; তার ওপর একটি head, যা একবারে একটি ঘর পড়ে, লেখে, আর বাঁয়ে বা ডানে এক ঘর সরে; আর সসীম state-এর একটি নিয়ন্ত্রক। Formal রূপে M = (Q, Σ, Γ, δ, q0, qaccept, qreject), যেখানে Σ ⊆ Γ, blank ␣ ∈ Γ \ Σ, আর δ: Q′ × Γ → Q × Γ × {L, R}; Q′ মানে থামার দুই state বাদে বাকি state. Head প্রথম ঘরে থাকা অবস্থায় বাঁয়ে সরতে বললে সে নড়ে না (Sipser-এর রীতি)। পর্ব ৪৪-এ এই মডেলে যন্ত্র নকশার কৌশল দেখেছেন: দাগ দেওয়া, আঁকাবাঁকা যাতায়াত, tape সরানো।
এই পছন্দগুলো কি জরুরি? Tape দুটি হলে, দুই দিকে অসীম হলে, বা head দাঁড়িয়ে থাকতে পারলে কী হয়? পাঠ্যবইভেদে পছন্দ আলাদা: Sipser এক দিকে অসীম tape নেন, Hopcroft–Motwani–Ullman দুই দিকে। প্রতিটি ছোট পরিবর্তনে চেনা যায় এমন language-এর শ্রেণি বদলালে “computable” শব্দের কোনো স্থির অর্থ থাকত না।
ঢাকা থেকে চট্টগ্রামে পার্সেল ট্রাকে যেতে পারে, ট্রেনে যেতে পারে, বা তিনটি ছোট ভ্যানে ভাগ হয়ে যেতে পারে। পৌঁছানোর সময় আলাদা, কিন্তু কোন ঠিকানায় পৌঁছানো সম্ভব, সেই তালিকা একই। Turing machine-এর রূপভেদও এমন: গতি আলাদা, চেনা যায় এমন language এক।
এই পর্বের মূল যন্ত্রটি হবে simulation argument, যা আপনি পর্ব ৩৩-এ PDA-র দুই গ্রহণ-পদ্ধতির সমতায় আর পর্ব ০৪-এ প্রমাণের কৌশল হিসেবে দেখেছেন। “শক্তিশালী দেখতে” যন্ত্র M-এর জন্য আমরা মূল মডেলের একটি যন্ত্র S বানাই, যার tape-এ M-এর পুরো configuration একটি সংকেতে লেখা থাকে, আর S ধাপে ধাপে M-কে নকল করে। লক্ষ্যটি সুনির্দিষ্টভাবে:
দুটি যন্ত্র-মডেলকে সমতুল্য বলা হয়, যদি এক মডেলের প্রতিটি যন্ত্র M-এর জন্য অন্য মডেলে একটি যন্ত্র S থাকে, যাতে L(S) = L(M), আর উল্টোটাও। আমরা আরও একটি শর্ত চাইব: M কোনো input-এ থামলে S-ও সেই input-এ থামে, আর M না থামলে S-ও থামে না। তাহলে M একটি decider হলে S-ও decider; অর্থাৎ দুই মডেল একই recognizable language চেনে এবং একই decidable language decide করে।
উল্টো দিকটি সহজ: মূল মডেলের প্রতিটি যন্ত্র রূপভেদেরও একটি বিশেষ ক্ষেত্র (যেমন একটি tape-এর multi-tape যন্ত্র)। তাই কাজ এক দিকে: “বাড়তি সুবিধা” নতুন শক্তি দেয় না, তা দেখানো। আর সমতা মানে একই language-এর শ্রেণি, একই গতি নয়; দামের হিসাব পরে time complexity-র তত্ত্বে (পর্ব ৫৭) কাজে লাগবে।
২ · Multi-tape Turing machine — সংজ্ঞা আর একটি দ্রুত যন্ত্র
বাজারঘরের গুদামে একজন কর্মী পার্সেলের গায়ে ছাপা order ID আর database-এর order ID মেলাচ্ছেন। এক খাতায় তাঁকে বারবার আগে-পিছে যেতে হয়; দুটি খাতা পাশাপাশি খোলা থাকলে দুই আঙুলে একবারেই মেলানো যায়। Multi-tape Turing machine সেই দুই আঙুলের যন্ত্র।
একটি k-tape Turing machine (k ≥ 1 একটি স্থির সংখ্যা) দেখতে মূল মডেলের মতোই একটি 7-tuple (Q, Σ, Γ, δ, q0, qaccept, qreject), শুধু transition function হলো
δ: Q′ × Γk → Q × Γk × {L, R, S}k.
অর্থাৎ যন্ত্র একসঙ্গে k-টি head-এর নিচের k-টি চিহ্ন পড়ে, আর বর্তমান state ও এই k-টি চিহ্ন দেখে ঠিক করে: পরের state কী, প্রতিটি tape-এ কী লিখবে, আর প্রতিটি head বাঁয়ে (L), ডানে (R) যাবে নাকি দাঁড়িয়ে থাকবে (S, stay). শুরুতে input w থাকে tape ১-এর বাঁ দিকে, বাকি সব tape ফাঁকা, সব head প্রথম ঘরে। প্রতিটি head-এর জন্য বাঁ প্রান্তের রীতি একই: প্রথম ঘর থেকে L মানে নড়া নয়।
একটি configuration হলো বর্তমান state আর k-টি tape-এর প্রতিটির (লেখা, head-এর অবস্থান). গ্রহণ, প্রত্যাখ্যান আর L(M)-এর সংজ্ঞা মূল মডেলের মতোই।
S চালটি সংজ্ঞায় রাখা হলো, কারণ প্রায়ই এক head দাঁড়িয়ে থাকে আর অন্যটি সরে (মূল মডেলে S না থাকলেও ক্ষতি নেই, অংশ ৫)। বাজারঘরের প্রশ্ন: L = {w#w : w ∈ {0, 1}∗}, অর্থাৎ # চিহ্নের দুই পাশের order ID হুবহু এক কি না। পর্ব ৪৩-এ এক tape-এর যন্ত্র এটি আঁকাবাঁকা পথে দাগ দিয়ে দিয়ে করেছিল। দুই tape-এ পরিকল্পনা সরল: tape ২-এর শুরুতে $ দাগ দিয়ে w কপি করা, # পেলে tape ২-এর head $ পর্যন্ত ফেরানো, তারপর দুই head একসঙ্গে ডানে চালিয়ে মেলানো; দুটিতেই ␣ এলে accept.
| state | পড়া (tape ১, tape ২) | লেখা (tape ১, tape ২) | চাল | পরের state |
|---|---|---|---|---|
| q0 | (x, ␣), যেকোনো x | (x, $) | S, R | copy |
| copy | (a, ␣), a ∈ {0, 1} | (a, a) | R, R | copy |
| copy | (#, ␣) | (#, ␣) | R, L | back |
| back | (x, a), a ∈ {0, 1} | (x, a) | S, L | back |
| back | (x, $) | (x, $) | S, R | cmp |
| cmp | (a, a), a ∈ {0, 1} | (a, a) | R, R | cmp |
| cmp | (␣, ␣) | (␣, ␣) | S, S | qaccept |
টেবিলে নেই এমন সব (state, জোড়া) সরাসরি qreject-এ যায়, পর্ব ৪৪-এর “implicit reject” রীতি। নিচের stepper “01#01”-এ যন্ত্রটির ১০ ধাপ দেখায়; বন্ধনী [ ] মানে head যে ঘরে আছে।
| ধাপ শেষ | |
| state | |
| tape ১ | |
| tape ২ |
- শুরু। Input tape ১-এ, tape ২ পুরো ফাঁকা, দুই head প্রথম ঘরে। এখনো কোনো ধাপ হয়নি।
- বাঁ প্রান্তে দাগ। ধাপ ১: tape ২-এ $ লেখা হলো, শুধু tape ২-এর head ডানে গেল (tape ১: S). $ পরে ফেরার থামার জায়গা।
- কপি। ধাপ ২ আর ৩: 0 আর 1 tape ২-এ কপি হলো, দুই head একসঙ্গে ডানে। এখন tape ১-এর head # চিহ্নে।
- # পার। ধাপ ৪: tape ১-এর head # পেরিয়ে দ্বিতীয় অংশের প্রথম ঘরে, আর tape ২-এর head এক ঘর বাঁয়ে, শেষ কপি করা 1-এর ওপর। State back.
- ফেরা। ধাপ ৫ আর ৬: tape ১ দাঁড়িয়ে, tape ২-এর head বাঁয়ে $-এ পৌঁছায়। এক tape-এ এই ফেরা বারবার লাগত; এখানে একবার।
- মেলানো শুরু। ধাপ ৭: $ দেখে tape ২-এর head ডানে; দুই head এখন দুই order ID-র প্রথম চিহ্নে।
- গ্রহণ। ধাপ ৮ আর ৯: (0, 0) আর (1, 1) মিলল, দুই head ডানে। ধাপ ৯-এর পর দুই head-এর নিচে ␣, তাই ধাপ ১০-এ accept. মোট ১০ ধাপ = 3 · 2 + 4.
হিসাবটি সাধারণভাবে: |w| = m হলে q0-এ ১, copy-তে m + 1, back-এ m + 1, cmp-এ m + 1 ধাপ: মোট 3m + 4, অর্থাৎ input-এর দৈর্ঘ্য n = 2m + 1-এর linear. নিচের ব্লক একটি ছোট k-tape simulator (k = 1 দিলে মূল মডেল), যা সবসময় একটি ধাপের সীমা (step cap) রাখে, যাতে কোনো ভুল যন্ত্র ব্রাউজার আটকে না দেয়। এরপর যন্ত্রটিকে দৈর্ঘ্য ৭ পর্যন্ত {0, 1, #}-এর সব string-এ language-এর সংজ্ঞার সঙ্গে মেলায়। এই ব্লক আর পরের দুটি একই namespace ভাগ করে (data-shared), তাই আগে এটি চালান।
# A k-tape TM simulator (k = 1 is the basic model), always with a STEP CAP
B = "␣" # the blank symbol
MOVE = {"L": -1, "R": 1, "S": 0}
def run(delta, w, k, cap=100_000):
tapes = [list(w) or [B]] + [[B] for _ in range(k - 1)]
heads, q, steps = [0] * k, "q0", 0
while q not in ("acc", "rej"):
if steps == cap: return "cap", steps # stop, don't loop forever
syms = tuple(t[h] for t, h in zip(tapes, heads))
q, writes, moves = delta.get((q, syms), ("rej", syms, "S" * k))
for i in range(k): # missing rule = reject
tapes[i][heads[i]] = writes[i]
heads[i] = max(0, heads[i] + MOVE[moves[i]]) # left end: stay put
if heads[i] == len(tapes[i]): tapes[i].append(B)
steps += 1
return q, steps
# 2-tape machine for {w#w : w in {0,1}*}: copy w, rewind tape 2, compare
D2 = {}
for x in "01#" + B:
D2["q0", (x, B)] = ("copy", (x, "$"), "SR") # $ marks tape 2's left end
for a in "01": D2["back", (x, a)] = ("back", (x, a), "SL")
D2["back", (x, "$")] = ("cmp", (x, "$"), "SR")
for a in "01":
D2["copy", (a, B)] = ("copy", (a, a), "RR")
D2["cmp", (a, a)] = ("cmp", (a, a), "RR")
D2["copy", ("#", B)] = ("back", ("#", B), "RL")
D2["cmp", (B, B)] = ("acc", (B, B), "SS")
from itertools import product
inL = lambda s: s.count("#") == 1 and s.split("#")[0] == s.split("#")[1]
bad = [s for n in range(8) for s in map("".join, product("01#", repeat=n))
if (run(D2, s, 2)[0] == "acc") != inL(s)]
print("strings checked up to length 7:", sum(3**n for n in range(8)), "| mismatches:", len(bad))
for w in ["01", "0110", "01101001"]:
print(f"{w}#{w}: 2-tape steps =", run(D2, w + "#" + w, 2)[1])আসল আউটপুট (ব্রাউজারের Python):
strings checked up to length 7: 3280 | mismatches: 0
01#01: 2-tape steps = 10
0110#0110: 2-tape steps = 16
01101001#01101001: 2-tape steps = 28
দৈর্ঘ্য ০ থেকে ৭-এর সব ৩২৮০টি string-এ (ফাঁকা string, শুধু “#”, দুটি # সহ) যন্ত্র আর সংজ্ঞা একবারও অমিল করেনি। ধাপ m = 2, 4, 8-এ ১০, ১৬, ২৮: ঠিক 3m + 4. delta.get(…, ("rej", …)) হলো implicit reject, max(0, …) বাঁ প্রান্তের রীতি। ভুল নিয়মে যন্ত্র না থামলে ফল আসত ("cap", 100000): “থামেনি, আমরা থামিয়েছি”, যা reject নয়।
৩ · এক tape-এ অনেক tape — simulation-এর প্রমাণ
2-tape যন্ত্রটি দ্রুত, কিন্তু বেশি শক্তিশালী নয়। এর প্রমাণের কৌশল পর্ব ৪৬ আর ৪৮-এও আসবে।
প্রতিটি k-tape Turing machine M-এর জন্য একটি single-tape Turing machine S আছে, যাতে L(S) = L(M), আর প্রতিটি input-এ S থামে ঠিক তখন, যখন M থামে। ফলে M decider হলে S-ও decider. (Sipser-এর বইয়ে Theorem 3.13.)
ভাবনা: S তার tape-এ M-এর k-টি tape-এর ব্যবহৃত অংশ পাশাপাশি লেখে, মাঝে ‖ দিয়ে (Sipser লেখেন #, কিন্তু আমাদের input-এই # আছে)। M-এর head যে ঘরে, সেই চিহ্নের একটি “দাগানো” রূপ লেখা হয় (Sipser বিন্দু দেন, আমরা লিখি [0]). তাই S-এর tape alphabet Γ ∪ {ȧ : a ∈ Γ} ∪ {‖}, এখনো সসীম।
দুই tape-এর একটি configuration এক tape-এ
ওপরে M: দুটি tape, কমলা ঘরে head. নিচে S: একটি tape, ‖ দিয়ে ভাগ করা, আর বিন্দু-দেওয়া ঘর মানে সেখানে M-এর একটি head. Configuration: “01#01”-এর ৭ ধাপের পর, state cmp.
নির্মাণটি ধাপে ধাপে, Sipser-এর high-level বর্ণনার ধাঁচে:
- Tape-কে সাজান: ‖[w1]w2⋯wn‖[␣]‖[␣]‖ ⋯ ‖, অর্থাৎ প্রথম অংশে input, বাকি k − 1 অংশে একটি করে দাগানো ␣.
- M-এর একটি ধাপ নকল করতে প্রথম ‖ থেকে শেষ ‖ পর্যন্ত ডানে যান, আর পথে k-টি দাগানো চিহ্ন finite control-এ মনে রাখুন। তারপর বাঁ প্রান্তে ফিরুন।
- M-এর state আর এই k-টি চিহ্ন দেখে δ থেকে লেখা আর চাল বের করুন। আবার একটি sweep-এ প্রতিটি দাগানো ঘরে নতুন চিহ্ন লিখুন, আর দাগটি এক ঘর বাঁয়ে বা ডানে সরান (S হলে রেখে দিন; অংশের প্রথম ঘর থেকে L হলেও রেখে দিন)।
- কোনো দাগ ডানে সরে একটি ‖-এর ওপর পড়লে, মানে M-এর ওই head এখন পর্যন্ত না-ছোঁয়া একটি ফাঁকা ঘরে গেছে: সেই ‖ থেকে শেষ পর্যন্ত সব চিহ্ন এক ঘর ডানে সরান, আর খালি হওয়া ঘরে দাগানো ␣ লিখুন।
- M qaccept-এ গেলে accept, qreject-এ গেলে reject; নইলে ধাপ ২-এ ফিরুন।
ধাপ ২-এ “k-টি চিহ্ন মনে রাখা” বৈধ, কারণ Γk সসীম: S-এর state হলো (M-এর state, দেখা চিহ্নগুলো, sweep-এর পর্যায়), যা অনেক কিন্তু সসীম। নিচের stepper ছোট input “0#0”-এ M-এর প্রতিটি ধাপের পাশে S-এর tape দেখায়, ঠিক অংশ ৪-এর কোড যেভাবে ছাপে।
| M-এর ধাপ | |
| M-এর state | |
| M: tape ১ / ২ | |
| এই ধাপে shift |
- Format. ‖, input “0#0” (প্রথম ঘর দাগানো), ‖, tape ২-এর জন্য একটি দাগানো ␣, ‖: মোট ৭টি ঘর।
- ধাপ ১: লেখা আর shift. S sweep করে দাগানো চিহ্ন (0, ␣) পায়। δ অনুযায়ী tape ২-এ $ লেখা হবে আর tape ২-এর head ডানে যাবে। কিন্তু ডানে শেষ ‖! তাই ‖ এক ঘর সরে যায় আর ফাঁকা হওয়া ঘরে দাগানো ␣ বসে।
- ধাপ ২: দুই দাগ একসঙ্গে। পড়া (0, ␣), ফল: tape ২-এ 0 লেখা, দুই head ডানে। tape ১-এর দাগ # চিহ্নে যায়; tape ২-এর দাগ আবার ‖-এ পড়ে, তাই আরেকটি shift.
- ধাপ ৩: উল্টো দিকের চাল। পড়া (#, ␣): tape ১-এর দাগ ডানে, tape ২-এর দাগ বাঁয়ে 0-তে। বাঁয়ে সরতে shift লাগে না; ␣ ঘরটি রয়ে যায়।
- ধাপ ৪: $ পর্যন্ত ফেরা। পড়া (0, 0): tape ১-এর দাগ দাঁড়িয়ে, tape ২-এর দাগ বাঁয়ে $-এ।
- ধাপ ৫: মেলানোর শুরু। পড়া (0, $): tape ২-এর দাগ এক ঘর ডানে, state cmp. এখন দুই দাগ দুই order ID-র প্রথম চিহ্নে।
- ধাপ ৬: মিল, আর shift. পড়া (0, 0) মিলেছে, দুই দাগ ডানে। tape ১-এর দাগ ‖-এ পড়ে, তাই tape ১-এর অংশে একটি ␣ ঢোকে; tape ২-এর দাগ আগে থেকে থাকা ␣ ঘরে যায়, shift লাগে না।
- ধাপ ৭: গ্রহণ। পড়া (␣, ␣), M accept করে, S-ও। প্রতিটি ধাপের পর S-এর tape ছিল M-এর configuration-এর হুবহু সংকেত: এটিই প্রমাণের invariant.
প্রমাণ (উপপাদ্য ৩.১): M-এর i ধাপের পরের configuration Ci হলে, enc(Ci) মানে S-এর tape-এ তার সংকেত (অংশগুলো ‖ দিয়ে ভাগ, head-এর ঘর দাগানো) আর S-এর control-এ M-এর state.
- শুরু: নির্মাণের ধাপ ১-এর পর S-এর অবস্থা enc(C0), কারণ C0-এ input tape ১-এ, বাকি tape ফাঁকা, সব head প্রথম ঘরে। — নির্মাণ ৩.২-এর ধাপ ১
- Invariant: চক্রের শুরুতে S-এর অবস্থা enc(Ci) আর Ci থামার configuration নয় ধরুন। ধাপ ২-এর sweep ঠিক Ci-এর head-গুলোর নিচের k-টি চিহ্ন পড়ে। — সংকেতের সংজ্ঞা: প্রতি অংশে ঠিক একটি দাগ
- ধাপ ৩ প্রতিটি অংশে δ-এর লেখা বসায় আর দাগ সরায়, বাঁ প্রান্তের রীতিসহ; ধাপ ৪ শুধু তখনই ঘর যোগ করে, যখন M-এর head প্রথমবার একটি নতুন ঘরে যায়, আর সেই ঘর M-এর tape-এও ␣. তাই চক্র শেষে S-এর অবস্থা enc(Ci+1). — δ-এর সংজ্ঞা
- Induction: i-এর ওপর induction-এ, M যতক্ষণ চলে, প্রতিটি চক্রের শেষে S-এর অবস্থা enc(Ci). — ধাপ ১ থেকে ৩
- উপসংহার: M কোনো i ধাপে qaccept বা qreject-এ গেলে S-ও সেই চক্রে একই সিদ্ধান্তে থামে। M কখনো না থামলে S অসীম সংখ্যক চক্র চালায়, প্রতিটি চক্র সসীম, তাই S-ও থামে না। অতএব L(S) = L(M), আর থামা-না-থামা হুবহু এক। ∎
৪ · দাম কত — O(t2) slowdown আর তা কি এড়ানো যায়
শক্তি একই, এবার গতি। একটি যন্ত্রের time complexity t(n) মানে দৈর্ঘ্য n-এর যেকোনো input-এ সে বড়জোর t(n) ধাপে থামে (বিস্তারিত পর্ব ৫৭-এ)। Simulation-এ এই সংখ্যা কতটা বাড়ে, তার নাম simulation overhead.
ধরুন t(n) ≥ n. প্রতিটি t(n)-সময়ের k-tape Turing machine-এর একটি সমতুল্য O(t(n)2)-সময়ের single-tape Turing machine আছে। (Sipser-এর বইয়ে Theorem 7.8.)
প্রমাণ (নির্মাণ ৩.২-এর S-এর ধাপ গোনা; k স্থির, তাই k-এর গুণক O-এর ভেতরে যায়):
- প্রতি ধাপে একটি head বড়জোর এক ঘর সরে, তাই t(n) ধাপে M-এর কোনো tape-এর ব্যবহৃত অংশ বড়জোর t(n) + 1 ঘর; tape ১-এ input-এর n ঘরও আছে, আর n ≤ t(n). — শর্ত t(n) ≥ n
- তাই S-এর tape-এর দৈর্ঘ্য সবসময় বড়জোর k(t(n) + 1) + k + 1 = O(t(n)). — k-টি অংশ আর k + 1টি ‖
- একটি simulation-চক্রে দুটি sweep, প্রতিটি পুরো tape একবার যাওয়া-আসা: O(t(n)). বড়জোর k-টি shift, প্রতিটি tape-এর বাকি অংশ এক ঘর সরানো: O(t(n)). মোট চক্র প্রতি O(t(n)). — ধাপ ২
- শুরুর format (input এক ঘর ডানে সরিয়ে ‖ আর দাগ বসানো): O(n) = O(t(n)). — শর্ত t(n) ≥ n
- M বড়জোর t(n) ধাপ চলে, তাই S-এর মোট সময় O(t(n)) + t(n) · O(t(n)) = O(t(n)2). ∎
শর্ত t(n) ≥ n লাগে, কারণ input না পড়া যন্ত্রের জন্যও S-কে শুরুতে পুরো input সাজাতে হয়। এবার যন্ত্রে মিলিয়ে দেখি। প্রথমে একই language-এর এক tape-এর যন্ত্র (পর্ব ৪৩-এর আঁকাবাঁকা পথে দাগ দেওয়ার যন্ত্র, x মানে কাটা চিহ্ন) ওপরের simulator-এ k = 1 দিয়ে চালানো, তারপর দুই যন্ত্রের ধাপ পাশাপাশি।
# 1-tape zig-zag machine for {w#w} (crossing off, as in পর্ব ৪৩) vs the 2-tape D2
D1 = {}
def rule(q, a, q2, b, m): D1[q, (a,)] = (q2, (b,), m)
rule("q0", "0", "c0", "x", "R"); rule("q0", "1", "c1", "x", "R")
rule("q0", "#", "end", "#", "R")
for a in "01":
rule("c0", a, "c0", a, "R"); rule("c1", a, "c1", a, "R")
rule("back2", a, "back2", a, "L")
for a in "01x": rule("back1", a, "back1", a, "L")
rule("c0", "#", "f0", "#", "R"); rule("c1", "#", "f1", "#", "R")
rule("f0", "x", "f0", "x", "R"); rule("f1", "x", "f1", "x", "R")
rule("f0", "0", "back1", "x", "L"); rule("f1", "1", "back1", "x", "L")
rule("back1", "#", "back2", "#", "L"); rule("back2", "x", "q0", "x", "R")
rule("end", "x", "end", "x", "R"); rule("end", B, "acc", B, "S")
agree = all(run(D1, s, 1)[0] == run(D2, s, 2)[0]
for n in range(8) for s in map("".join, product("01#", repeat=n)))
print("D1 and D2 agree on all 3280 strings:", agree)
print(f"{'|w|':>4} {'n':>4} {'2-tape':>7} {'1-tape':>7} {'1-tape/n^2':>11}")
for m in [4, 8, 16, 32, 64, 128]:
w = ("0110" * 40)[:m]; s = w + "#" + w; n = len(s)
t2, t1 = run(D2, s, 2)[1], run(D1, s, 1)[1]
print(f"{m:>4} {n:>4} {t2:>7} {t1:>7} {t1 / n**2:>11.3f}")আসল আউটপুট (ব্রাউজারের Python):
D1 and D2 agree on all 3280 strings: True
|w| n 2-tape 1-tape 1-tape/n^2
4 9 16 50 0.617
8 17 28 162 0.561
16 33 52 578 0.531
32 65 100 2178 0.516
64 129 196 8450 0.508
128 257 388 33282 0.504
দুই যন্ত্র ৩২৮০টি string-এ একই সিদ্ধান্ত দেয়, তাই একই language. কিন্তু ধাপ: 2-tape-এ m দ্বিগুণ হলে ধাপ প্রায় দ্বিগুণ (3m + 4), 1-tape-এ প্রায় চারগুণ। সূত্রটি 2(m + 1)2 (৫০ = 2 · 52, ১৬২ = 2 · 92), অর্থাৎ প্রায় n2/2; শেষ কলাম ০.৫-এর দিকে। m = 128-এ পার্থক্য প্রায় ৮৬ গুণ, কারণ প্রতিটি চিহ্ন মেলাতে head-কে # পেরিয়ে Θ(m) পথ যাওয়া-আসা করতে হয়।
এবার নির্মাণ ৩.২-এর S নিজেই। নিচের ব্লক S-এর tape একটি list হিসেবে রাখে, আর প্রতিটি নকল-ধাপে head কত ঘর হাঁটে, তা গোনে: যাওয়া-আসার দুটি sweep আর প্রতিটি shift-এর খরচ। সততার জন্য বলে রাখি: আমরা S-এর পুরো δ টেবিল লিখিনি, শুধু তার sweep-গুলোর হাঁটা গুনেছি, যা S-এর ধাপ-সংখ্যার সঙ্গে একটি ধ্রুবক গুণকে মেলে।
# One tape S simulating the 2-tape D2: ‖ tape1 ‖ tape2 ‖, heads = marked [x]
SEP = "‖"
def single(delta, w, k, show=0):
T = [SEP] + [(c, i == 0) for i, c in enumerate(w or B)] + [SEP]
T += [(B, True), SEP] * (k - 1) # (symbol, is_head_here)
q, moves_S, t = "q0", len(T), 0 # setup: write the format once
while q not in ("acc", "rej"):
if t < show: print(f"{q:5}", "".join(c if c == SEP else
(f"[{c[0]}]" if c[1] else c[0]) for c in T))
heads = [i for i, c in enumerate(T) if c != SEP and c[1]]
moves_S += 2 * (len(T) - 1) # pass 1: sweep right, come back
syms = tuple(T[i][0] for i in heads)
q, writes, mv = delta.get((q, syms), ("rej", syms, "S" * k))
for h, a, m in sorted(zip(heads, writes, mv), reverse=True):
T[h] = (a, m == "S" or (m == "L" and T[h - 1] == SEP))
if m == "L" and T[h - 1] != SEP: T[h - 1] = (T[h - 1][0], True)
if m == "R":
if T[h + 1] == SEP: # head hits ‖: shift right
T.insert(h + 1, (B, False)); moves_S += 2 * (len(T) - h)
T[h + 1] = (T[h + 1][0], True)
moves_S += 2 * (len(T) - 1); t += 1 # pass 2: update, come back
return q, t, moves_S
single(D2, "0#0", 2, show=7)
print(f"{'n':>4} {'t (2-tape)':>10} {'S moves':>9} {'S/t^2':>7}")
for m in [4, 8, 16, 32, 64]:
w = ("0110" * 20)[:m]; q, t, s = single(D2, w + "#" + w, 2)
assert q == "acc" and t == run(D2, w + "#" + w, 2)[1]
print(f"{2*m+1:>4} {t:>10} {s:>9} {s / t**2:>7.2f}")আসল আউটপুট (ব্রাউজারের Python):
q0 ‖[0]#0‖[␣]‖
copy ‖[0]#0‖$[␣]‖
copy ‖0[#]0‖$0[␣]‖
back ‖0#[0]‖$[0]␣‖
back ‖0#[0]‖[$]0␣‖
cmp ‖0#[0]‖$[0]␣‖
cmp ‖0#0[␣]‖$0[␣]‖
n t (2-tape) S moves S/t^2
9 16 1107 4.32
17 28 3195 4.08
33 52 10635 3.93
65 100 38571 3.86
129 196 146667 3.82
প্রথম সাত লাইন অংশ ৩-এর stepper-এর S-এর tape, হুবহু। assert নিশ্চিত করে, S M-এর মতোই accept করে আর ঠিক ততগুলো ধাপ নকল করে। শেষ কলাম (হাঁটা ÷ t2) ৪.৩২ থেকে ৩.৮২, একটি ধ্রুবকের দিকে: খরচ Θ(t2)-এর মাপে। তবে এই S হাতে লেখা 1-tape যন্ত্রের চেয়ে অনেক ধীর (n = 129-এ ১,৪৬,৬৬৭ বনাম ৮৪৫০); সাধারণ নির্মাণ সব যন্ত্রে খাটে, কোনোটিতে বিশেষ দক্ষ নয়।
বর্গ কি এড়ানো যায়? সাধারণভাবে না। ১৯৬০-এর দশকের মাঝামাঝি F. C. Hennie আর (আলাদাভাবে) Ya. M. Barzdin দেখান বলে পরিচিত যে palindrome চিনতে যেকোনো single-tape যন্ত্রের Ω(n2) ধাপ লাগে, crossing sequence কৌশলে ({w#w}-এও একই ধরনের যুক্তি খাটে)। অথচ দুই tape-এ O(n). তাই উপপাদ্য ৪.১-এর বর্গ সাধারণভাবে উন্নত করা যায় না।
সত্যিকারের run — automata-lib দিয়ে একই যন্ত্র
নিজের simulator-এর ফল একটি স্বাধীন library-তে মিলিয়ে নিই। automata-lib (Python, MIT licence)-এর DTM ক্লাস single-tape আর MNTM ক্লাস multi-tape যন্ত্র চালায়। এর কোডে কোনো network বা usage-reporting অংশ নেই, তা scratch-এ খুঁজে দেখা হয়েছে। একই দুটি যন্ত্র library-র dict-আকারে (blank ., S চালের নাম N). মূল অংশ:
m2 = MNTM(states={"q0", "copy", "back", "cmp", "acc"}, input_symbols={"0", "1", "#"},
tape_symbols={"0", "1", "#", "$", B}, n_tapes=2, transitions=T2,
initial_state="q0", blank_symbol=B, final_states={"acc"})
m1 = DTM(states=set(T1) | {"acc"}, input_symbols={"0", "1", "#"},
tape_symbols={"0", "1", "#", "x", B}, transitions=T1,
initial_state="q0", blank_symbol=B, final_states={"acc"})
...
def steps(machine, s): # configurations yielded minus the first
return sum(1 for _ in machine.read_input_stepwise(s)) - 1
...
for conf in m2.read_input_as_ntm("0#0"): # library's own single-tape simulation
(c,) = conf
print(f" {c.state:5} {''.join(c.tape.tape)}")সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12.13, uv 0.11.28):
~/bazarghar-toc$ uv run python tm_variants_lib.py
automata-lib 9.2.0 | Python 3.12.13
strings of length 1..7: 3279 | 2-tape correct: 3279 | 1-tape correct: 3279
|w| 2-tape 1-tape
4 16 50
8 28 162
16 52 578
32 100 2178
64 196 8450
single-tape simulation of the 2-tape machine on 0#0 (library's own format):
q0 0^#0_.^_
copy 0^#0_$.^_
copy 0#^0_$0.^_
back 0#0^_$0^._
back 0#0^_$^0._
cmp 0#0^_$0^._
cmp 0#0.^_$0.^_
acc 0#0.^_$0.^_
সঠিকতা: দৈর্ঘ্য ১ থেকে ৭-এর ৩২৭৯টি string-এ (ε বাদ) দুই যন্ত্রই সংজ্ঞার সঙ্গে মেলে। ধাপ: ব্রাউজারের ব্লকের সংখ্যার সঙ্গে হুবহু এক। Library-র single-tape রূপ: read_input_as_ntm ঠিক উপপাদ্য ৩.১-এর ভাবনা ব্যবহার করে, শুধু চিহ্ন আলাদা: _ হলো আমাদের ‖, আর head-এর ঘরের পরে একটি ^. যেমন “0#0^_$0^._” মানে tape ১-এর head শেষ 0-তে, tape ২-এর head 0-তে: আমাদের “‖0#[0]‖$[0]␣‖”. আটটি লাইন stepper-এর আট ধাপের সঙ্গে মেলে। Library S-এর ধাপ গোনে না, তাই ধাপ-গোনা আমাদের ব্লক থেকে।
৫ · Multi-track, stay-put আর ছোট alphabet — ছোট রূপভেদ
Multi-track tape. একটি multi-track tape-এ একটি tape-ই থাকে, একটি head-ও, কিন্তু প্রতিটি ঘর k-টি তলায় ভাগ: যেন একটি ক্রিকেট স্কোরবোর্ডের প্রতিটি কলামে ওপরে রান, নিচে উইকেট। Head একটি কলাম পড়ে মানে k-টি চিহ্ন একসঙ্গে পড়ে। কিন্তু এটি আসলে কোনো নতুন মডেলই নয়: tape alphabet হিসেবে Γ1 × Γ2 × ⋯ × Γk নিলেই হয়, যেখানে প্রতিটি k-tuple একটি একক চিহ্ন। Input চিহ্ন a-কে (a, ␣, …, ␣) হিসেবে ধরা হয়, আর blank হলো (␣, …, ␣). তাই multi-track যন্ত্র আক্ষরিক অর্থেই একটি মূল মডেলের যন্ত্র, শুধু বড় alphabet-এর; নকলের খরচ শূন্য।
অংশ ৩-এর দাগানো চিহ্নও একটি দুই-তলার track: ওপরে চিহ্ন, নিচে “head আছে কি না”. Turing ১৯৩৬ সালে অঙ্ক লিখতেন একটি অন্তর একটি ঘরে (F-squares), আর মাঝের ঘর (E-squares) রাখতেন দাগের জন্য: দুই তলার tape-এর একটি আদি রূপ।
Stay-put চাল. মূল মডেলে head-কে প্রতি ধাপে সরতেই হয়। একটি stay-put move (S) দিলে কি বেশি শক্তি আসে? না। δ(q, a) = (p, b, S) নিয়মটির বদলে একটি নতুন state p′ যোগ করুন আর দুটি নিয়ম লিখুন:
δ′(q, a) = (p′, b, R), δ′(p′, x) = (p, x, L) প্রতিটি x ∈ Γ-এর জন্য।
প্রথমে ডানে এক ঘর গিয়ে, সেখানে কিছু না বদলে, আবার বাঁয়ে ফেরা। (উল্টো ক্রম, আগে L, প্রথম ঘরে ভুল করত, কারণ সেখানে L নড়ে না।) খরচ বড়জোর 2t ধাপ।
ছোট alphabet. ছোট alphabet-এও শক্তি কমে না। Γ-এর প্রতিটি চিহ্নকে b = ⌈log2 |Γ|⌉ বিটের একটি block হিসেবে লিখলে tape alphabet {0, 1, ␣} যথেষ্ট। মূল যন্ত্রের একটি ধাপ নকল করতে নতুন যন্ত্র একটি block পড়ে, নতুন block লেখে আর b ঘর সরে: প্রতি ধাপে O(b), আর b ধ্রুবক। এই কারণেই পর্ব ৪৮-এ সব যন্ত্রকে binary string হিসেবে লেখা যাবে।
৬ · দুই দিকে অসীম tape — ভাঁজ করে এক দিকে
একটি two-way infinite tape-এর ঘর …, −2, −1, 0, 1, 2, …; input ঘর 0 থেকে ডানে, আর head বাঁয়েও যতদূর ইচ্ছা যায়। এক দিকে অসীম মডেল কি দুর্বল? না; কৌশল হলো tape-টি ঘর 0-এর কাছে কাগজের মতো ভাঁজ করা।
এক দিকে অসীম যন্ত্র S দুই-track-এর tape নেয় (অংশ ৫: আসলে জোড়া-চিহ্নের alphabet). অবস্থান p = 0-তে একটি বাঁ-প্রান্তের দাগ ▸. অবস্থান p ≥ 1-এ:
ওপরের track = M-এর ঘর p − 1, নিচের track = M-এর ঘর −p.
অর্থাৎ ঘর 0, 1, 2, … ওপরের track-এ ডানে ছড়ায়, আর ঘর −1, −2, −3, … নিচের track-এ, সেটিও ডানে। S তার state-এ মনে রাখে head এখন কোন track-এ। ওপরের track-এ M-এর L আর R ঠিক তেমনই থাকে; নিচের track-এ উল্টে যায় (M-এর L মানে S-এর R, কারণ ঘর −2 ঘর −1-এর ডানে বসেছে)। ওপরের track-এ p = 1 থেকে L গেলে বা নিচের track-এ p = 1 থেকে R গেলে S ▸ পড়ে; তখন এক ঘর ডানে ফিরে track বদলায়। শুরুতে S input এক ঘর ডানে সরিয়ে ▸ বসায় আর প্রতিটি a-কে (a, ␣) জোড়ায় বদলায়: O(n) ধাপ।
নিচের stepper-এ M-এর ঘর −2 থেকে 2-এ b, a, 1, 0, 1, head ঘর 1-এ, আর M চলে L, L, L, R, R. শুধু ঘর 0 আর −1-এর সীমানা পারাপারে S-এর বাড়তি ধাপ লাগে।
| M-এর head | |
| S-এর head | |
| পড়া চিহ্ন | |
| ধাপ: M / S |
- শুরুর অবস্থা। M-এর head ঘর 1-এ (চিহ্ন 0), যা ভাঁজে p = 2-এর ওপরের track. p = 1-এ জোড়া (1, a): ঘর 0 আর −1 একই কলামে।
- L, ওপরের track-এ। M ঘর 0-তে যায়। ওপরের track-এ চাল বদলায় না: S-ও p = 2 থেকে p = 1-এ, পড়ে ওপরের 1. দুই যন্ত্রেরই এক ধাপ।
- আবার L: সীমানায় ধাক্কা। M ঘর −1-এ যেতে চায়। S p = 0-তে গিয়ে ▸ পড়ে: M-এর কোনো ঘর নয়, শুধু “ভাঁজে এসেছেন” সংকেত। M-এর ধাপ এখনো শেষ হয়নি।
- Track বদল। ▸ দেখে S এক ঘর ডানে ফেরে, p = 1, আর state-এ track = “নিচে” লেখে। এখন পড়া চিহ্ন a, যা M-এর ঘর −1. M-এর এই একটি ধাপে S-এর দুটি ধাপ লাগল।
- L, নিচের track-এ: দিক উল্টো। M আরও বাঁয়ে, ঘর −2. নিচের track-এ M-এর L মানে S-এর R: p = 1 থেকে p = 2, পড়ে নিচের b. সীমানা থেকে দূরে প্রতিটি চাল আবার এক ধাপের।
- R, নিচের track-এ। M ডানে, ঘর −1. S বাঁয়ে, p = 2 থেকে p = 1, নিচের a. দিক উল্টানোর নিয়ম দুই দিকেই একইভাবে খাটে।
- আবার সীমানা। M ডানে, ঘর 0. নিচের track-এ p = 1 থেকে R মানে S-এর বাঁয়ে যাওয়া: ▸ পড়ে, ডানে ফেরে, track = “ওপরে”, পড়ে 1. আবার দুই ধাপ। মোট: M-এর ৫ ধাপ, S-এর ৭ ধাপ; বাড়তি ২ ধাপ ঠিক দুটি সীমানা-পারাপারের।
খরচ তাই বড়জোর 2t + O(n), যেখানে O(n) শুরুর সাজানো। মজার তথ্য: অংশ ৪-এর automata-lib-এর tape আসলে দুই দিকে অসীম (source code-এ দেখা যায়, বাঁয়ে গেলে নতুন ফাঁকা ঘর জোড়ে)। আমাদের যন্ত্র দুটি কখনো প্রথম ঘরের বাঁয়ে যায় না, তাই দুই রীতিতে ধাপ হুবহু এক।
৭ · Enumerator — যে যন্ত্র language ছাপে
এবার এমন যন্ত্র, যে input নেয় না, শুধু একটির পর একটি string ছাপে, রেলস্টেশনের ডিসপ্লে বোর্ডের মতো। “Recursively enumerable” নামটি এখান থেকে।
একটি enumerator E হলো একটি Turing machine, যার সঙ্গে একটি printer যুক্ত (formal রূপে: একটি বাড়তি, শুধু-লেখা-যায় output tape, যেখানে string-গুলো একটি বিভাজক দিয়ে আলাদা করে লেখা হয়)। E শুরু হয় ফাঁকা work tape নিয়ে, আর চলার পথে মাঝে মাঝে একটি string ছাপে। E-এর language L(E) হলো E যত string কখনো ছাপে, তাদের set. E যেকোনো ক্রমে ছাপতে পারে, একই string বারবার ছাপতে পারে, আর কখনো না থামতে পারে।
একটি language L Turing-recognizable, যদি এবং কেবল যদি কোনো enumerator E-এর জন্য L(E) = L. (Sipser-এর বইয়ে Theorem 3.21.)
প্রমাণ, (⇐) দিক (E থেকে recognizer):
- M = “input w-এ: E চালানো; E প্রতিবার একটি string ছাপলে সেটি w-এর সঙ্গে মেলানো; মিললে accept.” (multi-tape-এ সরল, আর উপপাদ্য ৩.১ বলে বৈধ) — নির্মাণ
- w ∈ L হলে E কোনো এক সময় w ছাপে, তখন M accept করে। — L(E)-এর সংজ্ঞা
- w ∉ L হলে E কখনো w ছাপে না, তাই M কখনো accept করে না (E থামলে M reject করতে পারে, না থামলে M-ও চলতে থাকে)। অতএব L(M) = L. ∎ — L(E)-এর সংজ্ঞা
(⇒) দিকে একটি ফাঁদ আছে। স্বাভাবিক ভাবনা: string-গুলো shortlex order-এ সাজিয়ে, s1 = ε, s2, … (পর্ব ০২), একে একে M চালানো। কিন্তু M decider নয়: কোনো sj ∉ L-এ M চিরকাল চললে E সেখানেই আটকে যায়।
প্রমাণ, (⇒) দিক (recognizer M থেকে E, dovetailing দিয়ে):
- E = “ফাঁকা input উপেক্ষা করে, i = 1, 2, 3, … ক্রমে: s1, …, si-এর প্রতিটিতে M-কে বড়জোর i ধাপ চালানো; যেটিকে M এই i ধাপের মধ্যে accept করে, সেটি ছাপা।” প্রতিটি পর্যায় (round) সসীম কাজ: i-টি string, প্রতিটিতে i ধাপ। — নির্মাণ
- E যা ছাপে, তা M-এর গৃহীত, তাই L-এর সদস্য। — ছাপার শর্ত
- উল্টো দিকে, w ∈ L হলে w = sj কোনো j-এর জন্য, আর M তাকে কোনো সসীম t ধাপে accept করে। i = max(j, t) পর্যায়ে sj চালানো হয় আর i ≥ t ধাপ পায়, তাই ছাপা হয়। — shortlex-এ প্রতিটি string-এর সসীম অবস্থান
- প্রতিটি পর্যায় সসীম, তাই E প্রতিটি পর্যায়ে একসময় পৌঁছায়; কোনো অসীম loop তাকে আটকাতে পারে না। অতএব L(E) = L. ∎
এই কৌশলের নাম dovetailing (কাঠের “ঘুঘুর লেজ” জোড়ার মতো, দাঁত একটির পর একটি ঢোকে)। বাজারঘরের একজন ডেলিভারিকর্মী অনেক ঠিকানা খুঁজছেন, যার কিছু ভুল। একটি পুরো খুঁজে তবেই পরেরটি ধরলে একটি ভুল ঠিকানায় জীবন কেটে যেতে পারে; প্রতিদিন প্রতিটিতে একটু বেশি সময় আর তালিকায় একটি নতুন ঠিকানা দিলে, পাওয়া সম্ভব এমন সব ঠিকানা একদিন পাওয়া যাবেই।
উদাহরণ: Σ = {a, b}, L = {w : w-তে a আর b সমান সংখ্যক}. আমাদের recognizer M ইচ্ছা করে খারাপ: w একবার পড়ে (|w| ধাপ), সমান হলে পরের ধাপে accept, নইলে চিরকাল চলে, কখনো reject করে না। নিচের stepper প্রথম ছয়টি পর্যায় দেখায়।
| পর্যায় i | |
| চালানো string | |
| প্রতিটিতে ধাপ | |
| নতুন ছাপা |
- পর্যায় ১। শুধু s1 = ε, এক ধাপ। ε-তে পড়ার কিছু নেই, a আর b শূন্যটি করে, তাই প্রথম ধাপেই accept: ε ছাপা হলো।
- পর্যায় ২। ε আর a, দুই ধাপ করে। ε আগেই ছাপা (Sipser-এর E আবার ছাপত, L(E) একই)। a: এক ধাপ পড়া, তারপর loop.
- পর্যায় ৩। b যোগ হলো। a আর b দুটিই তিন ধাপ পায়, দুটিই loop-এ। সরল enumerator এখানে a-তেই চিরকাল আটকে থাকত; dovetailing পরের পর্যায়ে চলে যায়।
- পর্যায় ৪। aa যোগ হলো: দুই ধাপ পড়ে, তারপর loop. মোট ৪ × ৪ = ১৬ ধাপ, সসীম।
- পর্যায় ৫। s5 = ab যোগ হলো। M দুই ধাপে পড়ে, তৃতীয় ধাপে accept; ৫ ≥ ৩, তাই ab ছাপা হলো। j = 5 আর t = 3, তাই প্রমাণের max(j, t) = ৫ পর্যায়েই।
- পর্যায় ৬। s6 = ba একইভাবে তিন ধাপে গৃহীত, ছাপা হলো। aa আর bb প্রতিটি পর্যায়ে আরও ধাপ পায়, কিন্তু কখনো accept হয় না, তাই কখনো ছাপা হয় না। ঠিক এটিই চাই।
নিচের ব্লক দুটি enumerator চালায়: সরল (১০০০ ধাপের সীমাসহ) আর dovetailing (৩০ পর্যায়)। M একটি Python generator, প্রতিটি yield একটি ধাপ।
# Recognizer -> enumerator: naive order vs dovetailing (always a STEP CAP)
from itertools import count, product
def M(w): # recognizer as a generator, one item per step
for _ in w: yield "run" # scan w once
if w.count("a") == w.count("b"): yield "acc" # accept if #a = #b
while True: yield "run" # otherwise LOOP FOREVER (never rejects)
def shortlex(): # ε, a, b, aa, ab, ba, bb, aaa, ...
for n in count():
yield from map("".join, product("ab", repeat=n))
def naive(cap=1000): # finish each string before the next one
for w in shortlex():
for steps, s in enumerate(M(w), 1):
if s == "acc": print("naive: print", repr(w or "ε")); break
if steps == cap: return print(f"naive: stuck on {w!r} after {cap} steps")
def dovetail(rounds): # round i: first i strings, i steps each
printed = []
for i in range(1, rounds + 1):
for w in [s for s, _ in zip(shortlex(), range(i))]:
ok = "acc" in [s for s, _ in zip(M(w), range(i))]
if ok and w not in printed:
printed.append(w); print(f"round {i:2}: print {w or 'ε'!r}")
return printed
naive()
out = dovetail(30)
want = [w for n in range(5) for w in map("".join, product("ab", repeat=n))
if w.count("a") == w.count("b")]
print("every member of length <= 4 printed:", set(want) <= set(out))আসল আউটপুট (ব্রাউজারের Python):
naive: print 'ε'
naive: stuck on 'a' after 1000 steps
round 1: print 'ε'
round 5: print 'ab'
round 6: print 'ba'
round 19: print 'aabb'
round 21: print 'abab'
round 22: print 'abba'
round 25: print 'baab'
round 26: print 'baba'
round 28: print 'bbaa'
every member of length <= 4 printed: True
সরল enumerator ε ছেপে a-তেই আটকে যায়; সীমা না থাকলে চিরকাল, আর ab কখনো ছাপা হতো না। Dovetailing stepper-এর মতোই ε, ab, ba ছাপে। aabb shortlex-এ ১৯তম string (১ + ২ + ৪ + ৮-এর পর চতুর্থ) আর ৫ ধাপে গৃহীত, তাই পর্যায় max(19, 5) = ১৯. শেষ লাইন: দৈর্ঘ্য ৪ পর্যন্ত সব সদস্য ছাপা হয়েছে। ক্রম এখানে shortlex-এর মতো, কিন্তু সাধারণভাবে নয়: একটি ছোট string অনেক ধাপে গৃহীত হলে পরে ছাপা হতে পারে।
একটি গভীর সত্য: L decidable ঠিক তখন, যখন কোনো enumerator L-কে shortlex ক্রমে ছাপে (অনুশীলন ২)। “যেকোনো ক্রমে” বনাম “ক্রমানুসারে” তালিকার পার্থক্যই recognizable বনাম decidable (পর্ব ৫০)।
৮ · RAM, দুই stack আর অন্য আত্মীয় — সমতার মানচিত্র
RAM-ধাঁচের যন্ত্র. Algorithm-এর বইগুলো (DSA কোর্সে আপনি যা দেখেছেন) RAM model ব্যবহার করে: register, অসীম সংখ্যক memory ঘর, আর যেকোনো ঠিকানা এক ধাপে পড়া। TM-এ “যেকোনো ঘরে লাফ” নেই, তবু multi-tape TM একটি RAM নকল করে: এক tape-এ memory (ঠিকানা, মান) জোড়ার তালিকা, আরেকটিতে register, আর প্রতিটি পড়ায় তালিকা খোঁজা। শক্তি সমান, সময়ে polynomial দাম, যদি সংখ্যার বিট-দৈর্ঘ্য যুক্তিসংগতভাবে বাড়ে (logarithmic cost model বা O(log n) বিটের word); Cook ও Reckhow-এর ১৯৭৩ সালের প্রবন্ধ এর একটি পরিচিত উৎস।
দুই stack, queue আর counter. পর্ব ৩২-এর two-stack PDA TM-এর সমান: এক stack head-এর বাঁয়ের অংশ, অন্যটি বাকি অংশ। একটি queue-সহ finite automaton-ও সমান, এমনকি দুটি counter-ও (Minsky-র ফল বলে পরিচিত, পর্ব ৪৯)।
কোন পরিবর্তন শক্তি কমায়. Memory input-এর দৈর্ঘ্যে বাঁধা হলে linear bounded automaton, যার সব language decidable (পর্ব ০৬); একটি stack হলে PDA, যা aⁿbⁿcⁿ-ও চেনে না (পর্ব ৩৬); আর head লিখতে না পারলে, দুই দিকে চললেও, শুধু regular language (Rabin–Scott আর Shepherdson, ১৯৫৯)। শিক্ষা: সীমাহীন, লেখা-মোছা যায় এমন memory-ই শক্তির উৎস; tape-এর সংখ্যা বা দিক খুঁটিনাটি।
| রূপভেদ | শক্তি (মূল TM-এর তুলনায়) | মূল মডেলে নকলের খরচ (t ধাপ, input n) | কোথায় |
|---|---|---|---|
| Stay-put চাল (S) | সমান | বড়জোর 2t | অংশ ৫ |
| Multi-track tape | সমান | t (শুধু বড় alphabet) | অংশ ৫ |
| Alphabet {0, 1, ␣}-এ নামানো | সমান | O(t), ধ্রুবক গুণক | অংশ ৫ |
| দুই দিকে অসীম tape | সমান | 2t + O(n) | অংশ ৬ |
| k-টি tape | সমান | O(t2) (t ≥ n), কিছু language-এ অবশ্যম্ভাবী | অংশ ৩–৪ |
| RAM-ধাঁচের যন্ত্র | সমান | polynomial (যুক্তিসংগত cost model-এ) | অংশ ৮ |
| দুই stack বা একটি queue | সমান | পর্ব ৩২-এর নির্মাণে polynomial | পর্ব ৩২ |
| Nondeterministic TM | সমান | exponential পর্যন্ত (জানা পদ্ধতিতে) | পর্ব ৪৬ |
| LBA, PDA, লিখতে-না-পারা TM | দুর্বল | প্রযোজ্য নয় | পর্ব ০৬, ৩২ |
এই টেবিল Church–Turing thesis-এর (পর্ব ৪৭) পক্ষে বড় সাক্ষ্য। তবে প্রতিটি “সমান” একটি প্রমাণিত উপপাদ্য; thesis তার চেয়ে বড় দাবি (যেকোনো যান্ত্রিক পদ্ধতি এই সীমায়), যা প্রমাণ করা যায় না। আর nondeterminism ছাড়া সব সারির খরচ polynomial, তাই class P সব যুক্তিসংগত deterministic মডেলে এক, অথচ “P = NP?” খোলা প্রশ্ন (পর্ব ৬৩)।
আরও গভীরে: Multi-tape থেকে single-tape-এ বর্গ-দাম অবশ্যম্ভাবী, কিন্তু দুই tape-এ নামলে দাম অনেক কম: Hennie আর Stearns ১৯৬৬ সালে দেখান, যেকোনো k-tape যন্ত্রের t ধাপ একটি 2-tape যন্ত্র O(t log t) ধাপে নকল করতে পারে; এই ফল পর্ব ৬৭-এর time hierarchy theorem-এর পরিচিত রূপে log t গুণকটি আনে। আর একটি পুরোনো প্রশ্ন আজও খোলা: deterministic আর nondeterministic LBA কি সমান শক্তিশালী (“LBA problem”)? এর সঙ্গী প্রশ্নের (context-sensitive language complement-এ বন্ধ কি না) উত্তর “হ্যাঁ”, Immerman আর Szelepcsényi ১৯৮৭–৮৮ সালে প্রমাণ করেন।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন আসতে পারে:
- Multi-tape TM কি single-tape-এর চেয়ে শক্তিশালী? না; একই language চেনে। এক tape-এ সব tape ‖ দিয়ে পাশাপাশি লিখে head-এর ঘর দাগিয়ে নকল করা যায়, খরচ O(t2).
- O(t2) কোথা থেকে? Tape O(t) ঘর, প্রতি নকল-ধাপে sweep ও shift O(t), মোট t · O(t).
- Enumerator কী, আর recognizable language-এর সঙ্গে সম্পর্ক? যে TM string ছাপে; L recognizable ⇔ কোনো enumerator L ছাপে। Recognizer থেকে enumerator বানাতে dovetailing লাগে।
- দুই দিকে অসীম tape এক দিকে কীভাবে? ঘর 0-এ ভাঁজ, দুই track, নিচের track-এ L/R উল্টো।
- কোন রূপভেদ শক্তি কমায়? Tape input-এর দৈর্ঘ্যে সীমিত (LBA), একটি stack (PDA), বা লিখতে না পারা (শুধু regular).
৯ · AI-এর যুগে TM-এর রূপভেদ
AI assistant এই বিষয়ে সাধারণত গোছানো উত্তর দেয়; ঝুঁকি খুঁটিনাটিতে: খরচের হিসাব, নকলের দিক, আর অসীম loop. পরিচিত ভুল আর ধরার উপায়:
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| “Multi-tape TM বেশি শক্তিশালী” বা “বেশি language চেনে” | শক্তি আর গতি আলাদা করুন: উপপাদ্য ৩.১ বলে language একই, শুধু সময় বদলায় |
| Simulation-এর খরচ O(t) বা exponential বলা, বা শর্ত t(n) ≥ n বাদ দেওয়া | Tape-এর দৈর্ঘ্য O(t) আর প্রতি ধাপে sweep O(t) হিসাব করুন; ছোট যন্ত্রে ধাপ গুনে অনুপাত দেখুন |
| Recognizer থেকে enumerator বানাতে string একে একে পুরো চালানো | একটি recognizer নিন, যা কিছু string-এ loop করে; সরল ক্রম সেখানে আটকায় কি না দেখুন |
| দুই দিকে অসীম tape-এর ভাঁজে নিচের track-এ L/R না উল্টানো, বা ঘর 0 পার হওয়া না সামলানো | ঘর 1 থেকে −2 পর্যন্ত গিয়ে ফেরার একটি trace হাতে করুন, অংশ ৬-এর stepper-এর মতো |
| LBA বা PDA-কেও “TM-এর আরেকটি সমতুল্য রূপভেদ” বলা | Memory সীমিত বা শুধু একটি stack হলে শক্তি কমে; aⁿbⁿcⁿ বা একটি recognizable-কিন্তু-undecidable language দিয়ে পার্থক্য দেখুন |
প্রমাণের সঙ্গে চালানো যায় এমন যাচাই আর নির্দিষ্ট সংখ্যা চান, যা নিজে মেলাবেন।
(নিজে যাচাই করুন: ধাপের সূত্র নকশাভেদে বদলায়, কিন্তু linear হতেই হবে; এখানে 3m + 4. AI-এর table two_tape.py-র D2-এর জায়গায় বসিয়ে ৩২৮০টি string-এ চালান।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Sipser এক দিকে অসীম tape নেন, Hopcroft–Motwani–Ullman দুই দিকে অসীম, আর Turing নিজে ১৯৩৬ সালে অন্য রীতি। এত আলাদা সংজ্ঞা থাকা কি সমস্যা? কোন সংজ্ঞা “সঠিক”?
Turing-এর ১৯৩৬ সালের প্রবন্ধ “On Computable Numbers”-এর যন্ত্র আজকের পাঠ্যবইয়ের যন্ত্রের মতো দেখতে নয়। তাঁর যন্ত্রের মূল কাজ ছিল একটি বাস্তব সংখ্যার দশমিক (আসলে binary) অঙ্কগুলো একটির পর একটি লেখা, থামা নয়; একটি “ভালো” যন্ত্র চিরকাল চলে আর অঙ্ক লিখতে থাকে। তিনি অঙ্ক লিখতেন একটি অন্তর একটি ঘরে, আর মাঝের ঘরগুলো রাখতেন দাগ ও খসড়ার জন্য। আধুনিক “accept/reject” রূপ, 7-tuple, আর “decider” শব্দ পরের দশকগুলোতে Post, Kleene, Davis আর পরে পাঠ্যবইয়ের লেখকদের হাতে গড়ে ওঠে।
এটি সমস্যা হতো, যদি সংজ্ঞাভেদে চেনা যায় এমন language-এর শ্রেণি বদলাত। এই পর্বের উপপাদ্যগুলো দেখায় তা বদলায় না: ভাঁজ করা tape, দাগানো চিহ্ন আর stay-put-এর দুই ধাপের কৌশল যেকোনো এক রূপকে অন্য রূপে নিয়ে যায়, থামা-না-থামা সমেত। তাই “decidable” বা “recognizable” শব্দের অর্থ বই বদলালেও বদলায় না; একটি বইয়ে প্রমাণিত undecidability অন্য বইয়ের মডেলেও সত্য।
তবে একটি সতর্কতা: সময় নিয়ে কথা বললে মডেল আবার গুরুত্বপূর্ণ হয়ে ওঠে। একই language-এ এক tape-এ n2 আর দুই tape-এ n লাগতে পারে। তাই complexity-র বইগুলো সাধারণত স্পষ্ট বলে দেয় কোন মডেলে সময় মাপা হচ্ছে (প্রায়ই multi-tape), আর শুধু সেই সিদ্ধান্তগুলোকে মডেল-নিরপেক্ষ ধরে, যেগুলো polynomial দামে টেকে, যেমন “এই সমস্যা P-তে আছে”।
মূল উপলব্ধি: কোনো একটি সংজ্ঞা “সঠিক” নয়; সঠিক হলো সেই ধারণা, যা সব যুক্তিসংগত সংজ্ঞায় একই থাকে। Computability এমন একটি ধারণা, আর সূক্ষ্ম সময়ের হিসাব তা নয়।
প্র ০২একই language-এ এক tape-এ n2 আর দুই tape-এ n. তাহলে algorithm-এর বইয়ে বলা “এই algorithm O(n)” কথাটির মানে কী, আর complexity তত্ত্ব কেন “polynomial” স্তরে কথা বলতে পছন্দ করে?
Algorithm-এর বইয়ের O(n) একটি নির্দিষ্ট মডেলের কথা: RAM, যেখানে যেকোনো memory ঘর এক ধাপে পড়া যায়। একই algorithm একটি single-tape TM-এ চালালে head-কে ডেটার এক মাথা থেকে আরেক মাথায় হাঁটতে হয়, আর খরচ এক বা দুই polynomial ঘাত বেড়ে যেতে পারে। এই পর্বের {w#w}-এর হিসাব সেটিই দেখায়: 2-tape-এ 3m + 4 ধাপ, 1-tape-এ 2(m + 1)2. আর Hennie ও Barzdin-এর crossing sequence যুক্তি (১৯৬০-এর দশকের মাঝামাঝি) দেখায়, palindrome-এর মতো language-এ এক tape-এর এই বর্গ কোনো চতুর নকশায় এড়ানো যায় না। অর্থাৎ “linear time” কথাটি মডেল ছাড়া অর্থহীন।
Juris Hartmanis আর Richard Stearns ১৯৬৫ সালে time complexity-র ভিত্তি গড়ার সময় multi-tape TM বেছে নেন, অংশত এই কারণেই যে এটি single-tape-এর চেয়ে বাস্তব কম্পিউটারের কাছাকাছি। প্রায় একই সময়ে, ১৯৬৫ সালে, Cobham আর Edmonds-এর কাজে ধারণা দানা বাঁধে যে “দক্ষ” মানে polynomial সময়, আর এই সংজ্ঞার একটি বড় সুবিধা ছিল দৃঢ়তা: single-tape, multi-tape, RAM (যুক্তিসংগত cost model-এ) সবাই একে অপরকে polynomial দামে নকল করে। তাই “P-তে আছে” কথাটি মডেল বদলালে বদলায় না, যদিও n আর n2-এর পার্থক্য বদলায়।
প্রোগ্রামারের জন্য দুই স্তরই দরকারি: কোড লেখায় RAM-এর O(n) বনাম O(n log n) গুরুত্বপূর্ণ, আর একটি সমস্যা আদৌ দক্ষভাবে সমাধানযোগ্য কি না, সেই বড় প্রশ্নে polynomial স্তরই নির্ভরযোগ্য ভাষা।
মূল উপলব্ধি: সময়ের প্রতিটি দাবি একটি মডেলের সাপেক্ষে। সূক্ষ্ম ঘাত মডেল-নির্ভর, polynomial-এর সীমা মডেল-নিরপেক্ষ; complexity তত্ত্ব তাই দ্বিতীয়টির ওপর দাঁড়ায়।
প্র ০৩“Recursively enumerable” নামটি কোথা থেকে এল, আর dovetailing-এর ভাবনা তত্ত্বের বাইরে কোথায় দেখা যায়?
১৯৩০-এর দশকে computability-র প্রথম ভাষা ছিল recursive function: Gödel, Herbrand আর Kleene-এর কাজ থেকে আসা function-এর একটি শ্রেণি। একটি সংখ্যার set-কে “recursively enumerable” বলা হতো, যদি কোনো recursive function তার সদস্যগুলোকে একটি তালিকায় (সম্ভবত পুনরাবৃত্তিসহ) গুনে যায়; অর্থাৎ “এমন একটি যান্ত্রিক পদ্ধতি আছে, যা set-টির সব সদস্য এক এক করে বলে যায়”. Emil Post-এর ১৯৪৪ সালের প্রভাবশালী প্রবন্ধ “Recursively enumerable sets of positive integers and their decision problems” এই set-গুলোকে কেন্দ্রে আনে। উপপাদ্য ৭.২ ঠিক এই পুরোনো নাম আর আধুনিক “Turing-recognizable” নামকে মেলায়: তালিকা করা যায় ⇔ চেনা যায়। এই কারণে বইভেদে RE, recognizable আর semi-decidable তিন নামই চলে।
Dovetailing-এর ভাবনা হলো: অনেকগুলো সম্ভাব্য-অসীম কাজ একটির পর একটি না করে পালা করে অল্প অল্প করা, যাতে কোনো একটি অসীম কাজ বাকিদের না খেয়ে ফেলে। Operating system-এর time-sharing scheduler একই দর্শনে চলে: প্রতিটি process একটি ছোট সময়-খণ্ড পায়, তাই একটি অসীম loop-এ পড়া program পুরো কম্পিউটার আটকায় না। গণিতে Cantor-এর জোড়া-গোনা (ℕ × ℕ-কে কর্ণ বরাবর গোনা) একই কৌশল: (string নম্বর, ধাপ সংখ্যা) জোড়াগুলো কর্ণ ধরে ঘোরা।
একটি বাস্তব শিক্ষাও আছে। Breadth-first search অসীম গাছে কাজ করে, depth-first search একটি অসীম শাখায় হারিয়ে যেতে পারে; পরের পর্বের (পর্ব ৪৬) nondeterministic TM-এর deterministic simulation ঠিক এই কারণে BFS ব্যবহার করে। অসীম সম্ভাবনার জগতে “ন্যায্য” (fair) ক্রমে খোঁজা সঠিকতার শর্ত, শুধু দক্ষতার নয়।
মূল উপলব্ধি: Recognizable মানে তালিকাযোগ্য; আর অসীম কাজের সংগ্রহ সামলানোর সাধারণ কৌশল হলো সবাইকে পালা করে ক্রমবর্ধমান সময় দেওয়া, যাতে কেউ চিরকাল অপেক্ষায় না থাকে।
প্র ০৪আসল কম্পিউটারের memory সসীম, তাহলে কি তা আসলে একটি finite automaton? RAM model আর Turing machine-এর মধ্যে কোনটি বাস্তবের বেশি কাছের?
কঠোর অর্থে, হ্যাঁ: কয়েক গিগাবাইট RAM আর একটি নির্দিষ্ট disk-এর একটি কম্পিউটারের সম্ভাব্য অবস্থা সসীম (যদিও কল্পনাতীত বড়, 2-এর ঘাত কয়েক হাজার কোটি), তাই নীতিগতভাবে এটি একটি বিশাল finite automaton. কিন্তু এই দৃষ্টিভঙ্গি প্রায় কোনো কাজে লাগে না। একটি DFA হিসেবে দেখলে “সুষম বন্ধনী চেনা” কম্পিউটারের অসাধ্য হতো, অথচ বাস্তবে আমরা জানি, বন্ধনী যতই গভীর হোক, আরেকটু memory দিলে একই program কাজ করে। তাত্ত্বিক মডেল তাই program-এর আচরণ ধরে, যন্ত্রের আকার নয়: “memory যতটা লাগে, ততটা দেওয়া যায়” ধরে নিলে কোন সমস্যা আদৌ সমাধানযোগ্য, সেটিই প্রশ্ন। এই অর্থে Turing machine আর RAM দুটিই “সীমাহীন memory”-র আদর্শ রূপ।
গতির প্রশ্নে RAM বাস্তবের বেশি কাছে: আধুনিক processor একটি ঠিকানা থেকে প্রায় স্থির সময়ে পড়ে, tape-এর মতো হেঁটে যায় না। তাই DSA কোর্সে RAM model ব্যবহার হয়। তবে RAM-এরও সীমা আছে। “প্রতিটি গাণিতিক কাজ এক ধাপ” নিয়মে যদি সংখ্যার আকার সীমাহীন হয়, তাহলে বারবার বর্গ করে একটি RAM কয়েক ধাপে বিশাল সংখ্যা বানাতে পারে, যার বিট-সংখ্যা ধাপের সংখ্যার exponential; এমন unit-cost RAM বাস্তবের চেয়ে বেশি শক্তিশালী আচরণ দেখাতে পারে, যা Hartmanis ও Simon-এর ১৯৭০-এর দশকের কাজে আলোচিত বলে পরিচিত। এজন্য তত্ত্বে word RAM (প্রতিটি word O(log n) বিট) বা logarithmic cost model ব্যবহার করা হয়, আর তখন Cook ও Reckhow-এর ১৯৭৩ সালের বিশ্লেষণের ধাঁচে TM আর RAM polynomial দামে একে অপরকে নকল করে।
মূল উপলব্ধি: মডেল বাছাই প্রশ্ন অনুযায়ী: কী সম্ভব, তার জন্য সীমাহীন-memory-র TM; কত দ্রুত, তার জন্য সাবধানে সংজ্ঞায়িত RAM. দুটি polynomial দামে মেলে বলেই একটির সিদ্ধান্ত অন্যটিতে ব্যবহার করা যায়।
প্র ০৫কোন “ছোট” পরিবর্তন Turing machine-এর শক্তি কমিয়ে দেয়? সর্বজনীনতার (universality) জন্য ন্যূনতম উপকরণ কী?
এই পর্বের টেবিলের নিচের সারিগুলো দেখায়, সব পরিবর্তন নিরীহ নয়। প্রথম, memory-র সীমা: tape input-এর দৈর্ঘ্যে আটকে দিলে linear bounded automaton, যা context-sensitive language চেনে; Kuroda ১৯৬৪ সালে এই সমতা দেখান বলে পরিচিত। এই শ্রেণির সব language decidable, তাই LBA মূল TM-এর চেয়ে কঠোরভাবে দুর্বল। দ্বিতীয়, memory-র ধরন: একটি stack দিলে PDA, যা aⁿbⁿcⁿ-ও চিনতে পারে না। তৃতীয়, লেখার অধিকার: head দুই দিকে চললেও লিখতে না পারলে যন্ত্রটি two-way finite automaton, আর Rabin–Scott ও Shepherdson ১৯৫৯ সালে দেখান, এরা শুধু regular language চেনে। দুই দিকে চলার স্বাধীনতা একা কিছুই যোগ করে না।
উল্টো দিকে, অবাক করার মতো সামান্য উপকরণে পূর্ণ শক্তি আসে। দুটি stack যথেষ্ট (পর্ব ৩২)। একটি queue যথেষ্ট। দুটি counter, যারা শুধু বাড়ে-কমে আর শূন্য কি না বলে, যথেষ্ট, যা Minsky-র ১৯৬০-এর দশকের ফল বলে পরিচিত (পর্ব ৪৯), যদিও তাতে input একটি বিশাল সংখ্যায় সংকেত করতে হয় আর গতি ভয়ংকর কমে। এমনকি এমন TM-ও সর্বজনীন হতে পারে, যা কোনো চিহ্ন মুছতে পারে না, শুধু ফাঁকা ঘরে লিখতে পারে; Hao Wang-এর ১৯৫০-এর দশকের কাজে এমন যন্ত্রের আলোচনা পাওয়া যায় বলে বর্ণিত।
সব মিলিয়ে সর্বজনীনতার ন্যূনতম শর্তকে মোটামুটি এভাবে বলা যায়: একটি সসীম নিয়ন্ত্রক, আর এমন একটি memory যা সীমাহীনভাবে বাড়তে পারে আর যাতে পুরোনো তথ্য আবার পড়া ও বদলানো (বা বদলানোর সমতুল্য কিছু) যায়। Memory সীমিত হলে, বা তথ্য একবার “চাপা পড়ে” আর ফেরত আসে না (একটি stack-এর নিচের অংশ), শক্তি কমে।
মূল উপলব্ধি: শক্তির উৎস tape-এর সংখ্যা বা দিক নয়, বরং সীমাহীন, পুনর্ব্যবহারযোগ্য memory. সেটি থাকলে প্রায় যেকোনো মডেল সর্বজনীন; সেটি কাটলে ক্ষমতা নিচের Chomsky স্তরে নেমে যায়।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। two_tape.py আর single_tape_sim.py ব্লকে যন্ত্র বা input বদলে উত্তর যাচাই করতে পারেন।
-
নকশা (2-tape): L = {anbncn : n ≥ 0}-এর জন্য একটি 2-tape Turing machine নকশা করুন, যা O(n) ধাপে থামে। Transition table দিন, আর anbncn (n ≥ 1) গ্রহণ করতে ঠিক কত ধাপ লাগে, তা বের করুন।
ভাবনা: tape ২-কে একটি counter হিসেবে ব্যবহার করা: প্রতিটি a-র জন্য একটি X লেখা, প্রতিটি b-তে একটি X বাঁয়ে পেরোনো, প্রতিটি c-তে একটি X ডানে পেরোনো। tape ২-এর শুরুতে $ বাঁ প্রান্তের দাগ।
state পড়া লেখা চাল পরে q0 (x, ␣) (x, $) S, R qa qa (a, ␣) (a, X) R, R qa qa (b, ␣) (b, ␣) S, L qb qa (␣, ␣) (␣, ␣) S, L qe qe (␣, $) (␣, $) S, S accept qb (b, X) (b, X) R, L qb qb (c, $) (c, $) S, R qc qc (c, X) (c, X) R, R qc qc (␣, ␣) (␣, ␣) S, S accept বাকি সব জোড়া reject, যেমন qb-তে (b, $) মানে b বেশি, (c, X) মানে b কম। qe ধরে ফাঁকা input: ␣-এ পৌঁছে tape ২-এর head $-এ ফেরে কেবল কোনো a না থাকলে। ধাপ: q0-তে ১, qa-তে n + 1 (শেষটি b দেখে ফেরা), qb-তে n + 1, qc-তে n + 1: মোট 3n + 4, অর্থাৎ O(n). Scratch-এ যন্ত্রটি অংশ ২-এর simulator-এ বসিয়ে দৈর্ঘ্য ৯ পর্যন্ত {a, b, c}-এর সব ২৯,৫২৪টি string-এ সংজ্ঞার সঙ্গে মেলানো হয়েছে (অমিল ০), আর n = 1, 2, 10, 100-এ ধাপ ৭, ১০, ৩৪, ৩০৪; ফাঁকা input ৩ ধাপে গৃহীত।
-
প্রমাণ: প্রমাণ করুন, একটি language L decidable, যদি এবং কেবল যদি কোনো enumerator L-কে shortlex ক্রমে ছাপে (প্রতিটি string একবার, ছোট থেকে বড়)।
(⇒)
- D একটি decider ধরুন। E = “s1, s2, s3, … (shortlex) ক্রমে প্রতিটি sj-এ D চালানো; accept হলে sj ছাপা।” — নির্মাণ
- D সব input-এ থামে, তাই E প্রতিটি sj পেরিয়ে পরেরটিতে যায়, কোথাও আটকায় না। — decider-এর সংজ্ঞা
- E ঠিক L-এর সদস্যগুলো ছাপে, আর sj বাড়ার ক্রমে, তাই shortlex ক্রমে, প্রতিটি একবার। — নির্মাণ
(⇐)
- L সসীম হলে L decidable, কারণ একটি যন্ত্র সসীম তালিকাটি নিজের state-এ রেখে w-কে মিলিয়ে দেখতে পারে। — সসীম language
- L অসীম আর E তাকে shortlex ক্রমে ছাপে ধরুন। D = “input w-এ: E চালানো; E w ছাপলে accept; E shortlex-এ w-এর পরের কোনো string ছাপলে reject.” — নির্মাণ
- L অসীম, তাই E একসময় w-এর চেয়ে বড় একটি string ছাপে (w-এর আগে বা সমান string সসীম সংখ্যক)। তাই D সব input-এ থামে। — shortlex-এ প্রতিটি string-এর আগে সসীম সংখ্যক
- w ∈ L হলে E w-কে তার পরের সবার আগে ছাপে, তাই D accept করে; w ∉ L হলে E কখনো w ছাপে না, আর বড় string ছাপলে D reject করে। অতএব D L-এর decider. ∎ — ক্রমের শর্ত
ধাপ ১-এর ক্ষেত্রভাগ জরুরি: সসীম L-এ ধাপ ২-এর D একটি বড় w-তে কখনো না-ও থামতে পারত।
-
Output অনুমান (trace): (ক) single_tape_sim.py-তে
single(D2, "0#0", 2, show=7)-এর বদলেsingle(D2, "1#1", 2, show=7)দিলে চতুর্থ লাইনে (state back) কী ছাপা হবে? (খ) |w| = 10 হলে w#w-এ 2-tape আর 1-tape যন্ত্র কত ধাপ নেবে? (গ) “10#01” input-এ কোন যন্ত্র আগে reject করে, আর কত ধাপে?(ক)
back ‖1#[1]‖$[1]␣‖. যন্ত্রটি 0 আর 1-এ একইভাবে আচরণ করে, তাই “0#0”-এর চতুর্থ লাইনে 0-এর জায়গায় 1 বসে।(খ) 2-tape: 3 · 10 + 4 = 34; 1-tape: 2(10 + 1)2 = 242. ধাপ শুধু দৈর্ঘ্যের ওপর নির্ভর করে; scratch-এ দুটি ভিন্ন w-তে ৩৪ আর ২৪২ এসেছে।
(গ) 1-tape যন্ত্র ৪ ধাপে reject করে: প্রথম 1 কেটে ডানে যায়, 0 পেরিয়ে # পায়, তারপর # পেরিয়ে 0 পায়, যেখানে 1 প্রত্যাশিত; নিয়ম নেই। 2-tape যন্ত্র নেয় ৮ ধাপ, কারণ প্রথমে পুরো w কপি করে ফিরে আসে, তারপর প্রথম তুলনাতেই অমিল পায়। শিক্ষা: “2-tape দ্রুত” কথাটি সবচেয়ে খারাপ ক্ষেত্রের (worst case) দাবি, প্রতিটি input-এর নয়।
-
প্রমাণে ভুল খুঁজুন: একজন লিখলেন: “একটি 3-tape যন্ত্রকে আগে একটি 2-tape যন্ত্রে নকল করি (খরচ বর্গ হয়), তারপর সেটিকে 1-tape-এ (আবার বর্গ)। তাই 3-tape যন্ত্রের t ধাপের জন্য 1-tape-এ O(t4) লাগে, আর সাধারণভাবে k-tape-এর জন্য O(t2k−1). অতএব k-tape যন্ত্র single-tape যন্ত্রের চেয়ে t2k−1 মাপে দ্রুত হতে পারে।” কোথায় কোথায় ভুল?
- প্রথম ত্রুটি (দুর্বল সীমা): বারবার নকল করার যুক্তিটি ভুল নয়, শুধু অপ্রয়োজনীয়ভাবে দুর্বল। নির্মাণ ৩.২ যেকোনো স্থির k-এর জন্য একবারেই k-টি অংশ পাশাপাশি রাখে, আর উপপাদ্য ৪.১-এর প্রমাণে k শুধু ধ্রুবক গুণকে আসে: সরাসরি O(t2). — উপপাদ্য ৪.১
- দ্বিতীয় ত্রুটি (যুক্তির দিক): একটি নির্মাণ খরচের একটি ওপরের সীমা দেয়: “এত ধাপে নকল করা যায়”. তা থেকে “এর চেয়ে কমে করা যায় না” সিদ্ধান্ত আসে না। Multi-tape যন্ত্র কতটা দ্রুত হতে পারে, তা বলতে একটি নিচের সীমার প্রমাণ লাগে, যেমন crossing sequence যুক্তি। — ওপরের সীমা বনাম নিচের সীমা
- সঠিক বক্তব্য: k-tape-এর t ধাপ single-tape-এ O(t2) ধাপে নকল হয় (t ≥ n), আর palindrome-এর মতো language দেখায় যে কিছু ক্ষেত্রে বর্গের পার্থক্য সত্যিই থাকে। তাই সর্বোচ্চ পার্থক্য বর্গ মাপের, t2k−1 নয়। ∎
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমSingle-tape যন্ত্র S একটি k-tape যন্ত্র M-এর একটি ধাপ নকল করছে। কাজগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Tape-এর বাঁ প্রান্তের ‖ থেকে শুরু করা
- ডানে sweep করে k-টি দাগানো চিহ্ন finite control-এ মনে রাখা
- M-এর state আর এই k-টি চিহ্ন দিয়ে δ থেকে লেখা ও চাল বের করা
- দ্বিতীয় sweep-এ প্রতিটি দাগানো ঘরে নতুন চিহ্ন লেখা আর দাগ সরানো
- কোনো দাগ ‖-এর ওপর পড়লে বাকি tape এক ঘর ডানে সরিয়ে ␣ বসানো
- M থেমে থাকলে একই সিদ্ধান্তে থামা, নইলে বাঁ প্রান্তে ফিরে পরের ধাপ
t(n) ≥ n ধরে, একটি t(n)-সময়ের 3-tape Turing machine-কে একটি single-tape যন্ত্রে নকল করলে সবচেয়ে ভালো সাধারণ সীমা কোনটি?
- O(t(n))
- O(t(n)4)
- O(t(n)2)
- 2O(t(n))
নিচের কোন যন্ত্র Turing machine-এর চেয়ে কঠোরভাবে দুর্বল, অর্থাৎ কিছু Turing-recognizable language চিনতে পারে না?
- দুটি stack-সহ একটি finite-state যন্ত্র
- একটি Turing machine, যার head দুই দিকে চলে কিন্তু কিছু লিখতে পারে না
- দুই দিকে অসীম tape-এর Turing machine
- তিন track-এর tape-সহ Turing machine
একটি language L-এর জন্য একটি recognizer M দেওয়া আছে, যা L-এর বাইরের কিছু string-এ চিরকাল চলে। M থেকে L-এর একটি enumerator বানাতে কোন পদ্ধতি সঠিক?
- Shortlex ক্রমে প্রতিটি string-এ M শেষ পর্যন্ত চালানো, accept হলে ছাপা
- আগে M-কে একটি decider-এ বদলে নেওয়া, তারপর ক্রমে চালানো
- প্রতিটি string-এ M-কে ১০০০ ধাপ পর্যন্ত চালানো, তার মধ্যে accept হলে ছাপা
- পর্যায় i = 1, 2, 3, …-এ প্রথম i-টি string-এর প্রতিটিতে M-কে i ধাপ চালানো, accept হলে ছাপা
দুই দিকে অসীম tape-কে এভাবে ভাঁজ করা হলো: অবস্থান p ≥ 1-এ ওপরের track-এ ঘর p − 1, নিচের track-এ ঘর −p, আর p = 0-তে একটি দাগ ▸. মূল যন্ত্রের ঘর −3 কোথায় থাকে?
- অবস্থান 3, নিচের track
- অবস্থান 3, ওপরের track
- অবস্থান 4, নিচের track
- অবস্থান 2, নিচের track
একটি enumerator E একটি language L-এর প্রতিটি string ঠিক একবার, shortlex ক্রমে (দৈর্ঘ্য, তারপর অভিধান) ছাপে। L সম্পর্কে সবচেয়ে শক্ত সঠিক সিদ্ধান্ত কোনটি?
- L Turing-recognizable, কিন্তু decidable না-ও হতে পারে
- L regular
- L decidable
- L context-free
L = {w#w : w ∈ {0, 1}∗}. একটি 2-tape যন্ত্র |w| = m হলে 3m + 4 ধাপে, আর একটি 1-tape যন্ত্র 2(m + 1)2 ধাপে গ্রহণ করে। কোন সিদ্ধান্তটি সঠিক?
- 2-tape যন্ত্র 1-tape যন্ত্রের চেয়ে বেশি language চিনতে পারে
- এই দুটি সংখ্যা থেকেই প্রমাণ হয় যে কোনো 1-tape যন্ত্র L-কে O(n)-এ চিনতে পারে না
- সব m-এর জন্য 1-tape যন্ত্র অন্তত দশ গুণ ধীর
- দুটি একই language চেনে; এই দুই যন্ত্রের খরচ যথাক্রমে Θ(n) আর Θ(n2)
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Multi-tape, multi-track, stay-put, দুই দিকে অসীম tape আর ছোট alphabet: সব রূপভেদ ঠিক Turing-recognizable language চেনে, আর simulation থামা-না-থামা রক্ষা করে বলে decidable language-ও একই।
- k-tape থেকে 1-tape: সব tape ‖ দিয়ে পাশাপাশি, head-এর ঘর দাগানো, প্রতি ধাপে দুটি sweep আর দরকারে shift. খরচ O(t(n)2) (t(n) ≥ n), আর palindrome-এর মতো language-এ এই বর্গ এড়ানো যায় না।
- Stay-put: R তারপর L, বড়জোর 2t. দুই দিকে অসীম tape: ঘর 0-এ ভাঁজ, দুই track, নিচের track-এ L/R উল্টো, 2t + O(n). Multi-track: শুধু বড় alphabet.
- Enumerator: L recognizable ⇔ কোনো enumerator L ছাপে। Recognizer থেকে enumerator বানাতে dovetailing; shortlex ক্রমে ছাপা যায় ⇔ L decidable.
- শক্তির উৎস সীমাহীন, লেখা-মোছা যায় এমন memory. RAM আর দুই stack সমান; LBA, এক stack আর লিখতে-না-পারা যন্ত্র দুর্বল।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৩২ · Pushdown automaton — stack-সহ automatonফিরে দেখুনএক stack-এর সীমা আর দুই stack কেন Turing machine-এর সমান।
- পর্ব ০৬ · Chomsky hierarchy-র মানচিত্র — চার শ্রেণির language আর machineফিরে দেখুনLBA, Type 0 আর কোন যন্ত্র কোন স্তরে।
- পর্ব ০২ · প্রয়োজনীয় গণিত — set, relation, function, graph আর countabilityভিত্তিShortlex ক্রম আর Σ∗-এর গণনা, enumerator-এর পেছনের গণিত।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৪৬ nondeterministic Turing machine.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৫ — Turing machine-এর পরিচয়পাশের ট্র্যাকTuring machine, computability আর halting problem-এর একটি সংক্ষিপ্ত পরিচয়।
- DSA · পর্ব ০৪ — বৃদ্ধির হার আর Big-O, Ω, Θপাশের ট্র্যাকRAM model-এ সময় মাপার ভাষা, এই পর্বের O(t2)-এর পটভূমি।