Turing machine-এর পরিচয় — computability আর halting problem

১ · ফিতা, মাথা আর নিয়মের টেবিল — Turing machine কী

পর্ব ৭৩ “Grammar আর formal language — BNF থেকে Chomsky-র শ্রেণি”-তে language মানে Σ*-এর একটি subset, আর পর্ব ৭৪ “Finite automaton আর regular expression-এর পরিচয়”-তে সসীম স্মৃতির যন্ত্র। এখানে স্মৃতিকে অসীম করে জিজ্ঞেস করি: তাহলেও কি কিছু অসম্ভব থাকে? পুরো তত্ত্ব থাকবে পরিকল্পিত Theory of Computation কোর্সে; এখানে discrete math-এর দৃষ্টিতে সংজ্ঞা, ছোট উপপাদ্য আর প্রমাণ।

δ(q, a) = (p, b, R) পড়ুন এভাবে: “অবস্থা q-তে মাথার নিচে a থাকলে সেখানে b লিখুন, মাথা এক ঘর ডানে নিন, অবস্থা p-তে যান।” ফিতা দুই দিকেই অসীম (শুধু ডানে অসীম ফিতার সংস্করণও ক্ষমতায় সমান, §৪), শুরুতে ইনপুট w লেখা, বাকি সব ঘর ফাঁকা, মাথা প্রথম চিহ্নে। সুবিধার জন্য আমরা একটি প্রথা নেব: কোনো (q, a)-এর নিয়ম লেখা না থাকলে যন্ত্র সরাসরি q_rej-এ যায়।

ফলাফল তিন রকম: গ্রহণ, বর্জন, অথবা কখনো না থামা। Finite automaton ইনপুট ফুরালেই থামে; Turing machine ফিরে আসতে আর লিখতে পারে, তাই চিরকাল ঘুরতেও পারে। এই তৃতীয় সম্ভাবনাই পরের সব কঠিন প্রশ্নের উৎস। নিচের ছবিতে §২-এর binary increment যন্ত্রটি চলার মাঝপথে।

২ · প্রথম যন্ত্র — binary increment আর unary যোগ

বাজারঘরের অর্ডার নম্বর binary-তে রাখা হয়; নতুন অর্ডার এলে নম্বরে এক যোগ করতে হয়। হাতে আমরা যা করি: ডান দিক থেকে শুরু, 1 পেলে 0 লিখে হাতে এক রেখে বাঁয়ে যাই, 0 পেলে 1 লিখে থামি। যন্ত্রকে প্রথমে ডান প্রান্তে পৌঁছাতে হয়, কারণ সে শুরু করে বাঁ প্রান্ত থেকে। পুরো নিয়মের টেবিল:

1start: [q0] 10112q0: 0→0,R  1→1,R3q0: _→_,L  goto q14q1: 1→0,L  (carry)5q1: 0→1,L  goto acc

দৈর্ঘ্য n আর শেষে পরপর k-টি 1 থাকলে যন্ত্র n ধাপে ডানে যায়, ১ ধাপে ফেরে, k ধাপে carry টানে, ১ ধাপে শেষ 1 বসায়: মোট n + k + 2; 1011-এ 4 + 2 + 2 = 8. (দৈর্ঘ্য ১ থেকে ৮-এর সব ইনপুটে scratch script-এ সূত্রটি মেলানো।)

1. q0-এর অংশ শুধু ডানে সরে, কিছু বদলায় না, আর n ধাপ পর ফাঁকা ঘর পায়; তখন মাথা শেষ অঙ্কে আর অবস্থা q1. — নিয়মের টেবিল
2. Loop invariant (পর্ব ১৩): মাথা যে ঘরে, তার স্থানীয় মান 2^j হলে (ডানের j-টি অঙ্ক প্রক্রিয়া হয়েছে), “ফিতার সংখ্যা + 2^j = val(w) + 1”. শুরুতে j = 0, ফিতায় w, তাই val(w) + 1 = val(w) + 1. — ভিত্তি
3. q1-এ 1 পড়লে 0 লেখা হয়: ফিতার সংখ্যা 2^j কমে, আর j এক বাড়ে, তাই নতুন যোগফল (আগের − 2^j) + 2^j+1 = আগের + 2^j, invariant টিকে থাকে। — সংরক্ষণ
4. q1-এ 0 বা ফাঁকা পড়লে 1 লেখা হয়: ফিতার সংখ্যা 2^j বাড়ে, আর invariant থেকে তা ঠিক val(w) + 1; যন্ত্র গ্রহণ করে। — শেষ অবস্থা
5. q1-এর প্রতিটি ধাপে মাথা বাঁয়ে সরে, আর w-এর বাঁয়ে ফাঁকা ঘর আছে (ফিতা দুই দিকে অসীম), তাই বড়জোর n + 1 ধাপে 0 বা ফাঁকা মিলবেই। যন্ত্র থামে। ∎ — সীমিত ঘর

দ্বিতীয় যন্ত্রটি আরও সরল। Unary লেখায় m সংখ্যাটি m-টি 1: 3 = 111. ইনপুট 1^m+1ⁿ থেকে 1^m+n বানাতে + চিহ্নকে 1 করে দিন, তারপর ডান প্রান্তে গিয়ে শেষ 1টি মুছে দিন। এর জন্য পাঁচটি নিয়মই যথেষ্ট (নিচের কোডে ADD নামের টেবিল)।

