Turing Machine Simulator

কেন এই প্রজেক্ট

turing-machines আর church-turing-thesis লেসনে আপনি transition table হাতে লিখে trace করেছেন — কাগজে, ধাপে ধাপে, একটা tape diagram দেখে। এই প্রজেক্টে সেই একই কাজটা একটা প্রোগ্রামে বদলাবেন — আর তাতে একটা জিনিস অবিলম্বে স্পষ্ট হয়ে উঠবে যা কাগজে সহজে চোখ এড়িয়ে যায়: tape অসীম, কিন্তু মেমরি না। প্রতিটা ডিজাইন সিদ্ধান্তে (কীভাবে tape represent করবেন, negative index সামলাবেন কীভাবে, কখন থামবেন না জানলে কী করবেন) সেই ফাঁকটার মুখোমুখি হতে হবে।

সবচেয়ে গুরুত্বপূর্ণ অংশ শেষে — universal TM। এখানে আপনি সত্যিই Turing-এর ১৯৩৬-এর মূল অন্তর্দৃষ্টিটা কোডে অনুভব করবেন: একটা মেশিন U, যেটা নিজে fixed থাকে, কিন্তু ইনপুট হিসেবে অন্য একটা মেশিনের বর্ণনা নিয়ে সম্পূর্ণ ভিন্ন আচরণ প্রদর্শন করে। এটাই আপনার Python interpreter নিজে যা করে প্রতিদিন — আপনার .py ফাইলকে “ডেটা” হিসেবে পড়ে, “প্রোগ্রাম” হিসেবে চালায়।

ধাপে ধাপে

১. Tape abstraction

Python list-এ tape রাখলে negative index সমস্যা করে (Python-এ negative index মানে শেষ থেকে গোনা, tape-এ বাম দিকে যাওয়া না)। সবচেয়ে পরিষ্কার সমাধান — dict[int, str], blank-এর জন্য default:

from collections import defaultdict

class Tape:
    def __init__(self, input_str: str, blank: str = "_"):
        self.blank = blank
        self.cells = defaultdict(lambda: blank)
        for i, ch in enumerate(input_str):
            self.cells[i] = ch
        self._min_written = 0
        self._max_written = len(input_str) - 1

    def read(self, pos: int) -> str:
        return self.cells[pos]

    def write(self, pos: int, symbol: str):
        self.cells[pos] = symbol
        self._min_written = min(self._min_written, pos)
        self._max_written = max(self._max_written, pos)

    def snapshot(self, head: int) -> str:
        """Debug/trace-এর জন্য — head-সহ tape-এর দৃশ্যমান অংশ string করে।"""
        lo, hi = self._min_written, self._max_written
        chars = []
        for i in range(lo, hi + 1):
            c = self.cells[i]
            chars.append(f"[{c}]" if i == head else c)
        return "".join(chars) or self.blank

defaultdict ব্যবহার করার সুবিধা — যত দূরেই head যাক, শুধু ব্যবহৃত ঘরগুলোই মেমরিতে থাকে, বাকি সব “conceptually blank” — ঠিক formal সংজ্ঞার “অসীম কিন্তু বেশিরভাগ blank” tape-এর একটা বাস্তবসম্মত রূপ।

Checkpoint: Tape("101").write(-5, "X") করে snapshot(0) কল করুন — নিশ্চিত হোন negative position-এও লেখা আর পড়া ঠিকঠাক কাজ করছে, আর _min_written আপডেট হচ্ছে।

২. Generic TM interpreter

একটা TuringMachine ক্লাস যা transition table, states, start/accept/reject ধরে রাখে, আর একটা run() মেথড যা ধাপে ধাপে চালায়:

class TuringMachine:
    def __init__(self, states, tape_alphabet, blank, transitions,
                 start, accept, reject):
        self.states = states
        self.blank = blank
        self.delta = transitions        # {(state, symbol): (new_state, write, move)}
        self.start = start
        self.accept = accept
        self.reject = reject

    def run(self, input_str: str, max_steps: int = 1_000_000, trace: bool = False):
        tape = Tape(input_str, self.blank)
        head, state, steps = 0, self.start, 0

        while state not in (self.accept, self.reject):
            if steps >= max_steps:
                return "TIMEOUT", steps, tape
            key = (state, tape.read(head))
            if key not in self.delta:
                return "REJECT (undefined transition)", steps, tape
            new_state, write, move = self.delta[key]
            tape.write(head, write)
            state = new_state
            head += 1 if move == "R" else -1
            steps += 1
            if trace:
                print(f"  step {steps:>4}  state={state:<10}  {tape.snapshot(head)}")

        verdict = "ACCEPT" if state == self.accept else "REJECT"
        return verdict, steps, tape

