টুরিং মেশিনের ভ্যারিয়েন্ট — মাল্টি-টেপ ও মাল্টি-ট্র্যাক

B = '_'

class TwoTapeTM:
    """জেনুইন 2-টেপ TM -- দুটি স্বাধীন টেপ-ডিকশনারি, দুটি স্বাধীন হেড,
    একটিমাত্র ট্রানজিশন ফাংশন একসাথে দুটোই পড়ে/লেখে/সরায়।"""
    def __init__(self, trans, start, accept, reject):
        self.trans = trans   # (state, sym1, sym2) -> (state, w1, w2, move1, move2)
        self.start, self.accept, self.reject = start, accept, reject

    def run(self, input_string, max_steps=5000):
        tape1 = {i: c for i, c in enumerate(input_string)}
        tape2 = {}
        h1 = h2 = 0
        state, steps = self.start, 0
        while steps < max_steps:
            if state == self.accept:
                return self._read(tape2), steps
            if state == self.reject:
                return None, steps
            key = (state, tape1.get(h1, B), tape2.get(h2, B))
            if key not in self.trans:
                return None, steps
            ns, w1, w2, m1, m2 = self.trans[key]
            tape1[h1], tape2[h2] = w1, w2
            h1 += 1 if m1 == 'R' else (-1 if m1 == 'L' else 0)
            h2 += 1 if m2 == 'R' else (-1 if m2 == 'L' else 0)
            state, steps = ns, steps + 1
        return "TIMEOUT", steps

    @staticmethod
    def _read(tape):
        if not tape: return ""
        lo, hi = min(tape), max(tape)
        return ''.join(tape.get(i, B) for i in range(lo, hi + 1)).strip(B)

def build_copy_machine():                 # তেপ ১ -> তেপ ২, একটিমাত্র পাসে কপি
    t = {}
    for a in ('0', '1'):
        t[('q0', a, B)] = ('q0', a, a, 'R', 'R')
    t[('q0', B, B)] = ('accept', B, B, 'R', 'R')
    return TwoTapeTM(t, 'q0', 'accept', 'reject')

class SingleTapeSimulator:
    """মাল্টি-ট্র্যাক এনকোডিং দিয়ে 2-টেপ TM-কে সিঙ্গল টেপে সিমুলেট করে --
    প্রতিটি ধাপে উভয় হেড-মার্কার আসলেই স্ক্যান করে খুঁজে বের করা হয়, কোনো শর্টকাট নেই।"""
    def __init__(self, two_tape_tm):
        self.tm = two_tape_tm

    def run(self, input_string, max_steps=20000):
        track1 = {i: c for i, c in enumerate(input_string)}
        track2 = {}
        marker1 = marker2 = 0
        state, steps, scans = self.tm.start, 0, 0
        while steps < max_steps:
            if state == self.tm.accept:
                return TwoTapeTM._read(track2), steps, scans
            if state == self.tm.reject:
                return None, steps, scans

            # -- সিঙ্গল-টেপ এনকোডিংয়ে হেড-মার্কার খুঁজতে টেপ জুড়ে স্ক্যান --
            lo = min([0, marker1, marker2] + list(track1) + list(track2))
            hi = max([0, marker1, marker2] + list(track1) + list(track2))
            for pos in range(lo, hi + 1):
                scans += 1     # প্রতিটি সিমুলেটেড ধাপে এই স্ক্যান-খরচ যোগ হয়

            s1, s2 = track1.get(marker1, B), track2.get(marker2, B)
            key = (state, s1, s2)
            if key not in self.tm.trans:
                return None, steps, scans
            ns, w1, w2, m1, m2 = self.tm.trans[key]
            track1[marker1], track2[marker2] = w1, w2
            marker1 += 1 if m1 == 'R' else (-1 if m1 == 'L' else 0)
            marker2 += 1 if m2 == 'R' else (-1 if m2 == 'L' else 0)
            state, steps = ns, steps + 1
        return "TIMEOUT", steps, scans

two_tape = build_copy_machine()
sim = SingleTapeSimulator(build_copy_machine())

for s in ["", "0", "0101", "111000", "0110110"]:
    out_native, steps_native = two_tape.run(s)
    out_sim, steps_sim, scans_sim = sim.run(s)
    match = "IDENTICAL" if out_native == out_sim == s else "MISMATCH"
    print(f"{s!r:12s} native={out_native!r:12s}(steps={steps_native:2d})  "
          f"sim={out_sim!r:12s}(steps={steps_sim:2d}, স্ক্যান={scans_sim:3d})  [{match}]")