সরাসরি পর্বে যান
পর্ব ৫৪ · ৮৫-এর মধ্যে · মডিউল ৯

Post correspondence problem আর grammar-এর undecidable প্রশ্ন

The Post Correspondence Problem — Dominoes, Modified PCP, Computation Histories, and Why Ambiguity, Intersection, Universality and Equivalence of Context-Free Grammars Are Undecidable

Taught in Bangla, this lesson presents the Post correspondence problem as a domino puzzle and shows it is recognizable by search. It proves undecidability through A_TM ≤m MPCP ≤m PCP by encoding a Turing machine's computation history as dominoes, then reduces PCP to show that ambiguity, empty intersection, universality and equivalence of context-free grammars are undecidable. It marks the boundary: bounded PCP, two-domino and unary cases are decidable, and in-page Python (Pyodide) searches instances.

এই পর্বে যা শিখবেন

  • PCP-র formal সংজ্ঞা, ডমিনো-চিহ্ন, সমাধান আছে আর নেই এমন instance, আর হাতে-কলমে না-থাকা প্রমাণের দুটি কৌশল
  • BFS দিয়ে সমাধান খোঁজা, step cap ছোঁয়ার মানে, আর কেন PCP recognizable কিন্তু তার complement নয়
  • Modified PCP, ⋆ কৌশলে MPCP ≤m PCP, আর computation history থেকে ডমিনো বানিয়ে ATM ≤m MPCP
  • PCP থেকে CFG-এর ambiguity, ছেদের শূন্যতা, universality আর equivalence-এর undecidability, প্রতিটি reduction-এর সঠিক দিকসহ
  • কোন সীমাবদ্ধ রূপে PCP decidable, কোথায় প্রশ্ন খোলা, আর বাস্তবের grammar tool কীভাবে এই সীমার সঙ্গে চলে

১ · ডমিনোর ধাঁধা — PCP কী

এ পর্যন্ত undecidable সমস্যাগুলো ছিল যন্ত্র নিয়ে: “M কি w গ্রহণ করে?”, “M কি থামে?”। কিন্তু grammar নিয়ে প্রশ্ন, যেমন পর্ব ২৭-এর “এই CFG কি ambiguous?” বা পর্ব ৩৭-এর “দুটি CFL-এর ছেদ কি ফাঁকা?”, সরাসরি যন্ত্রের মতো দেখায় না। এই দূরত্ব পার হওয়ার সেতু একটি নিরীহ চেহারার ধাঁধা, যা Emil Post ১৯৪৬ সালে প্রকাশ করেন। ধাঁধাটি শুধু string জোড়া নিয়ে, কোনো যন্ত্র ছাড়াই; ঠিক এ কারণেই grammar-এর প্রশ্নে রূপান্তর সহজ।

বাজারঘরের গুদামে দুজন কেরানি দুটি খাতায় লেখেন। প্রতিটি পার্সেলের একটি কার্ড আছে; কার্ডের ওপরের অংশ প্রথম কেরানি তাঁর খাতায় হুবহু টুকে নেন, নিচের অংশ দ্বিতীয় কেরানি তাঁর খাতায়। একই কার্ড বারবার আসতে পারে। দিনের শেষে হিসাব-পরীক্ষক জানতে চান: কার্ডগুলোর এমন কোনো ক্রম কি আছে, যাতে দুই খাতার পুরো লেখা অক্ষরে অক্ষরে এক হয়? কার্ড মাত্র চার রকম, তবু উত্তর খোঁজার কোনো সাধারণ নিয়ম নেই, যা সব কার্ড-সেটে কাজ করে।

সংজ্ঞা ১.১ (Post correspondence problem)

Alphabet Σ-এর ওপর একটি instance হলো k ≥ 1টি ডমিনোর তালিকা P = {[t1/b1], [t2/b2], …, [tk/bk]}, যেখানে প্রতিটি ti, bi ∈ Σ+ (ওপরের আর নিচের string).
একটি match বা সমাধান হলো সূচকের একটি অ-ফাঁকা ক্রম i1, i2, …, im (m ≥ 1, প্রতিটি 1 থেকে k-এর মধ্যে, পুনরাবৃত্তি চলবে), যাতে

ti1 ti2 ⋯ tim = bi1 bi2 ⋯ bim.

Language হিসেবে: PCP = {⟨P⟩ : P-র একটি match আছে}.

চিহ্নগুলো এক এক করে পড়ুন। [t/b] লেখা মানে একটি ডমিনো, যার ওপরে t আর নিচে b; ভগ্নাংশের মতো দেখালেও কোনো ভাগ নেই। ⟨P⟩ হলো instance-টির string-রূপ (পর্ব ০৫-এর encoding). Instance সসীম, কিন্তু match-এর দৈর্ঘ্য m-এর কোনো সীমা নেই, আর সেখানেই সব জটিলতা। কয়েকটি বইয়ে খালি string-ও ডমিনোতে রাখা যায়; এই কোর্সে ti, bi অ-ফাঁকা, যা ফলাফল বদলায় না।

Sipser-এর বইয়ের পরিচিত উদাহরণটি নিন। চারটি ডমিনো: [b/ca], [a/ab], [ca/a], [abc/c]. ক্রম 2, 1, 3, 2, 4 নিলে ওপরে a·b·ca·a·abc = abcaaabc, নিচে ab·ca·a·ab·c = abcaaabc: হুবহু এক। নিচের ছবিতে দেখুন, ওপর আর নিচের ডমিনোর সীমানা আলাদা জায়গায় পড়ে, কিন্তু অক্ষরগুলো ঘরে ঘরে মেলে।

চারটি ডমিনো আর তাদের একটি match

রং দিয়ে বোঝানো হয়েছে কোন অক্ষর কোন ডমিনো থেকে এসেছে।

Four PCP dominoes and the match 2, 1, 3, 2, 4 চারটি ডমিনো bca aab caa abcc ১২৩৪ match: ২, ১, ৩, ২, ৪ ওপর নিচ abcaaabc abcaaabc দুই সারিতেই একই string: abcaaabc
ছবি ৫৪.১ — Match মানে ডমিনোগুলো এক সারিতে বসানো, যাতে ওপরের সব অক্ষর আর নিচের সব অক্ষর ঘরে ঘরে মেলে; ডমিনোর সীমানা মেলার দরকার নেই।

সমাধান কীভাবে খোঁজা হয়, তা ধাপে ধাপে দেখা যাক। প্রতি ধাপে একটি ডমিনো যোগ হয়, আর দুই লাইনের মধ্যে যেটি এগিয়ে আছে, তার বাড়তি অংশ (ইংরেজিতে overhang বলা হয়) মনে রাখতে হয়। পিছিয়ে থাকা লাইনকে সেই বাড়তি অংশ দিয়েই শুরু করে মেলাতে হবে।

1ডমিনো ১: [b / ca]2ডমিনো ২: [a / ab]3ডমিনো ৩: [ca / a]4ডমিনো ৪: [abc / c]
এ পর্যন্ত
ক্রম
ওপর
নিচ
বাড়তি অংশ
  1. প্রথম ডমিনো। শুরু হতে পারে এমন ডমিনো, যার ওপর আর নিচের একটি অন্যটির শুরু (prefix). [b/ca]-তে b আর c প্রথম অক্ষরেই আলাদা, [abc/c]-ও তাই, [ca/a]-তেও c ≠ a. থাকে শুধু [a/ab]: নিচের লাইন b দিয়ে এগিয়ে।
  2. b মেলানো। ওপরের লাইনকে এখন b দিয়ে শুরু করতে হবে; ওপরে b আছে শুধু ডমিনো ১-এর। বসালে ওপরে ab, নিচে abca: নিচের লাইন এখন ca দিয়ে এগিয়ে।
  3. c মেলানো। ওপরের লাইনকে c দিয়ে শুরু হতে হবে: ডমিনো ৩ [ca/a]. ওপরে abca, নিচে abcaa. নিচে একটি বাড়তি a.
  4. a মেলানো। ওপরের লেখা a দিয়ে শুরু হয় ডমিনো ২ আর ৪-এ। ডমিনো ৪ বসালে ওপরে abc আসে, আর নিচে বাড়তি a-এর পরে c: দ্বিতীয় অক্ষরে b ≠ c, তাই বাদ। ডমিনো ২ বসালে ওপরে abcaa, নিচে abcaaab: বাড়তি ab.
  5. শেষ ডমিনো। ওপরের লাইনকে ab দিয়ে শুরু হতে হবে আর নিচের লাইনকে ধরে ফেলতে হবে। ডমিনো ৪ [abc/c]: ওপরে abc-এর ab বাড়তি অংশ মেলায়, আর তার c নিচের নতুন c-এর সঙ্গে মেলে। দুই লাইন এখন abcaaabc: match.
  6. সারকথা। প্রতিটি ধাপে বাড়তি অংশ ঠিক করে দেয় কোন ডমিনো বসতে পারে। এখানে বাড়তি অংশ ছোট ছিল বলে খোঁজা সহজ হলো; কিন্তু বাড়তি অংশ ক্রমাগত বড় হতে পারে, আর তখন খোঁজার কোনো শেষ থাকে না। এটাই পরের অংশের মূল কথা।

একই কাজ এবার আপনার ব্রাউজারে। নিচের JavaScript ব্লক একটি ক্রম পেলে ডমিনো একে একে বসায় আর প্রতি ধাপে ওপর, নিচ আর বাড়তি অংশ ছাপে; কোথাও অক্ষর না মিললে সেখানেই থামে। lay([...]) লাইন বদলে নিজের ক্রম চেষ্টা করুন।

// Domino matcher: lay dominoes one by one and watch the two lines.
const D = { 1: ["b", "ca"], 2: ["a", "ab"], 3: ["ca", "a"], 4: ["abc", "c"] };
function lay(seq) {
  let top = "", bot = "";
  console.log("sequence " + seq.join(","));
  for (const i of seq) {
    top += D[i][0]; bot += D[i][1];
    const n = Math.min(top.length, bot.length);
    let k = 0;
    while (k < n && top[k] === bot[k]) k++;          // first disagreement
    let state;
    if (k < n) state = `MISMATCH at position ${k + 1}`;
    else if (top.length === bot.length) state = "MATCH";
    else state = (top.length > bot.length ? "top" : "bottom") +
                 ` ahead by "${(top.length > bot.length ? top : bot).slice(n)}"`;
    console.log(`  +${i}  top ${top.padEnd(9)} bottom ${bot.padEnd(9)} ${state}`);
    if (state.startsWith("MISMATCH")) return;
  }
}
lay([2, 1, 3, 2, 4]);   // Sipser's solution
lay([2, 1, 3, 4]);      // a wrong guess
lay([1]);               // b on top, c on the bottom: dead at once