Checkpoint: states/tape_alphabet এখানে আসলে চালানোর জন্য লাগে না (delta dict-ই আসল সত্য), কিন্তু রেখে দিন — পরের ধাপে (encoding) এগুলো serialize করতে লাগবে। মন্তব্যে লিখুন কেন run() max_steps ছাড়া কখনো একটা loop-করা মেশিনে থামবে না — সরাসরি halting problem লেসনের সাথে সংযোগ।

৩. ক্লাসিক মেশিন — unary ও binary increment

unary_increment = TuringMachine(
    states={"q0", "qaccept"}, tape_alphabet={"1", "_"}, blank="_",
    transitions={
        ("q0", "1"): ("q0", "1", "R"),
        ("q0", "_"): ("qaccept", "1", "R"),   # শেষে পৌঁছে একটা 1 যোগ
    },
    start="q0", accept="qaccept", reject="qreject",
)

binary_increment = TuringMachine(
    states={"q0", "q1", "qaccept"}, tape_alphabet={"0", "1", "_"}, blank="_",
    transitions={
        ("q0", "0"): ("q0", "0", "R"), ("q0", "1"): ("q0", "1", "R"),
        ("q0", "_"): ("q1", "_", "L"),           # ডান প্রান্তে পৌঁছে ফিরে carry শুরু
        ("q1", "1"): ("q1", "0", "L"),           # 1 -> 0, carry চালিয়ে যাও
        ("q1", "0"): ("qaccept", "1", "R"),      # 0 -> 1, carry শেষ
        ("q1", "_"): ("qaccept", "1", "R"),      # সব 1 ছিল (যেমন 111 -> 1000)
    },
    start="q0", accept="qaccept", reject="qreject",
)

print(unary_increment.run("111")[:2])       # ACCEPT, tape দৈর্ঘ্য 4
print(binary_increment.run("101")[:2])      # ACCEPT — 101(5) -> 110(6)
print(binary_increment.run("111")[:2])      # ACCEPT — 111(7) -> 1000(8), carry chain

Checkpoint: binary_increment.run("111", trace=True) চালিয়ে দেখুন carry chain-টা ধাপে ধাপে বাম দিকে কীভাবে propagate করে — প্রতিটা 1 → 0 একটা carry, 0 → 1-এ থেমে যাওয়া।

৪. Palindrome checker

দুই প্রান্ত থেকে ভেতরের দিকে মিলিয়ে, প্রতিটা মেলা অক্ষর X দিয়ে mark করে — TM-এ “state দিয়ে মনে রাখা কোন অক্ষর মিলাচ্ছি” একটা সাধারণ কৌশল:

palindrome = TuringMachine(
    states={"q_right0", "q_right1", "find_end0", "find_end1",
            "q_left", "qaccept"},
    tape_alphabet={"0", "1", "X", "_"}, blank="_",
    transitions={
        # বাম প্রান্তের অক্ষর মনে রেখে (state-এ) ডানে যাও
        ("q_right0", "0"): ("q_right0", "0", "R"),
        ("q_right0", "1"): ("q_right0", "1", "R"),
        ("q_right0", "X"): ("q_right0", "X", "R"),
        ("q_right0", "_"): ("find_end0", "_", "L"),
        ("q_right1", "0"): ("q_right1", "0", "R"),
        ("q_right1", "1"): ("q_right1", "1", "R"),
        ("q_right1", "X"): ("q_right1", "X", "R"),
        ("q_right1", "_"): ("find_end1", "_", "L"),

        # ডান প্রান্তের অক্ষর যাচাই করো, mark করো, বামে ফিরে যাও
        ("find_end0", "0"): ("q_left", "X", "L"),
        ("find_end1", "1"): ("q_left", "X", "L"),
        ("find_end0", "X"): ("qaccept", "X", "R"),   # সব মিলে গেছে
        ("find_end1", "X"): ("qaccept", "X", "R"),

        # বাম দিকে ফিরে, পরবর্তী unmark করা অক্ষর খুঁজে বের করো
        ("q_left", "X"): ("q_left", "X", "L"),
        ("q_left", "0"): ("q_right0", "X", "R"),
        ("q_left", "1"): ("q_right1", "X", "R"),
        ("q_left", "_"): ("qaccept", "_", "R"),      # মাঝখানে পৌঁছে গেছে
    },
    start="q_left", accept="qaccept", reject="qreject",
)

for w in ["0110", "0100", "101", "1", ""]:
    verdict, steps, _ = palindrome.run(w)
    print(f"{w!r:>6} -> {verdict}  ({steps} steps)")

Checkpoint: find_end0/find_end1-এ যদি ডান প্রান্তের অক্ষর মেলে না (mismatch) — লক্ষ্য করুন কোনো transition নেই, তাই এটা REJECT (undefined transition) হয়ে যায় স্বয়ংক্রিয়ভাবে। এটা কি সঠিক আচরণ? মন্তব্যে লিখুন কেন “undefined = reject” একটা যুক্তিসঙ্গত convention, কিন্তু formal সংজ্ঞায় δ কে total function ধরা হয় — পার্থক্যটা ব্যাখ্যা করুন।

৫. `{0ⁿ1ⁿ}` — turing-machines লেসনের মেশিন পুনর্ব্যবহার

turing-machines লেসনে হাতে বানানো cross-off মেশিনটা এখানে আনুন এবং TuringMachine ক্লাসে বসান। এটা আপনার interpreter-এর প্রথম “সত্যিকার regression test” — লেসনে হাতে করা ১৩-step trace-এর সাথে আপনার প্রোগ্রামের output মিলতে হবে।

eq_count = TuringMachine(
    states={"q0", "q1", "q2", "q3", "qaccept"},
    tape_alphabet={"0", "1", "X", "Y", "_"}, blank="_",
    transitions={
        ("q0", "0"): ("q1", "X", "R"), ("q0", "Y"): ("q3", "Y", "R"),
        ("q0", "_"): ("qaccept", "_", "R"),
        ("q1", "0"): ("q1", "0", "R"), ("q1", "Y"): ("q1", "Y", "R"),
        ("q1", "1"): ("q2", "Y", "L"),
        ("q2", "0"): ("q2", "0", "L"), ("q2", "Y"): ("q2", "Y", "L"),
        ("q2", "X"): ("q0", "X", "R"),
        ("q3", "Y"): ("q3", "Y", "R"), ("q3", "_"): ("qaccept", "_", "R"),
    },
    start="q0", accept="qaccept", reject="qreject",
)

verdict, steps, _ = eq_count.run("0011", trace=True)
assert verdict == "ACCEPT" and steps == 13, f"লেসনের trace-এর সাথে মিলল না: {steps} steps"

Checkpoint: যদি steps != 13 হয়, আপনার interpreter আর হাতে-করা trace-এর মধ্যে একটা পার্থক্য আছে — সাধারণত head movement বা write order-এ off-by-one। এই ধাপটা বাদ দেবেন না — এটাই নিশ্চিত করে বাকি সব মেশিনের output বিশ্বাসযোগ্য।

৬. TM encoding — একটা মেশিনকে একটা string-এ

Universal TM বানানোর আগে, একটা মেশিনকে সম্পূর্ণভাবে একটা single string-এ এনকোড করতে হবে (JSON না — সত্যিকার tape-এ লেখার মতো, delimiter দিয়ে):

def encode_tm(tm: TuringMachine) -> str:
    """(state, symbol) -> (new_state, write, move) — প্রতিটা transition
    একটা '#'-দিয়ে আলাদা রেকর্ড, ভেতরে ':' দিয়ে ক্ষেত্র আলাদা।"""
    parts = [f"START:{tm.start}", f"ACCEPT:{tm.accept}", f"REJECT:{tm.reject}",
              f"BLANK:{tm.blank}"]
    for (state, sym), (new_state, write, move) in tm.delta.items():
        parts.append(f"{state},{sym}->{new_state},{write},{move}")
    return "#".join(parts)


def decode_tm(encoded: str) -> TuringMachine:
    fields = encoded.split("#")
    meta = dict(f.split(":", 1) for f in fields[:4])
    delta = {}
    states, alphabet = set(), set()
    for rule in fields[4:]:
        lhs, rhs = rule.split("->")
        state, sym = lhs.split(",")
        new_state, write, move = rhs.split(",")
        delta[(state, sym)] = (new_state, write, move)
        states.update([state, new_state])
        alphabet.update([sym, write])
    return TuringMachine(states, alphabet, meta["BLANK"], delta,
                          meta["START"], meta["ACCEPT"], meta["REJECT"])