নিচের ব্লক একটি ছোট simulator লেখে, যা প্রতিটি configuration ছাপে, তারপর দুই যন্ত্রকে সব ছোট ইনপুটে মেলায়। পরের ব্লক এই simulator-ই আবার ব্যবহার করে, তাই আগে এটি চালান। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product
def show(tape, pos, q):                   # configuration u[q]v
    lo, hi = min(min(tape), pos), max(max(tape), pos)
    cells = "".join(tape.get(i, "_") for i in range(lo, hi + 1))
    return cells[:pos - lo] + "[" + q + "]" + cells[pos - lo:]
def run(delta, w, cap=10_000, trace=False):
    tape, pos, q, steps = dict(enumerate(w or "_")), 0, "q0", 0
    while q not in ("acc", "rej") and steps < cap:
        if trace: print("  ", show(tape, pos, q))
        key = (q, tape.get(pos, "_"))
        if key not in delta:              # no rule: the machine rejects
            q = "rej"; break
        q, tape[pos], move = delta[key]
        pos += 1 if move == "R" else -1
        steps += 1
    if trace: print("  ", show(tape, pos, q))
    return q, "".join(tape[i] for i in sorted(tape)).strip("_"), steps
INC = {("q0", "0"): ("q0", "0", "R"), ("q0", "1"): ("q0", "1", "R"),
       ("q0", "_"): ("q1", "_", "L"), ("q1", "1"): ("q1", "0", "L"),
       ("q1", "0"): ("acc", "1", "L"), ("q1", "_"): ("acc", "1", "L")}
ADD = {("q0", "1"): ("q0", "1", "R"), ("q0", "+"): ("q1", "1", "R"),
       ("q1", "1"): ("q1", "1", "R"), ("q1", "_"): ("q2", "_", "L"),
       ("q2", "1"): ("acc", "_", "L")}
print("binary increment on 1011:")
print(run(INC, "1011", trace=True))
print("unary 3 + 2 on 111+11:")
print(run(ADD, "111+11", trace=True))
inputs = ["".join(b) for n in range(1, 11) for b in product("01", repeat=n)]
ok_inc = all(int(run(INC, w)[1], 2) == int(w, 2) + 1 for w in inputs)
ok_add = all(run(ADD, "1" * m + "+" + "1" * n)[1] == "1" * (m + n)
             for m in range(10) for n in range(10))
print("increment correct on all", len(inputs), "inputs of length 1..10:", ok_inc)
print("addition correct for all 100 pairs m, n < 10:", ok_add)

binary increment on 1011:
   [q0]1011
   1[q0]011
   10[q0]11
   101[q0]1
   1011[q0]_
   101[q1]1_
   10[q1]10_
   1[q1]000_
   [acc]1100_
('acc', '1100', 8)
unary 3 + 2 on 111+11:
   [q0]111+11
   1[q0]11+11
   11[q0]1+11
   111[q0]+11
   1111[q1]11
   11111[q1]1
   111111[q1]_
   11111[q2]1_
   1111[acc]1__
('acc', '11111', 8)
increment correct on all 2046 inputs of length 1..10: True
addition correct for all 100 pairs m, n < 10: True

৩ · aⁿbⁿcⁿ — আঁকাবাঁকা পথে দাগ দেওয়ার যন্ত্র

পর্ব ৭৩-এ বলা হয়েছে, L = {aⁿbⁿcⁿ : n ≥ 0} context-free নয়, আর পর্ব ৭৪-এর pumping lemma দেখায় aⁿbⁿ-ও regular নয়। অর্থাৎ সসীম স্মৃতির যন্ত্র বা একটি stack-এর যন্ত্র এই ভাষা চিনতে পারে না। Turing machine পারে, কারণ সে ফিতায় দাগ দিয়ে “কাটা” রাখতে পারে। বাজারঘরের ভাষায়: সমান সংখ্যক বাক্স (a), রসিদ (b) আর ডেলিভারি স্লিপ (c) আছে কি না, প্রতিটি থেকে একটি করে টিক দিয়ে মেলানো।

কৌশল: প্রথম না-কাটা a-কে X করুন, ডানে গিয়ে প্রথম না-কাটা b-কে Y, আরও ডানে প্রথম না-কাটা c-কে Z, তারপর বাঁয়ে X পর্যন্ত ফিরে আসুন। আবার শুরু। যখন X-এর পরে আর a নেই, শুধু Y আর Z আছে কি না দেখে নিন।

অন্য যেকোনো (অবস্থা, চিহ্ন)-এ নিয়ম নেই, তাই বর্জন। যেমন q1 b খুঁজতে গিয়ে c বা ফাঁকা পেলে, বা q4 কোনো a, b, c পেলে।

1q0: a→X,R  goto q12q1: skip a,Y; b→Y,R3q2: skip b,Z; c→Z,L4q3: back to X; X→q05q0: Y→Y,R  goto q46q4: skip Y,Z; _→acc