আসল আউটপুট (ব্রাউজারের JavaScript):

sequence 2,1,3,2,4
  +2  top a         bottom ab        bottom ahead by "b"
  +1  top ab        bottom abca      bottom ahead by "ca"
  +3  top abca      bottom abcaa     bottom ahead by "a"
  +2  top abcaa     bottom abcaaab   bottom ahead by "ab"
  +4  top abcaaabc  bottom abcaaabc  MATCH
sequence 2,1,3,4
  +2  top a         bottom ab        bottom ahead by "b"
  +1  top ab        bottom abca      bottom ahead by "ca"
  +3  top abca      bottom abcaa     bottom ahead by "a"
  +4  top abcaabc   bottom abcaac    MISMATCH at position 6
sequence 1
  +1  top b         bottom ca        MISMATCH at position 1

প্রথম ক্রম stepper-এর পাঁচ ধাপের সঙ্গে হুবহু মেলে, শেষে MATCH. দ্বিতীয় ক্রমে চতুর্থ ধাপে ডমিনো ২-এর জায়গায় ৪ বসানো হয়েছে: ষষ্ঠ ঘরে ওপরে b, নিচে c, তাই সেখানেই মৃত্যু। তৃতীয়টি দেখায়, ডমিনো ১ দিয়ে শুরুই করা যায় না। লক্ষ করুন, এই ব্লক একটি দেওয়া ক্রম যাচাই করে, যা সবসময় সহজ; কঠিন কাজ হলো কোনো ক্রম আদৌ আছে কি না খুঁজে বের করা।

২ · সমাধান খোঁজা — recognizable, কিন্তু decidable?

কিছু instance-এর সমাধান নেই, আর তা যুক্তি দিয়ে সহজেই দেখানো যায়। দুটি সাধারণ কৌশল:

  1. দৈর্ঘ্যের যুক্তি: Plong = {[abc/ab], [ca/a], [acc/ba]}. প্রতিটি ডমিনোর ওপরের লেখা নিচের চেয়ে ঠিক এক অক্ষর লম্বা, তাই m টি ডমিনোর পরে ওপরের দৈর্ঘ্য নিচের চেয়ে m বেশি, কখনো সমান নয়। সমাধান নেই। (Sipser-এর বইয়েও এই instance আছে।)
  2. শুরুর যুক্তি: কোনো ডমিনোর ওপর আর নিচের একটি অন্যটির prefix না হলে প্রথম ডমিনোই বসানো যায় না, তাই সমাধান নেই। একইভাবে শেষের অক্ষর দেখে “কোনো ডমিনো দিয়ে শেষ করা যায় না” যুক্তিও খাটে।

কিন্তু এমন সহজ যুক্তি সবসময় পাওয়া যায় না। সাধারণ পদ্ধতি হলো খোঁজা। মূল পর্যবেক্ষণ: অংশ ১-এর stepper-এ প্রতি ধাপে দরকার ছিল শুধু দুটি তথ্য, কোন লাইন এগিয়ে, আর বাড়তি অংশটি কী। এই জোড়াকে একটি অবস্থা ধরলে খোঁজা হয় অবস্থার graph-এ BFS: শুরুতে প্রতিটি বসানো-যায় এমন ডমিনো, প্রতিটি অবস্থা থেকে প্রতিটি ডমিনো চেষ্টা, আর বাড়তি অংশ ফাঁকা হলেই match. BFS স্তরে স্তরে চলে বলে প্রথম যে match পায়, সেটিই সবচেয়ে কম ডমিনোর।

উপপাদ্য ২.১

PCP Turing-recognizable.

প্রমাণ:

  1. যন্ত্র R = “input ⟨P⟩-এর ওপর: m = 1, 2, 3, …-এর জন্য দৈর্ঘ্য m-এর সব সূচক-ক্রম (মোট kmটি) একে একে পরীক্ষা করুন; কোনোটিতে ওপর আর নিচ এক হলে গ্রহণ করুন।” — নির্মাণ
  2. প্রতিটি m-এর কাজ সসীম: kmটি ক্রম, প্রতিটির string জোড়া আর তুলনা সসীম। — প্রতিটি পর্যায় থামে
  3. ⟨P⟩ ∈ PCP হলে কোনো দৈর্ঘ্য m0-এর একটি match আছে; পর্যায় m0-এ R সেটি পায় আর গ্রহণ করে। — সম্পূর্ণতা
  4. R গ্রহণ করলে সে একটি সত্যিকারের match দেখেছে, তাই ⟨P⟩ ∈ PCP. ⟨P⟩ ∉ PCP হলে R কখনো গ্রহণ করে না (চিরকাল চলতে পারে), যা recognizer-এর জন্য অনুমোদিত। ∎ — সঠিকতা

লক্ষ করুন, R-এর “না” কখনো আসে না। R যদি কোনো সীমায় থেমে “সমাধান নেই” বলত, তবে সেই সীমার চেয়ে লম্বা সমাধানওয়ালা instance-এ ভুল করত। আর অংশ ৪-এ প্রমাণ হবে, PCP decidable নয়। তখন পর্ব ৫০-এর উপপাদ্য (L decidable ⇔ L আর L̄ দুটিই recognizable) থেকে সরাসরি আসে: PCP-র complement, অর্থাৎ “এই instance-এর কোনো সমাধান নেই”, recognizable-ও নয়। সমাধান না থাকার কোনো সাধারণ, যন্ত্রে যাচাইযোগ্য সসীম সাক্ষ্য হয় না।

এবার Python-এ BFS খোঁজা, একটি step cap-সহ: সর্বোচ্চ ১ লাখ অবস্থা দেখা হবে। তিন রকম ফল হতে পারে: SOLVED (match পাওয়া গেছে, আর কোড নিজেই আবার মিলিয়ে দেখে), NO SOLUTION (সব শাখা মরে গেছে, অর্থাৎ পৌঁছানো যায় এমন অবস্থা সসীম আর সবই দেখা শেষ, তাই এটি একটি প্রমাণ), আর CAP (সীমা ছুঁয়েছে, কোনো রায় নেই)। পাঁচটি instance: Sipser-এর, Hopcroft–Motwani–Ullman বইয়ের একটি পরিচিত উদাহরণ, Plong, আর দুটি ছোট কিন্তু কঠিন instance.

from collections import deque
def solve(doms, cap=100000):        # BFS over the "overhang"; returns (verdict, sequence)
    def step(side, rest, t, b):     # side "T": top is ahead by rest; "B": bottom is ahead
        top, bot = (rest + t, b) if side == "T" else (t, rest + b)
        if top.startswith(bot): return ("T", top[len(bot):])
        return ("B", bot[len(top):]) if bot.startswith(top) else None  # None: dead end
    seen, queue = {}, deque()
    for i, (t, b) in enumerate(doms, 1):
        s = step("T", "", t, b)
        if s and s not in seen: seen[s] = (None, i); queue.append(s)
    while queue:
        s = queue.popleft()
        if s[1] == "":                       # overhang empty: top == bottom
            seq = []
            while s: s, i = seen[s]; seq.append(i)
            return "SOLVED", seq[::-1]
        for i, (t, b) in enumerate(doms, 1):
            n = step(*s, t, b)
            if n and n not in seen:
                if len(seen) >= cap: return "CAP", None   # no verdict
                seen[n] = (s, i); queue.append(n)
    return "NO SOLUTION", None               # every branch died: proven unsolvable
P = {"sipser": [("b", "ca"), ("a", "ab"), ("ca", "a"), ("abc", "c")],
     "hmu":    [("1", "111"), ("10111", "10"), ("10", "0")],
     "longer": [("abc", "ab"), ("ca", "a"), ("acc", "ba")],
     "long4":  [("1000", "0"), ("01", "0"), ("1", "101"), ("00", "001")],
     "x3":     [("100", "1"), ("0", "100"), ("1", "0")]}
for name, doms in P.items():
    verdict, seq = solve(doms)
    if seq:
        top = "".join(doms[i - 1][0] for i in seq)
        ok = top == "".join(doms[i - 1][1] for i in seq)      # re-check the match
        show = seq if len(seq) <= 8 else f"{len(seq)} dominoes, |top| = {len(top)}"
        print(f"{name:6} {verdict}: {show}  check={ok}")
    else: print(f"{name:6} {verdict}")

আসল আউটপুট (ব্রাউজারের Python):

sipser SOLVED: [2, 1, 3, 2, 4]  check=True
hmu    SOLVED: [2, 1, 1, 3]  check=True
longer NO SOLUTION
long4  SOLVED: 206 dominoes, |top| = 412  check=True
x3     CAP

প্রথম দুটি ছোট সমাধান: Sipser-এর instance-এ অংশ ১-এর 2, 1, 3, 2, 4, আর HMU-র instance-এ 2, 1, 1, 3 (ওপরে আর নিচে 101111110; অনুশীলন ৩-এ হাতে করবেন)। Plong-এ BFS-এর সব শাখা মরে যায়: দৈর্ঘ্যের যুক্তির সঙ্গে মিলে NO SOLUTION, আর এখানে এটি একটি প্রমাণ, কারণ খোঁজা সম্পূর্ণ শেষ হয়েছে। চতুর্থটি চমক: চারটি ছোট ডমিনো, অথচ সবচেয়ে ছোট সমাধানে ২০৬টি ডমিনো আর ওপরের string ৪১২ অক্ষরের। হাতে কেউ এটি খুঁজে পেতেন না; BFS পায় প্রায় ৮০ হাজার অবস্থা দেখে। শেষেরটি মাত্র তিনটি ডমিনো, কিন্তু ১ লাখ অবস্থা দেখেও রায় নেই। Scratch-এ ৩০ লাখ অবস্থা পর্যন্ত খুঁজেও আমরা কোনো match পাইনি, কিন্তু তা “সমাধান নেই”-এর প্রমাণ নয়: CAP মানে শুধু “এখনো জানি না”।

সাধারণ ভুল: “অবস্থা তো বাড়তি অংশ, আর ডমিনো সসীম, তাই অবস্থাও সসীম; BFS সবসময় থামবে।” না। বাড়তি অংশের দৈর্ঘ্যের কোনো সীমা নেই: যে ডমিনোতে ওপর নিচের চেয়ে লম্বা, তা বারবার বসালে বাড়তি অংশ বাড়তেই থাকে। Plong-এ সব শাখা নিজে থেকে মরে গিয়েছিল বলে খোঁজা শেষ হয়েছিল; সাধারণভাবে তা হয় না। আর অংশ ৪-এর উপপাদ্য বলে, এই ফাঁক কোনো চতুর algorithm দিয়েও বন্ধ করা সম্ভব নয়।

৩ · Modified PCP আর ⋆ কৌশল

