টুরিং মেশিন ডিজাইন করা — worked examples

B = '_'

class TM:
    def __init__(self, trans, start, accept, reject):
        self.trans, self.start = trans, start
        self.accept, self.reject = accept, reject

    def run(self, s, max_steps=50000):
        tape = {i: c for i, c in enumerate(s)}
        head, state, steps = 0, self.start, 0
        while steps < max_steps:
            if state == self.accept:
                return "accept", steps
            if state == self.reject:
                return "reject", steps
            sym = tape.get(head, B)
            key = (state, sym)
            if key not in self.trans:
                return "reject", steps
            ns, w, mv = self.trans[key]
            tape[head] = w
            head += 1 if mv == 'R' else -1
            state = ns
            steps += 1
        return "timeout", steps

def build_ww_tm():
    t = {}
    t[('find_left', B)] = ('accept', B, 'R')          # খালি স্ট্রিং -- accept

    # ধাপ ১: leftmost অচিহ্নিত সিম্বলকে a-ট্যাগ দাও, তারপর ডানপ্রান্তে গিয়ে
    # rightmost অচিহ্নিত সিম্বলকে b-ট্যাগ দাও -- এভাবে দুই দিক থেকে এগোতে থাকো
    t[('find_left', '0')] = ('seek_right', 'a0', 'R')
    t[('find_left', '1')] = ('seek_right', 'a1', 'R')
    t[('find_left', 'a0')] = ('find_left', 'a0', 'R')
    t[('find_left', 'a1')] = ('find_left', 'a1', 'R')
    t[('find_left', 'b0')] = ('phase2_start', 'b0', 'L')  # a আর b মিলে গেল -- মিডপয়েন্ট!
    t[('find_left', 'b1')] = ('phase2_start', 'b1', 'L')

    for sym in ('0', '1', 'a0', 'a1', 'b0', 'b1'):
        t[('seek_right', sym)] = ('seek_right', sym, 'R')
    t[('seek_right', B)] = ('find_right', B, 'L')

    t[('find_right', 'b0')] = ('find_right', 'b0', 'L')
    t[('find_right', 'b1')] = ('find_right', 'b1', 'L')
    t[('find_right', '0')] = ('back_to_left', 'b0', 'L')
    t[('find_right', '1')] = ('back_to_left', 'b1', 'L')
    t[('find_right', 'a0')] = ('reject', 'a0', 'L')      # একটিমাত্র মাঝের সেল -- বিজোড় দৈর্ঘ্য
    t[('find_right', 'a1')] = ('reject', 'a1', 'L')

    for sym in ('0', '1', 'b0', 'b1'):
        t[('back_to_left', sym)] = ('back_to_left', sym, 'L')
    t[('back_to_left', 'a0')] = ('find_left', 'a0', 'R')
    t[('back_to_left', 'a1')] = ('find_left', 'a1', 'R')

    # ধাপ ২: বাম প্রান্তে ফিরে গিয়ে a[i] বনাম b[i] একে একে মেলাও
    t[('phase2_start', 'a0')] = ('phase2_start', 'a0', 'L')
    t[('phase2_start', 'a1')] = ('phase2_start', 'a1', 'L')
    t[('phase2_start', B)] = ('cmp_find_a', B, 'R')

    t[('cmp_find_a', 'X0')] = ('cmp_find_a', 'X0', 'R')
    t[('cmp_find_a', 'X1')] = ('cmp_find_a', 'X1', 'R')
    t[('cmp_find_a', 'a0')] = ('cmp_seek_b0', 'X0', 'R')
    t[('cmp_find_a', 'a1')] = ('cmp_seek_b1', 'X1', 'R')
    t[('cmp_find_a', B)] = ('accept', B, 'R')            # সব জোড়া মিলে গেছে -- accept

    for v, other in (('0', '1'), ('1', '0')):
        st = 'cmp_seek_b' + v
        t[(st, 'a0')] = (st, 'a0', 'R')
        t[(st, 'a1')] = (st, 'a1', 'R')
        t[(st, 'X0')] = (st, 'X0', 'R')
        t[(st, 'X1')] = (st, 'X1', 'R')
        t[(st, 'b' + v)] = ('cmp_back', 'X' + v, 'L')     # মিলেছে
        t[(st, 'b' + other)] = ('reject', 'b' + other, 'R')  # মেলেনি

    for sym in ('a0', 'a1', 'X0', 'X1', 'b0', 'b1'):
        t[('cmp_back', sym)] = ('cmp_back', sym, 'L')
    t[('cmp_back', B)] = ('cmp_find_a', B, 'R')

    return TM(t, 'find_left', 'accept', 'reject')

tm = build_ww_tm()
tests = ["0101", "1111", "", "0110", "010"]
for s in tests:
    result, steps = tm.run(s)
    w_repr = s[:len(s)//2] if len(s) % 2 == 0 else "N/A"
    print(f"{s!r:8s} -> {result:8s} (ধাপ {steps:3d}) | w={w_repr!r}")

def build_increment_tm():
    t = {}
    t[('scan_right', '0')] = ('scan_right', '0', 'R')
    t[('scan_right', '1')] = ('scan_right', '1', 'R')
    t[('scan_right', B)] = ('carry', B, 'L')      # রাইটমোস্ট ডিজিটের পরে ব্ল্যাংক পেলে ক্যারি শুরু

    t[('carry', '0')] = ('done', '1', 'L')        # 0+1=1 -- ক্যারি থেমে গেল
    t[('carry', '1')] = ('carry', '0', 'L')       # 1+1=10 -- 0 লেখো, ক্যারি বামে চালিয়ে যাও
    t[('carry', B)] = ('done', '1', 'L')          # সব ডিজিট 1 ছিল -- বাম প্রান্তে নতুন 1 বসাও (টেপ বাড়ল!)

    t[('done', '0')] = ('done', '0', 'L')
    t[('done', '1')] = ('done', '1', 'L')
    t[('done', B)] = ('accept', B, 'R')

    return TM(t, 'scan_right', 'accept', 'reject')

def read_tape(tm, s):
    tape = {i: c for i, c in enumerate(s)}
    head, state, steps = 0, tm.start, 0
    while steps < 5000 and state != tm.accept:
        sym = tape.get(head, B)
        ns, w, mv = tm.trans[(state, sym)]
        tape[head] = w
        head += 1 if mv == 'R' else -1
        state = ns
        steps += 1
    lo, hi = min(tape), max(tape)
    return ''.join(tape.get(i, B) for i in range(lo, hi + 1)).strip(B), steps

incr = build_increment_tm()
for s in ["011", "111", "0", "1", "1011", "1111"]:
    out, steps = read_tape(incr, s)
    print(f"{s!r:6s} (={int(s,2):2d}) -> {out!r:6s} (={int(out,2):2d})  ধাপ={steps}  "
          f"টেপ {'বাড়ল' if len(out) > len(s) else 'বাড়েনি'}")