1. (থামা) প্রতিটি পূর্ণ দফা তিনটি না-কাটা চিহ্ন কমায়, আর দফার ভেতরে মাথা ইনপুট-অংশের বাইরে এক ঘরের বেশি যায় না; q4 শুধু ডানে যায়। তাই সসীম ধাপে থামে। — কমতে থাকা পরিমাণ (পর্ব ১৩-এর variant)
2. (গ্রহণ ⇒ L-এ আছে) দফা i শুরুর আগে invariant: ফিতা Xⁱ a^p Yⁱ b^q Zⁱ c^r আকারের, যেখানে a^i+pb^i+qc^i+r = w. ভিত্তি i = 0-এ ফিতা w-ই, যদি w-এ a, b, c ক্রম মেনে আসে; ক্রম ভাঙলে কোনো এক দফায় q1 বা q2 অপ্রত্যাশিত চিহ্নে আটকে বর্জন করে। — invariant
3. q0 গ্রহণ করে শুধু দুইভাবে: ফাঁকা দেখে (w = ε, n = 0), অথবা Y দেখে q4-এ গিয়ে শেষে ফাঁকা পেয়ে। দ্বিতীয় ক্ষেত্রে p = 0, আর q4 কোনো b বা c পায়নি, তাই q = r = 0; ফলে w = aⁱbⁱcⁱ. — শেষ অবস্থার বিশ্লেষণ
4. (L-এ আছে ⇒ গ্রহণ) w = aⁿbⁿcⁿ হলে প্রতিটি দফায় একটি করে a, b, c পাওয়া যায়, n দফা পর ফিতা XⁿYⁿZⁿ, আর q0 → q4 → গ্রহণ। ∎ — n-এর ওপর induction

যে যন্ত্র প্রতিটি ইনপুটে থামে, সে decider; উপপাদ্য ৩.১ অনুযায়ী L একটি decidable language. ধাপ কয়টি? প্রতিটি দফায় মাথা বড়জোর পুরো ইনপুটের ওপর একবার যায় আর ফেরে, আর দফা n-টি, তাই ধাপের সংখ্যা O(n²). নিচের ব্লক যাচাই করে, আর দেখায় যে মাপা সংখ্যাগুলো ঠিক 4n² + 3n + 1 সূত্রে বসে।

ABC = {("q0", "_"): ("acc", "_", "R"), ("q0", "a"): ("q1", "X", "R"),
       ("q0", "Y"): ("q4", "Y", "R"),
       ("q1", "a"): ("q1", "a", "R"), ("q1", "Y"): ("q1", "Y", "R"),
       ("q1", "b"): ("q2", "Y", "R"),
       ("q2", "b"): ("q2", "b", "R"), ("q2", "Z"): ("q2", "Z", "R"),
       ("q2", "c"): ("q3", "Z", "L"),
       ("q3", "X"): ("q0", "X", "R"),
       ("q4", "Y"): ("q4", "Y", "R"), ("q4", "Z"): ("q4", "Z", "R"),
       ("q4", "_"): ("acc", "_", "R")}
for s in "abYZ":                          # q3 walks left over these
    ABC[("q3", s)] = ("q3", s, "L")
def in_lang(w):                           # the set-theoretic definition
    k = len(w) // 3
    return w == "a" * k + "b" * k + "c" * k
total = wrong = accepted = 0
for n in range(9):
    for t in product("abc", repeat=n):
        w = "".join(t); total += 1
        verdict = run(ABC, w)[0] == "acc"
        accepted += verdict
        wrong += verdict != in_lang(w)
print("strings of length 0..8:", total, " accepted:", accepted, " disagreements:", wrong)
for w in ["aabbcc", "aabbc", "abcabc", "acb"]:
    print(f"{w:7}", run(ABC, w))
print("steps on a^n b^n c^n, n = 0..6:",
      [run(ABC, "a" * n + "b" * n + "c" * n)[2] for n in range(7)])

strings of length 0..8: 9841  accepted: 3  disagreements: 0
aabbcc  ('acc', 'XXYYZZ', 23)
aabbc   ('rej', 'XXYYZ', 13)
abcabc  ('rej', 'XYZabc', 7)
acb     ('rej', 'Xcb', 1)
steps on a^n b^n c^n, n = 0..6: [1, 8, 23, 46, 77, 116, 163]

৪ · Church–Turing thesis, অন্য রকম যন্ত্র আর universal machine

এত সরল যন্ত্র দিয়ে কি সব গণনা হয়? উত্তরটি একটি বিশ্বাস, যার পক্ষে প্রচুর প্রমাণ জমেছে।

Church–Turing thesis উপপাদ্য নয়, কারণ “স্পষ্ট যান্ত্রিক পদ্ধতি” একটি অনানুষ্ঠানিক ধারণা; গাণিতিক সংজ্ঞা ছাড়া কোনো কিছুর প্রমাণ হয় না। এর পক্ষে প্রমাণ হলো মিল: ১৯৩৬ সালে Alonzo Church-এর λ-calculus, প্রায় একই সময়ে Turing-এর যন্ত্র, Gödel ও Kleene-এর recursive function, Emil Post-এর পদ্ধতি, সবগুলো ঠিক একই ফাংশন গুনতে পারে বলে প্রমাণিত হয়েছে। আজকের ভাষায়: যেকোনো সাধারণ প্রোগ্রামিং ভাষা (অসীম মেমরি ধরে নিলে) Turing machine-এর সমান ক্ষমতার, যাকে বলে Turing-complete.

ক্ষমতায় সমান রূপভেদ

(ক)-এর ধারণা: k-টি ফিতাকে এক ফিতায় k-টি “ট্র্যাক” হিসেবে লিখুন, মাথাগুলো দাগ দিয়ে চিহ্নিত; এক ধাপ নকল করতে O(t) দৈর্ঘ্যের ব্যবহৃত অংশ একবার পড়ুন, মোট O(t²). (খ)-এর ধারণা: সব সম্ভাব্য পথ একটি গাছ, যাকে deterministic যন্ত্র স্তরে স্তরে (BFS) ঘোরে, যাতে অসীম শাখায় আটকে না যায়; শাখা গুণে বাড়ে, তাই সূচকীয় সময়। এই সূচকীয় ব্যবধান মুছে ফেলা যায় কি না, সেটাই §৮-এর P বনাম NP প্রশ্নের এক রূপ।