PCP undecidable প্রমাণের পরিকল্পনা: একটি Turing machine M আর input w থেকে এমন ডমিনো বানানো, যাদের match ঠিক M-এর w-এর ওপর গ্রহণকারী computation-এর লেখা। একটি অসুবিধা: সাধারণ PCP-তে যেকোনো ডমিনো দিয়ে শুরু করা যায়, অথচ আমাদের দরকার match শুরু হোক M-এর শুরুর configuration দিয়ে। তাই প্রথমে একটি মধ্যবর্তী সমস্যা।

সংজ্ঞা ৩.১ (Modified PCP)

MPCP = {⟨P⟩ : P-র এমন একটি match আছে, যা প্রথম ডমিনো [t1/b1] দিয়ে শুরু হয়}. অর্থাৎ i1 = 1 বাধ্যতামূলক; বাকি সব নিয়ম PCP-র মতো।

এরপর দেখাতে হবে MPCP ≤m PCP, অর্থাৎ একটি computable function f আছে যাতে ⟨P⟩ ∈ MPCP ⇔ f(⟨P⟩) ∈ PCP. পর্ব ৫২-এর দিকের নিয়মটি এখানে মনে রাখুন: A ≤m B আর B decidable হলে A decidable; A undecidable হলে B undecidable. তাই MPCP undecidable জানলে এই reduction PCP-কে undecidable করে, উল্টো নয়।

কৌশলটি হলো একটি নতুন চিহ্ন ⋆, যা প্রতিটি অক্ষরের আগে বা পরে বসে। u = u1u2⋯un হলে লিখি:

⋆u = ⋆u1⋆u2⋯⋆un, u⋆ = u1⋆u2⋆⋯un⋆, ⋆u⋆ = ⋆u1⋆u2⋆⋯⋆un⋆

f(⟨P⟩) হলো এই ডমিনোগুলো: শুরুতে [⋆t1 / ⋆b1⋆], তারপর প্রতিটি i = 1, …, k-এর জন্য [⋆ti / bi⋆], আর শেষে [⋆◇ / ◇], যেখানে ◇ আরেকটি নতুন চিহ্ন।

লেমা ৩.২

MPCP ≤m PCP.

প্রমাণের রূপরেখা:

  1. f computable: প্রতিটি string-এ ⋆ বসানো আর তিন রকম ডমিনো লেখা একটি সরল, সবসময় থামা algorithm. — f-এর গণনাযোগ্যতা
  2. (⇒) P-র MPCP match 1, i2, …, im থাকলে নতুন instance-এ নিন: বিশেষ প্রথম ডমিনো, তারপর i2, …, im-এর ⋆-রূপ, আর শেষে [⋆◇/◇]. ওপরে ⋆-চিহ্ন প্রতিটি অক্ষরের আগে, নিচে প্রতিটি অক্ষরের পরে, আর নিচের শুরুর বাড়তি ⋆ ও শেষের ⋆◇ দুই লাইনকে সমান করে; ⋆ মুছলে দুই লাইনই আগের match. — একটি দিক
  3. (⇐) নতুন instance-এর যেকোনো match-এর প্রথম ডমিনোর ওপর আর নিচ একই অক্ষরে শুরু হতে হবে। ওপর সবসময় ⋆ দিয়ে শুরু হয়, কিন্তু নিচ ⋆ দিয়ে শুরু হয় শুধু বিশেষ প্রথম ডমিনোতে; তাই match সেটি দিয়েই শুরু। একইভাবে শেষে ওপর-নিচ একই অক্ষরে শেষ হয় শুধু [⋆◇/◇]-এ। ⋆ আর ◇ মুছে ফেললে পাওয়া যায় P-র এমন একটি match, যা ডমিনো ১ দিয়ে শুরু। — উল্টো দিক
  4. তাই ⟨P⟩ ∈ MPCP ⇔ f(⟨P⟩) ∈ PCP. ∎ (বিশেষ প্রথম ডমিনো match-এর মাঝখানে এলে কী হয়, সেই খুঁটিনাটি Sipser-এর বইয়ে আছে।)

৪ · Computation history থেকে ডমিনো — PCP undecidable

এবার মূল নির্মাণ। পর্ব ৪৩-এর রীতিতে configuration লেখা হয় u q v: tape-এর লেখা uv, state q, আর head v-এর প্রথম অক্ষরের ওপর। M-এর w-এর ওপর একটি গ্রহণকারী computation history হলো configuration-এর ক্রম C1, C2, …, Cl, যেখানে C1 = q0w, প্রতিটি Ci+1 আগেরটি থেকে এক ধাপে আসে (Ci ⊢ Ci+1), আর Cl-এ state qaccept. এদের # দিয়ে জুড়ে লিখলে পাওয়া যায় #C1#C2#⋯#Cl#.

ধারণাটি এক বাক্যে: নিচের লাইন সবসময় ওপরের লাইনের চেয়ে ঠিক একটি configuration এগিয়ে থাকে। ওপরের লাইন Ci কপি করার সময় নিচের লাইনে ডমিনোগুলো Ci+1 লিখতে বাধ্য হয়। ঠিক যেমন পুরোনো দিনের কপি-খাতায় একটি লাইন দেখে পরের লাইন লিখতে হয়, আর নিয়ম ভাঙলে খাতা মেলে না।

নির্মাণ ৪.১ (Sipser-এর সাত অংশ)

