Decidability ও The Halting Problem — গণনার তত্ত্বের সবচেয়ে গুরুত্বপূর্ণ প্রমাণ

আগে এটা বুঝি

২০১৭ সালে WannaCry ransomware বিশ্বব্যাপী ২ লক্ষেরও বেশি কম্পিউটার সংক্রমিত করেছিল, হাসপাতাল পর্যন্ত অচল করে দিয়েছিল। প্রশ্ন উঠেছিল — কেন antivirus সফটওয়্যার এটা আটকাতে পারল না? উত্তরের একটা অংশ practical (signature database আপডেট হয়নি, patch করা হয়নি) — কিন্তু একটা গভীরতর অংশ আছে যেটা কোনো প্রকৌশলগত উন্নতি দিয়েই সমাধান করা যায় না।

কল্পনা করুন একটা “নিখুঁত antivirus” — এমন একটা প্রোগ্রাম যেটা যেকোনো প্রোগ্রামের কোড দেখে নির্ভুলভাবে বলে দিতে পারে সেটা malicious আচরণ করবে কি না। এমন কিছু বানানো কি নীতিগতভাবে সম্ভব?

এই লেসনের উত্তর: না — এবং এটা একটা প্রকৌশল সীমাবদ্ধতা না, একটা গাণিতিক প্রমাণিত অসম্ভবতা। আমরা এখন সেই প্রমাণটার দিকে যাচ্ছি — এই কারিকুলামের, হয়তো পুরো কম্পিউটার বিজ্ঞানের, সবচেয়ে গুরুত্বপূর্ণ একক প্রমাণ।

মূল ধারণা

Decidable, recognizable — সংজ্ঞা নিয়ে সতর্ক হওয়া জরুরি

এই লেসনে প্রতিটা শব্দ নিখুঁতভাবে সংজ্ঞায়িত হতে হবে — শিথিল ভাষায় এই বিষয়ে ভুল বোঝাবুঝি সবচেয়ে বেশি হয়।

একটা ভাষা L (string-এর একটা সেট) —

Decidable (সিদ্ধান্তযোগ্য): একটা TM M আছে যা প্রতিটা ইনপুট w-এর জন্য সবসময় থামে, এবং w ∈ L হলে accept করে, w ∉ L হলে reject করে।

এখানে “সবসময় থামে” শব্দটা গুরুত্বপূর্ণ — decidable-এর জন্য মেশিনকে নিশ্চিতভাবে, প্রতিটা ইনপুটে একটা সসীম সংখ্যক step-এ উত্তর দিতে হবে। এমন মেশিনকে বলে decider বা total TM।

Turing-recognizable (বা recursively enumerable, semi-decidable): একটা TM M আছে যেখানে w ∈ L ⟺ M w-কে accept করে (সসীম সময়ে)। কিন্তু w ∉ L হলে M reject-ও করতে পারে, অথবা চিরকাল loop করতে পারে।

পার্থক্যটা একটা টেবিলে:

	`w ∈ L` হলে	`w ∉ L` হলে
Decidable	নিশ্চিতভাবে accept (সসীম সময়ে)	নিশ্চিতভাবে reject (সসীম সময়ে)
শুধু Recognizable	নিশ্চিতভাবে accept (সসীম সময়ে)	reject অথবা loop — নিশ্চয়তা নেই

      সব ভাষা (সব সম্ভাব্য string-এর সেটের সেট)
   ┌───────────────────────────────────────────┐
   │  Turing-recognizable                       │
   │  ┌─────────────────────────────────────┐   │
   │  │      Decidable                       │   │
   │  │  (regular ⊂ context-free ⊂ decidable)│   │
   │  └─────────────────────────────────────┘   │
   │           ← halting problem এখানে,         │
   │             recognizable কিন্তু decidable না │
   └───────────────────────────────────────────┘
                ← কিছু ভাষা এমনকি recognizable-ও না
                  (পরের লেসনে দেখব — co-halting problem)

ভাষার তিনটা স্তর — decidable একটা কড়া উপসেট recognizable-এর।

একটা গুরুত্বপূর্ণ উপ-উপপাদ্য যা আমরা পরে ব্যবহার করব:

L decidable ⟺ L এবং L-এর complement (L̄) দুইটাই Turing-recognizable।

কেন: (⟹) সহজ — যদি L decidable হয়, তার decider সামান্য পরিবর্তন করে (accept/reject উল্টে দিয়ে) L̄-এরও decider বানানো যায়, আর decider তো recognizer-ও বটেই। (⟸) কম সহজাত কিন্তু গুরুত্বপূর্ণ — যদি L-এর জন্য একটা recognizer M1 থাকে আর L̄-এর জন্য একটা recognizer M2 থাকে, তাহলে দুইটাকে সমান্তরালে চালান (একটা step M1, একটা step M2, পালাক্রমে) — যেই আগে accept করবে, ইনপুটটা সেই ভাষায় (বা তার complement-এ) — এভাবে সবসময় থামা একটা decider বানানো যায়, কারণ w হয় L-এ, নয় L̄-এ, তাই M1 বা M2 একটা নিশ্চিতভাবে সসীম সময়ে accept করবেই।

এই উপ-উপপাদ্যটাই পরের অংশে halting problem-এর অসিদ্ধান্তযোগ্যতা প্রমাণের একটা শক্তিশালী “shortcut” রূপে ব্যবহার হবে।

ভেতরে কী ঘটছে

Halting problem — আনুষ্ঠানিক বিবৃতি

HALT = {⟨M, w⟩ : M একটা TM, যা input w-তে চালালে থামে (accept বা reject, যেকোনোটাতেই)}

প্রশ্ন: HALT কি decidable? অর্থাৎ, একটা TM H কি বানানো সম্ভব যা যেকোনো ⟨M, w⟩ নিয়ে সবসময় সসীম সময়ে সঠিকভাবে বলে দেয় M w-তে থামবে কি না?

স্বজ্ঞাতভাবে এটা যুক্তিসঙ্গত মনে হতে পারে — “শুধু M-এর কোড বিশ্লেষণ করুন, loop খুঁজে বের করুন, ব্যাস।” আমরা এখন প্রমাণ করব এটা কখনোই সম্ভব না — কোনো H নেই, থাকতে পারে না, ভবিষ্যতেও কেউ বানাতে পারবে না, প্রোগ্রামিং যত উন্নতই হোক।

'চালিয়ে দেখলেই হয়' কেন যথেষ্ট না

একটা স্বাভাবিক প্রথম চিন্তা: “M-কে w-তে চালান, থামলে ‘হ্যাঁ’ বলুন।” এটা কাজ করে যদি M থামে। কিন্তু যদি না থামে? আপনি কতক্ষণ অপেক্ষা করবেন? ১ মিনিট? ১ বছর? ১০০ বছর? কোনো সসীম সময়সীমাই নিশ্চিত করে না যে মেশিনটা আরেকটু পরেই থামত না। “চালিয়ে দেখা” HALT-কে recognizable বানায় (নিচে দেখুন) কিন্তু decidable বানায় না — এটাই ঠিক পার্থক্যটা যা আগের অংশে সংজ্ঞায়িত করেছি।

প্রমাণ — সম্পূর্ণ, ধাপে ধাপে

কৌশল: বিরোধিতা দ্বারা প্রমাণ (proof by contradiction), diagonalization ব্যবহার করে।

ধরে নিই HALT decidable — অর্থাৎ একটা TM H আছে যা:

H(\langle M, w \rangle) = \begin{cases} \text{accept} & \text{যদি } M \text{ থামে } w\text{-তে} \\ \text{reject} & \text{যদি } M \text{ না থামে } w\text{-তে} \end{cases}

আর H সবসময় থামে (কারণ decider)।

ধাপ ১ — H ব্যবহার করে একটা নতুন মেশিন D বানাই।

D একটামাত্র argument নেয় — একটা TM-এর encoding ⟨M⟩ (w না, শুধু M)। D নিজের ইনপুট হিসেবে ⟨M⟩ পেয়ে, এটাকে M-এর নিজের encoding-এর উপর চালানোর প্রশ্ন করে (অর্থাৎ w = ⟨M⟩ ধরে):

D(⟨M⟩):
    যদি H(⟨M, ⟨M⟩⟩) = accept   (মানে M নিজের কোডের উপর চালালে থামে):
        loop forever   (ইচ্ছাকৃতভাবে না থামা)
    যদি H(⟨M, ⟨M⟩⟩) = reject   (মানে M নিজের কোডের উপর চালালে থামে না):
        accept ও থামো

লক্ষ্য করুন — D তৈরি করা সম্পূর্ণ বৈধ, কারণ আমরা ধরে নিয়েছি H বিদ্যমান আর decider (সবসময় থামে)। D নিজেও একটা সুনির্দিষ্ট, সসীম বর্ণনার TM — শুধু H-কে subroutine হিসেবে ব্যবহার করছে।

          ┌─────────────────────────────────┐
  ⟨M⟩ ──▶ │  D                                │
          │  ⟨M, ⟨M⟩⟩ বানাও                   │
          │  H(⟨M, ⟨M⟩⟩) জিজ্ঞেস করো ──┐       │
          │                            ▼       │
          │   accept হলে → loop forever        │
          │   reject হলে → accept & থামো       │
          └─────────────────────────────────┘

D-এর গঠন — H-কে subroutine হিসেবে ব্যবহার করে, তারপর ইচ্ছাকৃতভাবে বিপরীত আচরণ করে।

ধাপ ২ — D-কে নিজের উপর চালাই (self-reference)।

D-ও একটা TM, তাই তার নিজস্ব encoding ⟨D⟩ আছে। এখন প্রশ্ন করি: D(⟨D⟩) কী করে?

D-এর সংজ্ঞা অনুযায়ী (M = D বসিয়ে):

D(⟨D⟩):
    যদি H(⟨D, ⟨D⟩⟩) = accept   (মানে D নিজের কোডের উপর চালালে থামে):
        loop forever
    যদি H(⟨D, ⟨D⟩⟩) = reject   (মানে D নিজের কোডের উপর চালালে থামে না):
        accept ও থামো

H(⟨D, ⟨D⟩⟩) জিজ্ঞেস করছে — “D কি ⟨D⟩-এর উপর চালালে থামে?” এটা ঠিক সেই প্রশ্ন যার উত্তর আমরা এখনই বের করার চেষ্টা করছি — কিন্তু ধরে নিয়েছি H সবসময় সঠিক উত্তর দেয় (decider বলে)।

ধাপ ৩ — দুইটা সম্ভাবনা বিবেচনা করি, দুইটাই দ্বন্দ্বে পৌঁছায়।

সম্ভাবনা A: ধরি D থামে ⟨D⟩-তে।

যেহেতু H সঠিক (আমাদের ধরে নেওয়া অনুযায়ী), H(⟨D, ⟨D⟩⟩) = accept। কিন্তু D-এর সংজ্ঞা অনুযায়ী, H যখন accept বলে, D তখন loop forever করে — অর্থাৎ D থামে না। এটা আমাদের অনুমানের (D থামে) সরাসরি বিপরীত। দ্বন্দ্ব।

সম্ভাবনা B: ধরি D থামে না ⟨D⟩-তে।

যেহেতু H সঠিক, H(⟨D, ⟨D⟩⟩) = reject। কিন্তু D-এর সংজ্ঞা অনুযায়ী, H যখন reject বলে, D তখন accept করে ও থামে — অর্থাৎ D থামে। এটা আমাদের অনুমানের (D থামে না) সরাসরি বিপরীত। আবার দ্বন্দ্ব।

উভয় সম্ভাবনাতেই দ্বন্দ্ব — তাই মূল অনুমান মিথ্যা।

$\therefore \text{কোনো decider } H \text{ HALT-এর জন্য থাকতে পারে না।} \qquad \blacksquare$

দ্বন্দ্বের হৃদয় — একটা লায়ার প্যারাডক্স, কোডে লেখা

লক্ষ্য করুন D(⟨D⟩)-এর সংজ্ঞাটা আসলে বলছে: “আমি ঠিক তাই করব যা H predict করে আমি করব না।” এটা “এই বাক্যটা মিথ্যা” — classic liar’s paradox-এর একটা যান্ত্রিক রূপ। D বিশেষভাবে বানানো হয়েছে যাতে H-এর যেকোনো উত্তরকে ভুল প্রমাণ করে — এই “স্ব-বিরোধী নির্মাণ” (self-referential construction) diagonalization-এর মূল কৌশল, আর এটা আবার আসবে Rice’s theorem আর অন্যান্য reduction proof-এ।

কেন নাম “diagonalization”

এই কৌশলটার নাম diagonalization কেন, তা বোঝা যুক্তিটার প্রকৃতি স্পষ্ট করে। কল্পনা করুন একটা (অসীম) টেবিল — প্রতিটা সারি একটা TM Mᵢ, প্রতিটা কলাম একটা TM-এর encoding ⟨Mⱼ⟩ (ইনপুট হিসেবে)। ঘরে লেখা H(⟨Mᵢ, ⟨Mⱼ⟩⟩) — অর্থাৎ Mᵢ কি ⟨Mⱼ⟩-এর উপর থামে।

              ⟨M1⟩   ⟨M2⟩   ⟨M3⟩   ⟨M4⟩  ...
       M1  [  H    হ্যাঁ   না    হ্যাঁ   ...  ]
       M2  [  না    (হ্যাঁ)  হ্যাঁ   না    ...  ]   ← কর্ণ-এ H(M2,⟨M2⟩) = হ্যাঁ
       M3  [  হ্যাঁ   না    (না)   হ্যাঁ   ...  ]   ← কর্ণ-এ H(M3,⟨M3⟩) = না
       M4  [  না    হ্যাঁ   হ্যাঁ   (হ্যাঁ)  ...  ]
       ...

       D-এর সারি বানাই কর্ণ উল্টে:
       D   [  না    না    হ্যাঁ   না   ...  ]
            ↑উল্টো  ↑উল্টো ↑উল্টো ↑উল্টো

Diagonalization — কর্ণ বরাবর প্রতিটা মানকে উল্টে একটা নতুন সারি (D) বানানো, যা টেবিলের কোনো সারির সাথে মেলে না।

D-এর সারিটা কর্ণের ঠিক বিপরীত— তাই এটা টেবিলের কোনো Mᵢ সারির সাথে হুবহু মিলতে পারে না (কারণ অন্তত কর্ণের i-তম ঘরে তারা আলাদা)। কিন্তু D নিজেও একটা TM, তাই তারও একটা সারি থাকতে বাধ্য টেবিলে (যদি টেবিলটা “সব TM” ধরে) — এই স্ব-বিরোধিতাই মূল দ্বন্দ্ব।

এই ঠিক কৌশলটাই Georg Cantor ১৮৯১ সালে প্রমাণ করেছিলেন real number-এর সেট countable না (কোনো enumeration সব real number ধরতে পারে না — একই diagonal-flip কৌশলে একটা নতুন real number বানানো যায় যা তালিকার কোনোটার সাথে মেলে না)। Turing-এর প্রমাণ কার্যত Cantor-এর কৌশলের একটা প্রয়োগ, সংখ্যার বদলে TM-এর উপর।

উদাহরণ

HALT recognizable — কিন্তু decidable না

আগে বলেছিলাম “চালিয়ে দেখা” recognizable বানায়, decidable না। এখন এটা সুনির্দিষ্টভাবে দেখানো যাক, কারণ এটা একটা গুরুত্বপূর্ণ বৈসাদৃশ্য তৈরি করে (উপরের উপ-উপপাদ্যের সাথে মিলিয়ে)।

Recognizer R, HALT-এর জন্য:

R(⟨M, w⟩):
    M-কে w-তে সিমুলেট করো
    যদি M থামে (accept বা reject): accept করো
    (যদি M না থামে, R-ও কখনো এই লাইনে পৌঁছায় না — loop করে)

⟨M, w⟩ ∈ HALT হলে (অর্থাৎ M সত্যিই থামে w-তে), সিমুলেশন কোনো এক-সসীম-সময়ে শেষ হবে, আর R accept করবে — সঠিক। ⟨M, w⟩ ∉ HALT হলে (অর্থাৎ M থামে না), R-ও কখনো থামবে না — R reject করে না, শুধু loop করে। এটাই recognizable-এর সংজ্ঞা মেনে চলে, decidable-এর না।

এখন উপ-উপপাদ্য প্রয়োগ করি: যদি HALT decidable হতো, তাহলে HALT আর HALT-এর complement (co-HALT) দুইটাই recognizable হতে হতো। আমরা এইমাত্র দেখালাম HALT recognizable। কিন্তু HALT decidable না (এইমাত্র diagonalization দিয়ে প্রমাণিত) — তাই উপ-উপপাদ্যের বিপরীত (contrapositive) অনুযায়ী, co-HALT recognizable হতে পারে না।

$\text{HALT decidable} \iff \text{HALT ও co-HALT দুইটাই recognizable}$ $\text{HALT recognizable, কিন্তু decidable নয়} \implies \text{co-HALT recognizable নয়}$

সরাসরি অর্থ: এমন কোনো প্রোগ্রাম নেই যা নিশ্চিতভাবে বলতে পারে “এই মেশিন থামবে না” (সসীম সময়ে, সব ক্ষেত্রে)। আপনি একটা মেশিন চালিয়ে দেখে “এটা থামে” প্রমাণ করতে পারেন (যদি সত্যিই থামে) — কিন্তু “এটা থামে না” কখনো একইভাবে প্রমাণ করতে পারবেন না, কারণ অপেক্ষা চিরকাল চলতে পারে।

একটা মানসিক মডেল যা মনে রাখা সহজ

Recognizable মানে — “হ্যাঁ” উত্তরের একটা প্রমাণ-খোঁজার পদ্ধতি আছে, যেটা ‘হ্যাঁ’ হলে খুঁজে পাবেই (সসীম সময়ে), ‘না’ হলে হয়তো কখনো থামবে না। এটা অনেকটা “প্রমাণ খুঁজে বের করা” —প্রমাণ থাকলে পাওয়া যাবে, না থাকলে খোঁজা চলতেই থাকবে, “নেই” ঘোষণা করার কোনো উপায় ছাড়াই।

Decidable মানে — সেই সাথে একটা “না” উত্তরেরও প্রমাণ-খোঁজার পদ্ধতি আছে যেটা সবসময় থামে। দুইটা প্রমাণ-পদ্ধতি (হ্যাঁ-এর জন্য, না-এর জন্য) মিলিয়ে একটা সবসময়-থামা decider বানানো যায় — ঠিক যেমন উপরের উপ-উপপাদ্যের প্রমাণে করেছি।

নিজে চালিয়ে দেখুন

EXPERIMENT

একটা টুল যা কিছু ক্ষেত্রে 'থামবে' বলতে পারে, কিন্তু কখনো নিশ্চিতভাবে 'থামবে না' বলতে পারে না

Python 3· ২০ মিনিট

def maybe_halts(program_fn, arg, step_budget=100_000):
    """
    একটা 'best effort' halt-checker। এটা HALT-এর একটা decider না —
    এটা সম্ভবই না (এই লেসনের প্রমাণ) — এটা শুধু একটা bounded simulator।
    """
    gen = program_fn(arg)     # generator হিসেবে চলবে, প্রতি 'yield' = এক ধাপ
    for step in range(step_budget):
        try:
            next(gen)
        except StopIteration:
            return f"থামল (accept/reject) — {step+1} ধাপে"
    return f"অজানা — {step_budget} ধাপেও থামেনি (হয়তো একটু পরে থামত, হয়তো কখনো না)"


def collatz_like(n):
    """একটা প্রোগ্রাম যা থামে কি না তা মানবজাতি আজও নিশ্চিতভাবে জানে না —
    Collatz conjecture আজও একটা খোলা গাণিতিক সমস্যা।"""
    steps = 0
    while n != 1:
        yield
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        steps += 1


def trivial_loop(n):
    """স্পষ্টতই কখনো থামে না।"""
    while True:
        yield


def trivial_halt(n):
    """স্পষ্টতই সবসময় থামে।"""
    yield
    return


print("collatz_like(27)  →", maybe_halts(collatz_like, 27))
print("collatz_like(97)  →", maybe_halts(collatz_like, 97))
print("trivial_loop(0)   →", maybe_halts(trivial_loop, 0, step_budget=1000))
print("trivial_halt(0)   →", maybe_halts(trivial_halt, 0))

প্রত্যাশিত ফলাফল:

collatz_like(27)  → থামল (accept/reject) — 111 ধাপে
collatz_like(97)  → থামল (accept/reject) — 118 ধাপে
trivial_loop(0)   → অজানা — 1000 ধাপেও থামেনি (হয়তো একটু পরে থামত, হয়তো কখনো না)
trivial_halt(0)   → থামল (accept/reject) — 1 ধাপে

গুরুত্বপূর্ণ পর্যবেক্ষণ: trivial_loop-এর ক্ষেত্রে output-টা “অজানা” — এটা “কখনো থামবে না” বলছে না, কারণ এই প্রোগ্রামটা নিজে জানে না (এটা শুধু একটা bounded simulator)। যদিও এই নির্দিষ্ট উদাহরণে আমরা মানুষ হিসেবে কোড পড়ে বলতে পারি এটা কখনো থামবে না (while True স্পষ্ট) — একটা সাধারণ, সব প্রোগ্রামে কাজ করা পদ্ধতি (algorithm) এটা করতে পারে না, এবং কখনো পারবে না।

collatz_like-এর গুরুত্ব: Collatz conjecture (৩n+1 problem) আজও গণিতের একটা অমীমাংসিত (open) সমস্যা — কোনো n-এর জন্য এই প্রক্রিয়া চিরকাল চলবে কি না তা কেউ প্রমাণ করেনি (বিশ্বাস করা হয় সবসময় থামে, কিন্তু প্রমাণিত না)। এটাই দেখায় halting problem নিছক তাত্ত্বিক কল্পনা না — এমনকি বিশেষ, সুনির্দিষ্ট প্রোগ্রামের জন্যও মানুষ এখনো সবসময় উত্তর জানে না।

এটা কী প্রমাণ করে

Recognizable-কিন্তু-না-decidable ধারণাটা বাস্তবে কেমন দেখায় — একটা সহজ 'halt-checker' যেটা step-limit দিয়ে চেষ্টা করে, কিন্তু timeout মানেই 'কখনো থামবে না' নয়, শুধু 'এত সময়ে থামেনি'।

নিজে বানান

BUILD IT

Diagonalization proof-টা নিজে কোডে দেখুন — একটা concrete পাল্টা উদাহরণ

Python · ●●●●○

একটা কাল্পনিক H (halt-decider) ধরে নিয়ে D ফাংশন লিখুন, যা H ব্যবহার করে
D(D) চালানোর চেষ্টা করে দেখুন লজিক্যাল দ্বন্দ্বটা কোডে কীভাবে প্রকাশ পায়
দেখান H-এর যেকোনো (কাল্পনিক) সংজ্ঞায় D(D) স্ববিরোধিতায় পৌঁছায়

এই কোডটা প্রমাণ চালায় না (তা সম্ভব না — HALT সত্যিই decidable হলে এটা কাজ করত, কিন্তু আমরা জানি এটা decidable না)। বরং এটা প্রমাণের লজিক্যাল গঠনটা concrete করে — H না থাকা সত্ত্বেও, H থাকলে কী দ্বন্দ্ব হতো তা দেখায়।

def build_D(H):
    """
    H: একটা ফাংশন যা (M_source, w) নেয় আর নিশ্চিতভাবে বলে দেয়
       M(w) থামবে কি না — অর্থাৎ H হলো আমাদের (অসম্ভব) halt-decider।

    D নিজেই একটা 'প্রোগ্রাম' — H-কে subroutine হিসেবে ব্যবহার করে।
    """
    def D(M_source):
        # M_source নিজের উপর চালালে থামে কি না জিজ্ঞেস করি — self-reference
        if H(M_source, M_source):     # H বলে: M থামবে
            while True:
                pass                   # ইচ্ছাকৃতভাবে না থামা
        else:                          # H বলে: M থামবে না
            return "accept"            # ইচ্ছাকৃতভাবে থামা
    return D


# ── এখন দেখাই: H যেই সংজ্ঞাই হোক, D(D) স্ববিরোধী ──

def fake_H_says_halts(M_source, w):
    """একটা কাল্পনিক H যা সবসময় 'হ্যাঁ, থামে' বলে।"""
    return True

def fake_H_says_loops(M_source, w):
    """একটা কাল্পনিক H যা সবসময় 'না, থামে না' বলে।"""
    return False


print("যদি H সবসময় 'থামে' বলে:")
D1 = build_D(fake_H_says_halts)
# D1(D1) চালালে: H বলবে 'থামে' → D1 তখন while True করে, আসলে থামে না
# কিন্তু H দাবি করেছিল থামবে — H ভুল ছিল!
print("  H predict করল: থামবে")
print("  বাস্তবে D１(D1) করে:  while True  →  থামে না  →  H ভুল")