যন্ত্রও একটি string — universal machine

একটি যন্ত্রের নিয়মের টেবিল সসীম, তাই তাকে একটি string হিসেবে লেখা যায়; লেখা হয় ⟨M⟩. একটি সহজ পদ্ধতি: অবস্থা q_i-কে 0ⁱ, চিহ্ন নম্বর j-কে 0^j, L-কে 0, R-কে 00 লিখুন, আর প্রতিটি নিয়ম δ(q_i, s_j) = (q_k, s_l, D)-কে 0ⁱ1 0^j1 0^k1 0^l1 0^d লিখে নিয়মগুলো 11 দিয়ে জুড়ুন। ফলে প্রতিটি যন্ত্র {0, 1}*-এর একটি সদস্য। যন্ত্র আর তার ইনপুট একসঙ্গে লিখলে ⟨M, w⟩.

প্রমাণের ধারণা: U একটি ফিতায় ⟨M⟩, আরেকটিতে M-এর ফিতার নকল, তৃতীয়টিতে M-এর বর্তমান অবস্থা রাখে; প্রতি ধাপে টেবিলে মিলে যাওয়া নিয়মটি খুঁজে প্রয়োগ করে (উপপাদ্য ৪.১-ক দিয়ে এক ফিতায় নামানো যায়)। ওপরের Python-এর run ফাংশনও তা-ই করে। “প্রোগ্রামও ডেটা”, এই ধারণা interpreter আর stored-program কম্পিউটারের তাত্ত্বিক ভিত্তি।

৫ · Decidable আর recognizable — আর কেন বেশিরভাগ ভাষার কোনো যন্ত্র নেই

পার্থক্যটি দোকানের দুই ধরনের কর্মীর মতো। Decidable-এর কর্মী প্রতিটি প্রশ্নে একসময় “হ্যাঁ” বা “না” বলেন। Recognizable-এর কর্মী “হ্যাঁ” হলে একসময় বলবেন, কিন্তু “না” হলে হয়তো চিরকাল খুঁজতেই থাকবেন, আর আপনি কখনো নিশ্চিত হবেন না যে তিনি আর একটু পরে “হ্যাঁ” বলবেন না। প্রতিটি decidable language recognizable; উল্টোটি নয় (§৬)।

1. প্রতিটি যন্ত্র M-এর একটি সসীম বিবরণ ⟨M⟩ ∈ {0, 1}* (§৪)। আলাদা language-এর যন্ত্র আলাদা, তাই recognizable language-এর সেট থেকে {0, 1}*-এ একটি one-to-one ফাংশন আছে (প্রতিটি language-এর জন্য একটি যন্ত্রের বিবরণ বেছে নিন)। — encoding
2. {0, 1}* countable: দৈর্ঘ্য অনুযায়ী, তারপর অভিধানের ক্রমে সাজালে প্রতিটি string একটি স্বাভাবিক সংখ্যা পায় (পর্ব ১৮; পর্ব ৭৩-এ Σ*-এর জন্য একই যুক্তি)। তাই recognizable language countable-অনেক। — countable-এর subset
3. সব language-এর সেট হলো P(Σ*), Σ*-এর power set. Σ* countably infinite, তাই Cantor-এর উপপাদ্যে P(Σ*) uncountable. — পর্ব ১৮-এর উপপাদ্য ৬.১
4. একটি uncountable সেট তার countable subset-এর সমান হতে পারে না, তাই কিছু language recognizable নয়। ∎

পর্ব ১৮-এর §৮-এ এই যুক্তি “প্রোগ্রাম” দিয়ে বলা হয়েছিল। এটি শুধু অস্তিত্ব দেখায়। নির্দিষ্ট উদাহরণ পেতে সরাসরি Cantor-এর diagonal লাগে। নিচের ব্লক একটি সসীম টেবিলে কৌশলটি দেখায়: সারি i একটি language L_i, কলাম j একটি string s_j, আর ঘরে 1 মানে s_j ∈ L_i. কর্ণ উল্টে বানানো D প্রতিটি সারি থেকে অন্তত এক ঘরে আলাদা।

strings = ["", "0", "1", "00", "01", "10"]       # s0..s5 in shortlex order
languages = [                                   # L0..L5, each with a decider
    ("even length",   lambda s: len(s) % 2 == 0),
    ("starts with 1", lambda s: s[:1] == "1"),
    ("contains 0",    lambda s: "0" in s),
    ("palindrome",    lambda s: s == s[::-1]),
    ("all strings",   lambda s: True),
    ("empty set",     lambda s: False)]
n = len(strings)
table = [[int(f(s)) for s in strings] for _, f in languages]
print("column j: is s_j in L_i ?  (1 = yes)")
print(" " * 18 + "".join(f"{s or 'e':>4}" for s in strings))
for i, (name, _) in enumerate(languages):
    print(f"L{i} {name:<15}" + "".join(f"{b:>4}" for b in table[i]))
D = [1 - table[j][j] for j in range(n)]          # flip the diagonal
print(f"{'D = flipped diag':<18}" + "".join(f"{b:>4}" for b in D))
for i in range(n):
    print(f"D vs L{i}: column {i} has {table[i][i]} in L{i} but {D[i]} in D",
          "-> different" if D[i] != table[i][i] else "-> same?!")
print("D equals some row:", any(D == row for row in table))

column j: is s_j in L_i ?  (1 = yes)
                     e   0   1  00  01  10
L0 even length       1   0   0   1   1   1
L1 starts with 1     0   0   1   0   0   1
L2 contains 0        0   1   0   1   1   1
L3 palindrome        1   1   1   1   0   0
L4 all strings       1   1   1   1   1   1
L5 empty set         0   0   0   0   0   0
D = flipped diag     0   1   1   0   0   1
D vs L0: column 0 has 1 in L0 but 0 in D -> different
D vs L1: column 1 has 0 in L1 but 1 in D -> different
D vs L2: column 2 has 0 in L2 but 1 in D -> different
D vs L3: column 3 has 1 in L3 but 0 in D -> different
D vs L4: column 4 has 1 in L4 but 0 in D -> different
D vs L5: column 5 has 0 in L5 but 1 in D -> different
D equals some row: False

1. (⇒) L-এর decider M সবসময় থামে, তাই সে L-কে চেনে। M-এর গ্রহণ আর বর্জন অদলবদল করলে যে যন্ত্র পাই, সেটিও সবসময় থামে আর L̄-কে decide করে, তাই চেনে। — অবস্থা অদলবদল
2. (⇐) M₁ L-কে আর M₂ L̄-কে চেনে। নতুন যন্ত্র N ইনপুট w-এ পালা করে M₁-এর এক ধাপ, M₂-এর এক ধাপ চালায় (দুই ফিতায়)। — পাশাপাশি চালানো
3. w ∈ L অথবা w ∈ L̄, ঠিক একটি; তাই M₁ বা M₂-এর একটি সসীম ধাপে গ্রহণ করবে। N সেই মুহূর্তে থামে: M₁ গ্রহণ করলে গ্রহণ, M₂ গ্রহণ করলে বর্জন। — সসীম অপেক্ষা
4. N প্রতিটি ইনপুটে থামে আর ঠিক উত্তর দেয়, তাই L decidable. ∎

৬ · Halting problem — নিজের কোড নিজেকে খাওয়ালে কী হয়

বাজারঘরের ডেভেলপার দল একটি টুল চায়: যেকোনো প্রোগ্রাম আর ইনপুট দিলে বলবে “থামবে” বা “চিরকাল আটকে থাকবে”, যাতে চেকআউটের কোডে অসীম লুপের ভয় না থাকে। নিচের উপপাদ্য বলে, এমন টুল সম্ভব নয়।

1. বিরোধের জন্য ধরুন এমন H আছে: H(⟨M, w⟩) সবসময় থামে, আর “থামে” বলে ঠিক যখন M, w-তে থামে, নইলে “থামে না”। — অনুমান
2. H ব্যবহার করে নতুন যন্ত্র D বানান। ইনপুট ⟨M⟩ পেলে D চালায় H(⟨M, ⟨M⟩⟩), অর্থাৎ জিজ্ঞেস করে “M নিজের কোডে থামে কি?”। উত্তর “থামে” হলে D ইচ্ছা করে একটি অসীম লুপে ঢোকে; উত্তর “থামে না” হলে D সঙ্গে সঙ্গে থামে। — নির্মাণ
3. D একটি বৈধ যন্ত্র: H-কে একটি উপ-অংশ হিসেবে চালানো, একটি string নকল করা আর একটি লুপ, সবই যন্ত্রে করা যায়। তাই D-এরও একটি সসীম কোড ⟨D⟩ আছে। — H থাকলে D-ও থাকে
4. এখন D-কে তার নিজের কোড দিন: D(⟨D⟩). এটি H(⟨D, ⟨D⟩⟩)-কে জিজ্ঞেস করে “D নিজের কোডে থামে কি?” — নিজের ওপর প্রয়োগ
5. H যদি বলে “থামে”, তাহলে D লুপে ঢোকে, অর্থাৎ D(⟨D⟩) থামে না; H ভুল। H যদি বলে “থামে না”, তাহলে D থামে; H আবার ভুল। H-এর আর কোনো উত্তর নেই, কারণ সে সবসময় থামে। — দুই ক্ষেত্র
6. দুই ক্ষেত্রেই ধাপ ১-এর অনুমানের বিরোধ। তাই H নেই, HALT undecidable. ∎ — বিরোধ দিয়ে প্রমাণ

1assume H(M, w) always answers2def D(M):3  if H(M, M) == "halts": loop forever4  else: halt5run D(D)6both cases fail: no such H

“নিজের কোড নিজেকে খাওয়ানো” রহস্য নয়: ⟨D⟩ একটি সসীম string. আর প্রমাণ বলে না যে কোনো নির্দিষ্ট প্রোগ্রামের থামা বোঝা অসম্ভব; বলে, সব প্রোগ্রামের জন্য একটিমাত্র নির্ভুল পদ্ধতি নেই।

প্রমাণ: universal machine U দিয়ে M-কে w-তে চালান; M থামলে (গ্রহণ বা বর্জন যেভাবেই) গ্রহণ করুন। M থামলে এটি গ্রহণ করে, না থামলে চিরকাল চলে, ঠিক recognizable-এর সংজ্ঞা। এখন complement-ও recognizable হলে উপপাদ্য ৫.৩ অনুযায়ী HALT decidable হতো, যা উপপাদ্য ৬.১-এর বিরোধী। ∎

৭ · Reduction, Rice-এর উপপাদ্য আর সফটওয়্যারের সীমা

একটি undecidable সমস্যা হাতে পেলে আরও অনেক পাওয়া যায়, প্রতিবার নতুন diagonal ছাড়াই। কৌশলটির নাম reduction: “B সমাধান করতে পারলে A-ও পারতাম; A অসম্ভব, তাই B-ও অসম্ভব।”

লেমার প্রমাণ এক লাইনের: A-র decider = “x থেকে f(x) গুনুন, তারপর B-এর decider চালান”; দুটি অংশই থামে, আর উত্তর ঠিক, কারণ x ∈ A ⇔ f(x) ∈ B. ∎ দিক গুলিয়ে ফেলা খুব সাধারণ ভুল: জানা কঠিন সমস্যা A থেকে নতুন সমস্যা B-তে reduce করতে হয়, উল্টো নয়।

1. HALT ≤_m HELLO দেখাব। ⟨M, w⟩ থেকে প্রোগ্রাম P_M,w বানান: “M-কে w-তে নকল করো, এর মধ্যে M যা কিছু ছাপতে চায় তা চেপে রাখো (ছেপো না); M থামলে hello ছাপো।” — নির্মাণ
2. এই রূপান্তর যান্ত্রিক: ⟨M⟩ আর w-কে একটি নির্দিষ্ট ছাঁচে বসানো মাত্র, P_M,w-কে চালাতে হয় না। তাই f(⟨M, w⟩) = ⟨P_M,w⟩ গণনাযোগ্য আর সবসময় থামে। — f গণনাযোগ্য
3. M, w-তে থামলে P_M,w hello ছাপে। না থামলে P_M,w নকলেই আটকে থাকে, আর ছাপার সব চেষ্টা চেপে রাখা হয়েছে, তাই কখনো hello ছাপে না। অর্থাৎ ⟨M, w⟩ ∈ HALT ⇔ ⟨P_M,w⟩ ∈ HELLO. — শর্ত মিলল
4. HELLO decidable হলে লেমা ৭.২ অনুযায়ী HALT decidable হতো, যা উপপাদ্য ৬.১-এর বিরোধী। ∎

ধাপ ১-এর “চেপে রাখা” অংশটি ভুলে গেলে প্রমাণ ভাঙে: M নিজেই hello ছাপতে পারত, থামুক বা না থামুক। একই ছাঁচে “দুটি প্রোগ্রাম কি সব ইনপুটে একই ফল দেয়?” ধরনের বহু প্রশ্ন undecidable; সাধারণ রূপটি নিচে।

Henry Gordon Rice ১৯৫০-এর দশকের শুরুতে (প্রকাশ ১৯৫৩ সালে বলে উল্লেখিত) এটি প্রমাণ করেন; প্রমাণটি ঠিক উপপাদ্য ৭.৩-এর ছাঁচে HALT থেকে reduction. কিন্তু শর্তগুলো খেয়াল করুন। ধর্মটি যন্ত্রের language-এর, কোডের চেহারার নয়: “M-এ ১০টির বেশি অবস্থা আছে কি?” decidable, কারণ টেবিল গুনলেই হয়। “M প্রথম ১০০ ধাপে থামে কি?” decidable, কারণ ১০০ ধাপ চালালেই হয়।

সফটওয়্যারের জন্য মানে

যেকোনো Turing-complete ভাষার প্রোগ্রামের জন্য একটি “নিখুঁত” টুল, যা সবসময় থামে, কখনো ভুল সতর্কবার্তা দেয় না আর কোনো আসল সমস্যা বাদ দেয় না, এমন termination checker, bug-finder বা virus detector সম্ভব নয়: “চিরকাল চলে”, “শূন্য দিয়ে ভাগ করে”, “ক্ষতিকর কাজ করে” সবই অতুচ্ছ আচরণগত ধর্ম। Virus সনাক্তকরণ সাধারণভাবে undecidable, এই ফল ১৯৮০-এর দশকে Fred Cohen-এর কাজে আসে বলে উল্লেখ করা হয়।

তবু বাস্তবের টুল কাজ করে, কারণ তারা ছাড় নেয়: “জানি না” উত্তরের অনুমতি, সন্দেহ হলেই সতর্ক করা (কিছু মিথ্যা সতর্কবার্তাসহ), বা সীমিত ভাষা ও সীমিত সময়। আর একটি নির্দিষ্ট প্রোগ্রামের জন্য মানুষের লেখা loop invariant আর variant (পর্ব ১৩) দিয়ে সঠিকতা আর থামা প্রমাণ করা যায়; Rice তা নিষেধ করে না। পর্ব ৭৭ “SAT আর SMT solver — discrete math দিয়ে software যাচাই”-এ এমন যন্ত্র-সহায়ক যাচাই দেখা যাবে, যা formal verification-এর অংশ।

৮ · Busy beaver আর জটিলতার এক ঝলক — P, NP

Halting problem-এর একটি সংখ্যাগত রূপ আছে। n-টি অবস্থা (থামার অবস্থা বাদে) আর চিহ্ন {0, 1}-এর যেসব যন্ত্র ফাঁকা ফিতায় শুরু করে একসময় থামে, তাদের মধ্যে সবচেয়ে বেশি ধাপ যে নেয়, সেই ধাপ-সংখ্যা S(n); আর থামার সময় ফিতায় সবচেয়ে বেশি যতটি 1 থাকে, তা Σ(n). এদের নাম busy beaver ফাংশন, Tibor Radó ১৯৬২ সালে প্রস্তাব করেন। প্রতিটি n-এ S(n) একটি নির্দিষ্ট সংখ্যা, তবু:

1. বিরোধের জন্য ধরুন S গণনাযোগ্য। “n-অবস্থার যন্ত্র M ফাঁকা ফিতায় থামে কি?” প্রশ্নটি এভাবে decide করুন: S(n) গুনুন, তারপর M-কে S(n) ধাপ চালান। — অনুমান
2. এর মধ্যে থামলে উত্তর “থামে”। না থামলে, S(n)-এর সংজ্ঞা অনুযায়ী কোনো থামা n-অবস্থার যন্ত্র এর বেশি ধাপ নেয় না, তাই M কখনো থামবে না। — S-এর সংজ্ঞা
3. ফলে ফাঁকা ফিতার halting problem decidable হতো। কিন্তু সেটি undecidable (⟨M, w⟩ থেকে “আগে w লিখে তারপর M চালাও” যন্ত্র বানিয়ে HALT থেকে reduction করা যায়)। বিরোধ। ∎

আসলে আরও বেশি সত্য: S যেকোনো গণনাযোগ্য ফাংশনের চেয়ে শেষমেশ দ্রুত বাড়ে। জানা মান (Radó-এর প্রথায়, শেষের থামার ধাপসহ গোনা): S(1) = 1, S(2) = 6, S(3) = 21, S(4) = 107; Σ(1) = 1, Σ(2) = 4, Σ(3) = 6, Σ(4) = 13. S(5) = 47,176,870 আর Σ(5) = 4098, যা ২০২৪ সালে bbchallenge নামের অনলাইন সহযোগী দলের কাজে প্রমাণিত, আর Coq নামের proof assistant-এ যন্ত্রে যাচাই করা হয়েছে বলে জানা যায়। S(6) অজানা; শুধু জানা যে এটি কল্পনাতীত বড়। নিচের ব্লক n = 2-এর সব যন্ত্র গুনে S(2) আর Σ(2) বের করে।

from itertools import product
from collections import Counter
# one action = (symbol to write, head move, next state); H means halt
actions = [(w, m, nxt) for w in (0, 1) for m in (-1, 1) for nxt in "ABH"]
keys = [("A", 0), ("A", 1), ("B", 0), ("B", 1)]
CAP = 50                        # we stop watching a machine after 50 steps
best_ones = halted = 0
by_steps = Counter(); champion = (0, 0, None)
for table in product(actions, repeat=4):
    rule = dict(zip(keys, table))
    tape, pos, q, steps = {}, 0, "A", 0
    while q != "H" and steps < CAP:
        write, move, q = rule[(q, tape.get(pos, 0))]
        tape[pos] = write; pos += move; steps += 1
    if q == "H":
        halted += 1; by_steps[steps] += 1
        ones = sum(tape.values())
        best_ones = max(best_ones, ones)
        if (steps, ones) > champion[:2]:
            champion = (steps, ones, table)
total = len(actions) ** 4
print("2-state, 2-symbol machines:", total)
print("halted within", CAP, "steps:", halted, " still running:", total - halted)
print("halting machines by step count:", sorted(by_steps.items()))
print("max steps S(2) =", max(by_steps), "  max ones Sigma(2) =", best_ones)
print("a champion (steps, ones, rules for A0 A1 B0 B1):", champion)
for n in (1, 2, 3, 4):
    print(f"n = {n} states: (4(n+1))^(2n) = {(4 * (n + 1)) ** (2 * n):,} machines")

2-state, 2-symbol machines: 20736
halted within 50 steps: 9784  still running: 10952
halting machines by step count: [(1, 6912), (2, 2304), (3, 384), (4, 128), (5, 16), (6, 40)]
max steps S(2) = 6   max ones Sigma(2) = 4
a champion (steps, ones, rules for A0 A1 B0 B1): (6, 4, ((1, -1, 'B'), (1, 1, 'B'), (1, 1, 'A'), (1, -1, 'H')))
n = 1 states: (4(n+1))^(2n) = 64 machines
n = 2 states: (4(n+1))^(2n) = 20,736 machines
n = 3 states: (4(n+1))^(2n) = 16,777,216 machines
n = 4 states: (4(n+1))^(2n) = 25,600,000,000 machines

গণনাযোগ্যের ভেতরে: সময়ের প্রশ্ন

Decidable হলেই কাজের নয়: 2ⁿ ধাপের decider n = 100-এ কার্যত কখনো শেষ হবে না। P হলো সেই language-গুলো, যাদের একটি deterministic Turing machine polynomial time-এ, অর্থাৎ কোনো স্থির k-এর জন্য O(n^k) ধাপে decide করে; §৩-এর aⁿbⁿcⁿ (O(n²)) তার একটি। NP হলো যাদের প্রতিটি “হ্যাঁ” উত্তরের একটি ছোট সাক্ষী (certificate) polynomial time-এ যাচাই করা যায়; সমতুল্যভাবে, nondeterministic যন্ত্র polynomial time-এ চেনে। Hamilton cycle (পর্ব ৬০) আর 3-colouring (পর্ব ৬৩) NP-তে আছে।

Stephen Cook ১৯৭১ সালে এটি প্রকাশ করেন, আর Leonid Levin স্বাধীনভাবে প্রায় একই ফল পান (প্রকাশ ১৯৭৩)। মূল ধারণা: যন্ত্রের পুরো চলাকে configuration-এর টেবিল হিসেবে লিখে “প্রতিটি সারি আগেরটি থেকে একটি নিয়মে আসে” শর্তকে CNF clause দিয়ে বাঁধা। P = NP কি না, তা আজও অজানা। SAT আর NP-completeness-এর ব্যবহারিক দিক পর্ব ০৭-এ দেখেছেন, পর্ব ৭৭-এ আরও গভীরে যাবেন, আর reduction-এর অ্যালগরিদমিক দিক DSA কোর্সের পর্ব ৬৪-এ।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: increment যন্ত্রের trace

§২-এর যন্ত্রে ইনপুট 111. সব configuration লিখুন, ফলাফল আর ধাপ-সংখ্যা বলুন।

1. ডানে যাত্রা: [q0]111 → 1[q0]11 → 11[q0]1 → 111[q0]_ (৩ ধাপ)।
2. ফেরা: 11[q1]1 (৪); carry: 1[q1]10 (৫), [q1]100 (৬), তারপর বাঁয়ের ফাঁকা ঘরে [q1]_000 (৭)।
3. ফাঁকা পেয়ে 1 লেখে, গ্রহণ: ফিতায় 1000 (7 + 1 = 8), মোট ৮ ধাপ; সূত্রে n + k + 2 = 3 + 3 + 2 = 8. (scratch script-এ trace মেলানো।)

অঙ্ক ২: যন্ত্রের সংখ্যা

n-টি অবস্থা (থামা বাদে), চিহ্ন {0, 1}, প্রতিটি নিয়মে লেখা চিহ্ন, L/R আর পরের অবস্থা (n-টির একটি বা থামা)। কয়টি আলাদা নিয়মের টেবিল?

1. (অবস্থা, চিহ্ন) জোড়া 2n-টি। প্রতিটির জন্য 2 × 2 × (n + 1) = 4(n + 1)টি পছন্দ। — গুণের নিয়ম
2. মোট (4(n + 1))²ⁿ. n = 1: 8² = 64; n = 2: 12⁴ = 20,736; n = 3: 16⁶ = 16,777,216 (§৮-এর ব্লকে মেলানো)।

অঙ্ক ৩: শ্রেণিবিভাগ

প্রতিটি language decidable, শুধু recognizable, নাকি recognizable-ও নয়? (ক) {aⁿbⁿcⁿ}; (খ) {⟨M⟩ : M ফাঁকা ফিতায় ১০০ ধাপের মধ্যে থামে}; (গ) HALT; (ঘ) HALT-এর complement.

1. (ক) decidable: §৩-এর decider. (খ) decidable: ১০০ ধাপ চালিয়ে দেখলেই হয়, সীমা নির্দিষ্ট।
2. (গ) recognizable, decidable নয়: উপপাদ্য ৬.১ আর ৬.২. (ঘ) recognizable নয়: অনুসিদ্ধান্ত ৬.৩.

প্রমাণের ভুল ধরুন: “HALT-এর complement recognizable”

একজন লিখলেন: “যন্ত্র N: ইনপুট ⟨M, w⟩ পেলে M-কে w-তে চালাও। M থামলে বর্জন করো; M না থামলে গ্রহণ করো। তাই N ঠিক সেই ⟨M, w⟩ গ্রহণ করে যেখানে M থামে না। ∎”

ভুল কোথায়: “M না থামলে গ্রহণ করো” কোনো যন্ত্রের নিয়ম হতে পারে না। যন্ত্র প্রতিটি মুহূর্তে শুধু জানে M এখন পর্যন্ত থামেনি; “কখনো থামবে না” জানার কোনো মুহূর্ত আসে না। M না থামলে N-ও চিরকাল M-কে চালাতে থাকে, কখনো গ্রহণ করে না। তাই N আসলে কিছুই গ্রহণ করে না। অনুসিদ্ধান্ত ৬.৩ বলে কোনো সংশোধনেই এটি বাঁচবে না।

১০ · AI-এর যুগে — computability-র যুক্তি যাচাই

AI সহকারী halting problem-এর গল্প সুন্দর বলে, কিন্তু প্রমাণের সূক্ষ্ম জায়গায় আর trace-এ ভুল করে:

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

• Reduction-এর দিক ঠিক: জানা কঠিন সমস্যা থেকে নতুনটিতে
• প্রতিটি নির্মাণ করা যন্ত্র সত্যিই একটি সসীম নিয়মের যন্ত্র, কোনো “ভবিষ্যৎ জানা” ধাপ নেই
• উপপাদ্যের শর্ত (অতুচ্ছ, language-এর ধর্ম, সবসময় থামা) মিলিয়েছি
• Trace আর ধাপ-সংখ্যা নিজের simulator-এ চালিয়ে মিলেছে
• “সব ছোট ইনপুটে ঠিক” আর “প্রমাণিত” দুটিকে আলাদা রেখেছি
• সাল, নাম আর busy beaver-এর মান বিশ্বস্ত উৎসে মিলিয়েছি

মনে রাখুন, simulator “থামে” প্রমাণ করতে পারে, “কখনো থামে না” পারে না; সেটির জন্য সবসময় একটি যুক্তি লাগে।