M = (Q, Σ, Γ, δ, q0, qaccept, qreject) আর w = w1⋯wn থেকে MPCP instance P′:
১. প্রথম ডমিনো: [# / #q0w1⋯wn#].
২. প্রতিটি δ(q, a) = (r, b, R), q ≠ qreject: [qa / br].
৩. প্রতিটি δ(q, a) = (r, b, L), q ≠ qreject, আর প্রতিটি c ∈ Γ: [cqa / rcb].
৪. প্রতিটি a ∈ Γ: [a / a] (যে অংশ বদলায় না, তার কপি)।
৫. [# / #] আর [# / ␣#] (দ্বিতীয়টি ডান প্রান্তে নতুন ফাঁকা ঘর যোগ করে)।
৬. প্রতিটি a ∈ Γ: [a qaccept / qaccept] আর [qaccept a / qaccept] (গ্রহণের পরে অক্ষর “খেয়ে ফেলা”)।
৭. [qaccept## / #] (শেষ করা)।

তিনটি সরলীকরণ মেনে নেওয়া হয়, যা M বদলে সবসময় পাওয়া যায়: M কখনো tape-এর বাঁ প্রান্ত থেকে বাঁয়ে সরার চেষ্টা করে না, w = ε হলে w-এর জায়গায় ␣ লেখা হয়, আর state নামগুলো Γ-এর অক্ষর থেকে আলাদা। এবার একটি ছোট উদাহরণ। যন্ত্র M-এর দুটি নিয়ম: δ(q0, 0) = (q1, 1, R) আর δ(q1, ␣) = (qaccept, ␣, R); Γ = {0, 1, ␣}; w = 0. কোডে ছোট রাখার জন্য q0 = p, q1 = q, qaccept = A লেখা হয়। M-এর computation: p0 ⊢ 1q␣ ⊢ 1␣A, অর্থাৎ গ্রহণ। নির্মাণে ১৫টি ডমিনো হয়: অংশ ১-এ [#/#p0#], অংশ ২-এ [p0/1q] আর [q␣/␣A], অংশ ৪-এ তিনটি, অংশ ৫-এ দুটি, অংশ ৬-এ ছয়টি, আর অংশ ৭-এ একটি। নিচের stepper দেখায়, ১২টি ডমিনোর MPCP match কীভাবে history-টি লেখে।

1অংশ ১: [# / #p0#]2অংশ ২: [p0 / 1q]3অংশ ২: [q␣ / ␣A]4অংশ ৪: [1 / 1]5অংশ ৫: [# / #], [# / ␣#]6অংশ ৬: [␣A / A], [1A / A]7অংশ ৭: [A## / #]
দুই লাইন
ওপর
নিচ
নিচের বাড়তি
  1. শুরু। MPCP-তে প্রথম ডমিনো বাধ্যতামূলক: ওপরে #, নিচে #p0#. নিচের লাইন শুরুর configuration C1 = p0 লিখে এক configuration এগিয়ে গেল। ওপরের লাইনকে এখন p0# কপি করতে হবে।
  2. এক move. ওপরে এখন প্রথমে p দরকার। কপি-ডমিনো [a/a] আছে শুধু Γ-এর অক্ষরের জন্য, আর p দিয়ে শুরু হওয়া ওপর আছে শুধু অংশ ২-এর [p0/1q]-এ: ওপরে p0, নিচে 1q. M-এর নিয়ম δ(p, 0) = (q, 1, R) এভাবেই নিচে বসল।
  3. Configuration-এর শেষ। ওপরে # দরকার। [#/#] দিলে নিচে C2 হতো 1q, যেখানে head-এর নিচে কিছু নেই; তাই [#/␣#] বেছে নেওয়া হয়, যা ডান প্রান্তে একটি ␣ যোগ করে। নিচে এখন C2 = 1q␣ সম্পূর্ণ।
  4. দ্বিতীয় move. ওপরের লাইন C2 কপি করে: [1/1] (বদলায় না এমন অংশ), [q␣/␣A] (নিয়ম δ(q, ␣) = (A, ␣, R)), আর [#/#]. নিচে C3 = 1␣A: state A মানে qaccept.
  5. খাওয়া শুরু। গ্রহণের পরে ওপর-নিচ মেলাতে হবে, অথচ নিচ এক configuration এগিয়ে। অংশ ৬-এর ডমিনো A-এর পাশের একটি অক্ষর ওপরে নেয় কিন্তু নিচে দেয় না: [1/1], [␣A/A], [#/#]. নিচে 1A, এক অক্ষর ছোট।
  6. আরেকবার খাওয়া। [1A/A] আর [#/#]: নিচে শুধু A. প্রতিবার configuration এক অক্ষর ছোট হয়, তাই ওপরের লাইন ধীরে ধীরে নিচকে ধরে ফেলে।
  7. শেষ। অংশ ৭-এর [A##/#] ওপরে A## আর নিচে # দেয়: দুই লাইন এখন হুবহু #p0#1q␣#1␣A#1A#A##. ১২টি ডমিনোর এই match-এর প্রথম তিনটি configuration-ই M-এর গ্রহণকারী history; শেষের অংশ শুধু “হিসাব মেলানো”।
উপপাদ্য ৪.২ (Post ১৯৪৬; এখানে Sipser-এর প্রমাণ)

ATM ≤m MPCP ≤m PCP. অতএব MPCP আর PCP দুটিই undecidable.

প্রমাণের রূপরেখা (ATM ≤m MPCP অংশের; বাকিটা লেমা ৩.২):

  1. f(⟨M, w⟩) = ⟨P′⟩, নির্মাণ ৪.১-এর ডমিনো। δ সসীম আর Γ সসীম, তাই ডমিনো সসীম, আর সেগুলো লেখা একটি সবসময় থামা algorithm. — f computable
  2. (⇒) M w গ্রহণ করলে গ্রহণকারী history C1, …, Cl আছে। Stepper-এর মতো প্রতিটি Ci কপি করার সময় অংশ ২–৫ নিচে Ci+1 লেখে; শেষে অংশ ৬–৭ দুই লাইন সমান করে। তাই P′-এর ডমিনো ১ দিয়ে শুরু হওয়া match আছে। — একটি দিক
  3. (⇐) উল্টো দিকে মূল যুক্তি হলো “ধরা পড়া”: যতক্ষণ qaccept আসেনি, প্রতিটি ডমিনোর নিচ ওপরের চেয়ে লম্বা (অংশ ১ আর [#/␣#]) বা সমান (অংশ ২–৫-এর বাকি সব), তাই ওপর কখনো নিচকে ধরতে পারে না। ধরা সম্ভব শুধু অংশ ৬–৭ দিয়ে, যাদের জন্য একটি configuration-এ qaccept থাকতেই হবে। — শেষ হতে হলে গ্রহণ চাই
  4. আর প্রতিটি পরের configuration বাধ্য: state-অক্ষরসহ টুকরো ওপরে মেলানো যায় শুধু অংশ ২–৩-এর ডমিনো দিয়ে, যারা δ-এর নিয়ম হুবহু মানে; বাকি অক্ষর অংশ ৪ শুধু কপি করে। তাই match-এর # দিয়ে ভাগ করা টুকরোগুলো একটি বৈধ গ্রহণকারী history. — প্রতিটি ধাপ বৈধ
  5. অতএব ⟨M, w⟩ ∈ ATM ⇔ ⟨P′⟩ ∈ MPCP. ATM undecidable (পর্ব ৫১), তাই দিকের নিয়মে MPCP undecidable, আর লেমা ৩.২ দিয়ে PCP undecidable. ∎

কোডে পুরো শৃঙ্খল চালিয়ে দেখা যাক। নিচের ব্লক আগের ব্লকের solve ব্যবহার করে (একই namespace). mpcp function নির্মাণ ৪.১ লেখে, star লেমা ৩.২-এর ⋆ কৌশল (কোডে ⋆ = *, ◇ = $, ␣ = _)। অর্থাৎ ⟨M, w⟩ থেকে একটি সাধারণ PCP instance বানিয়ে BFS চালানো হয়। শেষে একটি যন্ত্র, যা চিরকাল ডানে হাঁটে।

# M (states p = q0, q = q1, A = qaccept; blank "_"): p,0 -> q,1,R ; q,_ -> A,_,R
delta = {("p", "0"): ("q", "1", "R"), ("q", "_"): ("A", "_", "R")}
GAMMA, w = "01_", "0"
def mpcp(delta, w):                            # Sipser's parts 1-7
    D = [("#", "#p" + w + "#")]                               # 1: the first domino
    for (q, a), (r, b, mv) in delta.items():
        D += [(q + a, b + r)] if mv == "R" else \
             [(c + q + a, r + c + b) for c in GAMMA]          # 2, 3: one TM move
    D += [(a, a) for a in GAMMA] + [("#", "#"), ("#", "_#")]  # 4, 5: copy, new blank
    D += [(a + "A", "A") for a in GAMMA] + [("A" + a, "A") for a in GAMMA]  # 6: eat
    return D + [("A##", "#")]                                 # 7: finish
def star(D):                                   # MPCP -> PCP (the "*" trick)
    L = lambda u: "".join("*" + c for c in u)         # *u1*u2...
    R = lambda u: "".join(c + "*" for c in u)         # u1*u2*...
    return [(L(D[0][0]), "*" + R(D[0][1]))] + [(L(t), R(b)) for t, b in D] + [("*$", "$")]
D = mpcp(delta, w)
print(len(D), "dominoes, e.g.", D[:3])
verdict, seq = solve(star(D))
top = "".join(star(D)[i - 1][0] for i in seq)
print(verdict, "with", len(seq), "dominoes, first =", seq[0])
print(top.replace("*", "").replace("$", ""))
delta2 = {("p", "0"): ("p", "0", "R"), ("p", "_"): ("p", "_", "R")}   # runs right forever
print("looping M:", solve(star(mpcp(delta2, w)), cap=20000)[0])

আসল আউটপুট (ব্রাউজারের Python):

15 dominoes, e.g. [('#', '#p0#'), ('p0', '1q'), ('q_', '_A')]
SOLVED with 13 dominoes, first = 1
#p0#1q_#1_A#1A#A##
looping M: CAP

নির্মাণে ১৫টি ডমিনো, প্রথম তিনটি stepper-এর মতোই। ⋆-রূপে ১৭টি ডমিনো (বিশেষ প্রথমটি আর [⋆◇/◇] যোগ হয়ে), আর BFS-এর পাওয়া সবচেয়ে ছোট match-এ ১৩টি: stepper-এর ১২টি আর শেষের [⋆◇/◇]. লক্ষ করুন, “first = 1”: সাধারণ PCP হলেও match বাধ্য হয়ে বিশেষ প্রথম ডমিনো দিয়ে শুরু হয়েছে, ঠিক লেমা ৩.২-এর যুক্তি অনুযায়ী। ⋆ আর ◇ মুছলে তৃতীয় লাইনে stepper-এর শেষ string, যার শুরুতে M-এর গ্রহণকারী history. শেষ লাইনে চিরকাল চলা যন্ত্র: উপপাদ্য বলে এর instance-এর কোনো match নেই, কিন্তু BFS তা বলতে পারে না, শুধু CAP. এটাই পুরো পর্বের সারকথা: reduction f সবসময় গণনা করা যায়, কিন্তু তৈরি হওয়া instance-এর উত্তর গণনা করা যায় না।

৫ · Grammar-এর undecidable প্রশ্ন — ambiguity, ছেদ, universality, equivalence

PCP undecidable জানার পরে আসল লাভ: string জোড়ার এই ধাঁধা খুব সহজে context-free grammar-এ লেখা যায়। ধরুন instance P = {[t1/b1], …, [tk/bk]} Σ-এর ওপর, আর d1, …, dk নতুন চিহ্ন (Σ-এ নেই), প্রতিটি ডমিনোর একটি “রসিদ নম্বর”। দুটি grammar:

GA: A → ti A di ∣ ti di GB: B → bi B di ∣ bi di (i = 1, …, k)

GA তৈরি করে ঠিক LA = {ti1⋯tim dim⋯di1 : m ≥ 1}: বাঁ দিকে ওপরের লেখা, ডানে রসিদগুলো উল্টো ক্রমে। রসিদের অংশ থেকে সূচক-ক্রমটি হুবহু পড়া যায়, তাই LA-এর প্রতিটি string-এর ঠিক একটি derivation: GA unambiguous. GB-ও তাই। এখন দুটি জুড়ে দিন: G = GA ∪ GB ∪ {S → A ∣ B}. এটি পর্ব ২৭-এ রূপরেখা হিসেবে দেখা grammar; এখানে পুরো প্রমাণ।

উপপাদ্য ৫.১ (ambiguity)

AMBIGCFG = {⟨G⟩ : G একটি ambiguous CFG} undecidable, কারণ PCP ≤m AMBIGCFG.

প্রমাণ:

  1. f(⟨P⟩) = ⟨G⟩, ওপরের নির্মাণ; সরাসরি computable. — f
  2. (⇒) P-র match i1, …, im থাকলে x = ti1⋯tim dim⋯di1 = bi1⋯bim dim⋯di1. x-এর একটি derivation S ⇒ A দিয়ে, আরেকটি S ⇒ B দিয়ে: দুটি আলাদা parse tree, তাই G ambiguous. — match থেকে দ্ব্যর্থতা
  3. (⇐) G ambiguous হলে কোনো x-এর দুটি আলাদা leftmost derivation. দুটিই A দিয়ে শুরু হতে পারে না (GA unambiguous), দুটিই B দিয়েও না; তাই একটি A, একটি B দিয়ে। x-এর রসিদ-অংশ দুটিতেই একই, অর্থাৎ একই সূচক-ক্রম, আর Σ-অংশ বলে ওপরের লেখা = নিচের লেখা: P-র match. — দ্ব্যর্থতা থেকে match
  4. অতএব ⟨P⟩ ∈ PCP ⇔ ⟨G⟩ ∈ AMBIGCFG; PCP undecidable, তাই AMBIGCFG undecidable. ∎

একটি ছোট instance-এ দেখুন: Ps = {[ab/a], [b/bb]}, যার match 1, 2 (ওপরে ab·b = abb, নিচে a·bb = abb).

1S → A ∣ B2A → ab A d1 ∣ ab d13A → b A d2 ∣ b d24B → a B d1 ∣ a d15B → bb B d2 ∣ bb d2
দুটি derivation
A-পথ
B-পথ
  1. Grammar বানানো। Ps-এর দুটি ডমিনো থেকে A-এর দুটি নিয়ম-জোড়া (ওপরের লেখা ab, b) আর B-এর দুটি (নিচের লেখা a, bb). রসিদ d1 মানে ডমিনো ১, d2 মানে ডমিনো ২. এখানে d1, d2 একেকটি চিহ্ন।
  2. A-পথ, প্রথম ডমিনো। A → ab A d1: বাঁয়ে ওপরের লেখা ab, ডানে রসিদ d1. ভেতরের A বাকি ডমিনোর জন্য জায়গা রাখে।
  3. A-পথ, দ্বিতীয় ডমিনো। A → b d2 দিয়ে শেষ: ab b d2 d1 = abbd2d1. রসিদ উল্টো ক্রমে পড়লে d1, d2: ক্রম 1, 2.
  4. B-পথ, প্রথম ডমিনো। এবার S ⇒ B, আর B → a B d1: নিচের লেখা a, রসিদ d1.
  5. B-পথ, দ্বিতীয় ডমিনো। B → bb d2: a bb d2 d1 = abbd2d1, A-পথের হুবহু একই string.
  6. ফল। একই string abbd2d1-এর দুটি parse tree, একটির মূলের নিচে A, অন্যটির নিচে B: G ambiguous. আর এটি ঘটেছে কারণ একই ক্রম 1, 2-এ ওপর আর নিচ মিলেছে, অর্থাৎ Ps-এর match. Match না থাকলে A-পথ আর B-পথ কখনো একই string দিত না।

একই GA আর GB থেকে আরও তিনটি ফল আসে। প্রমাণের (⇐) অংশে আমরা আসলে দেখিয়েছি: LA ∩ LB ≠ ∅ ⇔ P-র match আছে।

উপপাদ্য ৫.২–৫.৪

৫.২ (ছেদ): {⟨G1, G2⟩ : L(G1) ∩ L(G2) = ∅} undecidable.
৫.৩ (universality): ALLCFG = {⟨G⟩ : L(G) = Σ∗} undecidable.
৫.৪ (equivalence): EQCFG = {⟨G1, G2⟩ : L(G1) = L(G2)} undecidable.

প্রমাণের রূপরেখা:

  1. ছেদ: f(⟨P⟩) = ⟨GA, GB⟩. ⟨P⟩ ∈ PCP ⇔ ছেদ অ-ফাঁকা ⇔ f(⟨P⟩) ছেদ-ফাঁকা সমস্যার বাইরে। তাই PCP ≤m (ছেদ-ফাঁকা-র complement). ছেদ-ফাঁকা decidable হলে তার complement-ও decidable হতো, আর তাহলে PCP-ও; তাই undecidable. — complement-এর সঙ্গে reduction
  2. Universality: LA একটি deterministic CFL: একটি DPDA বাঁ অংশ stack-এ রাখে, তারপর প্রতিটি রসিদ di পড়ে stack থেকে ti উল্টো করে মিলিয়ে নেয়। পর্ব ৩৫ অনুযায়ী DCFL complement-এর অধীনে বন্ধ, তাই L̄A, L̄B দুটিই CFL, আর তাদের grammar algorithm দিয়ে বানানো যায় (DPDA, complement, তারপর পর্ব ৩৪-এর PDA → CFG). GP নিন L̄A ∪ L̄B-এর grammar. De Morgan অনুযায়ী L(GP) = Σ∗ ⇔ LA ∩ LB = ∅ ⇔ P-র match নেই। তাই PCP-র complement ≤m ALLCFG; ALLCFG decidable হলে PCP-ও decidable হতো। — এখানে alphabet হলো Σ ∪ {d1, …, dk}
  3. Equivalence: ALLCFG ≤m EQCFG: G-কে নিয়ে যান (G, Gall)-এ, যেখানে Gall হলো S → aS ∣ ε (প্রতিটি a ∈ Σ)। L(G) = Σ∗ ⇔ L(G) = L(Gall). ∎

Sipser-এর বইয়ে ALLCFG প্রমাণ হয় আরেক পথে: সরাসরি computation history দিয়ে, যেখানে একটি PDA “এটি গ্রহণকারী history নয়” যাচাই করে (পর্ব ৩৭-এ এক অনুচ্ছেদের রূপরেখা আছে, আর পর্ব ৫২-এ computation history-র কৌশলটি)। দুই পথের মূল একই: computation history-কে string-এ লেখা। আমাদের PCP-পথের একটি বাড়তি ফল: ALLCFG recognizable-ও নয়, কারণ PCP-র complement-এর মতো একটি non-recognizable সমস্যা তাতে reduce হয়। অন্যদিকে ALLCFG-এর complement recognizable: L(G)-এর বাইরের একটি string খুঁজে পেলেই হলো, আর প্রতিটি string-এর membership পর্ব ৩১-এর CYK দিয়ে decidable.

নিচের Python ব্লক তিনটি instance-এ GA আর GB-এর সব derivation (এক থেকে পাঁচটি ডমিনো) তৈরি করে। প্রতিটি সূচক-ক্রম একটি derivation, তাই একই string দুটি ক্রম থেকে এলে সেটি দ্ব্যর্থতা। ছাপা হয়: GA একা কয়টি string দেয়, তার মধ্যে কয়টি একাধিক derivation-এর, আর LA ∩ LB-এ কয়টি string.

from itertools import product
def grammar(doms):                       # PCP instance -> CFG G (start S -> A | B)
    rules = ["S -> A | B"]
    for side, X in ((0, "A"), (1, "B")):
        for i, d in enumerate(doms, 1):
            rules.append(f"{X} -> {d[side]} {X} d{i} | {d[side]} d{i}")
    return rules
def derivations(doms, X, m):             # each A-derivation = one index sequence
    side = 0 if X == "A" else 1
    out = {}
    for k in range(1, m + 1):
        for seq in product(range(1, len(doms) + 1), repeat=k):
            s = "".join(doms[i - 1][side] for i in seq) + \
                "".join(f"d{i}" for i in reversed(seq))       # yield of the tree
            out.setdefault(s, []).append(seq)
    return out
P = {"small":  [("ab", "a"), ("b", "bb")],
     "sipser": [("b", "ca"), ("a", "ab"), ("ca", "a"), ("abc", "c")],
     "longer": [("abc", "ab"), ("ca", "a"), ("acc", "ba")]}
for r in grammar(P["small"]): print("  ", r)
for name, doms in P.items():
    A, B = derivations(doms, "A", 5), derivations(doms, "B", 5)
    twoA = sum(len(v) > 1 for v in A.values())           # A alone ambiguous?
    both = sorted(set(A) & set(B), key=len)              # L(G_A) ∩ L(G_B)
    print(f"{name:6} A-strings {len(A):4}  A-ambiguous {twoA}  "
          f"common {len(both)}", both[:1])

আসল আউটপুট (ব্রাউজারের Python):

   S -> A | B
   A -> ab A d1 | ab d1
   A -> b A d2 | b d2
   B -> a B d1 | a d1
   B -> bb B d2 | bb d2
small  A-strings   62  A-ambiguous 0  common 2 ['abbd2d1']
sipser A-strings 1364  A-ambiguous 0  common 1 ['abcaaabcd4d2d3d1d2']
longer A-strings  363  A-ambiguous 0  common 0 []

প্রথমে Ps-এর grammar, stepper-এর সঙ্গে হুবহু এক। তিনটি instance-এই “A-ambiguous 0”: GA একা কখনো ambiguous নয়, প্রমাণের ধাপ ৩-এর দাবির সঙ্গে মিলে (Ps-এ 2 + 4 + 8 + 16 + 32 = 62টি ক্রম, 62টিই আলাদা string). Ps-এ ছেদে দুটি string: ক্রম 1, 2 থেকে abbd2d1, আর ক্রম 1, 2, 1, 2 থেকে একটি লম্বা string, কারণ match জুড়ে দিলে আবার match হয়। Sipser-এর instance-এ ঠিক একটি, যা 2, 1, 3, 2, 4-এর রসিদ উল্টো ক্রমে বহন করে। Plong-এ ছেদ ফাঁকা, কারণ match নেই। মনে রাখুন, পাঁচ ডমিনো পর্যন্ত খোঁজা একটি সীমিত পরীক্ষা: “common 0” দেখে সাধারণভাবে grammar-কে unambiguous বলা যায় না; Plong-এর ক্ষেত্রে বলা যায় শুধু দৈর্ঘ্যের প্রমাণ আছে বলে।

প্রশ্ন (CFG G, G1, G2)Decidable?কারণ
w ∈ L(G)?হ্যাঁCNF + CYK, পর্ব ৩১
L(G) = ∅?হ্যাঁgenerating variable চিহ্নিত করা, পর্ব ৩৭
G ambiguous?নাPCP ≤m AMBIGCFG
L(G1) ∩ L(G2) = ∅?নাPCP ≤m এর complement
L(G) = Σ∗?নাPCP-র complement ≤m ALLCFG
L(G1) = L(G2)?নাALLCFG ≤m EQCFG

বাজারঘরের দলের জন্য এর মানে কী? Order query-ভাষার grammar কেউ নতুন করে লিখলে “পুরোনোটির সমান কি না” বা “কোথাও দ্ব্যর্থ কি না” প্রশ্নের জন্য কোনো tool সবসময় সঠিক রায় দিতে পারবে না। বাস্তবের tool তাই রক্ষণশীল পরীক্ষা করে: LR(1) table-এ conflict না থাকলে grammar নিশ্চিতভাবে unambiguous (পর্ব ৩৯), conflict থাকলে হয়তো ambiguous, হয়তো শুধু কঠিন; আর দুটি grammar-এর পার্থক্য খোঁজা হয় অনেক string-এ মিলিয়ে, যা পার্থক্য পেলে প্রমাণ, না পেলে শুধু আস্থা।

৬ · সীমানা — কোথায় PCP decidable, কোথায় অজানা

Undecidability সাধারণ সমস্যার ধর্ম; একটু সীমা টানলেই অনেক সময় সমস্যা decidable হয়ে যায়। PCP-র ক্ষেত্রে সীমানাটি আকর্ষণীয়ভাবে সূক্ষ্ম:

Bounded PCP

Instance-এর সঙ্গে একটি সংখ্যা K দেওয়া: K বা তার কম ডমিনোর match আছে কি? সসীম সংখ্যক ক্রম, তাই decidable. K-কে যথাযথভাবে input-এর অংশ ধরলে সমস্যাটি NP-complete বলে Garey ও Johnson-এর পরিচিত তালিকায় আছে (Constable, Hunt ও Sahni-র ১৯৭০-এর দশকের কাজের সূত্রে)। NP বোঝা যাবে পর্ব ৫৮–৫৯-এ।

এক অক্ষরের alphabet

Σ = {a} হলে শুধু দৈর্ঘ্য গুরুত্বপূর্ণ। কোনো ডমিনোর ওপর-নিচ সমান দৈর্ঘ্যের হলে সেটিই match; নইলে ওপর-লম্বা আর নিচ-লম্বা দুই রকম ডমিনো থাকলেই match হয়। Decidable (প্রমাণ অনুশীলন ২-এ)। দুই অক্ষরেই কিন্তু undecidable: যেকোনো alphabet-কে binary code-এ লেখা যায়।

ডমিনোর সংখ্যা

দুটি ডমিনোর PCP decidable বলে প্রমাণিত (Ehrenfeucht, Karhumäki ও Rozenberg, ১৯৮২ সালের দিকে)। পাঁচটি ডমিনোতেই undecidable (Turlough Neary, ২০১৫; আগে সাতটির জন্য Matiyasevich ও Sénizergues). তিন আর চারটির ক্ষেত্রে উত্তর এখনো অজানা, আমাদের জানামতে।

সমাধান খোঁজার গবেষণা

ছোট instance-এর সবচেয়ে ছোট সমাধান খুঁজতে গবেষকেরা কম্পিউটারে ব্যাপক খোঁজ চালিয়েছেন; long4-এর মতো ২০০-র বেশি ডমিনোর সমাধানওয়ালা instance এ ধরনের খোঁজেই পরিচিত হয়। x3-এর মতো কিছু ছোট instance-এর অবস্থা খোঁজার সীমার বাইরে থেকে যায়।

ইতিহাস: Emil Post ১৯৪৬ সালে “A variant of a recursively unsolvable problem” প্রবন্ধে সমস্যাটি দেন। তাঁর নিজের প্রমাণ Turing machine দিয়ে নয়, তাঁর নিজের string-বদলের ব্যবস্থা (normal system) থেকে এসেছিল বলে জানা যায়; computation history দিয়ে আজকের পাঠ্যবইয়ের প্রমাণটি পরে প্রচলিত হয়। Post ১৯৩৬ সালেই Turing-এর প্রায় সমান্তরালে একটি গণনার মডেল প্রস্তাব করেছিলেন, আর tag system (পর্ব ৪৯)-ও তাঁর। CFG-এর ছেদ, universality আর equivalence-এর undecidability সাধারণত Bar-Hillel, Perles ও Shamir-এর ১৯৬১ সালের প্রবন্ধের সঙ্গে যুক্ত করা হয়, আর ambiguity-র ফল ১৯৬২–৬৩ সালের দিকে কয়েকজনের স্বাধীন কাজ।

৭ · আরও গভীরে আর পরীক্ষার প্রস্তুতি

আরও গভীরে: PCP থেকে আরও অনেক undecidability আসে: পূর্ণসংখ্যার ৩ × ৩ matrix-এর একটি সেটের কোনো গুণফল শূন্য matrix হয় কি না (mortality problem, Paterson ১৯৭০ সালের দিকে), দুটি CFG-এর একটির language অন্যটির ভেতরে কি না, আর L(G) regular কি না (Greibach-এর একটি সাধারণ উপপাদ্যের ফল)। অন্যদিকে deterministic PDA-র equivalence decidable, যা Géraud Sénizergues ১৯৯৭ সালের দিকে প্রমাণ করেন। আর একটি সতর্কতা: পর্ব ৭১-এর “PCP theorem” (probabilistically checkable proofs) সম্পূর্ণ আলাদা বিষয়; শুধু সংক্ষিপ্ত নাম এক।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • এই PCP instance-এর একটি match দিন / সমাধান নেই প্রমাণ করুন। বাড়তি অংশ ধরে ধাপে ধাপে খুঁজুন; না থাকলে দৈর্ঘ্য বা শুরুর অক্ষরের যুক্তি।
  • PCP কি decidable? Recognizable? Decidable নয়, recognizable হ্যাঁ; তাই complement recognizable নয়।
  • MPCP কেন লাগে? Match-কে শুরুর configuration দিয়ে শুরু করাতে; ⋆ কৌশলে MPCP ≤m PCP.
  • CFG ambiguity undecidable কেন? PCP ≤m AMBIGCFG: GA আর GB-এর রসিদ-চিহ্নের grammar.
  • CFG-এর কোন প্রশ্ন decidable? Membership আর emptiness; ambiguity, ছেদ-শূন্যতা, universality, equivalence নয়।

৮ · AI-এর যুগে PCP আর reduction নিয়ে কাজ

AI assistant এই বিষয়ে কয়েকটি ভুল বারবার করে। সবচেয়ে বিপজ্জনক হলো reduction-এর দিক উল্টে ফেলা: “ambiguity undecidable প্রমাণ করতে ambiguity-কে PCP-তে reduce করি” লিখে দেওয়া। এতে প্রমাণ হয় শুধু ambiguity PCP-র চেয়ে কঠিন নয়, যা কিছুই বলে না। দ্বিতীয় ভুল: একটি instance-এ “সমাধান নেই” বলে দেওয়া, কারণ ছোট খোঁজায় পাওয়া যায়নি; long4-এর ২০৬ ডমিনোর সমাধান দেখিয়েছে এই যুক্তি কত দুর্বল। তৃতীয়: PCP আর PCP theorem গুলিয়ে ফেলা, বা “দুই ডমিনোর PCP undecidable”-এর মতো ভুল সীমানা আর বানানো রেফারেন্স।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
Reduction উল্টো দিকে (X ≤m PCP দিয়ে X-কে undecidable বলা)লিখে দেখুন: পরিচিত undecidable সমস্যা বাঁয়ে, নতুন সমস্যা ডানে আছে কি না
দাবি করা match আসলে মেলে না, বা ডমিনোর ক্রম ভুল গোনাঅংশ ১-এর JavaScript বা solve-এর check দিয়ে ওপর-নিচ জুড়ে মিলিয়ে দেখুন
“ছোট খোঁজায় পাইনি, তাই সমাধান নেই”সমাধান-নেই দাবির জন্য সম্পূর্ণ খোঁজ বা দৈর্ঘ্য/শুরুর যুক্তির মতো প্রমাণ চান; CAP-কে রায় ধরবেন না
Grammar নির্মাণে রসিদ-চিহ্ন বাদ, বা di সঠিক উল্টো ক্রমে নেইছোট instance-এ derivation-গুলো brute force করে GA একা unambiguous কি না গুনুন
সীমানার ভুল তথ্য, PCP theorem-এর সঙ্গে গুলিয়ে ফেলা, বানানো প্রবন্ধSipser বা Hopcroft–Motwani–Ullman আর মূল প্রবন্ধের নাম ও সাল নিজে মিলিয়ে নিন

AI-কে কাজে লাগানোর ভালো উপায়: নির্মাণ, দুই দিকের প্রমাণ, ছোট উদাহরণ আর একটি যাচাই-কোড একসঙ্গে চাওয়া, যা আপনি নিজে চালাবেন।

আমি গণনার তত্ত্বে Post correspondence problem শিখছি (Sipser-এর রীতি)। ১. PCP-র formal সংজ্ঞা দাও, আর {[ab/a], [b/bb]} instance-এর একটি match ধাপে ধাপে দেখাও। ২. MPCP ≤m PCP-র ⋆ কৌশল লেখো, আর দুই দিকের (⇒ এবং ⇐) যুক্তি আলাদা করে দাও। ৩. PCP থেকে CFG ambiguity-তে reduction দাও। কোন সমস্যা কোনটিতে reduce হচ্ছে আর কেন এই দিকেই, স্পষ্ট করে বলো। ৪. Step cap-সহ একটি Python BFS দাও, যা "SOLVED", "NO SOLUTION" আর "CAP" তিনটি ফল আলাদা করে, আর match পেলে ওপর-নিচ আবার মিলিয়ে দেখে। ৫. কোন সীমাবদ্ধ PCP decidable আর কোনটি এখনো খোলা প্রশ্ন, বলো; নিশ্চিত না হলে বলো, আর কোনো রেফারেন্স বানিয়ো না।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১PCP দেখতে একটি সসীম ধাঁধা: কয়েকটি ডমিনো, কয়েকটি অক্ষর। এমন সরল জিনিস কীভাবে halting problem-এর সমান কঠিন হতে পারে?

“সসীম” কথাটি এখানে বিভ্রান্তিকর। Instance সসীম, কিন্তু সম্ভাব্য সমাধান অসীম: যেকোনো দৈর্ঘ্যের ক্রম, পুনরাবৃত্তিসহ। Turing machine-ও তেমনি: নিয়মের তালিকা সসীম, কিন্তু computation-এর দৈর্ঘ্য সীমাহীন। কোনো সমস্যা কঠিন হওয়ার জন্য বড় বর্ণনা লাগে না; লাগে এমন একটি গঠন, যা সীমাহীন গণনা “ধরে রাখতে” পারে। PCP-তে সেই কাজ করে বাড়তি অংশ: নিচের লাইন ওপরের চেয়ে একটি configuration এগিয়ে থাকে, আর সেই বাড়তি অংশই যন্ত্রের tape আর state বহন করে। অংশ ৪-এর stepper-এ দেখেছেন, প্রতিটি নতুন ডমিনো আসলে যন্ত্রের একটি move.

এই ধাঁচ গণিতে বারবার দেখা যায়। Conway-এর Game of Life-এর নিয়ম মাত্র কয়েকটি, অথচ তা universal গণনা করতে পারে বলে দেখানো হয়েছে; ছোট tag system-ও (পর্ব ৪৯) universal. Hilbert-এর দশম সমস্যার উত্তরে (১৯৭০, Matiyasevich, আগের কাজে Davis, Putnam ও Robinson) দেখা যায়, পূর্ণসংখ্যার বহুপদী সমীকরণের সমাধান আছে কি না, সেটিও undecidable (পর্ব ৫৫)। প্রতিটি ক্ষেত্রে মূল কৌশল এক: দেখানো যে কোনো একটি সরল কাঠামো একটি Turing machine-এর history লিখতে পারে।

এখান থেকে একটি ব্যবহারিক শিক্ষা আসে। কোনো নতুন সমস্যা দেখে “এ তো ছোট, নিশ্চয়ই একটা algorithm আছে” ভাবা বিপজ্জনক। প্রশ্ন করা উচিত: এই কাঠামো কি সীমাহীন কিছু জমা রাখতে পারে, আর এক অংশ দিয়ে অন্য অংশ যাচাই করতে পারে? পারলে, সেখানে computation history লুকিয়ে রাখা সম্ভব হতে পারে। PCP-র ক্ষেত্রে ঠিক তাই হয়েছে, আর long4-এর ২০৬ ডমিনোর সমাধান দেখায়, ছোট instance-ও কত দীর্ঘ “গণনা” লুকিয়ে রাখতে পারে।

মূল উপলব্ধি: Undecidability আসে বর্ণনার আকার থেকে নয়, সীমাহীন গণনা লেখার ক্ষমতা থেকে; PCP-র বাড়তি অংশই সেই ক্ষমতা।

প্র ০২Grammar-এর প্রশ্নের undecidability প্রমাণে সরাসরি ATM না নিয়ে কেন প্রায়ই PCP ব্যবহার হয়? এই “মধ্যবর্তী সমস্যা” কৌশলের লাভ কী?

Reduction-এর শৃঙ্খলে প্রতিটি ধাপ একটি দূরত্ব পার হয়। ATM থেকে সরাসরি ambiguity-তে যেতে হলে একটি Turing machine-এর আচরণ grammar-এর ভাষায় লিখতে হতো: configuration, state, head, সব একসঙ্গে। PCP মাঝখানে একটি সেতু: প্রথম ধাপে যন্ত্রের সব জটিলতা একবারই ডমিনোতে রূপান্তর হয়, আর তারপর grammar-এর কাছে বাকি থাকে শুধু “দুটি string জোড়ার ক্রম মেলে কি না”। CFG-এর জন্য এটি স্বাভাবিক: A → ti A di নিয়ম বাঁয়ে লেখা জমায়, ডানে তার রসিদ, ঠিক যেমন stack বাঁ-ডান মেলায়। তাই একটি নির্মাণ থেকেই ambiguity, ছেদ, universality আর equivalence চারটি ফল আসে।

এই প্রকৌশলের ইতিহাসও এমন। ১৯৬১ সালে Bar-Hillel, Perles ও Shamir CFG-এর কয়েকটি প্রশ্নের undecidability দেখান, আর ১৯৬২–৬৩ সালের দিকে কয়েকজন গবেষক স্বাধীনভাবে ambiguity-র ফল পান বলে জানা যায়; এসব প্রমাণে PCP বা তার কাছাকাছি সমস্যা সেতু হিসেবে কাজ করে। Complexity তত্ত্বেও একই কৌশল: প্রতিটি নতুন NP-complete সমস্যার জন্য Cook–Levin-এর tableau আবার করতে হয় না; 3SAT-এর মতো সুবিধাজনক একটি সমস্যা থেকে reduce করলেই চলে (পর্ব ৫৯–৬১)।

সেতু বেছে নেওয়ার শিল্প আছে। যে সমস্যায় string-মেলানো মূল, সেখানে PCP; যেখানে তল ভরাট করা, সেখানে tiling সমস্যা; যেখানে সংখ্যা, সেখানে Hilbert-এর দশম সমস্যা বা counter machine. ভালো সেতু হলো সেটি, যা লক্ষ্য-সমস্যার “ভাষায়” কথা বলে। পরীক্ষার প্রশ্নেও এই বুদ্ধি কাজে লাগে: একটি নতুন undecidability প্রমাণ করতে গিয়ে আগে ভাবুন, কোন পরিচিত undecidable সমস্যা দেখতে সবচেয়ে কাছাকাছি।

মূল উপলব্ধি: PCP যন্ত্রের জটিলতাকে একবার string জোড়ায় রূপ দেয়, যাতে grammar-এর সব প্রশ্নে সহজ, প্রায় একই নির্মাণ খাটে; ভালো মধ্যবর্তী সমস্যা পুরো একটি পরিবারের প্রমাণ সহজ করে।

প্র ০৩দুটি ডমিনোর PCP decidable, পাঁচটিতে undecidable, তিন-চারটিতে অজানা। এমন সীমানা কী শেখায়, আর decidable আর undecidable-এর মাঝের এই “ধূসর অঞ্চল” কেন টিকে থাকে?

Undecidability-র প্রমাণ সবসময় একটি নির্মাণ: কোনো Turing machine বা universal যন্ত্রকে সমস্যার ভেতরে লেখা। যত কম উপকরণে সেটি করা যায়, তত ছোট instance-এ undecidability. পাঁচটি ডমিনোর ফল (Turlough Neary, ২০১৫) এসেছে খুব ছোট universal ব্যবস্থা, বিশেষ করে binary tag system, চতুরভাবে এনকোড করে; আগের সাত ডমিনোর ফল ছিল Matiyasevich আর Sénizergues-এর। অন্যদিকে decidability-র প্রমাণ হলো একটি algorithm: দুটি ডমিনোর ক্ষেত্রে Ehrenfeucht, Karhumäki আর Rozenberg দেখান, সমাধানের গঠন এত নিয়মিত যে তা সসীমভাবে বর্ণনা করা যায়; পরে Halava, Harju ও Hirvensalo-সহ কয়েকজন প্রমাণটি সরল করেন বলে জানা যায়।

তিন আর চারটির ক্ষেত্রে দুই দিকের কৌশলই এখনো যথেষ্ট নয়। একটি universal ব্যবস্থাকে তিনটি ডমিনোতে আঁটানো যায়নি, আবার তিন ডমিনোর সব সমাধানের নিয়মিত গঠনও পাওয়া যায়নি। Busy Beaver-এর গল্পও এমন (পর্ব ৫৫): ছোট যন্ত্রের মান হিসাব করে বের করা গেছে, বড়গুলোর জন্য অসম্ভব, আর মাঝখানে কোথাও সীমানা। x3-এর মতো একটি তিন ডমিনোর instance-এ ১ লাখ বা ৩০ লাখ অবস্থা খুঁজেও রায় না পাওয়া এই ধূসর অঞ্চলের একটি ছোট নমুনা।

শিক্ষাটি দুই দিকের। প্রথমত, “এই শ্রেণির সমস্যা undecidable” কথাটি সাধারণ সমস্যার কথা; বাস্তবের নির্দিষ্ট, সীমিত রূপ প্রায়ই decidable, এমনকি সহজ। দ্বিতীয়ত, কোনো নির্দিষ্ট সীমিত রূপ decidable কি না, তা নিজেই কঠিন গবেষণা-প্রশ্ন হতে পারে, আর দশকের পর দশক খোলা থাকতে পারে। AI বা বই যা-ই বলুক, এমন সীমানার দাবি সবসময় উৎস দেখে যাচাই করা উচিত, কারণ নতুন ফলে সংখ্যাগুলো বদলায়।

মূল উপলব্ধি: Decidability-র সীমানা খোঁজা মানে এক দিকে ছোট universal নির্মাণ আর অন্য দিকে নিয়মিত গঠনের algorithm; দুটো এখনো না মেলায় তিন-চার ডমিনোর PCP খোলা প্রশ্ন।

প্র ০৪Parser generator বা grammar নিয়ে কাজ করা tool undecidable প্রশ্নের মুখে কীভাবে কাজ চালায়? বাজারঘরের query-ভাষার grammar বদলানোর সময় একজন প্রকৌশলীর কী করা উচিত?

Tool-গুলো তিন রকম আপস করে। প্রথমটি রক্ষণশীল পরীক্ষা: LALR বা LR(1) parser generator table বানানোর সময় conflict খোঁজে। Conflict না থাকলে grammar নিশ্চিতভাবে unambiguous; conflict থাকলে tool সতর্ক করে বা কোনো নিয়মে একটি পথ বেছে নেয়। এখানে ভুল “unambiguous” কখনো আসে না, কিন্তু কিছু unambiguous grammar-ও বাতিল হয়। দ্বিতীয়টি সীমিত খোঁজ: কিছু গবেষণা-tool নির্দিষ্ট দৈর্ঘ্য পর্যন্ত সব string-এ দুটি parse tree খোঁজে, যেমন এই পর্বের pcp_to_cfg.py ব্লক। পেলে তা নিশ্চিত প্রমাণ, না পেলে শুধু আস্থা। তৃতীয়টি নিয়ম দিয়ে দ্ব্যর্থতা মেনে নেওয়া: precedence আর associativity ঘোষণা দিয়ে “দুটি tree-র মধ্যে কোনটি নেব” ঠিক করে দেওয়া (পর্ব ৪০, ৪২)।

বাজারঘরের দল যদি পুরোনো query grammar নতুন করে লেখে, তাহলে “দুটি সমান” প্রমাণ করার কোনো সাধারণ algorithm নেই (উপপাদ্য ৫.৪)। তবু বাস্তবে যা করা যায়: পুরোনো grammar থেকে অনেক বৈধ query তৈরি করে নতুন parser-এ চালানো, উল্টোটাও; আসল log থেকে নেওয়া query দিয়ে পরীক্ষা; random বা fuzz পরীক্ষা (সফটওয়্যার টেস্টিং কোর্সে property-based আর fuzz testing); আর দুই parser-এর parse tree বা ফলাফল তুলনা। এসব পার্থক্য পেলে তা একটি নিশ্চিত bug-রিপোর্ট; না পেলে আস্থা বাড়ে, প্রমাণ হয় না।

একটি সূক্ষ্ম দিক: এই সীমা সাধারণ CFG-এর। দুটি deterministic PDA-র language সমান কি না decidable (Sénizergues), আর regular grammar-এর equivalence সহজেই decidable (পর্ব ২০)। তাই ভাষার নকশা যদি LR বা regular শ্রেণিতে থাকে, যাচাইয়ের সুযোগ অনেক বেশি; যদিও deterministic ক্ষেত্রের algorithm বাস্তবে খুব জটিল।

মূল উপলব্ধি: Undecidable প্রশ্নে tool হয় রক্ষণশীল “হয়তো না”, নয় সীমিত খোঁজের “এখনো পাইনি” দেয়; প্রকৌশলীর কাজ এই দুই ধরনের উত্তরের মানে বুঝে পরীক্ষা সাজানো।

প্র ০৫BFS solver-এর তিনটি ফল, SOLVED, NO SOLUTION আর CAP, recognizable আর decidable-এর পার্থক্যের সঙ্গে কীভাবে মেলে? Cap বাড়িয়ে যেতে থাকলে কি একসময় সব instance-এর রায় পাওয়া যাবে?

SOLVED হলো recognizer-এর “হ্যাঁ”: সমাধান থাকলে যথেষ্ট বড় cap-এ BFS তা পাবেই, কারণ প্রতিটি নির্দিষ্ট দৈর্ঘ্যের সমাধান সসীম ধাপে পৌঁছানো যায়। এটি উপপাদ্য ২.১-এর বাস্তব রূপ। NO SOLUTION একটি সৌভাগ্যের ঘটনা: কিছু instance-এ পৌঁছানো যায় এমন অবস্থার সংখ্যা সসীম, যেমন Plong-এ, আর তখন সম্পূর্ণ খোঁজ নিজেই প্রমাণ। CAP হলো সেই বাকি অঞ্চল, যেখানে অবস্থা অসীম হতে পারে আর কোনো সমাধানও এখনো পাওয়া যায়নি।

Cap বাড়িয়ে গেলে কী হয়? যেসব instance-এর সমাধান আছে, তারা একসময় CAP থেকে SOLVED-এ যাবে। কিন্তু যেসব instance-এর সমাধান নেই আর অবস্থা অসীম, তারা চিরকাল CAP-এ থাকবে। কোনো একটি নির্দিষ্ট instance কোন দলে, তা আগে থেকে বলার উপায় থাকলে PCP decidable হতো, যা উপপাদ্য ৪.২ নিষেধ করে। আরও জোরালো কথা: “সমাধান নেই”-এর জন্য একটি সাধারণ সসীম সাক্ষ্য (যেমন কোনো invariant) সবসময় পাওয়া গেলে PCP-র complement recognizable হতো, তাহলে PCP decidable হতো। তাই কিছু unsolvable instance-এর কোনো সসীম, যাচাইযোগ্য প্রমাণ এই পদ্ধতিতে কখনো আসবে না।

এটি halting problem-এর সঙ্গে হুবহু মেলে (পর্ব ৫১)। একটি program-কে timeout দিয়ে চালালে “থেমেছে” একটি নিশ্চিত উত্তর, আর timeout শুধু “এখনো থামেনি”। বাস্তবের SAT solver, model checker বা theorem prover-ও এমন: কখনো উত্তর দেয়, কখনো resource শেষ বলে। ভালো tool সেই তৃতীয় অবস্থাকে স্পষ্টভাবে আলাদা রাখে, “না” হিসেবে চালিয়ে দেয় না; এই পর্বের solver-ও তাই CAP-কে আলাদা ফল হিসেবে ছাপে।

মূল উপলব্ধি: Recognizable সমস্যায় “হ্যাঁ” একসময় আসে, “না” হয়তো কখনো আসে না; cap সেই অনিশ্চয়তাকে লুকায় না, স্পষ্ট করে, আর তাকে “না” বলা একটি যুক্তির ভুল।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। pcp_bfs.py ব্লকে নিজের instance লিখে solve দিয়ে উত্তর যাচাইও করতে পারেন।

  1. নির্মাণ: একটি Turing machine-এর Γ = {0, 1, ␣}, আর একটি নিয়ম δ(q, 1) = (r, 0, L). নির্মাণ ৪.১-এর অংশ ৩ অনুযায়ী এই নিয়মের সব ডমিনো লিখুন। তারপর configuration 01q1 থেকে এক ধাপে কোন configuration আসে বলুন, আর কোন ডমিনো সেটি নিচের লাইনে লেখে, দেখান।

    ডমিনো: প্রতিটি c ∈ Γ-এর জন্য [c q 1 / r c 0]: [0q1 / r00], [1q1 / r10], [␣q1 / r␣0]. বাঁয়ে সরার সময় head-এর বাঁ পাশের অক্ষর c-ও নতুন configuration-এ state-এর ডানে চলে যায়, তাই c-কে ডমিনোতে রাখতে হয়; c কী হবে আগে জানা নেই বলে Γ-এর প্রতিটি অক্ষরের জন্য একটি।

    এক ধাপ: 01q1 মানে tape 011, head তৃতীয় ঘরে, state q. নিয়ম 1-এর জায়গায় 0 লিখে বাঁয়ে সরায়: 0r10. ওপরের লাইনে 01q1 কপি করার সময় [0/0] প্রথম 0 কপি করে, আর [1q1 / r10] বাকিটুকু: নিচে 0 + r10 = 0r10. ✓

  2. প্রমাণ: প্রমাণ করুন, এক অক্ষরের alphabet Σ = {a}-এর ওপর PCP decidable. (ইঙ্গিত: প্রতিটি ডমিনোর জন্য শুধু ওপর আর নিচের দৈর্ঘ্যের পার্থক্য গুরুত্বপূর্ণ।)

    ডমিনো i-এর জন্য gi = |ti| − |bi|. Σ-এ একটিমাত্র অক্ষর, তাই দুটি string সমান ⇔ দৈর্ঘ্য সমান। একটি ক্রম match ⇔ তার g-গুলোর যোগফল 0.

    Algorithm: কোনো gi = 0 হলে গ্রহণ; নইলে কোনো gi > 0 আর কোনো gj < 0 থাকলে গ্রহণ; নইলে বর্জন। সবসময় থামে।

    প্রমাণ: ১. gi = 0 হলে ক্রম “i” নিজেই match. ২. gi > 0 আর gj < 0 হলে i-কে |gj| বার আর j-কে gi বার নিন: যোগফল gi|gj| + gjgi = 0, তাই match (ক্রমের অবস্থান গুরুত্বহীন, কারণ সব অক্ষর a). ৩. বাকি ক্ষেত্রে সব g একই চিহ্নের আর কোনোটি 0 নয়, তাই যেকোনো অ-ফাঁকা ক্রমের যোগফল 0 নয়: match নেই। ৪. তিন ক্ষেত্র সব সম্ভাবনা ঢাকে, তাই algorithm সঠিক। ∎

  3. Trace আর ফল অনুমান: Instance {[1/111], [10111/10], [10/0]}-এ ক্রম 2, 1, 1, 3 নিন। প্রতিটি ডমিনোর পরে ওপরের লাইন, নিচের লাইন আর বাড়তি অংশ লিখুন। এটি কি match? আর pcp_bfs.py-র solve এই instance-এ কোন ক্রম ছাপবে, অনুমান করুন।

    +2: ওপরে 10111, নিচে 10; ওপর এগিয়ে 111. +1: ওপরে 101111, নিচে 10111; ওপর এগিয়ে 1. +1: ওপরে 1011111, নিচে 10111111; এবার নিচ এগিয়ে 1. +3: ওপরে 101111110, নিচে 101111110: match, ৯ অক্ষরের string.

    solve সবচেয়ে কম ডমিনোর match ছাপে। এক, দুই বা তিন ডমিনোর কোনো match নেই (ডমিনো ১ দিয়ে শুরু করলে নিচ ক্রমাগত এগিয়ে যায় আর কোনো ডমিনো তা ধরতে পারে না; ডমিনো ৩ দিয়ে শুরুই হয় না, কারণ 1 ≠ 0), তাই আউটপুট [2, 1, 1, 3], যা ব্লকের আসল আউটপুটের “hmu” লাইনের সঙ্গে মেলে।

  4. প্রমাণে ভুল খুঁজুন: একজন লিখেছেন: “PCP decidable. যন্ত্র D: বাড়তি অংশকে অবস্থা ধরে BFS চালান। বাড়তি অংশ সবসময় কোনো ডমিনোর ওপর বা নিচের string-এর শেষাংশ, আর ডমিনো সসীম, তাই অবস্থা সসীম; BFS তাই সবসময় থামে, আর match পেলে গ্রহণ, না পেলে বর্জন করে।” কোন বাক্যটি ভুল? একটি নির্দিষ্ট instance দিয়ে দেখান।

    ভুল বাক্য: “বাড়তি অংশ সবসময় কোনো ডমিনোর string-এর শেষাংশ”। বাড়তি অংশ জমতে থাকে: পিছিয়ে থাকা লাইন যদি আগের বাড়তি অংশের শুধু শুরুটুকু মেলায়, বাকিটার সঙ্গে নতুন ডমিনোর বাড়তি অংশ জুড়ে যায়।

    উদাহরণ: {[aa/a], [a/aa]}-এ ক্রম 1, 1, 1, … নিলে m টি ডমিনোর পরে ওপর a2m, নিচ am: বাড়তি অংশ am, যার দৈর্ঘ্য সীমাহীন। (এই instance-এর match আছে, যেমন 1, 2, তাই BFS এখানে থামে, কিন্তু অবস্থার set অসীম।) যে instance-এ match নেই আর অবস্থা অসীম, সেখানে D চিরকাল চলে; বাস্তবে long4-এ BFS প্রায় ৮০ হাজার অবস্থা দেখে, আর x3-এ ৩০ লাখ অবস্থাতেও রায় নেই। আর কোনো সংশোধিত D-ও কাজ করবে না, কারণ উপপাদ্য ৪.২ অনুযায়ী PCP undecidable.

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রম“CFG ambiguous কি না” প্রশ্নটি undecidable, এই প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Diagonalization দিয়ে ATM undecidable প্রমাণ
  2. Computation history থেকে ডমিনো বানিয়ে ATM ≤m MPCP
  3. ⋆ কৌশলে MPCP ≤m PCP
  4. রসিদ-চিহ্নের grammar দিয়ে PCP ≤m AMBIGCFG
  5. দিকের নিয়মে সিদ্ধান্ত: AMBIGCFG undecidable

একটি PCP instance-এ দুটি ডমিনো: ডমিনো ১ = [ab/a], ডমিনো ২ = [b/bb]. নিচের কোন সূচক-ক্রম একটি match?

  • 1
  • 1, 2
  • 2, 1
  • 1, 1

Post correspondence problem (PCP) সম্পর্কে কোন বিবৃতিটি সঠিক?

  • PCP decidable, কারণ প্রতিটি instance-এ ডমিনো সসীম
  • PCP recognizable-ও নয়
  • PCP recognizable, কিন্তু তার complement recognizable নয়
  • PCP-র complement recognizable, কিন্তু PCP নিজে নয়

“CFG ambiguous কি না” undecidable প্রমাণ করতে কোন reduction দেখাতে হয়? (A ≤m B মানে A-কে B-তে reduce করা।)

  • PCP ≤m AMBIGCFG
  • AMBIGCFG ≤m PCP
  • AMBIGCFG ≤m CFG membership
  • CFG emptiness ≤m AMBIGCFG

Modified PCP (MPCP) সাধারণ PCP থেকে কোথায় আলাদা?

  • MPCP-তে প্রতিটি ডমিনো বড়জোর একবার ব্যবহার করা যায়
  • MPCP-তে ঠিক দুটি ডমিনো থাকে
  • MPCP-তে match-এর দৈর্ঘ্যের একটি সীমা দেওয়া থাকে
  • MPCP-তে match-কে তালিকার প্রথম ডমিনো দিয়ে শুরু হতে হয়

G, G1, G2 context-free grammar আর w একটি string. নিচের কোন প্রশ্নটি decidable?

  • G ambiguous কি না
  • L(G) ফাঁকা কি না
  • L(G1) ∩ L(G2) ফাঁকা কি না
  • L(G1) = L(G2) কি না

PCP-র কোন রূপটি undecidable বলে প্রমাণিত?

  • এক অক্ষরের alphabet {a}-এর ওপর PCP
  • ঠিক দুটি ডমিনোর PCP
  • দুই অক্ষরের alphabet {0, 1}-এর ওপর PCP
  • দৈর্ঘ্যের সীমা K দেওয়া bounded PCP

একটি PCP instance-এ তিনটি ডমিনো: [abc/ab], [ca/a], [acc/ba]. এর match সম্পর্কে কী বলা যায়?

  • কোনো match নেই, কারণ প্রতিটি ডমিনোর ওপর নিচের চেয়ে লম্বা
  • ডমিনো ১ একাই একটি match
  • PCP undecidable, তাই এই instance সম্পর্কে কিছু বলা যায় না
  • ক্রম 1, 2 একটি match

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. PCP: ডমিনো [ti/bi]-এর এমন অ-ফাঁকা ক্রম আছে কি, যাতে ওপরের আর নিচের লেখা এক? পুনরাবৃত্তি চলে, দৈর্ঘ্যের সীমা নেই।
  2. PCP recognizable (সব ক্রম খোঁজা), কিন্তু undecidable; তাই “সমাধান নেই” recognizable-ও নয়। BFS-এর CAP মানে রায় নেই।
  3. ATM ≤m MPCP: ডমিনোর match = গ্রহণকারী computation history; MPCP ≤m PCP: ⋆ কৌশল।
  4. GA: A → ti A di ∣ ti di আর GB থেকে CFG-এর ambiguity, ছেদ-শূন্যতা, universality আর equivalence undecidable; প্রতিটি reduction PCP (বা তার complement) থেকে শুরু।
  5. Bounded PCP, এক অক্ষরের PCP আর দুই ডমিনোর PCP decidable; পাঁচ ডমিনোতে undecidable; তিন-চার অজানা।

পরের পর্বে: বাস্তবে undecidability: static analysis tool কেন মিথ্যা সতর্কবার্তা দেয়, Wang tile দিয়ে তল ভরাট, Hilbert-এর দশম সমস্যা, আর Busy Beaver function, যার পঞ্চম মান মাত্র ২০২৪ সালে প্রমাণিত হয়েছে।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান