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

Turing machine নকশা — ধাপে ধাপে উদাহরণ

Designing Turing Machines — Marking, Zig-zag, Shifting, Subroutines, Arithmetic on Tapes, Step Counting and Testing

Taught in Bangla, this lesson turns an algorithm in words into a Turing machine transition table using six techniques: crossing off, zig-zag, shifting the tape, extra tape symbols, remembering in states and subroutines. It designs binary increment, a palindrome machine, and unary addition and multiplication, then counts steps exactly, such as (n + 1)(n + 2)/2 for the palindrome machine. In-page Python (Pyodide) brute-forces every short input, and a real automata-lib 9.2.0 run confirms each machine.

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

  • High-level বর্ণনা থেকে implementation বর্ণনা হয়ে পূর্ণ transition table পর্যন্ত একটি TM নকশা করা
  • চিহ্ন দিয়ে কাটা, zig-zag, tape সরানো, বাড়তি চিহ্ন আর state-এ স্মৃতি রাখার কৌশল প্রয়োগ করা
  • Binary increment, unary যোগ, unary গুণ আর palindrome-এর TM বানিয়ে configuration ধরে trace করা
  • প্রতিটি যন্ত্রের ধাপ গুনে O(n) না O(n²), তা প্রমাণ করা আর Python-এ মেপে মেলানো
  • Step cap-সহ simulator আর brute force দিয়ে TM পরীক্ষা করা, আর AI-এর দেওয়া TM-এর ভুল ধরা

১ · নকশার ছক — কথার algorithm থেকে transition table

পর্ব ৪৩-এ Turing machine-এর সংজ্ঞা, configuration আর প্রথম দুটি যন্ত্র (anbncn আর {w#w}) দেখেছেন। এই পর্বের প্রশ্ন ব্যবহারিক: একটি নতুন সমস্যা হাতে পেলে যন্ত্রটি বানাবেন কীভাবে? DFA বা PDA-র মতো এখানে কোনো যান্ত্রিক রূপান্তর (subset construction বা grammar থেকে PDA) নেই। আছে কয়েকটি কৌশল, যা বারবার ফিরে আসে, আর একটি শৃঙ্খলা: আগে কথায় ভাবুন, তারপর চিহ্ন, তারপর সারণি। Tape আর head-এর সহজ পরিচয় ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৫-এ আছে।

পরীক্ষার হলে একজন পরিদর্শকের কথা ভাবুন। তাঁর হাতে লম্বা হাজিরা-খাতা, এক কলামে রোল নম্বর, পাশের কলামে উত্তরপত্রের নম্বর। তিনি একসঙ্গে পুরো খাতা মনে রাখতে পারেন না; আঙুল রেখে একটি ঘর দেখেন। প্রথম রোল দেখে পেনসিলে টিক দেন, তারপর আঙুল নিয়ে যান উত্তরপত্রের কলামে, মিলিয়ে সেখানেও টিক, তারপর ফিরে আসেন পরের টিক-না-দেওয়া রোলে। মাথায় রাখেন শুধু একটি ছোট তথ্য: “এখন কোন রোল খুঁজছি”। খাতা হলো tape, আঙুল হলো head, পেনসিলের টিক হলো চিহ্নিত চিহ্ন, আর মাথার ছোট তথ্যটি state. Turing machine-এর প্রায় সব নকশা এই পরিদর্শকের কাজের কোনো না কোনো রূপ।

এই মডিউলের রীতি (পর্ব ৪৩ থেকে)

M = (Q, Σ, Γ, δ, q0, qaccept, qreject), যেখানে Σ ⊆ Γ আর blank ␣ ∈ Γ \ Σ. δ: Q′ × Γ → Q × Γ × {L, R}, যেখানে Q′ হলো থামার দুটি state বাদে বাকি state. Tape ডানে অসীম, বাঁয়ে প্রথম ঘরে শেষ; প্রথম ঘরে থাকা অবস্থায় L বললে head সেখানেই থাকে (Sipser-এর রীতি)। ছবিতে “a → b, R” মানে a পড়ে b লিখে ডানে যাওয়া, আর “a → R” মানে কিছু না বদলে ডানে যাওয়া। Configuration লেখা হয় u q v: tape-এ uv, state q, head v-এর প্রথম চিহ্নে। সারণিতে কোনো নিয়ম না থাকলে যন্ত্র qreject-এ যায়: একে বলে implicit reject, আর এটি নকশাকে ছোট রাখে।

Sipser তিন স্তরের বর্ণনার কথা বলেন: high-level (algorithm কথায়, tape-এর খুঁটিনাটি ছাড়া), implementation (head কোথায় যায়, কোন ঘরে কী লেখে) আর formal (পূর্ণ δ). পরীক্ষায় প্রায়ই দ্বিতীয় বা তৃতীয় স্তর চাওয়া হয়। নকশার সময় তিনটিই ক্রমে লিখুন; ভুল সাধারণত এক স্তর থেকে পরের স্তরে যাওয়ার সময় ঢোকে। নিচের ছয়টি কৌশল প্রায় সব প্রশ্নে কাজ করে।

১. চিহ্ন দিয়ে কাটা

যে চিহ্ন হিসাবে ধরা হয়ে গেছে, তার জায়গায় X বা কোনো চিহ্নিত সংস্করণ লেখা। anbncn, {w#w} আর গুণ এভাবেই গোনে।

২. Zig-zag

একবার ডানে, একবার বাঁয়ে, প্রতিবার একটু ছোট অংশে। Palindrome-এ দুই প্রান্ত মুছে মুছে ভেতরে ঢোকা।

৩. Tape সরানো

মাঝখানে একটি ঘর ঢোকাতে বাকি সবকিছু এক ঘর ডানে ঠেলা। প্রতিটি ঘর পেরোনোর সময় আগের চিহ্নটি state-এ বয়ে নেওয়া।

৪. বাড়তি tape চিহ্ন

Γ যত ইচ্ছা বড় করা যায় (সসীম থাকলেই হলো): বিভাজক #, =, চিহ্নিত 0 আর 1 (এখানে O আর I), বাঁ প্রান্তের চিহ্ন।

৫. State-এ স্মৃতি

একটি সসীম তথ্য (একটি চিহ্ন, একটি carry বিট) state-এর নামে লুকিয়ে রাখা: qcarry=1, c0, c4. State-এর সংখ্যা গুণ হয়, কিন্তু সসীম থাকে।

৬. Subroutine

Copy, তুলনা, increment, “প্রথম ঘরে ফেরা”: ছোট যন্ত্র, একটি ঢোকার আর একটি বেরোনোর state দিয়ে বড় যন্ত্রে জোড়া।

Turing machine শুধু হ্যাঁ বা না বলে না, function-ও গণনা করে। সেই অর্থ পরিষ্কার করা দরকার, কারণ এই পর্বের অর্ধেক যন্ত্র “উত্তর লেখে”।

সংজ্ঞা ১.১ (Computable function)

একটি function f: Σ∗ → Σ∗ হলো computable, যদি এমন একটি TM M থাকে যে প্রতিটি input w-এ থামে আর থামার সময় tape-এ শুধু f(w) থাকে (বাকি সব ঘর ␣)। যেখানে f সংজ্ঞায়িত নয়, যেমন ভুল format-এর input, সেখানে M reject করতে পারে; তখন f-কে আংশিক (partial) function বলা হয়।

এই পর্বের দুটি যন্ত্রে (গুণ আর copy) “শুধু f(w)” শর্তে একটু ছাড় নেওয়া হয়েছে: চিহ্নিত ঘর বা বিভাজক রয়ে যায়, আর উত্তর থাকে একটি নির্দিষ্ট চিহ্নের ডানে। কেন পরিষ্কার করা কঠিন, সেটিও অংশ ৬-এ একটি শিক্ষা।

২ · প্রথম নকশা: binary increment আর বাঁ প্রান্তের ফাঁদ

সমস্যা: tape-এ একটি binary সংখ্যা w (সবচেয়ে গুরুত্বপূর্ণ বিট বাঁয়ে), যেমন 1011 = ১১. যন্ত্রকে লিখতে হবে w + 1, অর্থাৎ 1100 = ১২. বাজারঘরে প্রতিটি নতুন order-এর ক্রমিক নম্বর ঠিক এভাবে এক বাড়ে। High-level বর্ণনা স্কুলের যোগের মতো: ডানের শেষ বিট থেকে শুরু করুন; 1 পেলে 0 লিখে carry নিয়ে বাঁয়ে যান; 0 পেলে 1 লিখে থামুন।

প্রথম খসড়া (INC0). দুই state-এই হয়ে যায় বলে মনে হয়: q0-এ ডানে চলুন, ␣ পেলে বাঁয়ে ফিরে q1; q1-এ “1 → 0, L”, আর “0 → 1, R” বা “␣ → 1, R” দিয়ে qaccept. 1011-এ এটি ঠিক 1100 দেয়। কিন্তু 111-এ? Carry তিনটি 1-কে 0 বানায়, তারপর প্রথম ঘরে দাঁড়িয়ে L বলে। Sipser-এর রীতিতে head নড়ে না, পড়ে সদ্য লেখা 0, লেখে 1: ফল 100 = ৪, অথচ ঠিক উত্তর 1000 = ৮. যন্ত্রটি ভাবছিল প্রথম ঘরের বাঁয়ে একটি ␣ আছে; এক-দিকের tape-এ তা নেই। এটিই এই পর্বের প্রথম শিক্ষা: head প্রথম ঘরে আছে কি না, যন্ত্র নিজে জানে না; জানাতে হলে নকশায় ব্যবস্থা রাখতে হয়।

সমাধান: প্রথম ঘর চিহ্নিত করা। শুরুতেই প্রথম বিটটিকে একটি চিহ্নিত সংস্করণে বদলে দিন: 0 হলে O, 1 হলে I (বড় হাতের O আর I, দুটি বাড়তি tape চিহ্ন)। Carry বাঁয়ে যেতে যেতে O বা I পেলে যন্ত্র জানে, এটাই প্রথম ঘর। তখন তিনটি ক্ষেত্র: O-তে carry পৌঁছালে 1 লিখে শেষ; I-তে পৌঁছালে সব বিট ছিল 1, তাই উত্তর 1 আর তারপর n টি 0: প্রথম ঘরে 1 রেখে ডানে গিয়ে শেষে একটি 0 যোগ করুন; আর carry মাঝপথে কোনো 0-তে থামলে বাঁয়ে ফিরে চিহ্নটি মুছে আসল বিট ফিরিয়ে দিন। পূর্ণ যন্ত্র INC:

stateপড়া → লেখা, দিক, পরের stateকাজ
q00 → O, R, q1 · 1 → I, R, q1প্রথম ঘর চিহ্নিত
q10, 1 → R · ␣ → L, q2সংখ্যার শেষে যাওয়া
q21 → 0, L · 0 → 1, L, q3 · O → 1, R, qacc · I → 1, R, q4carry বাঁয়ে বয়ে নেওয়া
q30, 1 → L · O → 0, R, qacc · I → 1, R, qaccফিরে গিয়ে চিহ্ন মোছা
q40 → R · ␣ → 0, R, qaccসব 1 ছিল: শেষে একটি 0 যোগ

সারণিতে q0-এর ␣ নিয়ম নেই: ফাঁকা input কোনো সংখ্যা নয়, তাই যন্ত্র implicit reject করে। Γ = {0, 1, O, I, ␣}. নিচের ছবিতে একই যন্ত্র।

INC: চিহ্নিত প্রথম ঘর-সহ binary increment

প্রতিটি তীরে “পড়া → লেখা, দিক”. দুই দাগের বৃত্ত qacc; বাঁয়ের খোলা তীর start state q0-এ। যে নিয়ম আঁকা নেই, তা qreject-এ যায়।

Turing machine INC for binary increment with a marked first cell q0q1q2q3q4 qacc 0→O,R 1→I,R 0,1→R ␣→L 1→0,L 0→1,L 0,1→L I→1,R O→1,R O→0,R I→1,R 0→R ␣→0,R
ছবি ৪৪.১ — INC-এর তিনটি শেষ: carry O-তে পৌঁছায় (q2 → qacc), I-তে পৌঁছায় (q2 → q4, সব বিট 1 ছিল), বা মাঝপথে একটি 0-তে থামে (q2 → q3, ফিরে চিহ্ন মোছা)।

নিচের stepper 1011-এ INC-এর প্রতিটি configuration দেখায়। বাঁয়ে যে নিয়মটি এই configuration তৈরি করল, সেটি উজ্জ্বল।

1q0 : 1 → I, R2q1 : 0,1 → R3q1 : ␣ → L, q24q2 : 1 → 0, L5q2 : 0 → 1, L, q36q3 : I → 1, R, qacc
এই ধাপের configuration
u q v
ধাপ
carry
  1. শুরু। q0 1011: state q0, head প্রথম ঘরে। সংখ্যাটি ১১, উত্তর হওয়া উচিত ১২ = 1100.
  2. চিহ্ন। “1 → I, R”: প্রথম ঘরের 1 এখন I. মান একই, কিন্তু এখন এটি বাঁ প্রান্তের নিশানা।
  3. ডানে। q1 শুধু ডানে চলে, কিছু বদলায় না। Configuration I0 q1 11.
  4. ডানে। I01 q1 1. Head সংখ্যার শেষ বিটে।
  5. সংখ্যার শেষ। I011 q1 ␣: head প্রথম ␣-এ, অর্থাৎ input-এর ঠিক পরের ঘরে। এখানে ␣-এর নিয়ম না থাকলে যন্ত্র এখানেই reject করত: “␣ ভুলে যাওয়া” সবচেয়ে সাধারণ ভুল।
  6. Carry শুরু। “␣ → L”: q2-তে শেষ বিটে ফেরা। q2 মানে “এখানে 1 যোগ করতে হবে”; carry বিটটি state-এর নামেই লুকানো।
  7. 1 → 0. শেষ বিট 1, তাই 0 লিখে carry বাঁয়ে। Tape I010.
  8. আবার 1 → 0. Tape I000, head দ্বিতীয় ঘরে, যেখানে 0.
  9. Carry শেষ। “0 → 1, L”: 1 লিখে q3-তে। এখন বাকি কাজ শুধু প্রথম ঘরের চিহ্ন মোছা। Head প্রথম ঘরে, configuration q3 I100.
  10. গ্রহণ। “I → 1, R”: চিহ্ন মুছে qacc. Tape 1100 = ১২. মোট ৯টি ধাপ; n বিটের input-এ সবচেয়ে বেশি 3n + 1 ধাপ লাগে, যখন সব বিট 1 (অংশ ৭)।

৩ · Python-এ simulator, brute force আর একটি স্বাধীন library

কাগজে trace ভালো, কিন্তু একটি যন্ত্রের সঠিকতায় আস্থা আসে অনেক input-এ চালিয়ে। নিচের simulator একটি dict-এ δ রাখে: key (state, পড়া চিহ্ন), মান (পরের state, লেখা চিহ্ন, দিক)। নিয়ম লেখা হয় একটি ছোট লাইনে, যেমন q2 1 q2 0 L; লেখার জায়গায় = মানে “যা পড়েছি তা-ই”। দুটি নিরাপত্তা আছে: dict-এ নিয়ম না পেলে qreject (implicit reject), আর একটি step cap: ১০,০০০ ধাপের পরেও না থামলে simulator হাল ছেড়ে “cap” ফেরত দেয়। Cap ছাড়া একটি loop-করা যন্ত্র ব্রাউজার আটকে দিত। প্রথম ঘরে L মানে head সেখানেই থাকে।

B = "_"                                   # the blank symbol
def T(table):                             # rules "q read next write move", split by ";"
    d = {}
    for rule in table.replace("\n", ";").split(";"):
        q, reads, r, w, mv = rule.split()
        for s in reads.split(","):        # "=" means: write back what was read
            d[(q, s)] = (r, s if w == "=" else w, mv)
    return d
def run(d, w, cap=10_000, show=False):    # Sipser TM, one-way tape
    q, tape, h = "q0", list(w) or [B], 0
    for step in range(cap + 1):
        if show:
            u, v = "".join(tape[:h]), "".join(tape[h:]).rstrip(B) or B
            print(f"  {step}: " + f"{u} {q} {v}".strip())
        if q in ("qacc", "qrej"): return q, step, "".join(tape).strip(B)
        if step == cap: return "cap", step, None            # step cap: never hang
        q, tape[h], mv = d.get((q, tape[h]), ("qrej", tape[h], "R"))  # missing = reject
        if mv == "R":
            h += 1
            if h == len(tape): tape.append(B)
        else: h = max(h - 1, 0)           # L on the first cell: stay put
INC0 = T("""q0 0,1 q0 = R; q0 _ q1 = L
q1 1 q1 0 L; q1 0,_ qacc 1 R""")          # naive: carry may run off the left end
# O, I = the first cell's 0 or 1, marked
INC = T("""q0 0 q1 O R; q0 1 q1 I R
q1 0,1 q1 = R; q1 _ q2 = L
q2 1 q2 0 L; q2 0 q3 1 L; q2 O qacc 1 R; q2 I q4 1 R
q3 0,1 q3 = L; q3 O qacc 0 R; q3 I qacc 1 R
q4 0 q4 = R; q4 _ qacc 0 R""")
print("INC on 1011:"); run(INC, "1011", show=True)
print("on 111:  INC0 ->", run(INC0, "111")[2], "  INC ->", run(INC, "111")[2])
words = [format(i, f"0{k}b") for k in range(1, 11) for i in range(2 ** k)]
for name, d in [("INC0", INC0), ("INC", INC)]:
    bad = [w for w in words if run(d, w)[2] != format(int(w, 2) + 1, f"0{len(w)}b")]
    print(f"{name}: {len(words)} inputs, wrong on {len(bad)}: {bad[:4]}")

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

INC on 1011:
  0: q0 1011
  1: I q1 011
  2: I0 q1 11
  3: I01 q1 1
  4: I011 q1 _
  5: I01 q2 1
  6: I0 q2 10
  7: I q2 000
  8: q3 I100
  9: 1 qacc 100
on 111:  INC0 -> 100   INC -> 1000
INC0: 2046 inputs, wrong on 10: ['1', '11', '111', '1111']
INC: 2046 inputs, wrong on 0: []

প্রথম দশ লাইন stepper-এর দশটি configuration-এর সঙ্গে হুবহু মেলে (simulator ␣-কে _ দিয়ে ছাপে)। তারপর দৈর্ঘ্য ১ থেকে ১০ পর্যন্ত সব binary string, মোট 2 + 4 + ⋯ + 1024 = 2046টি, প্রত্যাশিত উত্তরের সঙ্গে মেলানো হয়েছে; প্রত্যাশিত উত্তর একই দৈর্ঘ্যে শূন্য-পূরণ করা w + 1, যেমন 0011 থেকে 0100. INC0 ভুল করে ঠিক ১০টিতে: 1, 11, 111, …, সবই শুধু 1 দিয়ে গড়া, প্রতিটি দৈর্ঘ্যে একটি করে। অর্থাৎ বাঁ প্রান্তের ফাঁদ শুধু তখনই ধরা পড়ে, যখন carry প্রথম ঘর পেরোতে চায়। হাতে বাছাই করা কয়েকটি উদাহরণে (যেমন 1011 বা 0101) এই ভুল সহজে চোখ এড়ায়; brute force এড়ায় না। INC কোনো input-এ ভুল করেনি।

একটি স্বাধীন library দিয়ে যাচাই। নিজের লেখা simulator-এ ভুল থাকলে যন্ত্র আর simulator একসঙ্গে ভুল করে “মিলে যেতে” পারে। তাই একই যন্ত্রগুলো automata-lib-এর DTM class-এ চালানো হলো (Python library, MIT licence; এতে network বা usage-reporting কোড নেই)। একটি গুরুত্বপূর্ণ পার্থক্য আছে: এই library-র tape দুই দিকে অসীম; প্রথম ঘরে L বললে বাঁয়ে একটি নতুন ␣ ঘর তৈরি হয়। ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে script-টির মূল অংশ:

from automata.tm.dtm import DTM
from automata.base.exceptions import RejectionException
import tms        # our machines: {(q, read): (next, write, move)}
def to_dtm(d):    # same table, library format {q: {read: (next, write, move)}}
    trans = {}
    for (q, s), (r, b, mv) in d.items():
        trans.setdefault(q, {})[s] = (r, b, mv)
    ...           # states, tape_symbols, blank_symbol="_", final_states={"qacc"}
def lib_run(M, w):                  # (result, steps, tape) from read_input_stepwise
    ...
print("INC0 111     ->", lib_run(INC0, "111"), " (library tape grows left)")
print("INC0 111     ->", tms.run(tms.INC0, "111")[:3], " (Sipser one-way tape)")
# then: INC on all 2046 binary strings, PAL (section 5) on all 2047 strings
# over {a, b} up to length 10, MUL (section 6) on 1^m*1^n for m, n <= 6

সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12.13):

~/bazarghar-toc$ uv run python run_dtm.py
automata-lib 9.2.0
INC  1011    -> ('accept', 9, '1100')
INC0 111     -> ('accept', 8, '1000')  (library tape grows left)
INC0 111     -> ('qacc', 8, '100')  (Sipser one-way tape)
MUL  11*111  -> ('accept', 99, 'aa*111=111111')
INC: 2046 inputs, library and our simulator agree (accept/reject; steps and tape when accepted) on 2046
PAL: 2047 inputs, library and our simulator agree (accept/reject; steps and tape when accepted) on 2047
MUL: 49 inputs, library and our simulator agree (accept/reject; steps and tape when accepted) on 49

দুটি শিক্ষা। প্রথমত, তিনটি যন্ত্রের সব input-এ দুই simulator ফল, ধাপের সংখ্যা আর শেষ tape-এ একমত, তাই আমাদের simulator-এর ওপর ভরসা করা যায়। দ্বিতীয়ত, একই transition table, দুই রীতিতে দুই উত্তর: INC0 দুই-দিকের tape-এ 111 থেকে ঠিক 1000 দেয়, কারণ বাঁয়ে সত্যিই একটি ␣ তৈরি হয়; এক-দিকের tape-এ দেয় ভুল 100. তাই TM নকশার উত্তরে কোন রীতি মানছেন, তা লিখে দিন। INC, PAL আর MUL কখনো প্রথম ঘরের বাঁয়ে যেতে চায় না, তাই দুই রীতিতেই একই ফল দেয়; এটিই ভালো নকশার লক্ষণ। Library-টি reject হলে exception দেয়, আর loop থামানোর কোনো ব্যবস্থা এতে নেই, তাই শুধু থামে এমন যন্ত্রই এতে চালানো হয়েছে।

৪ · Tape সরানো আর state-এ চিহ্ন মনে রাখা

বাজারঘরের order code-এর format হলো “BG-” আর চারটি অঙ্ক, যেমন BG-0042. পুরোনো একটি system থেকে আসা code-এ dash নেই: BG0042. যন্ত্রকে দ্বিতীয় অক্ষরের পরে একটি “-” ঢোকাতে হবে। Text editor-এ এটি এক চাপের কাজ; tape-এ কোনো “ঢোকানো” নেই, আছে শুধু ঘরে লেখা। তাই ঢোকানো মানে: নতুন চিহ্নের জায়গা থেকে শুরু করে বাকি সবকিছু এক ঘর ডানে ঠেলা।

কৌশল। “-” লিখুন আর যে চিহ্নটি মুছে গেল, তা state-এ মনে রাখুন। পরের ঘরে গিয়ে মনে রাখা চিহ্নটি লিখুন আর সেখানকার পুরোনো চিহ্নটি নতুন করে মনে রাখুন। ␣-এ পৌঁছালে শেষ মনে রাখা চিহ্নটি লিখে কাজ শেষ। সারির শেষ বাক্স খালি করে প্রতিটি বাক্স এক তাক ডানে সরানোর মতো, শুধু হাতে একবারে একটি বাক্স। Alphabet {B, G, 0, …, 9}-এ ১২টি চিহ্ন, তাই “cx: হাতে x আছে” ধরনের ১২টি state লাগে: cB, cG, c0, …, c9. প্রতিটি cx-এ নিয়ম “y → x, R, cy”, মোট ১২ × ১২ = ১৪৪টি. যন্ত্রের state সসীমই থাকে, কারণ alphabet সসীম; সংখ্যাটি নির্ভর করে |Γ|-এর ওপর, input-এর দৈর্ঘ্যের ওপর নয়। এটিই “state-এ স্মৃতি” কৌশল।

1q0, q1 : x → R2q2 : x → -, R, c_x3c_x : y → x, R, c_y4c_x : ␣ → x, L, qb5qb : y → L6qb : - → R, qacc
এই ধাপের configuration
u q v
হাতে (state-এ)
  1. শুরু। q0 BG0042. লক্ষ্য BG-0042: তৃতীয় ঘর থেকে সবকিছু এক ঘর ডানে।
  2. প্রথম অক্ষর। q0 যেকোনো চিহ্ন পেরিয়ে q1-এ। দুটি ঘর গোনার জন্য দুটি state, কারণ যন্ত্রের কোনো counter নেই।
  3. দ্বিতীয় অক্ষর। q1 পেরিয়ে q2: head এখন তৃতীয় ঘরে, যেখানে 0.
  4. ঢোকানো। q2 সেখানে “-” লেখে আর মুছে যাওয়া 0 নিয়ে c0-তে যায়। Tape BG-042: আপাতত একটি 0 কম, কারণ সেটি হাতে।
  5. প্রথম ঠেলা। c0 চতুর্থ ঘরে হাতের 0 লেখে আর সেখানকার পুরোনো 0 তোলে। দুটি একই চিহ্ন, তাই tape দেখতে একই, কিন্তু state ঠিকমতো c0-তেই থাকে।
  6. দ্বিতীয় ঠেলা। পঞ্চম ঘরে 0 লেখা, পুরোনো 4 তোলা: c4. Tape BG-002.
  7. তৃতীয় ঠেলা। ষষ্ঠ ঘরে 4 লেখা, 2 তোলা: c2. Head এখন ␣-এ।
  8. শেষ চিহ্ন। “␣ → 2, L”: হাতের 2 লিখে qb-তে। Tape BG-0042, ঠেলা শেষ।
  9. ফেরা। qb বাঁয়ে চলে। কেন ফেরা? একটি subroutine হিসেবে এই যন্ত্র যেখান থেকে ডাকা হয়েছিল, সেখানে head ফেরত দেয়।
  10. ফেরা। qb আরও এক ঘর বাঁয়ে, 0-এর ওপর।
  11. ফেরা। qb আরেকটি 0 পেরিয়ে এখন “-”-এর ওপর।
  12. শেষ। qb “-” পেয়ে ডানে এক ঘর গিয়ে qacc. মোট ১১টি ধাপ। সাধারণভাবে ঢোকানোর পরে k টি ঘর থাকলে ঠেলায় প্রায় k আর ফেরায় প্রায় k ধাপ, অর্থাৎ একবার ঢোকানো O(n), আর n বার ঢোকালে O(n²).

এই কৌশলের আরেকটি পুরোনো ব্যবহার: tape-এর বাঁ প্রান্তে একটি নিশানা (ধরুন ▷) বসানো। পুরো input এক ঘর ডানে ঠেলে প্রথম ঘরে ▷ লিখুন; তারপর থেকে যন্ত্র ▷ দেখেই জানে সে প্রথম ঘরে। INC-এ এর বদলে প্রথম ঘর চিহ্নিত করা হয়েছিল, যা সস্তা: O(n)-এর বদলে একটি ধাপ। দুটিই বাঁ প্রান্ত চেনার বৈধ উপায়।

৫ · Zig-zag আর চিহ্ন দিয়ে কাটা — palindrome যন্ত্র ও তার প্রমাণ

পর্ব ৪৩-এর anbncn যন্ত্র প্রতিটি a-এর জন্য একটি b আর একটি c কেটে দেয়, আর {w#w} যন্ত্র # পেরিয়ে বারবার আসা-যাওয়া করে চিহ্ন মেলায়; বাজারঘরের দুটি order ID সমান কি না, সেই পরীক্ষাও ঠিক এটাই। সেগুলো আবার না দেখিয়ে এখানে zig-zag-এর একটি নতুন উদাহরণ: Σ = {a, b}-এর ওপর palindrome, অর্থাৎ w = wR. পর্ব ৩২-এর PDA মাঝখান অনুমান করে stack দিয়ে এটি চিনত (জোড় দৈর্ঘ্যের রূপ)। TM-এর কাছে nondeterminism লাগে না: সে দুই প্রান্ত সরাসরি দেখতে পারে।

High-level: প্রথম চিহ্নটি পড়ুন, মনে রাখুন, মুছে দিন (␣ লিখে)। ডানে শেষ চিহ্নে যান; সেটি মনে রাখা চিহ্নের সমান না হলে reject, সমান হলে সেটিও মুছে দিন। বাঁয়ে ফিরে বাকি অংশের শুরুতে আসুন, আবার করুন। কিছু না থাকলে, বা মাঝে একটি মাত্র চিহ্ন থাকলে, accept. Formal: PAL-এর সারণি।

stateনিয়মকাজ
q0a → ␣, R, q1 · b → ␣, R, q3 · ␣ → R, qaccপ্রথম চিহ্ন মুছে state-এ রাখা
q1 / q3a, b → R · ␣ → L, q2 / q4ডান প্রান্তে যাওয়া (হাতে a / b)
q2a → ␣, L, q5 · ␣ → R, qaccশেষ চিহ্ন a কি না
q4b → ␣, L, q5 · ␣ → R, qaccশেষ চিহ্ন b কি না
q5a, b → L · ␣ → R, q0বাঁ প্রান্তে ফেরা

লক্ষ করুন, এখানে বাঁ প্রান্তের সমস্যা হয় না: প্রথম ধাপেই প্রথম ঘর ␣ হয়ে যায়, আর পরে মুছে যাওয়া ঘরগুলো দুই দিকেই দেয়াল হিসেবে কাজ করে। q2-তে ␣ পাওয়া মানে ডানে কিছু ছিল না, অর্থাৎ মুছে ফেলা চিহ্নটিই ছিল মাঝের একক চিহ্ন: বিজোড় দৈর্ঘ্যের palindrome. q2-তে b-এর নিয়ম নেই: implicit reject.

উপপাদ্য ৫.১

PAL একটি decider, আর L(PAL) = {w ∈ {a, b}∗ : w = wR}. দৈর্ঘ্য n-এর palindrome-এ PAL ঠিক (n + 1)(n + 2)/2 ধাপ নেয়।

প্রমাণ। “রাউন্ড” মানে q0-তে একবার ঢোকা থেকে পরেরবার ঢোকা পর্যন্ত।

  1. Invariant: প্রতিবার q0-তে ঢোকার সময় tape = ␣k x ␣ ␣ ⋯, head x-এর প্রথম ঘরে (বা x = ε হলে ঘর k-তে), আর w palindrome ⇔ x palindrome. — রাউন্ডের সংখ্যার ওপর induction
  2. ভিত্তি: শুরুতে k = 0, x = w. — শুরুর configuration
  3. x = ε: q0 ␣ পড়ে accept; ε palindrome. — q0-এর ␣ নিয়ম
  4. x = a (একটি চিহ্ন): a মুছে q1, পরের ঘরেই ␣, L দিয়ে মুছে যাওয়া ঘরে, q2 ␣ পড়ে accept. একক চিহ্ন palindrome. — q1, q2-এর ␣ নিয়ম
  5. x = a y c, |y| ≥ 0: q1 x-এর শেষে গিয়ে q2-তে c পড়ে। c = b হলে নিয়ম নেই, reject; তখন x-এর প্রথম আর শেষ চিহ্ন আলাদা, তাই x palindrome নয়। c = a হলে মুছে q5 বাঁয়ে প্রথম ␣ পর্যন্ত (ঘর k) যায়, তারপর R দিয়ে q0: নতুন x′ = y, আর x = a y a palindrome ⇔ y palindrome. — palindrome-এর সংজ্ঞা
  6. x শুরু b দিয়ে হলে q3, q4 দিয়ে একই যুক্তি। — প্রতিসাম্য
  7. প্রতিটি রাউন্ডে |x| দুই কমে, নয়তো যন্ত্র থামে; তাই প্রতিটি input-এ যন্ত্র থামে, আর থামার সিদ্ধান্ত ধাপ ৩–৬ অনুযায়ী সঠিক। — |x|-এর ওপর induction
  8. ধাপ গোনা: |x| = m ≥ 2 হলে একটি রাউন্ডে ১ (মোছা) + (m − 1) (ডানে) + ১ (␣ থেকে ফেরা) + ১ (শেষ চিহ্ন মোছা) + (m − 2) (বাঁয়ে) + ১ (␣ থেকে ডানে) = 2m + 1 ধাপ। জোড় n-এ রাউন্ডগুলো m = n, n − 2, …, 2, তারপর q0-তে ␣ পড়ার ১ ধাপ: যোগফল (n + 1)(n + 2)/2. বিজোড় n-এ শেষ রাউন্ড m = 1, যাতে ৩ ধাপ, আর যোগফল একই সূত্রে আসে। ∎ — সমান্তর ধারার যোগফল

Python-এ ধাপ ৮ যাচাই হয়েছে: abba-তে ১৫ ধাপ (5 · 6/2), aba-তে ১০ ধাপ (4 · 5/2), আর অংশ ৭-এর ব্লকে a128-এ ৮৩৮৫ ধাপ (129 · 130/2). Non-palindrome-এ যন্ত্র আগেই থামে, যেমন abab-এ ৬ ধাপে।

“চিহ্ন দিয়ে কাটা” বনাম “মুছে ফেলা”: PAL চিহ্ন মুছে দেয়, কারণ পরে মূল string-এর দরকার নেই। {w#w} বা গুণের যন্ত্রে মূল চিহ্ন পরে লাগে, তাই সেখানে মোছার বদলে X, a, b-এর মতো চিহ্নিত সংস্করণ লেখা হয়, যাতে দরকার হলে আবার ফিরিয়ে আনা যায়। কোনটি লাগবে, তা ঠিক করে প্রশ্ন: “এই তথ্য কি পরে আবার পড়তে হবে?”

৬ · Subroutine আর tape-এ গণিত — unary যোগ ও গুণ

Unary-তে সংখ্যা m লেখা হয় m টি 1 দিয়ে: ৩ = 111. যোগের যন্ত্র ADD-এর input 1m+1n, উত্তর 1m+n. কৌশলটি প্রায় মজার মতো সহজ: “+”-কে 1 বানিয়ে দিন, তাহলে tape-এ m + n + 1টি 1; শেষে গিয়ে একটি 1 মুছে দিন। নিয়ম মাত্র পাঁচটি: q0-এ “1 → R” আর “+ → 1, R, q1”; q1-এ “1 → R” আর “␣ → L, q2”; q2-তে “1 → ␣, L, qacc”. ধাপ ঠিক m + n + 3: m টি 1 পেরোনো, “+” বদলানো, n টি 1 পেরোনো, ␣ থেকে ফেরা, একটি 1 মোছা। Scratch-এ m, n ≤ 7-এর ৬৪টি জোড়ায় উত্তর আর এই সূত্র দুটিই মিলেছে। নিচের JavaScript ব্লক যন্ত্রটির প্রতিটি ধাপে tape আঁকে; বন্ধনী [ ] হলো head.

// Unary addition 1^m+1^n -> 1^(m+n) on a one-way tape, with a step cap.
const B = "_";
const delta = {                       // "state,read": [next, write, move]
  "q0,1": ["q0", "1", "R"], "q0,+": ["q1", "1", "R"],
  "q1,1": ["q1", "1", "R"], "q1,_": ["q2", "_", "L"],
  "q2,1": ["qacc", "_", "L"] };
function animate(w, cap = 50) {
  let q = "q0", tape = w ? w.split("") : [B], h = 0;
  console.log(`input ${w}`);
  for (let step = 0; step <= cap; step++) {
    const cells = tape.map((c, i) => (i === h ? `[${c}]` : ` ${c} `)).join("");
    console.log(`${String(step).padStart(2)} ${q.padEnd(4)} ${cells}`);
    if (q === "qacc" || q === "qrej") {
      const out = tape.join("").split(B).join("");
      return console.log(` halted in ${q}, tape holds ${out || "nothing"}`);
    }
    const [r, wr, mv] = delta[`${q},${tape[h]}`] || ["qrej", tape[h], "R"];
    tape[h] = wr; q = r;              // a missing rule means: reject
    if (mv === "R") { h++; if (h === tape.length) tape.push(B); }
    else h = Math.max(h - 1, 0);      // L on the first cell: stay put
  }
  console.log(` stopped by the step cap (${cap} steps)`);
}
animate("111+11");
animate("11");                        // no "+": the machine has no rule for _

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

input 111+11
 0 q0   [1] 1  1  +  1  1
 1 q0    1 [1] 1  +  1  1
 2 q0    1  1 [1] +  1  1
 3 q0    1  1  1 [+] 1  1
 4 q1    1  1  1  1 [1] 1
 5 q1    1  1  1  1  1 [1]
 6 q1    1  1  1  1  1  1 [_]
 7 q2    1  1  1  1  1 [1] _
 8 qacc  1  1  1  1 [1] _  _
 halted in qacc, tape holds 11111
input 11
 0 q0   [1] 1
 1 q0    1 [1]
 2 q0    1  1 [_]
 3 qrej  1  1  _ [_]
 halted in qrej, tape holds 11

3 + 2-এ ৮টি ধাপ, সূত্র m + n + 3-এর সঙ্গে মেলে, আর tape-এ পাঁচটি 1. ধাপ ৬-এ head প্রথমবার ␣-এ পৌঁছায়; simulator তখন tape-এর ডানে একটি নতুন ␣ ঘর জোড়ে, অসীম tape এভাবেই প্রয়োজনমতো “দেখা দেয়”। দ্বিতীয় input-এ “+” নেই: q0 ␣-এ পৌঁছায়, যেখানে কোনো নিয়ম নেই, তাই qrej. ভুল format-এর input এভাবে বাদ পড়ে; আলাদা কোনো “error” state লেখার দরকার হয়নি। Step cap ৫০; এই যন্ত্র কখনো সেখানে পৌঁছায় না, কিন্তু নিজের পরীক্ষামূলক নিয়ম বসালে cap আপনার ব্রাউজারকে রক্ষা করবে।

গুণ: subroutine-এর ভেতরে subroutine. Input 1m∗1n, যেমন 11∗111 (২ × ৩)। উত্তর হবে tape-এর শেষে “=”-এর ডানে 1mn. তিন স্তরে নকশা:

  1. High-level: প্রথম গুণকের প্রতিটি 1-এর জন্য দ্বিতীয় গুণকটি একবার করে উত্তরের শেষে copy করুন।
  2. Implementation: শুরুতে প্রথম গুণকের প্রথম 1-কে a লিখুন (এটিই বাঁ প্রান্তের নিশানা), শেষে “=” বসান। Copy subroutine: দ্বিতীয় গুণকের পরের 1-কে b লিখুন, ডানে শেষ ␣-এ গিয়ে 1 লিখুন, বাঁয়ে শেষ b-তে ফিরুন; কোনো 1 না থাকলে (“=” পেলে) সব b-কে আবার 1 বানিয়ে “∗”-এ ফিরুন। তারপর বাঁয়ে শেষ a-তে গিয়ে তার ডানের ঘর দেখুন: 1 হলে সেটিকে a লিখে আবার copy, “∗” হলে accept.
  3. Formal: নিচের সারণি, ১২টি কাজের state আর ২৭টি নিয়ম।
stateনিয়মকাজ
q01 → a, R, q1 · ∗ → R, qEপ্রথম 1 চিহ্নিত; m = 0 হলে qE
qE1 → R · ␣ → =, R, qaccm = 0: শুধু “=” লেখা
q1, q1bq1: 1 → R · ∗ → R, q1b; q1b: 1 → R · ␣ → =, L, q2শেষে “=” বসানো
q21 → L · ∗ → R, q3“∗”-এ ফেরা
q3b → R · 1 → b, R, q4 · = → L, q6পরের 1 খোঁজা (copy শুরু)
q41, = → R · ␣ → 1, L, q5শেষে একটি 1 লেখা
q51, = → L · b → R, q3শেষ b-তে ফেরা
q6b → 1, L · ∗ → L, q7b-গুলো আবার 1 (copy শেষ)
q71 → L · a → R, q8শেষ a খোঁজা
q81 → a, R, q9 · ∗ → R, qaccপরের 1 চিহ্নিত, নয়তো শেষ
q91 → R · ∗ → R, q3দ্বিতীয় গুণকে যাওয়া

সারণিতে input-এর format-ও যাচাই হয়: q1b-তে দ্বিতীয় একটি “∗” এলে নিয়ম নেই, তাই 1∗1∗1 reject হয়। নিচের stepper প্রতিটি ধাপ দেখায় না (মোট ৯৯টি), দেখায় দশটি মাইলফলক; মাঝের সব configuration scratch-এর simulator-এ ছাপা আর মেলানো হয়েছে।

1প্রথম গুণকের 1 → a2শেষে = বসানো3পরের 1 → b, শেষে 1 লেখা4b ফুরোলে সব b → 15a-র পরে ∗ হলে ACCEPT
এই মাইলফলকে
মোট ধাপ
u q v
উত্তরে 1
  1. শুরু। q0 11∗111 (simulator ∗-কে * লেখে)। m = 2, n = 3; উত্তর হবে ছয়টি 1.
  2. প্রস্তুতি, ৭ ধাপ। প্রথম 1 এখন a, ডান প্রান্তে “=” বসেছে, আর q2 বাঁয়ে “∗”-এর দিকে ফিরছে।
  3. প্রথম 1 copy, ধাপ ১৬। দ্বিতীয় গুণকের প্রথম 1 এখন b; “=”-এর ডানে প্রথম 1 লেখা হয়েছে, q5 শেষ b-তে ফিরছে।
  4. দ্বিতীয় 1 copy, ধাপ ২৫। দুটি b, উত্তরে দুটি 1. প্রতিটি copy-তে head-কে উত্তরের শেষ পর্যন্ত গিয়ে ফিরতে হয়, আর উত্তর যত লম্বা হয়, পথও তত লম্বা।
  5. প্রথম দফা শেষ, ধাপ ৩৪। তিনটি b, উত্তরে তিনটি 1: প্রথম গুণকের প্রথম 1-এর জন্য দ্বিতীয় গুণক একবার copy হলো।
  6. পুনরুদ্ধার, ধাপ ৪৬। q3 “=” পেয়ে q6-তে: সব b আবার 1. তারপর q7 বাঁয়ে শেষ a খুঁজে পায়, q8 তার ডানের 1-কে a লেখে। Tape aa∗111=111.
  7. দ্বিতীয় দফা, ধাপ ৫৫। আবার প্রথম b, উত্তরে চারটি 1.
  8. ধাপ ৭০। উত্তরে পাঁচটি 1. প্রথম দফার একই কাজে এখন বেশি ধাপ (১৫ বনাম ৯), কারণ উত্তর লম্বা হয়েছে।
  9. দ্বিতীয় দফা শেষ, ধাপ ৮৫। ছয়টি 1 লেখা হয়ে গেছে।
  10. গ্রহণ, ধাপ ৯৯। b-গুলো 1 হয়, q7 শেষ a-তে, q8 ডানে “∗” পায়: আর কোনো 1 বাকি নেই, accept. Tape aa∗111=111111: উত্তর “=”-এর ডানে ছয়টি 1. প্রথম গুণক a হিসেবেই রয়ে গেল, কারণ সেগুলো আবার 1 বানাতে বাঁয়ে যেতে হলে আবার বাঁ প্রান্ত চেনার সমস্যা আসে।

MUL-এর সঠিকতা একটি invariant থেকে আসে: প্রতিবার q3-তে ঢোকার সময় a-র সংখ্যা i আর b-র সংখ্যা j হলে উত্তরে ঠিক (i − 1)n + j টি 1 আছে। Copy সম্পূর্ণ হলে j = n, তাই উত্তর in; শেষে i = m, উত্তর mn. Scratch-এ m, n ≤ 5-এর ৩৬টি জোড়ায় (m বা n = 0 সহ) উত্তর সঠিক মিলেছে, আর library-তে m, n ≤ 6-এর ৪৯টিতে। Binary যোগ একই ছকে করা যায়: দুই সংখ্যার ডান থেকে একটি একটি বিট চিহ্নিত করে carry state-এ রেখে যোগ, যার খরচ প্রতিটি বিটে একবার আসা-যাওয়া, মোট O(n²). অথবা input-কে দুই সারির (two-track) চিহ্নে লিখলে, প্রতিটি ঘরে একটি বিট-জোড়, একবার ডান থেকে বাঁয়ে গিয়েই O(n) সময়ে হয়; পর্ব ১২-এর serial adder ঠিক এই ধারণা। এর পূর্ণ সারণি অনুশীলনের জন্য রইল।

৭ · ধাপ গোনা — কোন যন্ত্র কত দ্রুত

একটি decider-এর time complexity হলো f(n) = দৈর্ঘ্য n-এর যেকোনো input-এ থামার আগে সর্বোচ্চ কতগুলো transition. এটি worst-case মাপ, আর ধাপ মানে ঠিক একটি δ-প্রয়োগ। Big-O দিয়ে লিখলে ধ্রুবক বাদ যায়। এখানে দুটি দাবি প্রমাণ করা যাক, তারপর মেপে দেখা যাক।

উপপাদ্য ৭.১

n ≥ 1 বিটের যেকোনো input-এ INC সর্বোচ্চ 3n + 1 ধাপে থামে, আর w = 1n-এ ঠিক 3n + 1 ধাপ নেয়। তাই INC-এর time complexity Θ(n), অর্থাৎ linear.

প্রমাণ। (১) চিহ্ন দেওয়া ১ ধাপ, q1-এ বাকি n − 1টি বিট পেরোনো আর ␣ থেকে ফেরা: মোট n + 1 ধাপে head শেষ বিটে, state q2. (২) এরপর q2 আর q3-এর প্রতিটি নিয়ম, এমনকি q2-এর “0 → 1, L”-ও, head-কে এক ঘর বাঁয়ে নেয়, আর এরা থামে বা q4-এ যায় শুধু চিহ্নিত O বা I পড়লে। তাই শেষ বিট থেকে দ্বিতীয় ঘর পর্যন্ত n − 1 ধাপ আর প্রথম ঘরে ১ ধাপ: ঠিক n ধাপ। (৩) প্রথম ঘরে q2 যদি I পড়ে, অর্থাৎ সব বিট 1 ছিল, q4 n − 1টি 0 পেরিয়ে ␣-এ 0 লেখে: আরও n ধাপ। মোট সবচেয়ে বেশি (n + 1) + n + n = 3n + 1, আর অন্য সব input-এ ঠিক 2n + 1. ∎

Palindrome-এর জন্য উপপাদ্য ৫.১ ঠিক (n + 1)(n + 2)/2 দিয়েছে: quadratic, Θ(n²). নিচের ব্লক আগের ব্লকের T আর run ব্যবহার করে (একই namespace): প্রথমে PAL-কে দৈর্ঘ্য ১০ পর্যন্ত সব string-এ সংজ্ঞার সঙ্গে মেলায়, তারপর n দ্বিগুণ করে ধাপ মাপে। Fit-এর সহজ উপায়: ধাপ ÷ n আর ধাপ ÷ n² দুটি অনুপাত দেখা; যেটি একটি ধ্রুবকের দিকে স্থির হয়, বৃদ্ধি সেই হারে।

from itertools import product
# zig-zag: erase the first symbol, remember it in the state, check the last one
PAL = T("""q0 a q1 _ R; q0 b q3 _ R; q0 _ qacc = R
q1 a,b q1 = R; q1 _ q2 = L; q2 a q5 _ L; q2 _ qacc = R
q3 a,b q3 = R; q3 _ q4 = L; q4 b q5 _ L; q4 _ qacc = R
q5 a,b q5 = L; q5 _ q0 = R""")
words = ["".join(p) for k in range(11) for p in product("ab", repeat=k)]
res = [run(PAL, w)[0] for w in words]
bad = [w for w, r in zip(words, res) if (r == "qacc") != (w == w[::-1])]
print(f"PAL: {len(words)} strings, {res.count('qacc')} accepted, "
      f"disagreements {len(bad)}, step cap hit {res.count('cap')}")
print("   n    INC  INC/n     PAL  PAL/n^2")
for n in [8, 16, 32, 64, 128]:
    i, p = run(INC, "1" * n)[1], run(PAL, "a" * n)[1]
    print(f"{n:4} {i:6} {i / n:6.2f} {p:7} {p / n ** 2:8.3f}")

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

PAL: 2047 strings, 125 accepted, disagreements 0, step cap hit 0
   n    INC  INC/n     PAL  PAL/n^2
   8     25   3.12      45    0.703
  16     49   3.06     153    0.598
  32     97   3.03     561    0.548
  64    193   3.02    2145    0.524
 128    385   3.01    8385    0.512

দৈর্ঘ্য ০ থেকে ১০ পর্যন্ত 211 − 1 = 2047টি string-এ PAL সংজ্ঞার সঙ্গে একমত, আর কোনোটিতে step cap লাগেনি, অর্থাৎ সব input-এ থেমেছে। গৃহীত ১২৫টি: দৈর্ঘ্য k-এর palindrome 2⌈k/2⌉টি, আর 1 + 2 + 2 + 4 + 4 + 8 + 8 + 16 + 16 + 32 + 32 = 125. INC/n অনুপাত 3-এর দিকে নামছে: 3n + 1, linear. PAL/n² অনুপাত 0.5-এর দিকে: (n + 1)(n + 2)/2 = n²/2 + ছোট পদ, quadratic. দ্বিগুণ-পরীক্ষাতেও একই কথা: n দ্বিগুণ হলে INC-এর ধাপ প্রায় দ্বিগুণ (193 থেকে 385), PAL-এর প্রায় চার গুণ (2145 থেকে 8385). প্রতিটি সংখ্যা উপপাদ্যের সূত্র থেকে হাতেও মেলানো যায়: 3 · 128 + 1 = 385, 129 · 130/2 = 8385.

গুণের যন্ত্রের হিসাব আরও নাটকীয়। প্রতিটি উত্তর-1 লিখতে head-কে চলমান উত্তরের শেষ পর্যন্ত যেতে-আসতে হয়, আর উত্তর বেড়ে mn পর্যন্ত যায়; তাই মোট ধাপ মোটামুটি m²n²-এর ক্রমে। Scratch-এ m = n = 2, 4, 8-এ ধাপ ৫৯, ৪২৭, ৪৯৭৯: n দ্বিগুণে প্রায় ৭ গুণ, তারপর প্রায় ১২ গুণ, ১৬ গুণের দিকে এগোচ্ছে। Input-এর দৈর্ঘ্য N = m + n + 1 ধরলে এটি N4-এর মতো। কারণ দুটি: unary encoding নিজেই অপচয়ী (পর্ব ০৫-এ দেখেছেন, unary-তে সংখ্যার দৈর্ঘ্য binary-র তুলনায় exponential), আর এক-tape যন্ত্রকে প্রতিটি তথ্যের জন্য হেঁটে যেতে হয়। একাধিক tape-এ (পর্ব ৪৫) এই হাঁটা অনেক কমে; যেমন palindrome দুই-tape যন্ত্রে O(n) সময়ে চেনা যায়।

আরও গভীরে: PAL-এর Θ(n²) কি শুধু আমাদের নকশার দোষ? না। ১৯৬০-এর দশকে (প্রচলিতভাবে F. C. Hennie, ১৯৬৫) “crossing sequence” যুক্তিতে দেখানো হয় যে যেকোনো এক-tape deterministic TM-কে palindrome চিনতে সবচেয়ে খারাপ ক্ষেত্রে Ω(n²) ধাপ লাগে: tape-এর মাঝের প্রতিটি সীমানা head-কে বহুবার পেরোতে হয়, কারণ বাঁ অর্ধেকের তথ্য ডান অর্ধেকে বয়ে নেওয়ার আর কোনো পথ নেই। আবার এক-tape যন্ত্রে o(n log n) সময়ে চেনা প্রতিটি language আসলে regular, এমন একটি ফলও পরিচিত (B. A. Trakhtenbrot ১৯৬৪ আর J. Hartmanis ১৯৬৮-এর নামে উল্লেখ পাওয়া যায়)। তাই এক-tape মডেলে নিচের সীমা প্রমাণ করা যায়, কিন্তু সাধারণ মডেলে তেমন সীমা প্রমাণ করা খুব কঠিন; এই কঠিনতাই পর্ব ৬৩-এর P বনাম NP প্রশ্নের একটি বাধা।

৮ · সাধারণ ভুল আর পরীক্ষা করার নিয়ম

TM নকশার ভুলগুলো প্রায় সবসময় একই কয়েকটি জায়গায় থাকে। নিচের সারণি প্রতিটির একটি উদাহরণ আর ধরার উপায় দেয়।

ভুলউদাহরণকীভাবে ধরবেন
␣ ভুলে যাওয়া“1 থাকা পর্যন্ত ডানে চলা” আছে, কিন্তু ␣-এর নিয়ম নেই, তাই input শেষে rejectপ্রতিটি “ডানে চলা” state-এ ␣-এর সারি আছে কি না দেখুন; ε আর দৈর্ঘ্য ১-এর input চালান
বাঁ প্রান্ত থেকে “পড়ে যাওয়া”INC0: 111 থেকে 100শুধু একই চিহ্নের input (111, aaa) চালান; প্রথম ঘর চিহ্নিত করুন বা ▷ বসান
বাঁয়ে খোঁজা চিহ্ন প্রথম ঘরে নেই“␣ না পাওয়া পর্যন্ত বাঁয়ে” অথচ প্রথম ঘরে 1: head সেখানেই আটকে চিরকাল ঘোরেstep cap; যা খোঁজা হচ্ছে তা সবসময় আছে, invariant দিয়ে দেখান
নিয়ম বাদ পড়া (নীরব reject)PAL থেকে q2-এর ␣ নিয়ম বাদ: বিজোড় palindrome বাতিলসংজ্ঞার সঙ্গে brute force: missing তালিকা
চিহ্ন মুছতে ভুলে যাওয়াINC-এ q3 না থাকলে 1011 থেকে I100শেষ tape-এর সঙ্গে প্রত্যাশিত output হুবহু মেলান
ভুল দিকের রীতিদুই-দিকের tape ধরে নকশা, এক-দিকের রীতিতে চালানোরীতি লিখে দিন; দুই রীতির simulator-এ চালান

পরীক্ষার নিয়ম। (১) একটি reference লিখুন: সাধারণ Python-এ উত্তর, যেমন w == w[::-1] বা int(w, 2) + 1. (২) ছোট দৈর্ঘ্যের সব input-এ যন্ত্র চালিয়ে extra (ভুলে গৃহীত) আর missing (ভুলে বাতিল) দুটি তালিকা ছাপুন। (৩) Step cap রাখুন আর cap-এ পৌঁছানো input আলাদা গুনুন: decider হওয়ার দাবি থাকলে এই সংখ্যা শূন্য হতে হবে। (৪) প্রান্তের ক্ষেত্র আলাদা দেখুন: ε, এক চিহ্ন, সব একই চিহ্ন, সর্বোচ্চ carry. (৫) তারপর invariant দিয়ে প্রমাণ। Brute force সব দৈর্ঘ্যের জন্য কিছু প্রমাণ করে না, আর step cap-এ আটকানো মানেই যে যন্ত্র চিরকাল চলবে, তাও নয়; কোনো input-এ যন্ত্র থামবে কি না, তা সাধারণভাবে নির্ণয় করা অসম্ভব (পর্ব ৫১-এর halting problem). এই ধরনের পরীক্ষার সফটওয়্যার-রূপ হলো property-based testing: সফটওয়্যার টেস্টিং কোর্সের পর্ব ৫৮.

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

  • Binary সংখ্যায় 1 যোগ করার TM দিন আর 1011-এ trace করুন। ডানে গিয়ে carry বাঁয়ে; 111-এর মতো input-এ বাঁ প্রান্ত সামলাতে প্রথম ঘর চিহ্নিত করুন; 1011-এ ৯ ধাপে 1100.
  • Unary যোগ 1m+1n → 1m+n. “+”-কে 1 বানিয়ে শেষের একটি 1 মুছুন; m + n + 3 ধাপ।
  • Palindrome-এর TM আর তার time complexity. দুই প্রান্ত মুছে zig-zag; (n + 1)(n + 2)/2 = Θ(n²).
  • Tape-এ একটি চিহ্ন ঢোকাবেন কীভাবে? বাকি অংশ এক ঘর ডানে ঠেলুন, চলতি চিহ্ন state-এ বয়ে নিয়ে; |Γ| টি carry state.
  • TM কোনো ঘরের জন্য নিয়ম না পেলে কী হয়? Sipser-এর রীতিতে qreject-এ যায় (implicit reject).

৯ · AI-এর যুগে TM নকশা

AI assistant-কে “unary যোগের TM দাও” বললে কয়েক সেকেন্ডে একটি পরিচ্ছন্ন সারণি আসে। ভুল থাকে সাধারণত প্রান্তের ক্ষেত্রে: m = 0, শুধু একটি চিহ্ন, বা head-কে শুরুতে ফেরাতে গিয়ে বাঁ প্রান্তের ফাঁদ। নিচের ব্লকে তিনটি খসড়া (AI-এর উত্তরের ধাঁচে বানানো উদাহরণ) step cap-সহ একটি ছোট simulator-এ ছোট সব input-এ মেলানো হয়েছে; ব্লকটি স্বয়ংসম্পূর্ণ।

from itertools import product
def T(s):                                  # rules "q read next write move", split by ";"
    return {(q, a): (r, a if w == "=" else w, m) for q, aa, r, w, m in
            (x.split() for x in s.replace("\n", ";").split(";")) for a in aa.split(",")}
def run(d, w, cap=500):                    # Sipser TM with a step cap
    q, t, h = "q0", list(w) or ["_"], 0
    for _ in range(cap):
        if q in ("qacc", "qrej"): return q, "".join(t).strip("_")
        q, t[h], mv = d.get((q, t[h]), ("qrej", t[h], "R"))
        h = h + 1 if mv == "R" else max(h - 1, 0)
        if h == len(t): t.append("_")
    return "CAP", None
# AI draft A, unary addition: "erase the first 1, then turn + into 1"
A = T("q0 1 q1 _ R; q1 1 q1 = R; q1 + qacc 1 R")
# AI draft C, unary addition that "returns the head to the start" at the end
C = T("""q0 1 q0 = R; q0 + q1 1 R; q1 1 q1 = R; q1 _ q2 = L
q2 1 q3 _ L; q3 1 q3 = L; q3 _ qacc = R""")
# AI draft B, palindromes by zig-zag: no rule for "nothing left after erasing"
B = T("""q0 a q1 _ R; q0 b q3 _ R; q0 _ qacc = R
q1 a,b q1 = R; q1 _ q2 = L; q2 a q5 _ L
q3 a,b q3 = R; q3 _ q4 = L; q4 b q5 _ L
q5 a,b q5 = L; q5 _ q0 = R""")
add = [("1" * m + "+" + "1" * n, "1" * (m + n)) for m in range(5) for n in range(5)]
for name, d in [("A", A), ("C", C)]:
    bad = [(w, run(d, w)[0]) for w, want in add if run(d, w) != ("qacc", want)]
    print(f"draft {name}: wrong on {len(bad)} of {len(add)}, e.g. {bad[:3]}")
pal = ["".join(p) for k in range(7) for p in product("ab", repeat=k)]
miss = [w for w in pal if w == w[::-1] and run(B, w)[0] != "qacc"]
extra = [w for w in pal if w != w[::-1] and run(B, w)[0] == "qacc"]
print(f"draft B: misses {len(miss)} palindromes {miss[:5]}, extra {len(extra)}")

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

draft A: wrong on 5 of 25, e.g. [('+', 'qrej'), ('+1', 'qrej'), ('+11', 'qrej')]
draft C: wrong on 24 of 25, e.g. [('+1', 'CAP'), ('+11', 'CAP'), ('+111', 'CAP')]
draft B: misses 14 palindromes ['a', 'b', 'aaa', 'aba', 'bab'], extra 0

খসড়া A চতুর কৌশল ব্যবহার করে (প্রথম 1 মুছে “+”-কে 1 বানানো), কিন্তু ধরে নেয় m ≥ 1: “+” দিয়ে শুরু হলে q0-এর নিয়ম নেই, implicit reject. ২৫টির মধ্যে ঠিক m = 0-এর পাঁচটি ভুল। খসড়া C কাজ শেষে head-কে শুরুতে ফেরাতে চায়, “␣ না পাওয়া পর্যন্ত বাঁয়ে”। কিন্তু প্রথম ঘরে 1, তার বাঁয়ে কোনো ␣ নেই; L বললে head সেখানেই থাকে আর একই 1 পড়ে, তাই যন্ত্র চিরকাল ঘোরে। Step cap (৫০০) ছাড়া এই ব্লক ব্রাউজার আটকে দিত। একমাত্র “+” (০ + ০)-এ যোগের পরে tape ফাঁকা, তাই সেখানে ␣ পায় আর থামে। খসড়া B কোনো বাড়তি string নেয় না, কিন্তু দৈর্ঘ্য ৬ পর্যন্ত ১৪টি বিজোড় palindrome (2 + 4 + 8) বাতিল করে: মাঝের চিহ্ন মোছার পরে “আর কিছু নেই” ক্ষেত্রের নিয়ম নেই। অংশ ৫-এর PAL-এ q2 আর q4-এর ␣ নিয়ম ঠিক এই কাজ করে।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
প্রান্তের ক্ষেত্র বাদ: ε, m = 0, এক চিহ্ন, বিজোড় দৈর্ঘ্যছোট সব input-এ brute force; extra আর missing তালিকা
দুই-দিকের tape ধরে নেওয়া, বা “␣ না পাওয়া পর্যন্ত বাঁয়ে চলা”এক-দিকের রীতির simulator, step cap-সহ; সব-1 input
“এই TM O(n) সময়ে চলে” দাবি, অথচ zig-zag আছেn দ্বিগুণ করে ধাপ মাপুন; ধাপ ÷ n আর ধাপ ÷ n² দেখুন
Recognizer-কে decider বলাকোনো input-এ cap লাগছে কি না গুনুন, আর থামার যুক্তি চান
নিয়মের সংখ্যা বা state-এর নামে অসংগতি, সারণিতে নেই এমন চিহ্নসারণি সরাসরি simulator-এ বসিয়ে চালান; হাতের trace-এ ভরসা নয়
বানানো রেফারেন্স বা ইতিহাসSipser বা Hopcroft–Motwani–Ullman-এ নিজে মিলিয়ে নিন

AI-কে কাজে লাগানোর ভালো উপায়: শুধু সারণি নয়, তিন স্তরের বর্ণনা, রীতির ঘোষণা, ছোট trace আর একটি brute-force কোড চাওয়া, যা আপনি নিজে চালাবেন।

আমি গণনার তত্ত্ব শিখছি। tape-এ একটি binary সংখ্যা w (সবচেয়ে গুরুত্বপূর্ণ বিট বাঁয়ে) আছে; w থেকে 1 বিয়োগ করার (decrement) একটি Turing machine দাও। w = 0 হলে reject করবে। ১. Sipser রীতি মানো: tape শুধু ডানে অসীম, প্রথম ঘরে L বললে head নড়ে না, সারণিতে না থাকা নিয়ম মানে reject. এটি স্পষ্ট করে লেখো। ২. আগে high-level বর্ণনা, তারপর implementation বর্ণনা, তারপর পূর্ণ transition সারণি দাও ("q পড়া → লেখা, দিক, পরের q"). ৩. বাঁ প্রান্ত কীভাবে চেনা হচ্ছে, আলাদা করে ব্যাখ্যা করো। ৪. 1000, 0001 আর 1-এর জন্য configuration-ক্রম (u q v) দেখাও। ৫. শুধু standard library দিয়ে একটি ছোট Python simulator দাও, যাতে step cap আছে আর যা দৈর্ঘ্য 10 পর্যন্ত সব input-এ int(w, 2) − 1-এর সঙ্গে মিলিয়ে ভুলের তালিকা ছাপে। ৬. ধাপের সংখ্যার সর্বোচ্চ সীমা n-এর function হিসেবে দাও আর যুক্তি দেখাও। নিশ্চিত না হলে বলো; বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১Subroutine আর চিহ্নিত ঘরের ধারণা কি পরে আবিষ্কৃত কৌশল, নাকি Turing নিজেই এভাবে যন্ত্র লিখেছিলেন?

দুটি ধারণাই Turing-এর ১৯৩৬ সালের মূল প্রবন্ধ “On Computable Numbers, with an Application to the Entscheidungsproblem”-এ আছে, যদিও অন্য নামে। Turing তাঁর tape-এর ঘরগুলোকে দুই ধরনে ভাগ করেন বলে বর্ণিত: একটি অন্তর একটি ঘরে স্থায়ী অঙ্ক (তিনি বলেন F-squares, figures-এর জন্য), আর তাদের মাঝের ঘরগুলোতে অস্থায়ী চিহ্ন (E-squares, যা মোছা যায়)। মাঝের ঘরে একটি চিহ্ন বসানো মানে ঠিক এই পর্বের “চিহ্নিত সংস্করণ”: অঙ্কটি অক্ষত থাকে, পাশে একটি টিক পড়ে। আধুনিক পাঠ্যবইয়ে এর বদলে বাড়তি tape চিহ্ন (O, I, X) ব্যবহার হয়; দুটি সমতুল্য, কারণ একটি ঘর-জোড়কে একটি বড় alphabet-এর একটি চিহ্ন হিসেবে পড়া যায়।

Subroutine-এর জন্য Turing ব্যবহার করেন “skeleton table” আর m-configuration-এর function, যেমন একটি সাধারণ ছক “এই চিহ্নটি খুঁজে নিয়ে অমুক state-এ যাওয়া”, যার ভেতরে চিহ্ন আর পরের state প্যারামিটার। এভাবে তিনি “শেষ চিহ্নিত ঘর খোঁজা”, “শেষে copy করা”, “তুলনা করা” ধরনের ছোট যন্ত্র একবার লিখে বারবার ব্যবহার করেন, আর সেগুলো জুড়েই universal machine-এর বর্ণনা দাঁড় করান (পর্ব ৪৮)। প্রবন্ধটির ছাপা সংস্করণে কিছু ছাপার ভুলও ছিল, যা পরে অন্যরা, যেমন Emil Post, ধরিয়ে দেন বলে উল্লেখ পাওয়া যায়; এটিও মনে করিয়ে দেয় যে বড় TM হাতে লেখা কতটা ভুলপ্রবণ।

অর্থাৎ এই পর্বের কৌশলগুলো মডেলের জন্মের সঙ্গেই এসেছে। কারণটি গভীর: Turing একজন মানুষ “কম্পিউটার” (তখন এই শব্দের অর্থ ছিল হিসাবের কাজ করা মানুষ) কাগজে কী করেন, তা বিশ্লেষণ করে মডেলটি বানিয়েছিলেন। মানুষ খাতায় টিক দেয়, আঙুল দিয়ে ঘর ধরে, একই ছোট কাজ বারবার করে; মডেলটি সেই অভ্যাসেরই গাণিতিক রূপ।

মূল উপলব্ধি: চিহ্ন দিয়ে কাটা আর subroutine কোনো পরের যুগের সুবিধা নয়, এগুলো Turing machine ধারণার কেন্দ্রে; বড় যন্ত্র সবসময় ছোট, যাচাই-করা অংশ জুড়েই বানানো হয়।

প্র ০২এক-tape যন্ত্রে palindrome চিনতে n² ধাপ লাগে, অথচ যেকোনো laptop-এ এটি n ধাপে হয়। তাহলে Turing machine দিয়ে “দ্রুততা” মাপার অর্থ কী?

প্রশ্নটি সঠিক জায়গায় আঙুল রাখে: ধাপের সঠিক সংখ্যা মডেলের ওপর নির্ভর করে। এক-tape TM-এ palindrome-এর জন্য Ω(n²) একটি প্রমাণিত নিচের সীমা (প্রচলিতভাবে Hennie-র ১৯৬৫ সালের crossing sequence যুক্তি): tape-এর মাঝখানের সীমানা দিয়ে বাঁ অর্ধেকের তথ্য ডানে যেতে হয়, আর head প্রতিবার সীমানা পেরোলে বয়ে নিতে পারে শুধু state-এর সসীম তথ্য। দুই-tape TM-এ input একবার দ্বিতীয় tape-এ copy করে দুই head উল্টো দিকে চালালে O(n) হয় (পর্ব ৪৫)। আর RAM মডেলে, যেখানে যেকোনো ঘর এক ধাপে পড়া যায়, সেটিও O(n).

তবু TM দিয়ে মাপা অর্থহীন নয়, কারণ মডেলগুলোর পার্থক্য সীমিত। পর্ব ৪৫-এ দেখবেন, t(n) ধাপের একটি multi-tape যন্ত্রকে এক-tape যন্ত্র O(t(n)²) ধাপে অনুকরণ করতে পারে, আর যুক্তিসংগত RAM মডেলও polynomial খরচে TM-এ অনুকরণ করা যায়। অর্থাৎ মডেল বদলালে n থেকে n², n² থেকে n⁴ হতে পারে, কিন্তু polynomial থেকে exponential হয় না। এই কারণেই complexity তত্ত্বের মূল শ্রেণি P (পর্ব ৫৭) মডেল-নিরপেক্ষ: “polynomial সময়ে সমাধানযোগ্য” কথাটি এক-tape TM, multi-tape TM বা RAM, সবগুলোতে একই অর্থ রাখে। একে কখনো কখনো extended Church–Turing thesis-এর একটি দিক বলা হয়, যার সীমা নিয়ে পর্ব ৪৭ আর ৭৫-এ আলোচনা আছে।

ব্যবহারিক শিক্ষাটিও স্পষ্ট। Algorithm-এর কোর্সে (DSA কোর্সের পর্ব ০৪) Big-O মাপা হয় RAM-জাতীয় মডেলে, কারণ আসল কম্পিউটার তেমনই। TM-এর ধাপ গোনা কাজে আসে মডেলের সীমা বুঝতে, নিচের সীমা প্রমাণ করতে, আর P, NP-এর মতো শ্রেণি সংজ্ঞায়িত করতে, যেখানে polynomial-এর ভেতরের পার্থক্য উপেক্ষা করা হয়।

মূল উপলব্ধি: নির্দিষ্ট exponent মডেলের ওপর নির্ভর করে, কিন্তু polynomial বনাম exponential পার্থক্য মডেল বদলালেও টিকে থাকে; complexity তত্ত্ব ঠিক এই মজবুত পার্থক্যের ওপর দাঁড়িয়ে।

প্র ০৩Unary গুণে ১১∗১১১-এর মতো ছোট input-এও ৯৯ ধাপ লাগল। Input-এর encoding বদলালে একই সমস্যা সহজ বা কঠিন হয়ে যায় কেন?

সময় মাপা হয় input-এর দৈর্ঘ্যের function হিসেবে, আর দৈর্ঘ্য নির্ভর করে encoding-এর ওপর। সংখ্যা N-এর unary রূপের দৈর্ঘ্য N, binary রূপের প্রায় log2 N. ধরুন একটি algorithm N ধাপ নেয়: unary input-এর সাপেক্ষে এটি linear, কিন্তু binary input-এর দৈর্ঘ্য n ≈ log2 N-এর সাপেক্ষে N ≈ 2n, অর্থাৎ exponential. একই algorithm, একই ধাপ, শুধু মাপকাঠি বদলেছে।

গুণের ক্ষেত্রে unary-তে দুর্ভাগ্য দুই দিক থেকে আসে। প্রথমত, উত্তর লেখাই mn টি ঘর দাবি করে, তাই কোনো চতুর নকশাও mn ধাপের নিচে নামতে পারে না। দ্বিতীয়ত, এক-tape যন্ত্রকে প্রতিটি নতুন 1 লেখার জন্য হেঁটে উত্তরের শেষে যেতে হয়, তাই ধাপ m²n²-এর ক্রমে। Binary-তে স্কুলের গুণ (প্রতিটি বিটে shift আর যোগ) n বিটের সংখ্যায় এক-tape যন্ত্রেও polynomial, মোটামুটি n²-এর ক্রম বা কিছু বেশি, কারণ উত্তরের দৈর্ঘ্য মাত্র প্রায় 2n.

এই পার্থক্য complexity তত্ত্বে গুরুত্বপূর্ণ ভূমিকা রাখে। পর্ব ০৫-এ “reasonable encoding”-এর আলোচনায় দেখেছেন, সংখ্যা binary-তে (বা যেকোনো base ≥ 2-এ) লিখতে হয়; unary-তে লিখলে কৃত্রিমভাবে লম্বা input অনেক সমস্যাকে “দ্রুত” দেখায়। Subset sum-এর dynamic programming algorithm সংখ্যাগুলোর মানের polynomial, দৈর্ঘ্যের নয়: একে pseudo-polynomial বলে, আর এই কারণেই subset sum NP-complete থাকা সত্ত্বেও ছোট সংখ্যায় দ্রুত সমাধান হয় (পর্ব ৬১)। বাজারঘরের ক্ষেত্রেও একই সতর্কতা: “অর্ডারের টাকার পরিমাণের সমানুপাতিক সময়” শুনতে নিরীহ, কিন্তু টাকার অঙ্কের দৈর্ঘ্যের সাপেক্ষে তা exponential.

মূল উপলব্ধি: একটি যন্ত্র কত দ্রুত, সেই প্রশ্নের উত্তর input কীভাবে লেখা হলো তার ওপর নির্ভর করে; তাই complexity-র প্রতিটি দাবির সঙ্গে encoding-ও ঘোষণা করতে হয়।

প্র ০৪Simulator-এ step cap রাখা হলো। কিন্তু একটি সঠিক cap কি আগে থেকে হিসাব করা যায়? Busy Beaver এই প্রশ্নে কী বলে?

নির্দিষ্ট যন্ত্রের জন্য প্রায়ই যায়: PAL-এর জন্য (n + 1)(n + 2)/2, INC-এর জন্য 3n + 1. এমন একটি সীমা প্রমাণ করা মানেই প্রমাণ করা যে যন্ত্রটি decider. কিন্তু সব যন্ত্রের জন্য কাজ করে এমন একটি হিসাবযোগ্য cap নেই। Tibor Radó ১৯৬২ সালে Busy Beaver function সংজ্ঞায়িত করেন: k state আর দুই চিহ্নের যে TM-গুলো ফাঁকা tape থেকে শুরু করে শেষ পর্যন্ত থামে, তাদের মধ্যে সবচেয়ে বেশি ধাপ যে নেয়, তার ধাপের সংখ্যা S(k) (বইভেদে নাম আর রীতি একটু আলাদা)। Radó দেখান, S কোনো computable function দিয়ে ওপর থেকে বাঁধা যায় না; বাঁধা গেলে সেটি দিয়ে ফাঁকা tape-এর halting problem সমাধান হয়ে যেত।

ছোট k-এর জন্য মানগুলো পরিশ্রম করে বের করা হয়েছে। k = 5-এর জন্য S(5) = 47,176,870; এই মানের প্রার্থী যন্ত্রটি Heiner Marxen আর Jürgen Buntrock ১৯৮০-এর দশকের শেষে খুঁজে পান, আর ২০২৪ সালে bbchallenge নামের একটি অনলাইন সহযোগী দল প্রমাণ সম্পূর্ণ করে, যার মূল অংশ Coq proof assistant-এ যন্ত্র দিয়ে যাচাই করা। কাজটি ছিল বাকি প্রতিটি ৫-state যন্ত্রের জন্য দেখানো যে সেটি হয় এর আগেই থামে, নয়তো কখনো থামে না; হাজার হাজার যন্ত্রের জন্য আলাদা আলাদা “decider” প্রোগ্রাম লিখতে হয়েছিল। k = 6-এর জন্য এমন যন্ত্র জানা আছে যারা অকল্পনীয় বেশি ধাপ চলে বলে দেখানো হয়েছে, আর কিছু ছোট যন্ত্রের থামা-না-থামা গণিতের খোলা প্রশ্নের সঙ্গে জড়িত বলে জানা যায়।

এই পর্বের জন্য শিক্ষাটি ব্যবহারিক: step cap একটি নিরাপত্তা বেষ্টনী, বিচারক নয়। Cap-এ আটকানো মানে “এতক্ষণে থামেনি”, “কখনো থামবে না” নয়। তাই decider দাবি করতে হলে নকশার সঙ্গে থামার একটি যুক্তি দিন, যেমন প্রতিটি রাউন্ডে কিছু একটা কঠোরভাবে কমে। বিস্তারিত পর্ব ৫৫-এ।

মূল উপলব্ধি: নিজের নকশা-করা যন্ত্রের ধাপের সীমা প্রমাণ করা যায় আর করা উচিত; কিন্তু সব যন্ত্রের জন্য একটি সার্বজনীন cap অসম্ভব, আর Busy Beaver সেই অসম্ভবতার সবচেয়ে নাটকীয় রূপ।

প্র ০৫দৈর্ঘ্য ১০ পর্যন্ত ২০৪৬টি input-এ INC নিখুঁত। এটুকু পরীক্ষা কতটা ভরসা দেয়, আর কখন প্রমাণ অপরিহার্য?

Edsger Dijkstra-র নামে প্রচলিত একটি কথা আছে (১৯৬০-এর দশকের শেষে একটি সম্মেলনের প্রতিবেদনে পাওয়া যায় বলে উল্লেখ আছে): পরীক্ষা ভুলের উপস্থিতি দেখাতে পারে, অনুপস্থিতি নয়। INC0-এর ক্ষেত্রে brute force ঠিক তা-ই করেছে: ২০৪৬টির মধ্যে ১০টি ভুল ধরেছে, যা হাতের কয়েকটি উদাহরণে সহজে চোখ এড়াত। কিন্তু INC-এর শূন্য ভুল দৈর্ঘ্য ১১ বা ১০০০ সম্পর্কে কিছু প্রমাণ করে না।

তবু বাস্তবে ছোট পরিসরের নিখুঁত পরীক্ষা অনেক কিছু বলে। সফটওয়্যার যাচাইয়ের গবেষক Daniel Jackson “small scope hypothesis” নামে একটি পর্যবেক্ষণ জনপ্রিয় করেন: বেশিরভাগ ভুল ছোট উদাহরণেই ধরা পড়ে। TM-এর ক্ষেত্রে কারণটি স্বজ্ঞাত: যন্ত্রের state আর চিহ্ন সসীম, তাই ভুলগুলো সাধারণত কয়েকটি “ধরনের” input-এ দেখা দেয় (সব 1, ε, বিজোড় দৈর্ঘ্য), আর সেই ধরনগুলোর ছোট প্রতিনিধি দৈর্ঘ্য ১০-এর মধ্যেই থাকে। তবে এটি হাইপোথিসিস, theorem নয়: একটি যন্ত্র ইচ্ছা করে দৈর্ঘ্য ১০০-এ ভুল করতে পারে, যেমন state দিয়ে ১০০ পর্যন্ত গুনে।

প্রমাণ অপরিহার্য তিন জায়গায়। (১) দাবিটি সব দৈর্ঘ্যের জন্য, যেমন “PAL একটি decider”. (২) সময়ের সীমা, যেমন 3n + 1, যা মাপা সংখ্যার সঙ্গে মিললেও সাধারণ n-এর জন্য যুক্তি চায়। (৩) এমন যন্ত্র, যার আচরণ বড় input-এ বদলায়। আর একটি সীমাও জেনে রাখুন: “এই যন্ত্র কি তার বর্ণনা ঠিকমতো মানে?” প্রশ্নটি সাধারণভাবে স্বয়ংক্রিয়ভাবে নির্ণয়যোগ্য নয়; পর্ব ৫৩-এর Rice-এর theorem বলে, program-এর আচরণ নিয়ে প্রায় সব প্রশ্নই undecidable. তাই যাচাইয়ের ভার শেষ পর্যন্ত invariant আর প্রমাণের ওপর।

মূল উপলব্ধি: brute force ভুল খুঁজে বের করার সবচেয়ে সস্তা উপায় আর প্রমাণের আগে প্রথম ছাঁকনি; নিশ্চয়তা আসে শুধু invariant-ভিত্তিক প্রমাণ থেকে।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। tm_sim.py ব্লকে নিজের সারণি T("…") দিয়ে লিখে run(…, show=True) চালিয়ে উত্তর যাচাইও করতে পারেন।

  1. নকশা (copy subroutine): Input 1n (n ≥ 0). এমন একটি TM দিন, যা থামার সময় tape-এ 1n#1n রাখে (n = 0 হলে শুধু #). কোনো চিহ্নিত চিহ্ন যেন শেষে না থাকে। ধাপের সংখ্যা n-এর কোন ক্রমে বাড়ে?

    ধারণা: প্রথম 1-কে Y (বাঁ প্রান্তের নিশানা), পরেরগুলোকে X দিয়ে চিহ্নিত করুন; প্রতিটি চিহ্নের পরে ডানে গিয়ে শেষে একটি 1 লিখুন (প্রথমবার আগে # বসিয়ে)। সব চিহ্নিত হলে ডান থেকে বাঁয়ে X → 1 করুন; Y পেলে বোঝা যায় প্রথম ঘর, সেখানে 1 লিখে থামুন।

    সারণি: q0: 1 → Y, R, q1 · ␣ → #, R, qacc. q1: 1 → R · # → R, q2 · ␣ → #, R, q2. q2: 1 → R · ␣ → 1, L, q3. q3: 1, # → L · X, Y → R, q4. q4: 1 → X, R, q1 · # → L, q5. q5: X → 1, L · Y → 1, R, qacc.

    Scratch-এ n = 0 থেকে ৮ পর্যন্ত চালিয়ে tape ঠিক 1n#1n মিলেছে, আর ধাপ 1, 7, 17, 31, 49, …, 161, যা ঠিক 2n² + 4n + 1: quadratic, কারণ প্রতিটি copy-তে head প্রায় 2n ঘর যায়-আসে। লক্ষ করুন, Y ছাড়া শেষ ধাপে X-গুলো 1 বানাতে বাঁয়ে গিয়ে প্রথম ঘর চেনা যেত না।

  2. প্রমাণের ভুল খুঁজুন: একজন লিখেছেন, “INC0 (q0: 0, 1 → R · ␣ → L, q1; q1: 1 → 0, L · 0 → 1, R, qacc · ␣ → 1, R, qacc) সব input-এ সঠিক। প্রমাণ: q1 প্রতিটি 1-কে 0 করে বাঁয়ে যায়, যেমন হাতে carry নিয়ে যোগে হয়। প্রথম 0 বা ␣ পেলে 1 লেখে, তাই carry ঠিক জায়গায় বসে। সংখ্যার বাঁয়ে সবসময় ␣ থাকে, তাই সব 1-এর ক্ষেত্রেও উত্তর ঠিক। ∎” ভুলটি কোথায়? সঠিক বক্তব্য কী?

    ভুল শেষ বাক্যে: “সংখ্যার বাঁয়ে সবসময় ␣ থাকে” এক-দিকের tape-এ মিথ্যা। Input প্রথম ঘর থেকে শুরু, তার বাঁয়ে কোনো ঘর নেই; প্রথম ঘরে L বললে head সেখানেই থাকে। ফলে 1n-এ carry প্রথম ঘরকে 0 করে, head নড়ে না, তারপর সেই 0 পড়ে 1 লেখে: উত্তর 10n−1, অথচ ঠিক উত্তর 10n. পাল্টা উদাহরণ 111 → 100.

    সঠিক বক্তব্য: এক-দিকের tape-এ INC0 সঠিক ঠিক সেই input-গুলোতে, যাতে অন্তত একটি 0 আছে (তখন carry প্রথম ঘর পেরোতে চায় না)। tm_sim.py ব্লক দৈর্ঘ্য ১০ পর্যন্ত এটিই দেখিয়েছে: ২০৪৬টির মধ্যে শুধু ১০টি সব-1 input-এ ভুল। দুই-দিকের tape-এ (যেমন automata-lib-এ) INC0 সব input-এ সঠিক। প্রমাণে লুকানো অনুমান, এখানে tape-এর রীতি, সবচেয়ে সাধারণ ফাঁক।

  3. Trace আর অনুমান: অংশ ২-এর INC চালান (ক) 0111-এ আর (খ) 1111-এ। প্রতিটির শেষ tape আর মোট ধাপের সংখ্যা আগে অনুমান করুন, তারপর configuration লিখে মেলান।

    (ক) 0111: q0 0111 ⊢ O q1 111 ⊢ O1 q1 11 ⊢ O11 q1 1 ⊢ O111 q1 ␣ ⊢ O11 q2 1 ⊢ O1 q2 10 ⊢ O q2 100 ⊢ q2 O000 ⊢ 1 qacc 000. Carry চিহ্নিত O-তে পৌঁছায়, সেখানে 1 লিখে শেষ: tape 1000, ৯ ধাপ (2n + 1, n = 4).

    (খ) 1111: একই পথে q2 I000-তে পৌঁছায় (৮ ধাপ), তারপর “I → 1, R, q4”: 1 q4 000. q4 তিনটি 0 পেরিয়ে ␣-এ 0 লেখে: 10000 qacc ␣. Tape 10000, ১৩ ধাপ = 3n + 1, সবচেয়ে খারাপ ক্ষেত্র। দুটি সংখ্যাই scratch-এর simulator-এ মিলেছে।

  4. নকশা ও প্রমাণ (binary decrement): Binary w (n ≥ 1 বিট) থেকে w − 1 লেখার TM দিন, যা একই দৈর্ঘ্য রাখে (1000 থেকে 0111) আর w = 0 হলে reject করে। কেন এখানে implicit reject কাজে আসে? ধাপের সর্বোচ্চ সীমা কত?

    INC-এর আয়না-রূপ: borrow বাঁয়ে বয়ে নেওয়া। q0: 0 → O, R, q1 · 1 → I, R, q1. q1: 0, 1 → R · ␣ → L, q2. q2: 0 → 1, L · 1 → 0, L, q3 · I → 0, R, qacc. q3: 0, 1 → L · O → 0, R, qacc · I → 1, R, qacc.

    q2-তে O-এর কোনো নিয়ম নেই: borrow প্রথম ঘর পর্যন্ত পৌঁছে সেখানে 0 পাওয়া মানে সব বিট 0 ছিল, অর্থাৎ w = 0, তাই implicit reject ঠিক সেই কাজটি করে, আলাদা state ছাড়াই। ধাপ: n + 1 ধাপে শেষ বিটে, তারপর বাঁয়ে প্রথম ঘর পর্যন্ত মোট বড়জোর n ধাপ, তাই সর্বোচ্চ 2n + 1. Scratch-এ দৈর্ঘ্য ১ থেকে ১০-এর ২০৪৬টি input-এ int(w, 2) − 1-এর সঙ্গে মিলেছে, আর ঠিক ১০টি সব-0 input reject হয়েছে; 1000 আর 0001 দুটিতেই ৯ ধাপ।

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

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

ক্রমএকটি সমস্যা থেকে Turing machine নকশা আর যাচাইয়ের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Language বা function স্পষ্ট করা, ছোট উদাহরণ আর প্রান্তের ক্ষেত্র (ε, এক চিহ্ন) লেখা
  2. কথায় high-level algorithm লেখা
  3. Tape alphabet ঠিক করা: চিহ্নিত সংস্করণ, বিভাজক আর ␣
  4. প্রতিটি কাজকে state-এ ভাগ করে transition সারণি লেখা
  5. Step cap-সহ simulator-এ ছোট সব input-এ চালিয়ে সংজ্ঞার সঙ্গে মেলানো
  6. Invariant দিয়ে সঠিকতা আর ধাপ গুনে সময়ের সীমা প্রমাণ করা

Sipser-এর রীতির Turing machine-এ tape শুধু ডানে অসীম। Head প্রথম ঘরে আছে আর transition বলছে “লিখে L”. তখন কী হয়?

  • বাঁয়ে একটি নতুন ␣ ঘর তৈরি হয়ে head সেখানে যায়
  • চিহ্ন লেখা হয়, head প্রথম ঘরেই থাকে
  • যন্ত্র সঙ্গে সঙ্গে reject করে
  • কিছুই লেখা হয় না, যন্ত্র থেমে যায়

একটি Turing machine state q-তে চিহ্ন c পড়ছে, কিন্তু transition সারণিতে (q, c)-এর কোনো সারি নেই। Sipser-এর রীতিতে এর অর্থ কী?

  • যন্ত্র input গ্রহণ করে
  • যন্ত্র চিরকাল একই configuration-এ থাকে
  • যন্ত্র qreject-এ যায় (implicit reject)
  • যন্ত্র চিহ্ন না বদলে ডানে এক ঘর সরে

একটি TM tape-এর binary সংখ্যায় 1 যোগ করে এভাবে: q0-এ ডানে চলে, ␣ পেলে L দিয়ে q1; q1-এ “1 → 0, L”, আর “0 → 1, R” বা “␣ → 1, R” দিয়ে accept. Tape শুধু ডানে অসীম, প্রথম ঘরে L বললে head নড়ে না। Input 111 হলে শেষ tape কী?

  • 1000
  • 100
  • 000
  • যন্ত্র কখনো থামে না

এক-tape Turing machine দুই প্রান্তের চিহ্ন মুছে মুছে zig-zag পদ্ধতিতে palindrome যাচাই করে। দৈর্ঘ্য n-এর input-এ সবচেয়ে খারাপ ক্ষেত্রে ধাপের সংখ্যা কোন ক্রমের?

  • Θ(n)
  • Θ(n log n)
  • Θ(n²)
  • Θ(2n)

Tape alphabet Γ-তে k টি চিহ্ন। একটি TM মাঝখানে একটি নতুন চিহ্ন ঢোকাতে বাকি অংশ এক ঘর ডানে ঠেলে, প্রতিটি ঘরের পুরোনো চিহ্ন state-এ বয়ে নিয়ে। এই ঠেলার কাজে মোটামুটি কয়টি “হাতে চিহ্ন” state লাগে?

  • ১টি
  • প্রায় k টি, প্রতি চিহ্নে একটি
  • 2k টি
  • input-এর দৈর্ঘ্য n-এর সমান

Unary যোগের TM: q0-এ “1 → R” আর “+ → 1, R, q1”; q1-এ “1 → R” আর “␣ → L, q2”; q2-তে “1 → ␣, L, qaccept”. Input 111+11 (৩ + ২)-এ যন্ত্র মোট কয়টি ধাপে থামে?

  • ৫
  • ৬
  • ৮
  • ১০

শব্দকোষ

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

মনে রাখুন

  1. নকশা তিন স্তরে: high-level algorithm, implementation (head কোথায়, কী লেখে), formal সারণি; না-লেখা নিয়ম মানে implicit reject.
  2. ছয় কৌশল: চিহ্ন দিয়ে কাটা, zig-zag, tape সরানো, বাড়তি চিহ্ন, state-এ স্মৃতি, subroutine; state সবসময় সসীম, সংখ্যাটি |Γ|-এর ওপর নির্ভর করতে পারে, n-এর ওপর নয়।
  3. এক-দিকের tape-এ যন্ত্র প্রথম ঘর চেনে না: প্রথম ঘর চিহ্নিত করুন বা ▷ বসান; INC0-এর 111 → 100 এই ফাঁদের উদাহরণ।
  4. ধাপ গুনুন: INC ≤ 3n + 1 (linear), PAL = (n + 1)(n + 2)/2 (quadratic), unary গুণ প্রায় m²n²; encoding বদলালে সময়ের অর্থ বদলায়।
  5. পরীক্ষা: reference, ছোট সব input-এ brute force, step cap, প্রান্তের ক্ষেত্র; তারপর invariant দিয়ে প্রমাণ। Cap-এ আটকানো মানে “এখনো থামেনি”, “কখনো থামবে না” নয়।

পরের পর্বে: একাধিক tape, একাধিক track আর দুই দিকে অসীম tape-এর Turing machine: কেন এরা সবাই সমান শক্তিশালী, এক-tape যন্ত্রে multi-tape অনুকরণের খরচ কেন বর্গাকার, আর enumerator দিয়ে language “ছাপা”.

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

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