Reduction — একবার প্রমাণ করে বারবার ধার করা

আগে এটা বুঝি

আগের লেসনের শেষে একটা প্রশ্নের মুখোমুখি হয়েছিলাম — HALT undecidable, কিন্তু বাস্তবে শত শত সমস্যা আছে যেগুলো একইভাবে “সমাধানের কোনো সাধারণ পদ্ধতি নেই” বলে সন্দেহ হয়। “এই প্রোগ্রাম কি কখনো null রিটার্ন করে?” “দুইটা প্রোগ্রাম কি সবসময় একই আউটপুট দেয়?” “এই রেগেক্স কি কখনো catastrophic backtracking-এ পড়ে?” — প্রতিটার জন্য কি নতুন করে একটা D বানিয়ে, নিজের উপর চালিয়ে, দ্বন্দ্ব খুঁজে বের করতে হবে?

সৌভাগ্যক্রমে না। একটা আইনজীবীর উপমা দিয়ে শুরু করা যাক।

একজন আইনজীবী একটা মামলায় জেতার জন্য প্রতিবার শূন্য থেকে সংবিধান পুনর্ব্যাখ্যা করেন না — তিনি precedent (পূর্ববর্তী রায়) ব্যবহার করেন: “আদালত ইতিমধ্যে রায় দিয়েছে X ক্ষেত্রে Y, আর আমার মামলা X-এর সাথে সংরচনাগতভাবে অভিন্ন, তাই একই রায় এখানেও প্রযোজ্য।” পুরো যুক্তি কাঠামোটা ধার নেওয়া হয়, শুধু নতুন case-এর সাথে পুরনো case-এর মিলটা দেখাতে হয়।

Reduction ঠিক এই ভূমিকা পালন করে গণনার তত্ত্বে। একবার HALT undecidable প্রমাণিত হয়ে গেলে, একটা নতুন সমস্যা B-কে undecidable প্রমাণ করতে diagonalization পুনরাবৃত্তি করার দরকার নেই — শুধু দেখাতে হয় “HALT সমাধান করা B সমাধান করার চেয়ে সহজ না” — অর্থাৎ HALT-কে B-এর একটা বিশেষ ক্ষেত্র হিসেবে রূপান্তর করা যায়।

মূল ধারণা

Many-one reduction — আনুষ্ঠানিক সংজ্ঞা

ভাষা A many-one reducible (বা mapping reducible) ভাষা B-তে, লেখা হয় A ≤ₘ B, যদি একটা computable function f : Σ* → Σ* থাকে যেখানে:

$\forall w:\ w \in A \iff f(w) \in B$

শর্তগুলো লক্ষ্য করুন:

f অবশ্যই computable — অর্থাৎ কোনো TM আছে যা প্রতিটা w-এর জন্য f(w) গণনা করে, সবসময় থেমে (f নিজে একটা total computable function, decidability-র প্রশ্নটা A/B নিয়ে, f নিয়ে না)
দ্বিমুখী impliation (⟺, iff) — w ∈ A হলে f(w) ∈ B হতেই হবে, এবং w ∉ A হলে f(w) ∉ B হতেই হবে

   A-এর প্রশ্ন জগৎ                    B-এর প্রশ্ন জগৎ
   ─────────────────                  ─────────────────
   w ∈ A  ────f────▶  f(w) ∈ B        (উত্তর "হ্যাঁ" সংরক্ষিত)
   w ∉ A  ────f────▶  f(w) ∉ B        (উত্তর "না" সংরক্ষিত)

   f একটা computable "অনুবাদ" —
   A-এর যেকোনো instance-কে B-এর একটা equivalent instance-এ পাঠায়

Many-one reduction — f একটা 'অনুবাদক' যে A-এর প্রশ্নগুলোকে B-এর প্রশ্নে রূপান্তর করে, উত্তর সংরক্ষণ করে।

মূল উপপাদ্য — কোন দিকে তথ্য প্রবাহিত হয়

যদি A ≤ₘ B এবং B decidable, তাহলে A-ও decidable।

সমতুল্যভাবে (contrapositive): যদি A ≤ₘ B এবং A undecidable, তাহলে B-ও undecidable।

প্রমাণ (প্রথম দাবি): ধরি B-এর একটা decider M_B আছে, আর A ≤ₘ B (একটা computable f সহ)। তাহলে A-এর জন্য একটা decider বানাই:

M_A(w):
    f(w) গণনা করো          # সবসময় থামে, কারণ f computable
    M_B(f(w)) চালাও         # সবসময় থামে, কারণ M_B decider
    M_B যা বলে (accept/reject) তাই বলো

M_A সবসময় থামে (দুইটা sub-step-ই সবসময় থামে বলে ধরে নেওয়া), আর w ∈ A ⟺ f(w) ∈ B ⟺ M_B(f(w)) accept করে ⟺ M_A(w) accept করে। তাই M_A সঠিক এবং সবসময়-থামা — A-এর একটা বৈধ decider। ∎

দিকটা মুখস্থ করবেন না, যুক্তি দিয়ে বের করুন প্রতিবার

এই একটা ভুল বোঝাবুঝিই সবচেয়ে বেশি ছাত্রছাত্রীর reduction প্রমাণে ভুল করার কারণ। মনে রাখার সহজ উপায়:

A ≤ₘ B পড়ুন “A, B-এর চেয়ে সহজ বা সমান কঠিন” হিসেবে — অর্থাৎ B সমাধান করতে পারলে A-ও সমাধান করা যায় (B-র decider ধার করে)। তাই:

B easy (decidable) ⟹ A-ও easy — তথ্য নিচের দিকে প্রবাহিত
A hard (undecidable) ⟹ B-ও hard — তথ্য উপরের দিকে প্রবাহিত (contrapositive-এর মাধ্যমে)

undecidability প্রমাণ করতে সবসময় এই প্যাটার্নে reduce করুন: (পরিচিত undecidable) ≤ₘ (নতুন সমস্যা) — পরিচিত সমস্যাটা বাম পাশে। যদি উল্টো করে ফেলেন ((নতুন সমস্যা) ≤ₘ (পরিচিত undecidable)), কিছুই প্রমাণ হয় না — এটা শুধু বলে “নতুন সমস্যা HALT-এর চেয়ে সহজ বা সমান”, যা decidable এবং undecidable দুইটার সাথেই সামঞ্জস্যপূর্ণ।

কেন এই দিকটাই সঠিক — একটা সাদৃশ্য

কল্পনা করুন A = “এই ম্যাপ রঙ করা কি ৩-রঙে সম্ভব” (কঠিন, ধরুন আমরা জানি NP-hard), B = “এই সুডোকু সমাধানযোগ্য কি না” (নতুন সমস্যা, কঠিনতা অজানা)। যদি আমরা দেখাতে পারি প্রতিটা ম্যাপ-রঙ-করা সমস্যাকে একটা সুডোকু পাজলে রূপান্তর করা যায় (এমনভাবে যে ম্যাপ রঙ করা সম্ভব ⟺ সুডোকু সমাধানযোগ্য), তাহলে: যদি সুডোকু সহজে সমাধানযোগ্য হতো, আমরা সেই সহজ সমাধানকারীকে ম্যাপ-রঙ-করার জন্যও ব্যবহার করতে পারতাম (প্রথমে রূপান্তর করে, তারপর সুডোকু সমাধানকারী চালিয়ে) — কিন্তু আমরা জানি ম্যাপ-রঙ-করা সহজ না। তাই সুডোকুও সহজ হতে পারে না। এই একই যুক্তি — শুধু “সহজ” শব্দের বদলে “polynomial time”-এ — কয়েক লেসন পরে NP-completeness প্রমাণের ভিত্তি হবে।

ভেতরে কী ঘটছে

Reduction টেমপ্লেট — চারটা ধাপ

প্রতিটা reduction প্রমাণ একই কাঠামো অনুসরণ করে। এই টেমপ্লেটটা মুখস্থ করার মতো — প্রতিটা নতুন undecidability প্রমাণে হুবহু এই চারটা ধাপ প্রয়োগ হবে।

কোন পরিচিত undecidable ভাষা থেকে reduce করবেন তা বেছে নিন (সাধারণত HALT, অথবা HALT থেকে ইতিমধ্যে reduce করা একটা সমস্যা)
একটা computable function f সংজ্ঞায়িত করুন যা পরিচিত ভাষার instance-কে নতুন ভাষার instance-এ রূপান্তর করে
প্রমাণ করুন f computable — সাধারণত এটা সহজ, কারণ f সাধারণত একটা নতুন TM “বানানো”র একটা mechanical প্রক্রিয়া (কোড জেনারেট করা), TM চালানো না
প্রমাণ করুন ⟺ — দুই দিকেই — মূল instance ভাষায় থাকলে রূপান্তরিত instance-ও থাকে, এবং বিপরীতভাবে

Reduction প্রমাণের গঠন — layer বাই layer

পরিচিত undecidable সমস্যা (HALT)আগের লেসনে diagonalization দিয়ে প্রমাণিত — এখানে ভিত্তি ধরে নেওয়া হচ্ছে
রূপান্তর function f সংজ্ঞাএকটা নতুন TM প্রোগ্রামগতভাবে বানানো — এটাই "অনুবাদ"
f-এর computability যাচাইf নিজে সবসময় থামে এমন একটা mechanical নির্মাণ কি না
⟺ প্রমাণ — উভয় দিকমূল instance হ্যাঁ ⟺ রূপান্তরিত instance হ্যাঁ
সিদ্ধান্তনতুন সমস্যার decider থাকলে HALT-এরও decider হতো — দ্বন্দ্ব, তাই নতুন সমস্যা undecidable

উদাহরণ

উদাহরণ ১ — `PRINTS_HELLO` undecidable

PRINTS_HELLO = {⟨M⟩ : M, খালি ইনপুটে চালালে, কখনো "hello" প্রিন্ট করে}

দাবি: PRINTS_HELLO undecidable।

প্রমাণ (HALT ≤ₘ PRINTS_HELLO):

ধাপ ১-২ (রূপান্তর f সংজ্ঞা): HALT-এর একটা instance ⟨M, w⟩ দেওয়া হলে, একটা নতুন মেশিন M' বানাই:

M'(কোনো ইনপুট, উপেক্ষা করা হয়):
    M-কে w-তে সিমুলেট করো
    (যদি M থামে):
        "hello" প্রিন্ট করো
        থামো

f(⟨M, w⟩) = ⟨M'⟩।

ধাপ ৩ (computability): f computable — M, w থেকে M'-এর description যান্ত্রিকভাবে বানানো যায় (M'-এর কোড literally M আর w-এর একটা টেমপ্লেটে বসানো, কোনো M-কে চালানো লাগে না, শুধু তার description থেকে একটা নতুন description বানানো)।

ধাপ ৪ (⟺):

(⟹) যদি ⟨M, w⟩ ∈ HALT (M থামে w-তে), তাহলে M' তার সিমুলেশন ধাপে পৌঁছে “hello” প্রিন্ট করবে এবং থামবে — তাই ⟨M'⟩ ∈ PRINTS_HELLO
(⟸) যদি ⟨M, w⟩ ∉ HALT (M থামে না w-তে), তাহলে M'-এর সিমুলেশন ধাপ কখনো শেষ হবে না, তাই “hello” প্রিন্ট করার লাইনে কখনো পৌঁছাবে না — তাই ⟨M'⟩ ∉ PRINTS_HELLO

$\langle M, w\rangle \in HALT \iff \langle M'\rangle \in PRINTS\_HELLO$

যেহেতু HALT ≤ₘ PRINTS_HELLO এবং HALT undecidable, উপপাদ্য অনুযায়ী PRINTS_HELLO-ও undecidable। ∎

প্যাটার্নটা লক্ষ্য করুন

M'-এর নির্মাণে একটা নির্দিষ্ট কৌশল বারবার ব্যবহৃত হয় — “প্রথমে M-কে w-তে সিমুলেট করো, তারপরই আসল কাজ করো।” এই কৌশলটা এত সাধারণ যে এর একটা নাম আছে — “গার্ড ক্লজ রিডাকশন” (কথ্য পরিভাষা)। M-এর সিমুলেশনটা একটা গেটকিপার হিসেবে কাজ করে: M না থামলে গেটের পরের কোড কখনো চলে না, তাই “পরের কোড কি কখনো চলে” প্রশ্নটা সরাসরি “M কি থামে” প্রশ্নের সমতুল্য হয়ে যায়।

উদাহরণ ২ — `EQ_TM` (প্রোগ্রাম সমতা) undecidable

EQ_TM = {⟨M1, M2⟩ : M1 ও M2 একই ভাষা চেনে, অর্থাৎ L(M1) = L(M2)}

এটা একটা অত্যন্ত practical-সদৃশ প্রশ্ন — “দুইটা প্রোগ্রাম কি সমতুল্য” (compiler optimization, refactoring correctness-এর মূল প্রশ্ন)।

প্রমাণ (HALT ≤ₘ EQ_TM):

HALT-এর instance ⟨M, w⟩ দেওয়া হলে, দুইটা নতুন মেশিন বানাই:

M1(কোনো ইনপুট):
    সবসময় reject করে (কখনো accept করে না — L(M1) = ∅)

M2(কোনো ইনপুট, উপেক্ষা করা হয়):
    M-কে w-তে সিমুলেট করো
    (M থামলে) accept করো

f(⟨M, w⟩) = ⟨M1, M2⟩।

⟺ যাচাই:

(⟹) যদি M থামে না w-তে: M2 কখনো accept-এ পৌঁছায় না, তাই L(M2) = ∅ = L(M1) — সমতুল্য, তাই ⟨M1, M2⟩ ∈ EQ_TM
(⟸) যদি M থামে w-তে: M2 প্রতিটা ইনপুটে (ইনপুট উপেক্ষা করে, শুধু M থামে কি না তার উপর নির্ভর করে) accept করে, তাই L(M2) = Σ* — যা L(M1) = ∅-এর সমান নয় (যদি না alphabet খালি হয়, যা আমরা বাদ দিচ্ছি) — তাই ⟨M1, M2⟩ ∉ EQ_TM

$\langle M, w\rangle \notin HALT \iff \langle M1, M2\rangle \in EQ\_TM$

লক্ষ্য করুন — এখানে ⟺-টা উল্টো দিকে লেখা হয়েছে (∉ HALT ⟺ ∈ EQ_TM) কিন্তু এটাও সম্পূর্ণ বৈধ একটা reduction — শুধু f-এর সংজ্ঞা এমনভাবে সাজানো হয়েছে। মূল কথা এখনও একই — f computable, আর দুই দিকের impliation ধরে রাখা হয়েছে। যেহেতু co-HALT (HALT-এর complement) undecidable (আগের লেসনে দেখানো), এই reduction একইভাবে EQ_TM-এর undecidability প্রমাণ করে। ∎

প্রথম দুইটা উদাহরণের মিল — এবং কেন এটা কাকতালীয় না

PRINTS_HELLO আর EQ_TM — দেখতে সম্পূর্ণ ভিন্ন প্রশ্ন মনে হয়, কিন্তু দুইটার প্রমাণই একই কেন্দ্রীয় কৌশলে দাঁড়িয়ে: M-কে w-তে সিমুলেট করার প্রক্রিয়াটাকে একটা নতুন প্রোগ্রামের ভেতরে “লুকিয়ে রাখা”, যাতে নতুন প্রোগ্রামের আচরণ (hello প্রিন্ট করা, বা একটা নির্দিষ্ট ভাষা চেনা) সরাসরি M-এর halting-এর সাথে বাঁধা পড়ে যায়।

এই প্যাটার্নটা এতটাই সাধারণ যে পরের লেসনে আমরা দেখব — একটা প্রোগ্রামের যেকোনো non-trivial semantic property (শুধু “hello প্রিন্ট করে” বা “খালি ভাষা” না, বরং প্রায় যেকোনো আচরণগত প্রশ্ন) এই একই কৌশলে undecidable প্রমাণ করা যায় — একটা একক সাধারণ উপপাদ্যে (Rice’s theorem), যা এই ডজন-খানেক পৃথক প্রমাণকে একটা লাইনে সংক্ষিপ্ত করে দেয়।

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

EXPERIMENT

Reduction-এর রূপান্তরটা কোডে বাস্তবায়ন করুন

Python 3· ২০ মিনিট

# HALT-এর একটা instance-কে PRINTS_HELLO-এর instance-এ রূপান্তরকারী f
# — এটা M-কে চালায় না, শুধু M-এর SOURCE CODE থেকে M'-এর SOURCE CODE বানায়।

