থিওরি অফ কম্পিউটেশন কী ও কেন গুরুত্বপূর্ণ

১ · থিওরি অফ কম্পিউটেশন কী

থিওরি অফ কম্পিউটেশনTheory of Computationকম্পিউটেশনের গাণিতিক তত্ত্ব — কোন সমস্যা কম্পিউটারে সমাধানযোগ্য, এবং সমাধানযোগ্য হলে কতটা দক্ষতার সাথে, তা নির্দিষ্ট ভাষা/হার্ডওয়্যার থেকে স্বাধীনভাবে অধ্যয়ন করে। হলো এমন একটি গাণিতিক অধ্যয়ন যা "কম্পিউটেশন" ধারণাটিকেই বিমূর্তভাবে (abstractly) পরীক্ষা করে — কোনো নির্দিষ্ট প্রোগ্রামিং ল্যাঙ্গুয়েজ, কম্পাইলার, বা হার্ডওয়্যার নিয়ে না ভেবে। এটি "কীভাবে কোড লিখব" প্রশ্নের উত্তর দেয় না — বরং আরও গভীর প্রশ্নের উত্তর খোঁজে: কোন সমস্যা আদৌ কোনো অ্যালগরিদম দিয়ে সমাধানযোগ্য? আর যদি সমাধানযোগ্য হয়, তাহলে কি সেটি বাস্তবে (যুক্তিসঙ্গত সময়ের মধ্যে) কার্যকরভাবে করা সম্ভব?

২ · তিনটি মূল স্তম্ভ সংক্ষেপে

৩ · এই তাত্ত্বিক ভিত্তি কেন প্রতিটি প্রোগ্রামারের জন্য গুরুত্বপূর্ণ

আপনি হয়তো কখনো নিজে একটি টুরিং মেশিনের প্রুফ লিখবেন না — কিন্তু এই তত্ত্ব আপনার প্রতিদিনের প্রোগ্রামিং সিদ্ধান্তকেও প্রভাবিত করে —

• "এই সমস্যার কোনো নিখুঁত সমাধান নেই" বোঝা: কেন একটি অ্যান্টিভাইরাস প্রোগ্রাম কখনোই ১০০% নিশ্চিতভাবে সব ভাইরাস শনাক্ত করতে পারে না — হল্টিং প্রবলেমের সাথে সরাসরি সম্পর্কিত (M9, cross-ref ../cybersecurity/)।
• "এই সমস্যা কেন এত ধীর" বোঝা: কেন কিছু অপ্টিমাইজেশন সমস্যার (যেমন ট্র্যাভেলিং সেলসম্যান) কোনো জানা দ্রুত সমাধান নেই — NP-কমপ্লিটনেসের সাথে সরাসরি সম্পর্কিত (M10, cross-ref ../dsa/)।
• রেগুলার এক্সপ্রেশন কখন কাজ করবে না বোঝা: কেন একটি regex দিয়ে সঠিকভাবে ব্যালেন্সড বন্ধনী শনাক্ত করা যায় না — regex ফাইনাইট অটোমাটার সমতুল্য, আর ব্যালেন্সড বন্ধনী রেগুলার ল্যাঙ্গুয়েজ নয় (M3-এ প্রমাণসহ দেখানো হবে)।

৪ · একটি ছোট্ট DFA প্রিভিউ

নিচের কোড সেলে অটোমাটা থিওরির সবচেয়ে মৌলিক "মেশিন" — একটি DFA (Deterministic Finite Automaton) — এর একটি সত্যিকারের, সম্পূর্ণ কার্যকর সিমুলেশন দেখা যাক। এই DFA-টি সেই বাইনারি স্ট্রিংগুলো accept করে যাদের মধ্যে "1"-এর সংখ্যা জোড় (even) — M2-এ এটি ফরমালি সংজ্ঞায়িত করা হবে।

# একটি সত্যিকারের DFA সিমুলেটর -- L = { বাইনারি স্ট্রিং যাতে '1'-এর সংখ্যা জোড় }
# M2-এ এই DFA-টি ফরমালি (Q, Sigma, delta, q0, F) হিসেবে সংজ্ঞায়িত হবে

transitions = {
    ('q0', '0'): 'q0',   # even অবস্থায় '0' পড়লে even-ই থাকে
    ('q0', '1'): 'q1',   # even অবস্থায় '1' পড়লে odd হয়ে যায়
    ('q1', '0'): 'q1',   # odd অবস্থায় '0' পড়লে odd-ই থাকে
    ('q1', '1'): 'q0',   # odd অবস্থায় '1' পড়লে even হয়ে যায়
}
start_state = 'q0'
accept_states = {'q0'}   # শুধু 'even' অবস্থায় শেষ হলেই accept

def run_dfa(transitions, start, accept, string):
    state = start
    for ch in string:
        state = transitions[(state, ch)]
    return state in accept

test_strings = ["", "1010", "111", "0000", "11011"]
print("স্ট্রিং      | '1'-এর সংখ্যা | DFA-এর ফলাফল")
print("-" * 45)
for s in test_strings:
    ones = s.count('1')
    parity = "জোড় (even)" if ones % 2 == 0 else "বিজোড় (odd)"
    result = run_dfa(transitions, start_state, accept_states, s)
    verdict = "accept" if result else "reject"
    print(f"{s!r:12s} | {ones} টি, {parity:12s} | {verdict}")