print("\nযদি H সবসময় 'থামে না' বলে:")
D2 = build_D(fake_H_says_loops)
result = D2(D2)     # H বলে 'থামে না' → D2 accept করে, আসলে থামে
print("  H predict করল: থামে না")
print("  বাস্তবে D2(D2) =", result, " →  থামে (accept করল)  →  H ভুল")

print("\nদুইটা কাল্পনিক H-ই ভুল প্রমাণিত হলো D-এর নিজের উপর।")
print("H যেই সংজ্ঞাই হোক (এই দুইটা ছাড়াও), একই যুক্তি প্রযোজ্য —")
print("D সবসময় H-এর predict-এর বিপরীত করে, তাই কোনো H-ই সঠিক হতে পারে না।")

আউটপুট:

যদি H সবসময় 'থামে' বলে:
  H predict করল: থামবে
  বাস্তবে D１(D1) করে:  while True  →  থামে না  →  H ভুল

যদি H সবসময় 'থামে না' বলে:
  H predict করল: থামে না
  বাস্তবে D2(D2) = accept  →  থামে (accept করল)  →  H ভুল

দুইটা কাল্পনিক H-ই ভুল প্রমাণিত হলো D-এর নিজের উপর।
H যেই সংজ্ঞাই হোক (এই দুইটা ছাড়াও), একই যুক্তি প্রযোজ্য —
D সবসময় H-এর predict-এর বিপরীত করে, তাই কোনো H-ই সঠিক হতে পারে না।

গুরুত্বপূর্ণ সতর্কতা: এই দুইটা fake_H উদাহরণ trivial (সবসময় একই উত্তর) — একটা বাস্তব “চেষ্টা” (যেমন static analysis হিউরিস্টিক) বেশিরভাগ প্রোগ্রামে সঠিক উত্তর দিতে পারে। প্রমাণটা বলে না “কোনো H কখনো কোনো ক্ষেত্রে কাজে আসবে না” — বলে “কোনো H সব ক্ষেত্রে সঠিক হতে পারে না” — D-এর নির্মাণটা যেকোনো প্রস্তাবিত H-এর জন্য অন্তত একটা (D নিজেই) পাল্টা উদাহরণ তৈরি করে দেয়।

নিজে বাড়ান:

একটা তৃতীয়, “র‍্যান্ডম” fake_H লিখুন (input দেখে না, coin flip করে) — দেখান D(D)-এর আচরণ এখনো H-এর ভবিষ্যদ্বাণীর সাথে সামঞ্জস্যপূর্ণ থাকতে পারে না (কারণ D নিজেই H-এর উত্তর পড়ে সিদ্ধান্ত নেয়, তাই বিরোধিতা এখনো গ্যারান্টিড)
একটা মন্তব্যে লিখুন — কেন D-কে D-এর নিজের উপর (D(D)) চালানো জরুরি ছিল, D-কে অন্য কোনো নির্দিষ্ট প্রোগ্রামের উপর চালালে কেন দ্বন্দ্বটা তৈরি হতো না
Collatz-এর মতো একটা বাস্তব প্রোগ্রাম নিন যার halting status অজানা, আর ব্যাখ্যা করুন কেন উপরের proof সেই নির্দিষ্ট প্রোগ্রামের জন্য কিছুই বলে না (proof বলে “কোনো সার্বজনীন decider নেই”, কোনো নির্দিষ্ট প্রোগ্রামের উত্তর অজানা থাকা প্রমাণ করে না)

বাস্তব সিস্টেমে

Antivirus কখনো নিখুঁত হতে পারে না

লেসনের শুরুর প্রশ্নে ফিরি। “একটা প্রোগ্রাম malicious আচরণ করবে কি না” — এই প্রশ্নটা halting problem-এর একটা বিশেষ রূপ (পরের লেসনে আমরা দেখাব এই ধরনের প্রশ্ন আসলে halting problem থেকে reduce করা যায়, যা প্রমাণ করে এরাও undecidable)।

ব্যবহারিক পরিণতি:

Signature-based detection (known malware pattern খোঁজা) — এটা decidable, কারণ এটা “syntactic” প্রশ্ন (কোড কী দেখতে, রান না করেই) — কিন্তু নতুন/পরিবর্তিত malware ধরতে পারে না
Behavioral/heuristic detection (কোড চালিয়ে বা simulate করে আচরণ দেখা) — এটা recognizable-এর মতো: malicious আচরণ থাকলে খুঁজে পাওয়ার একটা ভালো সম্ভাবনা থাকে (চালিয়ে দেখে), কিন্তু নেই এটা নিশ্চিতভাবে প্রমাণ করা যায় না — malware কোড এমনভাবে লেখা যেতে পারে যা analysis sandbox-এ কখনো ক্ষতিকর আচরণ না দেখিয়ে (analysis এড়িয়ে) পরে বাস্তব সিস্টেমে সক্রিয় হয়
তাই বাস্তব antivirus সবসময় একটা trade-off নিয়ে কাজ করে — sandbox-এ সসীম সময় (কয়েক সেকেন্ড থেকে মিনিট) চালিয়ে দেখা, timeout হলে “সন্দেহজনক না” বলে দেওয়া — ঠিক আগের experiment-এর maybe_halts-এর মতো, একটা বাস্তব প্রকৌশলগত আপস, তাত্ত্বিক সীমাবদ্ধতার আশেপাশে

Compiler warning কেন হিউরিস্টিক

-Wall, -Wunreachable-code, static analyzer-এর “সম্ভাব্য infinite loop” warning — এই সবগুলোই একই সীমাবদ্ধতার মুখোমুখি। একটা compiler নিখুঁতভাবে বলতে পারে না “এই লুপ কখনো শেষ হবে না” — কারণ সেটা হবে HALT-এর complement সমাধান করা, যা আমরা প্রমাণ করেছি এমনকি recognizable-ও না।

তাই বাস্তব compiler warning রক্ষণশীল (conservative) — হয় সব সমস্যা ধরে কিন্তু কিছু নিরাপদ কোডকেও false positive হিসেবে চিহ্নিত করে (sound but incomplete), অথবা শুধু নিশ্চিত ক্ষেত্রে warning দেয় কিন্তু কিছু আসল সমস্যা miss করে (complete but unsound) — কখনোই দুইটাই একসাথে নিখুঁত না। এই sound/complete trade-off-এর পুরো আনুষ্ঠানিক আলোচনা আসবে দুই লেসন পরে, Rice’s theorem-এর realworld অংশে।

Compilers module-এর সাথে সরাসরি সংযোগ: একটা type checker-ও একইভাবে সীমাবদ্ধ — “এই প্রোগ্রাম কখনো runtime type error দেবে না” এই প্রশ্নটা সাধারণভাবে undecidable, তাই টাইপ সিস্টেম ইচ্ছাকৃতভাবে রক্ষণশীল — কিছু আসলে নিরাপদ প্রোগ্রামকেও প্রত্যাখ্যান করে (যেমন dependent টাইপ ছাড়া ভাষায়), যাতে যেগুলো accept করে সেগুলোর জন্য নিশ্চিত গ্যারান্টি দেওয়া যায়। এটা প্রকৌশলীর অলসতা না — এটা এই লেসনের প্রমাণেরই একটা সরাসরি, অনিবার্য পরিণতি।

Program verification-এর বাস্তব সীমা

Formal verification টুল (Coq, TLA+, model checker) — এগুলো প্রোগ্রামের সঠিকতা প্রমাণ করতে পারে, কিন্তু স্বয়ংক্রিয়ভাবে না, সব ক্ষেত্রে না। এই টুলগুলো হয় (ক) মানুষের সাহায্য নেয় (interactive theorem proving — মানুষ প্রমাণের কাঠামো দেয়, টুল যাচাই করে), অথবা (খ) একটা সীমাবদ্ধ ডোমেইনে কাজ করে (bounded model checking — শুধু N step পর্যন্ত যাচাই করে, HALT-এর মতো general প্রশ্নে হাত দেয় না)। এই সীমাবদ্ধতাগুলো সরাসরি এই লেসনের প্রমাণ থেকে আসে — এড়ানো যায় না, শুধু ব্যবস্থাপনা করা যায়।

যে ভুলগুলো সবাই করে

“Halting problem undecidable মানে কোনো নির্দিষ্ট প্রোগ্রাম থামবে কি না তা কখনো জানা সম্ভব না।”

সম্পূর্ণ ভুল, আর এটা সবচেয়ে সাধারণ ভুল ব্যাখ্যা। বেশিরভাগ বাস্তব প্রোগ্রামের জন্য আমরা সহজেই বলতে পারি থামবে কি না — একটা সাধারণ for i in range(100): ... লুপ স্পষ্টতই থামে; while True: pass স্পষ্টতই থামে না। এই দুইটাতেই মানুষ (বা একটা বিশেষ-নির্মিত checker) সহজেই সঠিক উত্তর দিতে পারে।

প্রমাণটা বলে: কোনো একটা সার্বজনীন algorithm নেই যা প্রতিটা সম্ভাব্য প্রোগ্রাম-ইনপুট জোড়ার জন্য কাজ করে। এটা একটা “for all” দাবি — “সব প্রোগ্রামের জন্য একটা একক পদ্ধতি” — না, বেশিরভাগ নির্দিষ্ট প্রোগ্রামের জন্য (“this specific program”) হ্যাঁ, সমাধান করা যায়।

উপমা: এমন কোনো সার্বজনীন algorithm নেই যা প্রতিটা গাণিতিক অনুমান (conjecture) সত্য না মিথ্যা তা প্রমাণ করে দেয় — তবু গণিতবিদরা প্রতিদিন নির্দিষ্ট উপপাদ্য প্রমাণ করেন। “সাধারণ সমাধান নেই” আর “কোনো নির্দিষ্ট উদাহরণ সমাধানযোগ্য না” — সম্পূর্ণ ভিন্ন দাবি।

“Halting problem শুধু তাত্ত্বিক curiosity — বাস্তব সফটওয়্যার ইঞ্জিনিয়ারিং-এ এর কোনো প্রভাব নেই।”

এই লেসনের realworld অংশেই এর বিপরীত প্রমাণ — antivirus-এর মৌলিক সীমাবদ্ধতা, compiler warning কেন সবসময় হয় sound-but-incomplete বা complete-but-unsound, type checker কেন রক্ষণশীল, formal verification কেন মানুষের সাহায্য লাগে — এই সবগুলোই সরাসরি এই একটা প্রমাণের পরিণতি।

এটাই একটা মূল্যবান শিক্ষা — একটা “pure” গাণিতিক প্রমাণ (কোনো বাস্তব compiler বা antivirus উল্লেখ ছাড়াই লেখা, ১৯৩৬ সালে) ৯০ বছর পরেও প্রতিদিনের সফটওয়্যার টুলের ডিজাইন সিদ্ধান্তে সরাসরি প্রতিফলিত হচ্ছে। “লিন্টার সব ধরতে পারে না” — এটা একটা বাগ না, একটা গাণিতিক অনিবার্যতা।

“প্রমাণটা শুধু কাজ করে কারণ D একটা 'অদ্ভুত', কৃত্রিম প্রোগ্রাম — বাস্তব প্রোগ্রামে এই সমস্যা হয় না।”

D-এর নির্মাণটা সত্যিই কৃত্রিম আর self-referential — কিন্তু এটা সম্পূর্ণ বৈধ। প্রমাণের যুক্তিতে D-কে “বাস্তব” বা “স্বাভাবিক” হতে হবে এমন কোনো শর্ত নেই — শুধু এটা একটা সুনির্দিষ্ট, সসীম বর্ণনার TM হতে হবে (যা এটা), আর H-কে subroutine হিসেবে ব্যবহার করতে পারতে হবে (যা H decidable/total ধরে নেওয়ায় সম্ভব)।

গণিতে “for all X, P(X)” দাবি খণ্ডন করতে একটা মাত্র পাল্টা উদাহরণ যথেষ্ট, এমনকি সেই উদাহরণটা অস্বাভাবিক হলেও। H দাবি করে “আমি প্রতিটা ⟨M, w⟩-এর জন্য সঠিক উত্তর দিই” — D একটা একক পাল্টা উদাহরণ তৈরি করে এই সার্বজনীন দাবি খণ্ডন করতে। এটা যে D-টা অস্বাভাবিক দেখতে, সেটা প্রমাণকে দুর্বল করে না — বরং এটাই প্রমাণ পদ্ধতির শক্তি: এটা দেখায় যেকোনো প্রস্তাবিত H-এর বিরুদ্ধে একটা পাল্টা উদাহরণ বানানো সবসময় সম্ভব, তাই কোনো H-ই টিকতে পারে না।