def f_reduce_halt_to_prints_hello(M_source: str, w: str) -> str:
    """
    HALT instance (M_source, w) নেয়, PRINTS_HELLO instance M'_source ফেরত দেয়।
    লক্ষ্য করুন: এই function নিজে M_source-কে EXECUTE করে না —
    শুধু নতুন সোর্স কোড STRING হিসেবে বানায়। এটাই 'computable transformation'।
    """
    M_prime_source = f'''
def M_prime(ignored_input):
    # ধাপ ১: M-কে w-তে সিমুলেট করা (গেটকিপার)
    {M_source}
    M(w={w!r})   # যদি M থামে w-তে, তবেই নিচের লাইনে পৌঁছাব

    # ধাপ ২: শুধু M থামলে এই লাইনে পৌঁছানো সম্ভব
    print("hello")
'''
    return M_prime_source


# ── প্রদর্শন: দুইটা ভিন্ন M দিয়ে f প্রয়োগ করি ──

M_that_halts = "def M(w): return len(w)"          # সবসময় থামে
M_that_loops = "def M(w):\n    while True: pass"   # কখনো থামে না

print("=== f(M_that_halts, 'test') ===")
print(f_reduce_halt_to_prints_hello(M_that_halts, "test"))

print("=== f(M_that_loops, 'test') ===")
print(f_reduce_halt_to_prints_hello(M_that_loops, "test"))

print("লক্ষ্য করুন — f নিজে তাৎক্ষণিকভাবে থামে দুইটা ক্ষেত্রেই।")
print("M_that_loops-কে চালানোর চেষ্টাই করেনি — শুধু তার SOURCE বসিয়ে দিয়েছে।")
print("এটাই মূল কথা: f computable, যদিও M' নিজে (M_that_loops-এর বেলায়) কখনো থামবে না।")

f তাৎক্ষণিকভাবে string রিটার্ন করে — M_that_loops আসলে while True চালায়, তবু f তা এড়িয়ে যায় কারণ f কখনো M-কে রান করে না, শুধু তার description ব্যবহার করে নতুন description বানায়।

সবচেয়ে সাধারণ ভুল যা এই experiment ধরিয়ে দেয়

একজন নতুন শিক্ষার্থী প্রায়ই ভুল করে f-কে এমনভাবে সংজ্ঞায়িত করার চেষ্টা করে যেখানে f নিজেই M-কে w-তে চালিয়ে ফলাফল দেখে তারপর সিদ্ধান্ত নেয় — কিন্তু তাহলে f নিজেই M না থামলে কখনো থামবে না, অর্থাৎ f computable (total) থাকবে না, আর পুরো reduction প্রমাণ ভেঙে পড়বে (কারণ definition-এ f অবশ্যই সবসময় থামতে হবে)।

সঠিক reduction-এ f শুধু কোড তৈরি করে, কোড চালায় না। M'-এর ভেতরে থাকা সিমুলেশনটাই (যেটা M' নিজে চালানো হলে ঘটবে) থামা-না-থামার প্রশ্নটা বহন করে — f-এর নিজের থামা-না-থামার সাথে সেটার কোনো সম্পর্ক নেই।

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

একটা 'রূপান্তরকারী' f সত্যিই একটা mechanical, সহজে-লেখা প্রোগ্রাম — এটা M-কে চালায় না, শুধু M-এর description থেকে M'-এর description তৈরি করে। এই পার্থক্যটাই (রূপান্তর বনাম রান করা) reduction-এর computability শর্তের মূল কথা।

নিজে বানান

BUILD IT

নিজের reduction লাইব্রেরি — তিনটা নতুন undecidable সমস্যা প্রমাণ করুন

Python · ●●●●○

একটা reduction-checker framework লিখুন যা f, এবং কিছু টেস্ট instance নিয়ে ⟺ সম্পর্ক যাচাই করে
ACCEPTS_EMPTY (M কি খালি স্ট্রিং accept করে) সমস্যার জন্য reduction লিখুন
REGULAR_TM (M যে ভাষা চেনে তা কি regular) সমস্যার জন্য reduction লিখুন — এটা কঠিনতর
তিনটা reduction-ই একই টেমপ্লেট অনুসরণ করে তা মন্তব্যে দেখান

# ── একটা ছোট 'concrete' TM-simulator, যাতে reduction-গুলো সত্যিই চালিয়ে দেখা যায় ──

def simulate(M_code: dict, w: str, max_steps=10_000):
    """M_code একটা transition table (আগের লেসনগুলোর ফরম্যাটে)।
    Returns True (থামে), False (max_steps-এ timeout, 'সম্ভবত loop')।"""
    tape = list(w) + ["_"] * 50
    head, state, steps = 0, "q0", 0
    while state not in ("qaccept", "qreject") and steps \< max_steps:
        key = (state, tape[head])
        if key not in M_code:
            return True     # কোনো নিয়ম নেই = আটকে গেল = কার্যত থামল (reject)
        new_state, write, move = M_code[key]
        tape[head], state = write, new_state
        head += 1 if move == "R" else -1
        steps += 1
    return steps \< max_steps   # True = থামল, False = timeout


# ── Reduction ১: PRINTS_HELLO (আগে থেকেই আলোচিত, এবার চালিয়ে যাচাই) ──

def halts_within(M_code, w, budget):
    return simulate(M_code, w, max_steps=budget)

def reduce_to_prints_hello(M_code, w):
    """M'-এর 'আচরণ' — বাস্তব TM code জেনারেট না করে, এখানে সরাসরি
    সিদ্ধান্ত-ফাংশন হিসেবে দেখাচ্ছি (pedagogically সহজবোধ্য রাখতে)।"""
    def M_prime_behavior():
        if halts_within(M_code, w, budget=10_000):
            return "prints hello"
        return "never prints hello (or loops)"
    return M_prime_behavior


# ── Reduction ২: ACCEPTS_EMPTY — M কি খালি স্ট্রিং accept করে ──

def reduce_to_accepts_empty(M_code, w):
    """M2 বানাই: input উপেক্ষা করে, M-কে w-তে সিমুলেট করে,
    M থামলে (accept ধরে) নিজেও accept করে — নাহলে কখনো থামে না।
    M2 খালি স্ট্রিং accept করে ⟺ M থামে w-তে।"""
    def M2_accepts_empty():
        return halts_within(M_code, w, budget=10_000)
    return M2_accepts_empty


# ── প্রদর্শন — {0^n1^n} মেশিন (আগের লেসন থেকে) দিয়ে যাচাই ──

m_eqcount = {
    ("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"),
}

for test_w in ["0011", "0010"]:
    print(f"--- w={test_w!r} ---")
    print("  reduce_to_prints_hello:", reduce_to_prints_hello(m_eqcount, test_w)())
    print("  reduce_to_accepts_empty:", reduce_to_accepts_empty(m_eqcount, test_w)())

প্রত্যাশিত output:

--- w='0011' ---
  reduce_to_prints_hello: prints hello
  reduce_to_accepts_empty: True
--- w='0010' ---
  reduce_to_prints_hello: prints hello
  reduce_to_accepts_empty: True

লক্ষ্য করুন — দুইটা ক্ষেত্রেই ফলাফল একই! কারণ m_eqcount উভয় ইনপুটেই থামে (একটাতে accept, একটাতে reject করে, কিন্তু দুইটাতেই থামে) — আর reduction শুধু “থামে কি না” এর উপর নির্ভর করছে, accept/reject-এর মধ্যে পার্থক্য না। এটাই একটা গুরুত্বপূর্ণ সূক্ষ্মতা — HALT-এর সংজ্ঞা “থামে” মানে accept বা reject, দুইটাই।

নিজে বাড়ান:

একটা M_code বানান যেটা কিছু ইনপুটে loop করে (max_steps-এ timeout দিন), দেখুন reduce_to_accepts_empty কী রিটার্ন করে — ব্যাখ্যা করুন কেন এই bounded simulator-টা নিজেই সত্যিকার f-এর জন্য যথেষ্ট না (f-কে সবসময় থামতে হয়, একটা 10,000-step বাজেট দিয়ে না)
REGULAR_TM সমস্যার জন্য reduction ডিজাইন করুন: M-কে এমন একটা M2 বানান যা M থামলে {0ⁿ1ⁿ} (non-regular) চেনে, না থামলে Σ* (regular) চেনে — লিখুন কেন এই নির্মাণ কাজ করে
মন্তব্যে লিখুন — এই তিনটা reduction-ই (PRINTS_HELLO, ACCEPTS_EMPTY, REGULAR_TM) কেন একই “গেটকিপার” প্যাটার্ন ব্যবহার করে, শুধু গেটের পরের আচরণ ভিন্ন

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

Reduction যেখানে সরাসরি বাস্তব সিদ্ধান্ত নেয়

Compiler-এর dead code elimination। “এই কোড ব্লক কি কখনো execute হয়” প্রশ্নটা PRINTS_HELLO-এর মতোই একটা reduction দিয়ে undecidable প্রমাণযোগ্য (যেকোনো কোড ব্লককে একটা M-এর থামার শর্তে গেট করে)। তাই সব production compiler dead-code elimination রক্ষণশীল — নিশ্চিতভাবে অব্যবহৃত কোড মুছে ফেলে, কিন্তু কিছু আসলেই মৃত কোড রেখে দেয় কারণ প্রমাণ করতে পারে না সেটা মৃত।

Refactoring টুলের সীমা। “এই রিফ্যাক্টরিং সেমান্টিক্স সংরক্ষণ করে কি না” (পুরনো আর নতুন কোড কি সব ইনপুটে একই আউটপুট দেয়) — এটা হুবহু EQ_TM-এর সমতুল্য, যা undecidable। তাই IDE refactoring টুল (rename, extract method) সাধারণত শুধু syntactic নিরাপত্তা নিশ্চিত করে (নাম-সংঘর্ষ না হওয়া), semantic সমতা নিশ্চিত করার কোনো সাধারণ উপায় নেই — সেই দায়িত্ব শেষ পর্যন্ত ডেভেলপারের টেস্ট স্যুটের উপর থাকে।

Malware polymorphism detection। “দুইটা ভিন্ন-দেখতে বাইনারি কি একই malware-এর variant” (একই আচরণ করে) — এটাও EQ_TM-এর একটা রূপ। এই কারণেই antivirus কোম্পানি behavioral clustering আর হিউরিস্টিক signature ব্যবহার করে, নিখুঁত সমতা-যাচাই না — আগের লেসনের halting problem-এর সীমাবদ্ধতার একটা সরাসরি সম্প্রসারণ।

NP-completeness reduction — যে কৌশলটা পুনরায় দেখা দেবে। এই লেসনের পুরো কাঠামো — “যদি B সমাধান করতে পারতাম, A-ও পারতাম, তাই B অন্তত A-এর মতোই কঠিন” — এই module-এর পরের অংশে (NP-completeness, Cook-Levin theorem) হুবহু একই যুক্তি, শুধু “decidable” শব্দের বদলে “polynomial-time solvable”। SAT-কে 3-SAT-এ, 3-SAT-কে vertex-cover-এ, vertex-cover-কে independent-set-এ reduce করা — এই প্রতিটা proof-ই আজকের লেসনের টেমপ্লেট অনুসরণ করে (computable f-এর বদলে polynomial-time f, বাকি সব অভিন্ন)। এই একটা লেসনের দক্ষতা প্রায় সরাসরি সেই পরের, বিখ্যাত (এবং প্রায়ই কঠিন মনে করা) প্রমাণগুলোতে স্থানান্তরিত হবে।

