Rice's Theorem — একটা বাক্য যা ডজন ডজন প্রমাণকে অপ্রয়োজনীয় করে দেয়

আগে এটা বুঝি

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

এটা একটা স্বাভাবিক সন্দেহ তোলে — যদি এই প্যাটার্নটা সবসময় কাজ করে, তাহলে হয়তো এমন কোনো প্রশ্নই নেই যা একটা প্রোগ্রামের “আচরণ” সম্পর্কে আর decidable? উত্তর, বিস্ময়করভাবে প্রায়, হ্যাঁ — প্রায় প্রতিটাই undecidable। আর এটা একটা আলাদা আলাদা প্রমাণের তালিকা না, একটা একক উপপাদ্য।

১৯৫৩ সালে Henry Gordon Rice এই পর্যবেক্ষণটা আনুষ্ঠানিক করলেন — একটা উপপাদ্য যা এতটাই সাধারণ যে এর প্রমাণ পড়ার পর আপনি চাইলেই নতুন প্রায় যেকোনো “প্রোগ্রাম X কি Y আচরণ করে” প্রশ্নের decidability সম্পর্কে তাৎক্ষণিকভাবে (কোনো নতুন reduction না লিখেই) সিদ্ধান্তে পৌঁছাতে পারবেন।

এই লেসনের পর আপনার হাতে যা থাকবে

Rice’s theorem শেখার পর, “এই প্রোগ্রাম-সম্পর্কিত প্রশ্নটা কি decidable?” — এই প্রশ্নের উত্তর প্রায়ই এক লাইনে দেওয়া সম্ভব হবে, একটা পূর্ণ reduction proof না লিখেই। এটা এই module-এর সবচেয়ে বেশি “ব্যবহারিক leverage” দেওয়া একটা একক উপপাদ্য — বাস্তব সফটওয়্যার ইঞ্জিনিয়ারিং-এর অনেক “কেন এই টুল এটা করতে পারে না” প্রশ্নের সরাসরি উত্তর দেয়।

মূল ধারণা

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

Rice’s theorem: P কোনো non-trivial property হোক Turing-recognizable ভাষার উপর (অর্থাৎ P একটা সেট of languages — M-এর গৃহীত ভাষা L(M) P-তে আছে কি না)। তাহলে

$L_P = \{\langle M \rangle : L(M) \in P\}$

undecidable।

প্রতিটা শব্দ এখানে ওজনদার — একটা একটা করে খুলি।

“Property of the language” — semantic, syntactic না

P একটা property ভাষার উপর (L(M)-এর উপর), মেশিনের বর্ণনার (source code) উপর না। এটাই semantic বনাম syntactic পার্থক্য।

	Semantic property (Rice প্রযোজ্য)	Syntactic property (Rice প্রযোজ্য না)
প্রশ্ন করে	`M` কী করে (input-output আচরণ)	`M`-এর কোড দেখতে কেমন
উদাহরণ	“M কি খালি স্ট্রিং accept করে?”	“M-এর কোডে কি ১০০টার বেশি state আছে?”
উদাহরণ	“M কি সবসময় থামে?”	“M-এর সোর্স কোডে কি ‘goto’ শব্দ আছে?”
Decidability	সাধারণত undecidable (Rice প্রযোজ্য)	সবসময় decidable (শুধু কোড পড়া, চালানো লাগে না)

কেন syntactic property সবসময় decidable: এগুলো M-এর description-এর উপর একটা সসীম, mechanical পরীক্ষা — M-কে চালানোর প্রয়োজনই নেই। “কোডে ‘goto’ আছে কি না” শুধু string-এর মধ্যে substring খোঁজা — এটা DFA দিয়েই করা যায়। Rice’s theorem শুধু semantic property নিয়ে — M কী করে, M কেমন দেখতে তা নিয়ে না।

“Non-trivial” — শুধু দুইটা তুচ্ছ ক্ষেত্র বাদ

P trivial যদি:

সবসময় false — কোনো TM-ই P সন্তুষ্ট করে না (P = ∅), অথবা
সবসময় true — প্রতিটা TM P সন্তুষ্ট করে (P = সব recognizable ভাষার সেট)

এই দুইটা ক্ষেত্রেই L_P-র উত্তর জানতে M-এর দিকে তাকানোরই দরকার নেই — উত্তর আগে থেকেই জানা (সবসময় “না”, বা সবসময় “হ্যাঁ”) — trivially decidable। P non-trivial মানে এই দুইটা তুচ্ছ ক্ষেত্রের বাইরে কিছু — অর্থাৎ অন্তত একটা মেশিন আছে যার ভাষা P-তে আছে, আর অন্তত একটা মেশিন আছে যার ভাষা P-তে নেই।

Rice's theorem প্রয়োগ করার একটা দ্রুত চেকলিস্ট

একটা নতুন প্রশ্ন “প্রোগ্রাম X কি Y করে” দেখলে, তিনটা প্রশ্ন করুন:

এটা কি semantic (input-output আচরণ নিয়ে), নাকি syntactic (কোডের গঠন নিয়ে)? Semantic হলেই এগিয়ে যান।
এটা কি non-trivial — অন্তত একটা প্রোগ্রাম আছে যা “হ্যাঁ” বলে, আর অন্তত একটা “না” বলে? যদি হ্যাঁ হয়…
তাহলে সরাসরি undecidable — কোনো প্রমাণ লেখারও দরকার নেই।

এই চেকলিস্টটাই এই লেসনের সবচেয়ে ব্যবহারিক টুল।

ভেতরে কী ঘটছে

প্রমাণ — আগের লেসনের টেমপ্লেটের একটা সাধারণীকরণ

Rice’s theorem-এর প্রমাণ কাঠামোগতভাবে আগের লেসনের প্রতিটা reduction-এর সাধারণীকৃত রূপ — এটাই কেন এতগুলো পৃথক প্রমাণ আসলে একই প্রমাণের বিশেষ ক্ষেত্র ছিল, তা স্পষ্ট করে।

সেটআপ: P একটা non-trivial semantic property। যেহেতু non-trivial, দুইটা মেশিন বিদ্যমান:

M_yes — যার ভাষা P-তে আছে (L(M_yes) ∈ P)
M_no — যার ভাষা P-তে নেই, বিশেষভাবে সরলতার জন্য ধরি M_no = এমন একটা মেশিন যা কখনো কিছু accept করে না (L(M_no) = ∅)

(টেকনিক্যাল নোট: যদি ∅ ∈ P হয়, তাহলে বদলে M_no = খালি-ভাষার মেশিন, M_yes = কোনো P-তে-থাকা মেশিন নিয়ে প্রতিসম যুক্তি চলে — মূল ধারণাটা অপরিবর্তিত থাকে।)

দাবি: HALT ≤ₘ L_P।

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

M'(x):
    M-কে w-তে সিমুলেট করো
    (M থামলে):
        M_yes-কে x-তে সিমুলেট করো, এবং তার উত্তর ফেরত দাও
    (M না থামলে):
        M' নিজেও কখনো থামে না — তাই সে-ইনপুটেও, x যাই হোক

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

   M থামে w-তে?
        │
       হ্যাঁ ──▶  M' এখন M_yes-এর মতোই আচরণ করে (সব x-এ)
        │           ⟹ L(M') = L(M_yes) ∈ P
        │
       না ──▶   M' কখনোই থামে না (কোনো x-এ)
                    ⟹ L(M') = ∅ ∉ P

Rice's theorem-এর reduction — M' এর আচরণ M-এর halting-এর সাথে বাঁধা।

⟺ যাচাই:

(⟹) M থামে w-তে ⟹ M' প্রতিটা x-এ ঠিক M_yes-এর মতোই আচরণ করে (সিমুলেশনের পর সরাসরি M_yes চালায়) ⟹ L(M') = L(M_yes), যা P-তে আছে ⟹ ⟨M'⟩ ∈ L_P
(⟸) M থামে না w-তে ⟹ M' কোনো x-এই কখনো সিমুলেশন ধাপ পার হয় না ⟹ L(M') = ∅ ∉ P (আমাদের M_no বাছাই অনুযায়ী) ⟹ ⟨M'⟩ ∉ L_P

f computable (M, w থেকে M'-এর কোড mechanical-ভাবে বানানো, M_yes-এর কোডও আগে থেকে জানা, সহজেই বসানো যায়)।

যেহেতু HALT ≤ₘ L_P এবং HALT undecidable, L_P undecidable। ∎ (এই প্রমাণটা P-তে ∅ ∉ P ধরে করা হলো; ∅ ∈ P হলে M_yes/M_no-এর ভূমিকা বদলে, একই কাঠামোয়, একটা প্রতিসম প্রমাণ হয়।)

আগের লেসনের প্রতিটা প্রমাণ এখন এক লাইনে

লক্ষ্য করুন উপরের M'-এর নির্মাণটা আগের লেসনের প্রতিটা reduction-এর হুবহু সাধারণীকরণ:

PRINTS_HELLO: P = “ভাষায় এমন কিছু আছে যার কারণে hello প্রিন্ট হয়”-এর একটা রূপ — M_yes = hello প্রিন্ট করা মেশিন
ALL_TM: P = “ভাষা = Σ*” — M_yes = সব-accept মেশিন
EQ_TM-এর মতো সমস্যা প্রকৃতপক্ষে Rice’s theorem-এর সরাসরি আওতার বাইরে (এটা দুইটা মেশিন তুলনা করে, একটা মেশিনের একক property না) — কিন্তু একই ধরনের reduction কৌশলে আলাদাভাবে প্রমাণযোগ্য, যেমনটা আগের লেসনে দেখানো হয়েছে

আগে আমরা প্রতিটা জন্য আলাদা M' ডিজাইন করেছি; এখন Rice’s theorem বলে দেয় যেকোনো non-trivial semantic P-র জন্য এই একই নির্মাণ কাজ করবে — একটাই সাধারণ প্রমাণ, অসীম সংখ্যক বিশেষ ক্ষেত্র ঢেকে রাখে।

উদাহরণ

দ্রুত প্রয়োগ — চারটা নতুন প্রশ্ন, প্রতিটার উত্তর তাৎক্ষণিক

১. “M কি কখনো null রিটার্ন করে?”

Semantic (input-output আচরণ নিয়ে) ✓। Non-trivial — কিছু প্রোগ্রাম null রিটার্ন করে (M_yes), কিছু কখনো করে না (M_no, যেমন যেটা সবসময় 0 রিটার্ন করে) ✓। সরাসরি undecidable, Rice’s theorem অনুযায়ী।

২. “M কি O(n log n)-এর মধ্যে থামে?”

Semantic (রানটাইম আচরণ) ✓। Non-trivial (কিছু প্রোগ্রাম দ্রুত, কিছু ধীর) ✓। Undecidable। (এটা একটা গুরুত্বপূর্ণ বাস্তব পরিণতি — algorithm-এর asymptotic complexity সাধারণভাবে automatically নির্ধারণ করার কোনো সাধারণ পদ্ধতি নেই — মানুষকে গাণিতিকভাবে প্রমাণ করতে হয়, যেমন induction module-এ আমরা হাতে করেছিলাম।)

৩. “M-এর সোর্স কোডে কি একটা for লুপ আছে?”

Syntactic (কোডের গঠন, আচরণ না) — Rice’s theorem প্রযোজ্য না। এটা আসলে decidable — শুধু কোড parse করে for টোকেন খোঁজা, একটা সাধারণ string-matching সমস্যা।

৪. “M কি ইনপুট হিসেবে দেওয়া প্রতিটা সংখ্যার জন্য সেটা মৌলিক (prime) কি না সঠিকভাবে বলে?”

Semantic ✓। Non-trivial — কিছু প্রোগ্রাম সঠিক primality checker (M_yes), কিছু না (M_no, যেমন সবসময় “না” বলা একটা ভুল প্রোগ্রাম) ✓। Undecidable — এমনকি একটা প্রোগ্রাম “সঠিকভাবে একটা সুনির্দিষ্ট, decidable গাণিতিক সমস্যা সমাধান করে কি না” প্রশ্নটাও undecidable, যদিও primality নিজে decidable! এটা একটা গুরুত্বপূর্ণ, প্রায়ই ভুল বোঝা বিষয় — নিচের misconception অংশে ফিরে আসছি।

প্রশ্ন	Semantic?	Non-trivial?	সিদ্ধান্ত
M কি কখনো `null` রিটার্ন করে?	হ্যাঁ	হ্যাঁ	Undecidable
M কি `O(n log n)`-এ থামে?	হ্যাঁ	হ্যাঁ	Undecidable
M-এর কোডে `for` লুপ আছে?	না (syntactic)	—	Decidable
M কি সঠিক primality checker?	হ্যাঁ	হ্যাঁ	Undecidable

চারটা প্রশ্ন, Rice's theorem-এর চেকলিস্ট প্রয়োগ করে দ্রুত মীমাংসা।

নিজে বানান

BUILD IT

একটা Rice's theorem checklist টুল — যেকোনো প্রশ্ন classify করুন

Python · ●●●○○

একটা property-বর্ণনাকারী ছোট DSL/dataclass বানান (semantic/syntactic flag, trivial কি না নির্দেশক উদাহরণ)
একটা classify() ফাংশন লিখুন যা Rice-এর চেকলিস্ট প্রয়োগ করে
পাঁচ-ছয়টা বাস্তব-সদৃশ static-analysis প্রশ্ন দিয়ে টুলটা পরীক্ষা করুন

from dataclasses import dataclass
from enum import Enum

class Kind(Enum):
    SEMANTIC = "semantic"      # প্রোগ্রামের input-output আচরণ নিয়ে
    SYNTACTIC = "syntactic"    # প্রোগ্রামের কোড/গঠন নিয়ে

@dataclass
class Property:
    name: str
    kind: Kind
    has_yes_example: bool   # অন্তত একটা প্রোগ্রাম আছে যা এটা satisfy করে
    has_no_example: bool    # অন্তত একটা প্রোগ্রাম আছে যা করে না

def classify(p: Property) -> str:
    if p.kind == Kind.SYNTACTIC:
        return "DECIDABLE (syntactic — Rice's theorem প্রযোজ্য না, সরাসরি কোড পরীক্ষা যথেষ্ট)"
    if not (p.has_yes_example and p.has_no_example):
        return "DECIDABLE (trivial — সব 'হ্যাঁ' বা সব 'না', উত্তর আগে থেকেই জানা)"
    return "UNDECIDABLE (Rice's theorem — non-trivial semantic property)"


questions = [
    Property("M কখনো null রিটার্ন করে", Kind.SEMANTIC, True, True),
    Property("M-এর কোডে recursion আছে", Kind.SYNTACTIC, True, True),
    Property("M সবসময় ইনপুটের দৈর্ঘ্যের সমান সময়ে থামে", Kind.SEMANTIC, True, True),
    Property("M একটা valid TM (সংজ্ঞা মেনে চলে)", Kind.SYNTACTIC, True, True),
    Property("M-এর ভাষা খালি (L(M) = ∅)", Kind.SEMANTIC, True, True),
    Property("M প্রতিটা ইনপুটে থামে (total)", Kind.SEMANTIC, True, True),
    Property("M একই ভাষা চেনে যেকোনো ইনপুটে (tautologically true)", Kind.SEMANTIC, True, False),  # trivial — সবসময় true
    Property("M-এর সোর্স কোড ১০০০ লাইনের কম", Kind.SYNTACTIC, True, True),
]

for q in questions:
    print(f"{q.name:55s} -> {classify(q)}")

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

M কখনো null রিটার্ন করে                                -> UNDECIDABLE (Rice's theorem — non-trivial semantic property)
M-এর কোডে recursion আছে                                 -> DECIDABLE (syntactic — Rice's theorem প্রযোজ্য না, সরাসরি কোড পরীক্ষা যথেষ্ট)
M সবসময় ইনপুটের দৈর্ঘ্যের সমান সময়ে থামে                  -> UNDECIDABLE (Rice's theorem — non-trivial semantic property)
M একটা valid TM (সংজ্ঞা মেনে চলে)                        -> DECIDABLE (syntactic — Rice's theorem প্রযোজ্য না, সরাসরি কোড পরীক্ষা যথেষ্ট)
M-এর ভাষা খালি (L(M) = ∅)                                -> UNDECIDABLE (Rice's theorem — non-trivial semantic property)
M প্রতিটা ইনপুটে থামে (total)                              -> UNDECIDABLE (Rice's theorem — non-trivial semantic property)
M একই ভাষা চেনে যেকোনো ইনপুটে (tautologically true)         -> DECIDABLE (trivial — সব 'হ্যাঁ' বা সব 'না', উত্তর আগে থেকেই জানা)
M-এর সোর্স কোড ১০০০ লাইনের কম                              -> DECIDABLE (syntactic — Rice's theorem প্রযোজ্য না, সরাসরি কোড পরীক্ষা যথেষ্ট)

লক্ষণীয় সারি: "M প্রতিটা ইনপুটে থামে (total)" — এটাই আসলে আগের লেসনের HALT-এরই একটা রূপ (TOTAL_TM), আর Rice’s theorem দিয়ে এক লাইনে undecidable প্রমাণিত হয়ে যাচ্ছে, যেখানে আগে আমাদের সম্পূর্ণ diagonalization লিখতে হয়েছিল।

নিজে বাড়ান:

আপনার প্রিয় ভাষার (Python/JavaScript) linter-এর ডকুমেন্টেশন থেকে ৫টা নিয়ম (rule) খুঁজে বের করুন, প্রতিটাকে Property হিসেবে classify করুন — কতগুলো আসলে semantic (তাই heuristic-নির্ভর), কতগুলো syntactic (তাই নিখুঁত)?
classify()-তে একটা তৃতীয় ধরনের প্রশ্ন যোগ করুন — “কম্পিউটেশনালি undecidable, কিন্তু bounded সংস্করণে decidable” (যেমন “M কি ১০০ step-এর মধ্যে থামে”) — ব্যাখ্যা করুন কেন এটা Rice’s theorem-এর আওতার বাইরে
মন্তব্যে লিখুন — কেন has_yes_example/has_no_example যাচাই করাটা বাস্তবে (একটা সত্যিকার নতুন প্রশ্নের জন্য) সহজ, যদিও L_P-র decidability নির্ণয় করা কঠিন — এই দুইটা ভিন্ন কাজের জটিলতার পার্থক্যটা কোথা থেকে আসে

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

Sound বনাম complete — static analysis-এর মৌলিক trade-off

Rice’s theorem-এর সবচেয়ে সরাসরি বাস্তব পরিণতি — প্রতিটা static analysis টুল (linter, type checker, security scanner, dead-code detector) একটা মৌলিক পছন্দের মুখোমুখি হয়, কারণ নিখুঁত বিশ্লেষণ নীতিগতভাবেই অসম্ভব।

Sound analysis: যদি একটা সমস্যা সত্যিই আছে, টুল সেটা ধরবেই (কোনো false negative নেই) — কিন্তু কিছু নিরাপদ কোডকেও ভুলভাবে “সমস্যাযুক্ত” বলতে পারে (false positive সম্ভব)।

Complete analysis: টুল যা কিছু চিহ্নিত করে তা সবসময় সত্যিই সমস্যা (কোনো false positive নেই) — কিন্তু কিছু আসল সমস্যা miss করতে পারে (false negative সম্ভব)।

কোনো টুলই একসাথে sound এবং complete হতে পারে না (যদি না সমস্যাটা trivial বা syntactic হয়) — এটাই Rice’s theorem-এর সরাসরি প্রকাশ।

একটা 'M কি null রিটার্ন করতে পারে' checker-এর দুইটা ডিজাইন সিদ্ধান্ত

Rice's theorem — L_P undecidableকোনো নিখুঁত decider নেই, প্রমাণিত
ডিজাইন সিদ্ধান্ত: sound নাকি complete?দুইটাই একসাথে অসম্ভব — একটা বেছে নিতেই হবে
Sound বেছে নিলে (যেমন Java-র nullability checker)নিরাপদ কোডেও মাঝে মাঝে false-positive warning — বিরক্তিকর কিন্তু নিরাপদ
Complete বেছে নিলে (যেমন বেশিরভাগ runtime-only checker)কিছু আসল null-pointer bug miss করবে — কম বিরক্তিকর কিন্তু ঝুঁকিপূর্ণ
বাস্তব টুল (ESLint, SpotBugs, Clippy)সচেতনভাবে একটা দিকে ঝুঁকে, ডকুমেন্টেশনে সীমাবদ্ধতা স্বীকার করে

উদাহরণ — Java-র @Nullable/@NonNull annotation checker। এটা sound হওয়ার চেষ্টা করে — যদি কোনো path দিয়ে null আসার সম্ভাবনা থাকে, warning দেবে, এমনকি যদি প্র্যাক্টিক্যালি সেই path কখনো নেওয়া না হয় (প্রোগ্রামার জানেন এটা “আসলে” নিরাপদ, কিন্তু checker প্রমাণ করতে পারে না)। এই কারণেই ডেভেলপাররা মাঝে মাঝে @SuppressWarnings ব্যবহার করেন — টুলটা false positive দিচ্ছে জেনেই।

উদাহরণ — Rust-এর borrow checker। এটাও sound (মেমরি নিরাপত্তার জন্য) — কিছু আসলে নিরাপদ প্রোগ্রাম প্রত্যাখ্যাত হয় (কারণ checker প্রমাণ করতে পারে না সেগুলো নিরাপদ), তাই unsafe ব্লক থাকে — প্রোগ্রামারকে ম্যানুয়ালি নিশ্চয়তা দেওয়ার একটা escape hatch, যেখানে compiler নিজে প্রমাণ করতে পারে না।

উদাহরণ — SQL injection scanner। সাধারণত complete-এর দিকে ঝোঁকে (শুধু স্পষ্ট pattern চিহ্নিত করে) কারণ sound হতে গেলে false positive-এর বন্যা বয়ে যেত (প্রায় প্রতিটা string concatenation “সম্ভাব্য বিপজ্জনক” হয়ে যেত) — তাই কিছু আসল vulnerability miss হয়ে যায়, manual security review-এর প্রয়োজনীয়তা থেকেই যায়।

Security module-এর সাথে সরাসরি সংযোগ

লেসনের শুরুতে উল্লেখিত antivirus সমস্যাটা এখন Rice’s theorem দিয়ে আরো তীক্ষ্ণভাবে বলা যায়: “এই প্রোগ্রাম malicious” একটা semantic, non-trivial property — তাই কোনো malware detector কখনো নিখুঁত হতে পারবে না, তার ডিজাইন যত উন্নতই হোক। প্রতিটা antivirus ইঞ্জিন — signature-based, heuristic, ML-based, sandbox-based — সবাই এই একই তাত্ত্বিক দেয়ালের সামনে দাঁড়িয়ে, শুধু ভিন্ন ভিন্ন কৌশলে “কতটা কাছাকাছি” পৌঁছানোর চেষ্টা করে।

Sound malware detector (কোনো malware miss করবে না) — practically অসম্ভব রকম বেশি false positive দেবে (প্রায় সব প্রোগ্রামকেই সন্দেহজনক বলবে, কারণ malicious আচরণ সম্ভব এমন প্রায় সব প্রোগ্রামের জন্যই প্রমাণ করা যায় না এটা অসম্ভব)।

Complete malware detector (যা চিহ্নিত করে তা সবসময় সত্যিই malware) — নতুন, না-দেখা malware pattern miss করতে বাধ্য (zero-day malware, ঠিক এই কারণেই সবসময় থেকে যায়)।

বাস্তব antivirus তাই কোনোটাই না — একটা practical মধ্যপথ, heuristic ও probabilistic — যা Rice’s theorem-এর গণিত সত্ত্বেও এখনও প্রয়োজনীয়, কারণ “নিখুঁত না হওয়া” মানে “অকেজো” না, শুধু মানে “কোনো গ্যারান্টি নেই”।

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

“Rice's theorem বলে প্রোগ্রামের যেকোনো প্রশ্নই undecidable।”

না — শুধু non-trivial semantic প্রশ্ন। এই লেসনের নিজের উদাহরণেই বহু decidable প্রশ্ন দেখানো হয়েছে:

Syntactic প্রশ্ন সবসময় decidable: “কোডে for লুপ আছে কি না”, “কোডের দৈর্ঘ্য কত”, “নির্দিষ্ট variable name ব্যবহৃত হয়েছে কি না” — এসব শুধু কোড পড়া, চালানো লাগে না
Trivial semantic প্রশ্ন decidable: “M-এর ভাষা হয় P-তে আছে নয় নেই” যদি P সব ভাষার জন্য একই উত্তর দেয়, উত্তর আগে থেকেই জানা

Rice’s theorem একটা নির্দিষ্ট, সরু কিন্তু অত্যন্ত গুরুত্বপূর্ণ শ্রেণির প্রশ্নে প্রযোজ্য — বাস্তবে যেটা সবচেয়ে দরকারি শ্রেণি (প্রোগ্রাম আসলে কী করে), তাই এর প্রভাব এত ব্যাপক মনে হয়।

“যেহেতু primality checking নিজেই decidable, একটা 'এই M কি সঠিক primality checker' প্রশ্নও decidable হওয়া উচিত।”

এই দুইটা সম্পূর্ণ ভিন্ন প্রশ্ন, আর এই বিভ্রান্তিটা module-এর একটা গুরুত্বপূর্ণ সূক্ষ্মতা প্রকাশ করে।

“একটা সংখ্যা মৌলিক কি না” — এটা decidable। একটা নির্দিষ্ট algorithm (trial division, বা AKS primality test) দেওয়া আছে যা সবসময় সঠিক উত্তর দেয়, সসীম সময়ে।

“একটা প্রদত্ত, arbitrary প্রোগ্রাম M কি সঠিকভাবে primality checking করে” — এটা সম্পূর্ণ ভিন্ন প্রশ্ন, এবং undecidable। এখানে আমরা M-এর প্রতিটা সম্ভাব্য ইনপুটের জন্য সঠিক আউটপুট নিশ্চিত করতে চাইছি — এটা একটা semantic property M-এর ভাষার উপর (L(M) = {n : n মৌলিক} কি না)। M নিজে ভুল লেখা হতে পারে হাজারো উপায়ে (off-by-one, ভুল বেস কেস, ইত্যাদি), আর “এই নির্দিষ্ট M-টা কোন ভুলগুলো করে” প্রশ্নটাই সাধারণভাবে undecidable — যদিও “সঠিক উত্তর কী” প্রশ্নটা (primality নিজে) decidable।

সাধারণ নীতি: “সমস্যাটা decidable” এবং “একটা প্রদত্ত প্রোগ্রাম সমস্যাটা সঠিকভাবে সমাধান করে কি না তা decidable” — এই দুইটা সম্পূর্ণ স্বাধীন প্রশ্ন। প্রথমটা decidable হওয়া দ্বিতীয়টার decidability সম্পর্কে কিছুই বলে না। এই কারণেই software testing (একটা প্রোগ্রাম সঠিক কি না যাচাই) মৌলিকভাবে formal verification-এর চেয়ে ভিন্ন একটা প্রচেষ্টা — এবং কেন কোনো টেস্ট স্যুট কখনো “সম্পূর্ণ প্রমাণ” দিতে পারে না, শুধু আস্থা বাড়াতে পারে।

“Rice's theorem মানে static analysis টুল লেখা অর্থহীন — যেহেতু নিখুঁত হওয়া অসম্ভব।”

সম্পূর্ণ ভুল সিদ্ধান্ত। Rice’s theorem বলে নিখুঁত (সব ক্ষেত্রে সঠিক) সমাধান অসম্ভব — এটা বলে না উপযোগী সমাধান অসম্ভব।

প্রতিদিন ব্যবহৃত হাজারো static analysis টুল (ESLint, Clippy, mypy, SpotBugs) — সবাই Rice’s theorem-এর সীমার ভেতরে থেকেই বিশাল মূল্য তৈরি করে। এরা conservative approximation ব্যবহার করে — নিশ্চিত ক্ষেত্রে সঠিক উত্তর দেয়, অনিশ্চিত ক্ষেত্রে রক্ষণশীল সিদ্ধান্ত নেয় (হয় সতর্ক করে দেয় যদিও নিশ্চিত না, অথবা চুপ থাকে যদিও ঝুঁকি আছে)।

এই লেসনের সঠিক শিক্ষা: “নিখুঁত” প্রত্যাশা করবেন না, এবং একটা টুল কিছু miss করলে সেটা বাজে ইঞ্জিনিয়ারিং এর প্রমাণ না — এটা একটা গাণিতিক অনিবার্যতার সাথে একটা যুক্তিসঙ্গত compromise। এই বোঝাপড়াটাই একজন পরিণত সফটওয়্যার ইঞ্জিনিয়ারকে একজন frustrated নতুন ইঞ্জিনিয়ার থেকে আলাদা করে — “linter কেন এটা ধরল না” প্রশ্নের উত্তর প্রায়ই “কারণ এটা গাণিতিকভাবে অসম্ভব ছিল, প্রতিটা ক্ষেত্রে একসাথে সঠিক হওয়া”, “কারণ ডেভেলপাররা অলস ছিল” না।

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

Rice’s theorem প্রয়োগ করার আগে যাচাই করার দুইটা শর্ত কী কী?

স্মরণ

১. প্রশ্নটা semantic হতে হবে — প্রোগ্রামের input-output আচরণ (L(M)) নিয়ে, প্রোগ্রামের কোড/গঠন (syntax) নিয়ে না।

২. প্রশ্নটা non-trivial হতে হবে — অন্তত একটা প্রোগ্রাম আছে যেটার জন্য উত্তর “হ্যাঁ”, আর অন্তত একটা আছে যেটার জন্য “না” (উভয় সম্ভাবনাই বাস্তবিক, শুধু একটা তুচ্ছভাবে সবসময়-সত্য বা সবসময়-মিথ্যা না)।

দুইটা শর্তই পূরণ হলে, প্রশ্নটা সরাসরি undecidable — কোনো নতুন প্রমাণ ছাড়াই।

নিচের প্রতিটা প্রশ্নের জন্য বলুন এটা decidable না undecidable — আর কেন (Rice’s theorem প্রযোজ্য কি না, প্রযোজ্য হলে কেন, না হলে কেন না):

(ক) “M-এর সোর্স কোডে কি অন্তত ৫টা variable declaration আছে?” (খ) “M কি ইনপুট হিসেবে পাওয়া প্রতিটা array সঠিকভাবে sort করে?” (গ) “M কি নিজের ইনপুটের দ্বিগুণ length-এর আউটপুট দেয়?”

প্রয়োগ

(ক) Decidable। এটা syntactic — শুধু কোড পার্স করে variable declaration গণনা করা, M চালানোর দরকার নেই। Rice’s theorem প্রযোজ্য না (semantic শর্ত পূরণ হয় না)।

(খ) Undecidable। এটা semantic (input-output আচরণ — M-এর ভাষা/ফাংশন সম্পর্কে) ✓। Non-trivial — কিছু প্রোগ্রাম সঠিক sorting algorithm (M_yes, যেমন সঠিক merge sort), কিছু না (M_no, যেমন কিছুই না করে ইনপুট ফেরত দেওয়া একটা ভুল প্রোগ্রাম) ✓। Rice’s theorem সরাসরি প্রযোজ্য — undecidable।

(গ) Undecidable। এটা semantic (আউটপুটের দৈর্ঘ্য একটা আচরণগত বৈশিষ্ট্য, input-output সম্পর্ক) ✓। Non-trivial — কিছু প্রোগ্রাম এটা করে (M_yes, যেমন input + input), কিছু না (M_no, যেমন input অপরিবর্তিত ফেরত দেওয়া) ✓। Undecidable, Rice’s theorem অনুযায়ী।

একজন সহকর্মী বলছেন: “TOTAL_TM (M কি প্রতিটা ইনপুটে থামে) undecidable প্রমাণ করতে Rice’s theorem ব্যবহার করা যায় না, কারণ Rice’s theorem শুধু L(M)-এর একটা property নিয়ে কথা বলে, আর ‘সবসময় থামা’ তো L(M)-এর property না, এটা M-এর একটা আলাদা বৈশিষ্ট্য।” এই আপত্তিটা কি সঠিক?

যুক্তি

আপত্তিটা ঠিক, কিন্তু উপসংহারটা ভুল — এবং এটা একটা গুরুত্বপূর্ণ, সূক্ষ্ম বিষয় স্পষ্ট করে।

সহকর্মী ঠিক বলেছেন যে “M সবসময় থামে” টেকনিক্যালি L(M)-এর (M যে ভাষা accept করে তার) একটা property না — এটা M-এর একটা broader আচরণগত বৈশিষ্ট্য (প্রতিটা ইনপুটে থামা, accept বা reject নির্বিশেষে)। এই লেসনের Rice’s theorem বিবৃতিটা কঠোরভাবে L(M)-এর (accepted language-এর) property নিয়ে বলা।

তবে: Rice’s theorem-এর একটা সম্প্রসারিত রূপ আছে (Rice-McNaughton-Myhill বা সাধারণভাবে “Rice’s theorem for functions/behaviors” নামে পরিচিত কিছু পাঠ্যবইয়ে) যেটা শুধু accepted language না, বরং computed partial function (M যে ইনপুট-আউটপুট সম্পর্ক গণনা করে, শুধু accept/reject না, actual output-সহ) নিয়ে একই ধরনের ফলাফল দেয়। “সবসময় থামে” এই বিস্তৃত অর্থে একটা non-trivial semantic property, আর সেই সম্প্রসারিত উপপাদ্য অনুযায়ী undecidable।

এবং, ব্যবহারিকভাবে: এমনকি এই সম্প্রসারণ ছাড়াও, TOTAL_TM আগের লেসনের কৌশলে সরাসরি HALT থেকে reduce করে undecidable প্রমাণ করা যায় (ঠিক ALL_TM-এর প্রমাণের মতো — Question 4, আগের লেসন)। তাই সহকর্মীর টেকনিক্যাল আপত্তিটা সঠিক হলেও, উপসংহার (“undecidable প্রমাণ করা যায় না”) ভুল — শুধু এই লেসনের সংকীর্ণ সংস্করণের Rice’s theorem সরাসরি প্রযোজ্য না, কিন্তু ফলাফলটা তবুও সত্য, ভিন্ন (কিন্তু কাছাকাছি) পথে প্রমাণযোগ্য।

শিক্ষা: একটা উপপাদ্যের সঠিক সীমা (scope) জানাটা গুরুত্বপূর্ণ — “এই নির্দিষ্ট উপপাদ্য প্রযোজ্য না” মানে “ফলাফলটা মিথ্যা” না, কখনো কখনো শুধু “অন্য একটা টুল দরকার” মানে।

আপনি একটা কোম্পানিতে কাজ করছেন যেখানে একজন প্রোডাক্ট ম্যানেজার দাবি করছেন: “আমাদের নতুন static analyzer-কে বলুন যেন এমন সব বাগ ধরতে পারে যেখানে একটা resource (file handle, network socket) খোলা হয় কিন্তু কখনো বন্ধ করা হয় না — এবং কোনো false positive বা false negative যেন না থাকে।” Rice’s theorem ব্যবহার করে ব্যাখ্যা করুন কেন এই চাহিদাটা নীতিগতভাবে পূরণযোগ্য না, এবং একজন engineer হিসেবে আপনি কী প্রস্তাব দেবেন।

ডিজাইন

কেন অসম্ভব: “M কি কখনো resource leak করে (খোলে কিন্তু বন্ধ করে না)” — এটা একটা semantic property (M-এর runtime আচরণ নিয়ে, কোড দেখতে কেমন তা না) ✓। Non-trivial — কিছু প্রোগ্রাম leak করে (M_yes), কিছু করে না (M_no, প্রতিটা open একটা matching close-সহ) ✓। Rice’s theorem অনুযায়ী সরাসরি undecidable।

তাই “কোনো false positive বা false negative ছাড়া” — এই দাবিটা একটা নিখুঁত decider দাবি করছে, যা Rice’s theorem অনুযায়ী থাকতেই পারে না, কোনো ইঞ্জিনিয়ারিং প্রচেষ্টা যতই ভালো হোক।

একজন engineer হিসেবে প্রস্তাব:

সঠিক প্রত্যাশা সেট করুন। ম্যানেজারকে ব্যাখ্যা করুন এটা একটা গাণিতিক সীমাবদ্ধতা (এই লেসনের প্রমাণ), প্রকৌশলগত না — কোনো টিম, কোনো বাজেট এটা এড়াতে পারবে না।
কোন trade-off নেওয়া হবে তা স্পষ্টভাবে সিদ্ধান্ত নিন। Sound (সব leak ধরবে, কিছু false positive দেবে — “সতর্ক থাকা ভালো” দর্শন) নাকি complete (যা বলবে সেটা নিশ্চিত bug, কিন্তু কিছু miss করবে — “শব্দ কম করা ভালো” দর্শন)? এটা প্রোডাক্টের context-এর উপর নির্ভর করে — একটা মেডিকেল ডিভাইস ফার্মওয়্যারে sound পছন্দনীয়, একটা দ্রুত-iteration ওয়েব অ্যাপে হয়তো complete।
Bounded/scoped বিশ্লেষণ বিবেচনা করুন। পুরো প্রোগ্রামের বদলে একটা নির্দিষ্ট call depth বা নির্দিষ্ট pattern (যেমন try-with-resources ব্যবহার না করা) পর্যন্ত সীমাবদ্ধ রাখলে, সমস্যাটা কার্যত decidable হয়ে যায় (যদিও তখন এটা আর “সাধারণ” প্রশ্ন না, একটা সংকীর্ণ, ব্যবহারিক প্রশ্ন)।
রানটাইম নিরাপত্তা জাল যোগ করুন। যেহেতু compile-time নিখুঁত গ্যারান্টি অসম্ভব, ভাষার ডিজাইন স্তরে (RAII, try-with-resources, defer, garbage-collected finalizer) leak-প্রতিরোধী প্যাটার্ন বাধ্যতামূলক করা — analysis টুলের বদলে ভাষার সিনট্যাক্সেই সমাধানের একটা অংশ সরিয়ে দেওয়া।

এরপর কী

Rice’s theorem দিয়ে আমরা এই module-এর computability-কেন্দ্রিক অংশের একটা শক্তিশালী উপসংহারে পৌঁছেছি: যেকোনো programming language-এর “কী করে” সম্পর্কিত প্রশ্ন — memory leak, null pointer, security vulnerability, সঠিকতা — এই সবগুলোই একটা একক উপপাদ্যের আওতায় undecidable, কয়েকটা ব্যতিক্রম (syntactic বা trivial প্রশ্ন) ছাড়া।

এই পর্যন্ত আমরা একটা একক প্রশ্নের চারপাশে ঘুরেছি — “সমাধানযোগ্য কি না” (decidability, একটা বাইনারি প্রশ্ন)। কিন্তু বাস্তবে আরেকটা, সমান গুরুত্বপূর্ণ প্রশ্ন আছে যেটা আমরা এখনো স্পর্শ করিনি — যেসব সমস্যা সমাধানযোগ্য, তাদের মধ্যে কোনগুলো দ্রুত সমাধানযোগ্য, আর কোনগুলো (বিশ্বাস করা হয়) মৌলিকভাবে ধীর? এই প্রশ্নটাই পরের লেসনগুলোতে complexity classes — P, NP, আর তাদের বিখ্যাত এখনো-অমীমাংসিত সম্পর্ক — নিয়ে আসবে। আর আশ্চর্যজনকভাবে, সেই আলোচনার কেন্দ্রীয় প্রমাণ-কৌশলটাও reduction — এই module-এর আগের লেসনে শেখা সেই একই ধারণা, শুধু “computable” শব্দের জায়গায় “polynomial-time computable” বসিয়ে।

Rice's Theorem — একটা বাক্য যা ডজন ডজন প্রমাণকে অপ্রয়োজনীয় করে দেয়

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

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

আগে এটা বুঝি

মূল ধারণা

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

“Property of the language” — semantic, syntactic না

“Non-trivial” — শুধু দুইটা তুচ্ছ ক্ষেত্র বাদ

ভেতরে কী ঘটছে

প্রমাণ — আগের লেসনের টেমপ্লেটের একটা সাধারণীকরণ

উদাহরণ

দ্রুত প্রয়োগ — চারটা নতুন প্রশ্ন, প্রতিটার উত্তর তাৎক্ষণিক

নিজে বানান

একটা Rice's theorem checklist টুল — যেকোনো প্রশ্ন classify করুন

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

Sound বনাম complete — static analysis-এর মৌলিক trade-off

Security module-এর সাথে সরাসরি সংযোগ

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

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

এরপর কী

আরও পড়ুন

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

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

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

◆মূল ধারণাCore concept

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

“Property of the language” — semantic, syntactic না

“Non-trivial” — শুধু দুইটা তুচ্ছ ক্ষেত্র বাদ

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

প্রমাণ — আগের লেসনের টেমপ্লেটের একটা সাধারণীকরণ

▶উদাহরণExample

দ্রুত প্রয়োগ — চারটা নতুন প্রশ্ন, প্রতিটার উত্তর তাৎক্ষণিক

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

একটা Rice's theorem checklist টুল — যেকোনো প্রশ্ন classify করুন

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

Sound বনাম complete — static analysis-এর মৌলিক trade-off

Security module-এর সাথে সরাসরি সংযোগ

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

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

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে বানান

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

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

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

এরপর কী