বুঝেছেন কি না দেখুন

Decidable আর Turing-recognizable-এর মধ্যে ঠিক কোন একটা মাত্র শর্তের পার্থক্য? (টেবিল দেখে মুখস্থ না করে, সংজ্ঞা থেকে বলুন।)

স্মরণ

পার্থক্যটা w ∉ L হলে কী ঘটে তাতে। Decidable-এ deciding TM-কে w ∉ L হলেও নিশ্চিতভাবে, সসীম সময়ে reject করতে হয়। Recognizable-এ TM w ∉ L হলে reject করতে পারে, অথবা কখনো না থেমে চিরকাল loop করতে পারে — কোনো নিশ্চয়তা নেই।

w ∈ L হলে দুইটাতেই একই আচরণ প্রত্যাশিত — সসীম সময়ে accept। তাই আসল পার্থক্যটা একমুখী: “না” উত্তরের ক্ষেত্রে থামার গ্যারান্টি আছে কি নেই।

Diagonalization প্রমাণে D(⟨D⟩) বিবেচনা করা কেন প্রয়োজনীয় ছিল — D-কে অন্য কোনো নির্দিষ্ট TM-এর encoding-এ (যেমন ⟨M₀⟩, যেখানে M₀ কোনো সাধারণ, অ-স্ব-নির্দেশক মেশিন) চালালে কেন দ্বন্দ্বটা তৈরি হতো না?

যুক্তি

দ্বন্দ্বটা তৈরি হয় কারণ D(⟨D⟩)-এর ফলাফল নির্ভর করে H কী predict করে D নিজে ⟨D⟩-তে কী করবে তার উপর — আর সেই একই predict-ই আবার D-এর নিজের আচরণকে নির্ধারণ করে। এই বৃত্তাকার (circular) নির্ভরতাটাই D-কে বাধ্য করে যেকোনো predict-এর বিপরীত করতে।

যদি আমরা D(⟨M₀⟩) বিবেচনা করতাম (M₀ ≠ D), তাহলে H(⟨M₀⟩, ⟨M₀⟩)-এর predict M₀-এর প্রকৃত আচরণ সম্পর্কে, যেটা D-এর নিজের আচরণের সাথে সরাসরি সম্পর্কিত না। H এখানে সঠিক হতেই পারে — কোনো দ্বন্দ্ব তৈরি হয় না, কারণ D-এর সিদ্ধান্ত (যা করবে) M₀-এর আচরণ বদলাতে পারে না (M₀ স্বাধীন, D-এর সংজ্ঞার অংশ না)।

শুধু D(⟨D⟩)-এই H-এর predict আর predict-করা-বিষয় (subject) একই সত্তা — এই self-reference-ই দ্বন্দ্বের অপরিহার্য উপাদান, ঠিক liar’s paradox-এ “এই বাক্যটা” নিজেকে নির্দেশ করার মতো।

প্রমাণ করুন: HALT-এর একটা নির্দিষ্ট সংস্করণ, HALT_ε = {⟨M⟩ : M খালি স্ট্রিং ε-তে থামে} — এটাও undecidable। (ইঙ্গিত: একই diagonalization পুনরাবৃত্তি না করে, সরাসরি এই লেসনের মূল ফলাফল ব্যবহার করার চেষ্টা করুন — এটা আসলে পরের লেসনের কৌশলের একটা আগাম ঝলক।)

প্রয়োগ

এই প্রশ্নটা reduction-এর একটা প্রাথমিক রূপ, যা পরের লেসনের মূল বিষয় — কিন্তু ধারণাটা এখনই ব্যবহারযোগ্য।

ধরি HALT_ε decidable — একটা decider H_ε আছে। তাহলে আমরা সাধারণ HALT-এর জন্য একটা decider বানাতে পারব, যা দ্বন্দ্বপূর্ণ (কারণ আমরা জানি HALT undecidable):

HALT-এর যেকোনো ইনপুট ⟨M, w⟩-এর জন্য, একটা নতুন মেশিন M' বানাই যেটা: “নিজের ইনপুট (যাই হোক না কেন, এমনকি খালি) উপেক্ষা করে, w টেপে লিখে, তারপর M-কে সিমুলেট করে।”

এখন লক্ষ্য করুন: M' খালি স্ট্রিং ε-তে থামে ঠিক তখনই যখন M w-তে থামে (কারণ M' প্রথমেই w লিখে নেয়, তার নিজের ইনপুট যাই থাকুক)।

তাই: ⟨M, w⟩ ∈ HALT ⟺ ⟨M'⟩ ∈ HALT_ε।