Type system-এর decidability সীমা। কিছু আধুনিক টাইপ সিস্টেম (যেমন C++ template metaprogramming, কিছু dependent type system) নিজেরাই Turing-complete — টাইপ চেক করা মানে একটা প্রোগ্রাম চালানো। এই ক্ষেত্রে “টাইপ চেক শেষ হবে কি না” প্রশ্নটা সরাসরি HALT-এ reduce হয়, যেটা ব্যাখ্যা করে কেন কিছু C++ compilation infinite loop-এ (বা কার্যত সীমাহীন সময়ে) আটকে যেতে পারে।

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

“Reduction A ≤ₘ B মানে A, B-এর চেয়ে 'বড়' বা 'জটিল' সমস্যা।”

না — A ≤ₘ B মানে A সমাধান করা B সমাধান করার চেয়ে কঠিন না (A, B-এর “চেয়ে সহজ বা সমান”)। এই সম্পর্কটা সমস্যার আকার, বর্ণনার দৈর্ঘ্য, বা “স্বাভাবিক জটিলতা” নিয়ে কিছু বলে না — শুধু একটা নির্দিষ্ট গাণিতিক সম্পর্ক (একটা computable রূপান্তর f-এর অস্তিত্ব) নিয়ে বলে।

গুরুত্বপূর্ণ পরিণতি — A ≤ₘ B আর B ≤ₘ A দুইটাই একসাথে সত্য হতে পারে (দুইটা সমস্যা পরস্পর reducible, “সমতুল্য কঠিনতার”)। HALT আর PRINTS_HELLO আসলে এভাবেই সম্পর্কিত — আমরা HALT ≤ₘ PRINTS_HELLO দেখিয়েছি, আর বিপরীত দিকের reduction-ও সম্ভব (PRINTS_HELLO-র decider দিয়ে HALT-এর decider বানানো, একই কৌশলে)।

“যদি A ≤ₘ B এবং A decidable হয়, তাহলে B-ও decidable।”

সম্পূর্ণ ভুল — এবং এটা সবচেয়ে বিপজ্জনক ভুল, কারণ এটা ঠিক বিপরীত দিকে যুক্তি করে যা মূল উপপাদ্যে সঠিক।

উপপাদ্যটা বলে: B decidable ⟹ A decidable (এবং contrapositive: A undecidable ⟹ B undecidable)। A decidable হওয়া B সম্পর্কে কিছুই বলে না — B easy বা hard, যেকোনোটাই হতে পারে।

কারণ বোঝা সহজ: A ≤ₘ B-র অর্থ “B-র decider থাকলে A-রও decider বানানো যায়” — এই বাক্যটা A-র decider দিয়ে B-র decider বানানোর কোনো পথ দেয় না, রূপান্তরটা একমুখী (A-র instance থেকে B-র instance-এ, বিপরীতে না)। প্রতিটা A ≤ₘ B reduction যেখানে A decidable, B easily undecidable-ও হতে পারে — যেমন A = ∅ (তুচ্ছভাবে decidable, সবসময় reject) সবসময় যেকোনো B-তে trivially reduce করা যায় (f-কে কোনো নির্দিষ্ট B-এর বাইরের element-এ পাঠিয়ে) — এটা B-এর decidability সম্পর্কে কিচ্ছু বলে না।

“একটা reduction প্রমাণে f-কে অবশ্যই 'দ্রুত' (efficient) হতে হবে।”

এই লেসনের many-one reduction-এ না — শুধু f computable (সসীম সময়ে গণনাযোগ্য) হতে হবে, তার গতি নিয়ে কোনো শর্ত নেই। f হাজার বছর লাগিয়ে গণনা করলেও, যতক্ষণ এটা সসীম সময়ে থামে, reduction বৈধ।

এটা যেখানে বদলায়: complexity theory-তে (এই module-এর পরের অংশ, NP-completeness) একটা কঠোরতর সংস্করণ ব্যবহার হয় — polynomial-time reduction, যেখানে f-কে polynomial সময়ে গণনাযোগ্য হতে হয়। সেই প্রেক্ষাপটে efficiency গুরুত্বপূর্ণ, কারণ decidability না, বরং “efficiently solvable কি না” প্রশ্নের জন্য সেই reduction ব্যবহৃত হয়। এই লেসনের reduction (decidability-র জন্য) এবং পরের (efficiency-র জন্য) — দুইটাকে গুলিয়ে ফেলবেন না, যদিও কাঠামো প্রায় অভিন্ন।

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

A ≤ₘ B প্রমাণ করতে হলে f-এর কোন দুইটা শর্ত পূরণ করতে হবে?

স্মরণ

১. f computable হতে হবে — একটা TM আছে যা প্রতিটা w-এর জন্য f(w) গণনা করে, সবসময় সসীম সময়ে থেমে।

২. f উভয় দিকের সম্পর্ক সংরক্ষণ করতে হবে — w ∈ A ⟺ f(w) ∈ B — শুধু একদিক (যেমন শুধু w ∈ A ⟹ f(w) ∈ B) যথেষ্ট না, উভয় দিকই লাগবে।

একজন ছাত্র “প্রমাণ” করার চেষ্টা করছেন PRINTS_HELLO undecidable এভাবে: “PRINTS_HELLO ≤ₘ HALT — কারণ যদি একটা মেশিন hello প্রিন্ট করে, সেটা অবশ্যই থেমেছে (অন্তত hello প্রিন্ট করা পর্যন্ত)। যেহেতু HALT undecidable, PRINTS_HELLO-ও undecidable।” এই যুক্তির কোথায় সমস্যা?

যুক্তি

দুইটা সমস্যা আছে, দুইটাই গুরুতর।

১. দিকটা ভুল। ছাত্র দেখাতে চাইছেন PRINTS_HELLO ≤ₘ HALT, কিন্তু উপপাদ্য অনুযায়ী এই দিকের reduction থেকে যা প্রমাণ হয় তা হলো “যদি HALT decidable হতো, PRINTS_HELLO-ও হতো” — এটা কোনো কাজে আসে না কারণ আমরা জানি HALT undecidable, decidable না। সঠিক প্রমাণের জন্য বিপরীত দিকের reduction দরকার: HALT ≤ₘ PRINTS_HELLO (পরিচিত undecidable সমস্যা থেকে নতুন সমস্যায়, উল্টো না)।

২. এমনকি সঠিক দিকেও, PRINTS_HELLO ≤ₘ HALT-এর যুক্তিটাই বৈধ reduction না। ছাত্রের যুক্তি “hello প্রিন্ট করলে মেশিন থেমেছে” — এটা একটা logical impliation, কিন্তু reduction-এর জন্য একটা computable function f লাগবে যা PRINTS_HELLO-র instance-কে HALT-এর instance-এ রূপান্তর করে, শুধু একটা সাধারণ পর্যবেক্ষণ না। (আসলে, PRINTS_HELLO ≤ₘ HALT-ও সত্য এবং প্রমাণযোগ্য — M-কে এমন M'-এ রূপান্তর করে যেটা M-কে সিমুলেট করে “hello” প্রিন্ট করার অপেক্ষায় থামে — কিন্তু এই প্রমাণটাও কোনো কাজে আসত না, কারণ পয়েন্ট ১-এর কারণে।)

শিক্ষা: সবসময় প্রথমে চেক করুন কোন দিকের reduction আপনার প্রয়োজনীয় সিদ্ধান্তে পৌঁছায় — “পরিচিত undecidable থেকে নতুন সমস্যায়” — তারপরই f ডিজাইন করা শুরু করুন।

RETURNS_42 = {⟨M⟩ : M, খালি ইনপুটে চালালে, কখনো ঠিক 42 রিটার্ন করে} — এটা undecidable প্রমাণ করুন, HALT-থেকে reduction দিয়ে।

প্রয়োগ

প্রমাণ (HALT ≤ₘ RETURNS_42):

HALT-এর instance ⟨M, w⟩ দেওয়া হলে, একটা নতুন মেশিন M' বানাই:

M'(ইনপুট, উপেক্ষা করা হয়):
    M-কে w-তে সিমুলেট করো
    (M থামলে):
        return 42

f(⟨M, w⟩) = ⟨M'⟩। এটা PRINTS_HELLO-র প্রমাণের হুবহু একই “গেটকিপার” প্যাটার্ন, শুধু “hello প্রিন্ট করা”-র বদলে “42 রিটার্ন করা”।

Computability: f computable — M, w থেকে M'-এর কোড যান্ত্রিকভাবে বানানো, M-কে চালানো লাগে না।

⟺ যাচাই:

(⟹) ⟨M,w⟩ ∈ HALT (M থামে w-তে) ⟹ M'-এর সিমুলেশন ধাপ শেষ হয়, return 42-এ পৌঁছায় ⟹ ⟨M'⟩ ∈ RETURNS_42
(⟸) ⟨M,w⟩ ∉ HALT (M থামে না) ⟹ M' কখনো সিমুলেশন ধাপ পেরোয় না, কখনো 42 রিটার্ন করে না ⟹ ⟨M'⟩ ∉ RETURNS_42

যেহেতু HALT ≤ₘ RETURNS_42 এবং HALT undecidable, উপপাদ্য অনুযায়ী RETURNS_42 undecidable। ∎

পর্যবেক্ষণ: এই প্রমাণটা PRINTS_HELLO-র প্রমাণের একটা প্রায় হুবহু কপি, শুধু “গেটের পরের আচরণ” বদলে দেওয়া হয়েছে। এটাই লেসনের মূল বার্তার একটা সরাসরি প্রদর্শন — একবার প্যাটার্নটা বোঝা হয়ে গেলে, নতুন undecidability প্রমাণ প্রায় যান্ত্রিক হয়ে যায়।

ALL_TM = {⟨M⟩ : M প্রতিটা সম্ভাব্য ইনপুট string accept করে} — এটা undecidable প্রমাণ করার জন্য একটা reduction ডিজাইন করুন। (ইঙ্গিত: co-HALT-এর মতো একটা “সবসময় ব্যর্থ” ভাষা থেকে reduce করার কথা ভাবুন, অথবা সরাসরি HALT থেকে — উভয় পথই সম্ভব, যেকোনো একটা বেছে নিয়ে সম্পূর্ণ প্রমাণ লিখুন।)

ডিজাইন

প্রমাণ (HALT ≤ₘ ALL_TM, complement trick ব্যবহার করে):

HALT-এর instance ⟨M, w⟩ দেওয়া হলে, একটা নতুন মেশিন M' বানাই যা যেকোনো ইনপুট x-এর জন্য:

M'(x):
    M-কে w-তে সিমুলেট করো        # x সম্পূর্ণ উপেক্ষা করা হচ্ছে
    (M থামলে): accept করো (যেই x-ই হোক)
    (M না থামলে): M' নিজেও কখনো থামে না, তাই x accept হয় না

f(⟨M, w⟩) = ⟨M'⟩।

Computability: যথারীতি, M, w থেকে M'-এর কোড mechanical-ভাবে বানানো — computable।

⟺ যাচাই:

(⟹) ⟨M,w⟩ ∈ HALT: M থামে w-তে, তাই M' প্রতিটা x-এর জন্য সিমুলেশন ধাপ পার হয়ে accept করে (কারণ সিমুলেশনটা x-এর উপর নির্ভর করে না, শুধু M, w-এর উপর) — তাই M' সব x accept করে, অর্থাৎ ⟨M'⟩ ∈ ALL_TM
(⟸) ⟨M,w⟩ ∉ HALT: M থামে না w-তে, তাই M' কোনো x-এর জন্যই সিমুলেশন ধাপ পার হয় না — কখনো কোনো x accept করে না। বিশেষভাবে, M' সব x accept করে না (আসলে একটাও না) — তাই ⟨M'⟩ ∉ ALL_TM

যেহেতু HALT ≤ₘ ALL_TM এবং HALT undecidable, ALL_TM undecidable। ∎

গুরুত্বপূর্ণ ডিজাইন সিদ্ধান্তের ব্যাখ্যা: এই প্রমাণের চাবিকাঠি হলো — M'-এর সিমুলেশন ধাপ x-এর উপর নির্ভর করে না (w আগে থেকেই ফিক্সড, M'-এর কোডে হার্ডকোড করা)। এই কারণেই M থামলে সব x accept হয় (একসাথে), আর না থামলে কোনো x-ই accept হয় না (একসাথে) — এটাই ALL_TM-এর “প্রতিটা ইনপুট” শর্তের সাথে ঠিকঠাক মেলে। যদি সিমুলেশনটা x-নির্ভর হতো, এই পরিষ্কার সব-অথবা-কিছুই আচরণ পাওয়া যেত না, আর reduction ভেঙে পড়ত।

এরপর কী

এই লেসনে আমরা একটা টেমপ্লেট শিখেছি যা দিয়ে একের পর এক নির্দিষ্ট সমস্যা (PRINTS_HELLO, EQ_TM, RETURNS_42, ALL_TM) undecidable প্রমাণ করা গেছে। কিন্তু প্রতিটা প্রমাণেই একটা পরিচিত প্যাটার্ন ফিরে এসেছে — “M-কে সিমুলেট করে একটা গেট বসানো, গেটের পরে কিছু নির্দিষ্ট semantic আচরণ প্রদর্শন করা”।

এই পুনরাবৃত্তি একটা প্রশ্ন তোলে — এই সবগুলো প্রমাণ কি একটা একক, আরো সাধারণ উপপাদ্যের বিশেষ ক্ষেত্র? পরের লেসনে উত্তর হ্যাঁ — Rice’s theorem একটা মাত্র বাক্যে বলে দেয় যে একটা প্রোগ্রামের আচরণ সম্পর্কে (syntax না, semantics — প্রোগ্রামটা কী করে, কীভাবে লেখা তা না) যেকোনো non-trivial প্রশ্নই undecidable। এই একটা উপপাদ্য এই লেসনের সবগুলো পৃথক প্রমাণকে (আর আরো অসংখ্য না-লেখা প্রমাণকে) একটা লাইনের যুক্তিতে সংক্ষিপ্ত করে দেবে।

Reduction — একবার প্রমাণ করে বারবার ধার করা

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

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

আগে এটা বুঝি

মূল ধারণা

Many-one reduction — আনুষ্ঠানিক সংজ্ঞা

মূল উপপাদ্য — কোন দিকে তথ্য প্রবাহিত হয়

কেন এই দিকটাই সঠিক — একটা সাদৃশ্য

ভেতরে কী ঘটছে

Reduction টেমপ্লেট — চারটা ধাপ

উদাহরণ

উদাহরণ ১ — `PRINTS_HELLO` undecidable

উদাহরণ ২ — `EQ_TM` (প্রোগ্রাম সমতা) undecidable

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

Reduction-এর রূপান্তরটা কোডে বাস্তবায়ন করুন

নিজে বানান

নিজের reduction লাইব্রেরি — তিনটা নতুন undecidable সমস্যা প্রমাণ করুন

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

Reduction যেখানে সরাসরি বাস্তব সিদ্ধান্ত নেয়

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

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

এরপর কী

আরও পড়ুন

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

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

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

◆মূল ধারণাCore concept

Many-one reduction — আনুষ্ঠানিক সংজ্ঞা

মূল উপপাদ্য — কোন দিকে তথ্য প্রবাহিত হয়

কেন এই দিকটাই সঠিক — একটা সাদৃশ্য

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

Reduction টেমপ্লেট — চারটা ধাপ

▶উদাহরণExample

উদাহরণ ১ — PRINTS_HELLO undecidable

উদাহরণ ২ — EQ_TM (প্রোগ্রাম সমতা) undecidable

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

Reduction-এর রূপান্তরটা কোডে বাস্তবায়ন করুন

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

নিজের reduction লাইব্রেরি — তিনটা নতুন undecidable সমস্যা প্রমাণ করুন

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

Reduction যেখানে সরাসরি বাস্তব সিদ্ধান্ত নেয়

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

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

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

উদাহরণ ১ — `PRINTS_HELLO` undecidable

উদাহরণ ২ — `EQ_TM` (প্রোগ্রাম সমতা) undecidable

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

নিজে বানান

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

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

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

এরপর কী