encoded = encode_tm(unary_increment)
print(encoded)
restored = decode_tm(encoded)
assert restored.run("111") == unary_increment.run("111")

Checkpoint: encoded স্ট্রিং প্রিন্ট করে দেখুন — এটাই আক্ষরিকভাবে ⟨M⟩, যা লেসনে আমরা tape-এ “লিখতে” বলেছিলাম কিন্তু বিমূর্তভাবে রেখে দিয়েছিলাম। এখন এটা concrete — শুধু একটা string, ঠিক input w-এর মতোই tape-এ বসানো যায়।

৭. Universal TM

এখন আসল কাজ — একটা function যা ⟨M⟩#w ফরম্যাটে একটা string নেয় আর M-কে w-তে simulate করে, ঠিক একই run() ব্যবহার করে যা আগে থেকেই আছে:

def universal_tm(encoded_program_and_input: str, max_steps=1_000_000):
    """
    U(⟨M⟩#w) — এই একটা function, কিন্তু ভেতরে যা encode করা আছে
    সেটা বদলে সম্পূর্ণ ভিন্ন মেশিনের আচরণ পাওয়া যায়। এটাই universality।
    """
    encoded_M, w = encoded_program_and_input.split("|", 1)
    M = decode_tm(encoded_M)
    return M.run(w, max_steps=max_steps)


program_input = encode_tm(eq_count) + "|" + "0011"
print("U(⟨eq_count⟩, '0011') =", universal_tm(program_input)[:2])

program_input2 = encode_tm(palindrome) + "|" + "0110"
print("U(⟨palindrome⟩, '0110') =", universal_tm(program_input2)[:2])

Checkpoint: এই মুহূর্তে আপনার কাছে একটা function আছে যেটা নিজে বদলায় না, কিন্তু তার ইনপুট বদলে সম্পূর্ণ ভিন্ন অ্যালগরিদম চালায় — eq_count, palindrome, binary_increment, যেটাই এনকোড করে দেবেন। এটাই Turing-এর ১৯৩৬-এর মূল insight, আর এটাই আজকের প্রতিটা interpreter (Python নিজেও) যা করে আপনার .py ফাইল পড়ে।

৮. Step-limit ও timeout হ্যান্ডলিং

def collatz_tm_style():
    """একটা প্রোগ্রাম যার halting status মানবজাতি আজও নিশ্চিতভাবে জানে না —
    সরাসরি decidability-and-halting-problem লেসনের experiment-এর reprise।"""
    # TM হিসেবে না লিখে সরাসরি Python-এ — TM-এ লেখা সম্ভব কিন্তু দীর্ঘ,
    # নিজে চেষ্টা করে দেখতে পারেন 'নিজে বাড়ান'-এ
    def run(n, max_steps=100_000):
        steps = 0
        while n != 1 and steps \< max_steps:
            n = n // 2 if n % 2 == 0 else 3 * n + 1
            steps += 1
        return ("ACCEPT" if n == 1 else "TIMEOUT"), steps
    return run

collatz = collatz_tm_style()
for n in [27, 97, 6171]:
    verdict, steps = collatz(n)
    print(f"n={n:>6} -> {verdict} ({steps} steps)")

Checkpoint: এই মুহূর্তে থামুন এবং লিখুন — আপনার universal_tm কখনো max_steps ছাড়া একটা loop-করা এনকোডেড মেশিনে চিরকাল আটকে যেতে পারে। এটা bug না — এটা প্রমাণ যে আপনি সত্যিই একটা universal simulator বানিয়েছেন, কোনো “সবসময়-জানে থামবে কি না” শর্টকাট ছাড়া। এই ফাঁকটাই decidability-and-halting-problem লেসনের পুরো বিষয়বস্তু — আপনার কোডে এটা একটা abstract প্রমাণ না, একটা বাস্তব, অনুভবযোগ্য সীমাবদ্ধতা।

নিজেকে চ্যালেঞ্জ করুন

encode_tm/decode_tm-কে সত্যিকার একটামাত্র tape alphabet-এ বসান (এখন #, ,, ->, | — এই বিশেষ চিহ্নগুলো tape alphabet-এর বাইরে) — শুধু 0 আর 1 ব্যবহার করে পুরো encoding করুন (unary বা binary সংখ্যা দিয়ে state/symbol representation)
Multi-tape TM simulator লিখুন (২টা independent tape, প্রতিটার নিজস্ব head) — turing-machines লেসনের “single tape দিয়ে simulate করা যায়” দাবিটা যাচাই করতে, সেই simulation-টাও লিখুন এবং speed তুলনা করুন
Nondeterministic TM simulator লিখুন (BFS দিয়ে সব branch একসাথে explore করা) — একটা ছোট NTM ডিজাইন করুন যেটা deterministic ভার্সনের চেয়ে “স্বাভাবিকভাবে” ছোট (কম states), তারপর branching factor বাড়ালে simulation কত ধীর হয় মাপুন
একটা visual tape renderer বানান — প্রতিটা step-এর পর tape, head position, state একটা প্রশস্ত টার্মিনাল আর্টে দেখান, ধীরে ধীরে animate করুন (time.sleep দিয়ে)
maybe_halts-এর মতো একটা heuristic halt-checker বানান যেটা কিছু সাধারণ প্যাটার্ন চেনে (যেমন state আর head position একই জায়গায় দুইবার আসা মানে নিশ্চিত loop, যদি tape-ও অপরিবর্তিত থাকে) — এবং একটা মন্তব্যে লিখুন এই heuristic কোন ক্ষেত্রে ব্যর্থ হবে (একটা মেশিন খুঁজে বের করুন যেটা loop করে কিন্তু কখনো একই configuration-এ ফিরে আসে না)

যা এখানে শিখলেন, পরে যেখানে লাগবে

এখানে	পরে
Tape abstraction, dict-ভিত্তিক sparse storage	যেকোনো sparse data structure — hash map-ভিত্তিক grid, sparse matrix
Generic transition-table interpreter	compilers module — bytecode interpreter, VM dispatch loop হুবহু একই প্যাটার্ন
TM encoding ⟨M⟩	church-turing-thesis-এর universal TM ধারণা concrete হলো — আর প্রোগ্রামিং ভাষার AST serialization/deserialization-এর পূর্বাভাস
Universal TM	প্রতিটা interpreter, VM, bytecode runtime — Python নিজে, JVM, এমনকি একটা browser-এর JS engine
Step-limit/timeout হ্যান্ডলিং	decidability-and-halting-problem-এর তাত্ত্বিক সীমা একটা হাতে-নাড়াচাড়া করা bug হয়ে উঠল — production system-এ timeout ডিজাইন করার সময় এই সীমাবদ্ধতা মনে রাখা জরুরি
Palindrome/eq-count মেশিন ডিজাইন	reductions-and-undecidable-problems-এর “গেটকিপার” প্যাটার্ন — একটা মেশিনকে subroutine হিসেবে ব্যবহার করে নতুন মেশিন বানানো

মাইলস্টোন

আগে যা পড়া দরকার

কেন এই প্রজেক্ট

ধাপে ধাপে

১. Tape abstraction

২. Generic TM interpreter

৩. ক্লাসিক মেশিন — unary ও binary increment

৪. Palindrome checker

৫. `{0ⁿ1ⁿ}` — turing-machines লেসনের মেশিন পুনর্ব্যবহার

৬. TM encoding — একটা মেশিনকে একটা string-এ

৭. Universal TM

৮. Step-limit ও timeout হ্যান্ডলিং

নিজেকে চ্যালেঞ্জ করুন

যা এখানে শিখলেন, পরে যেখানে লাগবে

মাইলস্টোন

আগে যা পড়া দরকার

কেন এই প্রজেক্ট

ধাপে ধাপে

১. Tape abstraction

২. Generic TM interpreter

৩. ক্লাসিক মেশিন — unary ও binary increment

৪. Palindrome checker

৫. {0ⁿ1ⁿ} — turing-machines লেসনের মেশিন পুনর্ব্যবহার

৬. TM encoding — একটা মেশিনকে একটা string-এ

৭. Universal TM

৮. Step-limit ও timeout হ্যান্ডলিং

নিজেকে চ্যালেঞ্জ করুন

যা এখানে শিখলেন, পরে যেখানে লাগবে

৫. `{0ⁿ1ⁿ}` — turing-machines লেসনের মেশিন পুনর্ব্যবহার