H_ε থাকলে, HALT-এর একটা decider বানানো যায়: “⟨M, w⟩ পেয়ে, M' বানাও (উপরের নিয়মে), তারপর H_ε(⟨M'⟩) চালাও, তার উত্তরই ফেরত দাও।” এটা সবসময় থামে (কারণ H_ε decider, আর M' বানানো নিজেই একটা সসীম, mechanical রূপান্তর)।

কিন্তু আমরা জানি HALT-এর কোনো decider নেই (এই লেসনের মূল প্রমাণ) — দ্বন্দ্ব। তাই H_ε থাকতে পারে না, অর্থাৎ HALT_ε undecidable।

এই কৌশলের নাম “reduction” — “যদি B (এখানে HALT_ε) সমাধানযোগ্য হতো, তাহলে A-ও (এখানে HALT) সমাধানযোগ্য হতো, কিন্তু A সমাধানযোগ্য না, তাই B-ও না।” পরের লেসনে এই কৌশলটাই আনুষ্ঠানিকভাবে সংজ্ঞায়িত হবে আর বারবার প্রয়োগ করা হবে — নতুন করে diagonalization না লিখেই।

একজন junior engineer প্রস্তাব দিচ্ছেন: “আমরা H-কে সীমাবদ্ধ করে দিই — শুধু সেই প্রোগ্রামগুলোর জন্য কাজ করবে যেগুলো 10^9 step-এর মধ্যে থামে বা না-থামার সিদ্ধান্ত নেওয়া যায়। এতে diagonalization কি আটকানো যাবে?”

ডিজাইন

এটা একটা বৈধ পদ্ধতি, কিন্তু এটা মূল সমস্যাটা এড়িয়ে যায়, সমাধান করে না — আর diagonalization-কে “আটকায়” না, বরং সমস্যাটাকে অন্যভাবে পুনর্গঠন করে।

এটা কী কাজ করে: H'(⟨M, w⟩) = “M-কে w-তে 10^9 step পর্যন্ত সিমুলেট করো; থামলে accept; না থামলে reject।” এটা সবসময় থামে (সংজ্ঞা অনুযায়ী, 10^9 step-এর বেশি কখনো চলে না) — তাই এটা একটা বৈধ decider, কিন্তু HALT-এর decider না — এটা একটা ভিন্ন ভাষার decider: HALT_{10^9} = {⟨M,w⟩ : M থামে w-তে 10^9 step-এর মধ্যে}।

কেন diagonalization এখানে প্রযোজ্য না, তবু সমস্যা রয়েই যায়: diagonalization proof-এ D নিজের উপর self-reference তৈরি করে H-কে subroutine হিসেবে ডাকে। H'-এর জন্যও একই D বানানো যায় (H'-কে subroutine হিসেবে ব্যবহার করে) — কিন্তু এবার দ্বন্দ্বটা হবে HALT_{10^9} সম্পর্কে, HALT সম্পর্কে না, এবং HALT_{10^9} আসলে decidable (কারণ H' নিজেই তার decider!) — তাই এখানে কোনো দ্বন্দ্ব নেই, D স্ববিরোধী হয় না।

তাহলে সমস্যা কোথায়? H' HALT-এর প্রশ্নের সঠিক উত্তর দেয় না — এটা শুধু বলে “১০⁹ step-এর মধ্যে থামে কি না”, যা মূল প্রশ্নের (অসীম সময় পর্যন্ত থামে কি না) একটা আন্ডার-অ্যাপ্রক্সিমেশন। M যদি 10^9 + 1 step-এ থামত, H' ভুলভাবে “reject” (মানে থামে না) বলবে। তাই এটা একটা practical heuristic — ঠিক যেমন এই লেসনের experiment-এর maybe_halts — কিন্তু কোনো ভাবেই HALT-এর আসল, নিখুঁত decider না। Junior engineer-এর প্রস্তাবটা diagonalization আটকায় না, বরং প্রশ্নটাই বদলে ফেলে একটা সহজ, ভিন্ন প্রশ্নে — যেটা বাস্তব সিস্টেমে (antivirus sandbox timeout, compiler-এর bounded loop analysis) ঠিক এভাবেই ব্যবহার হয়, উপরের realworld অংশে যেমন আলোচিত হয়েছে।

এরপর কী

আমরা এইমাত্র প্রমাণ করেছি একটা নির্দিষ্ট সমস্যা (HALT) undecidable — একটা সম্পূর্ণ, স্বনির্ভর diagonalization প্রমাণ দিয়ে। কিন্তু বাস্তবে শত শত সমস্যা undecidable — প্রতিটার জন্য কি নতুন করে diagonalization লিখতে হবে?

সৌভাগ্যবশত না। Question 3-এ আমরা একটা shortcut দেখেছি — reduction — যেখানে একটা নতুন সমস্যাকে HALT-এর সাথে সংযুক্ত করে undecidability “ধার” করা যায়, কোনো নতুন self-referential নির্মাণ ছাড়াই।

পরের লেসনে আমরা reduction-কে আনুষ্ঠানিকভাবে সংজ্ঞায়িত করব (many-one/mapping reduction), আর এটা ব্যবহার করে আরো কয়েকটা বাস্তব-সম্পর্কিত সমস্যা (যেমন “এই প্রোগ্রাম কি ‘hello’ প্রিন্ট করে”, “দুইটা প্রোগ্রাম কি সমতুল্য”) undecidable প্রমাণ করব — প্রতিটাই মাত্র কয়েক লাইনের যুক্তিতে, কারণ ভারী কাজটা (diagonalization) এই লেসনেই একবার হয়ে গেছে।

Decidability ও The Halting Problem — গণনার তত্ত্বের সবচেয়ে গুরুত্বপূর্ণ প্রমাণ

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

Decidable, recognizable — সংজ্ঞা নিয়ে সতর্ক হওয়া জরুরি

ভেতরে কী ঘটছে

Halting problem — আনুষ্ঠানিক বিবৃতি

প্রমাণ — সম্পূর্ণ, ধাপে ধাপে

কেন নাম “diagonalization”

উদাহরণ

HALT recognizable — কিন্তু decidable না

নিজে চালিয়ে দেখুন

একটা টুল যা কিছু ক্ষেত্রে 'থামবে' বলতে পারে, কিন্তু কখনো নিশ্চিতভাবে 'থামবে না' বলতে পারে না

নিজে বানান

Diagonalization proof-টা নিজে কোডে দেখুন — একটা concrete পাল্টা উদাহরণ

বাস্তব সিস্টেমে

Antivirus কখনো নিখুঁত হতে পারে না

Compiler warning কেন হিউরিস্টিক

Program verification-এর বাস্তব সীমা

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Decidable, recognizable — সংজ্ঞা নিয়ে সতর্ক হওয়া জরুরি

⚙ভেতরে কী ঘটছেUnder the hood

Halting problem — আনুষ্ঠানিক বিবৃতি

প্রমাণ — সম্পূর্ণ, ধাপে ধাপে

কেন নাম “diagonalization”

▶উদাহরণExample

HALT recognizable — কিন্তু decidable না

⌘নিজে চালিয়ে দেখুনExperiment

একটা টুল যা কিছু ক্ষেত্রে 'থামবে' বলতে পারে, কিন্তু কখনো নিশ্চিতভাবে 'থামবে না' বলতে পারে না

⚒নিজে বানানBuild it yourself

Diagonalization proof-টা নিজে কোডে দেখুন — একটা concrete পাল্টা উদাহরণ

◉বাস্তব সিস্টেমেReal-world usage

Antivirus কখনো নিখুঁত হতে পারে না

Compiler warning কেন হিউরিস্টিক

Program verification-এর বাস্তব সীমা

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী