Rice's Theorem
রাইসের উপপাদ্য
একটা প্রোগ্রামের semantic (input-output আচরণ সম্পর্কিত) যেকোনো non-trivial property-ই undecidable — শুধু syntactic (কোড দেখতে কেমন) বা trivial (সবসময় হ্যাঁ/না) প্রশ্ন বাদে। ডজন ডজন পৃথক undecidability প্রমাণকে একটা বাক্যে সংক্ষিপ্ত করে।
also: Rice theorem, Rice's theorem
প্রয়োগের চেকলিস্ট: প্রশ্নটা (১) semantic (আচরণ নিয়ে, কোড-গঠন নিয়ে না) এবং (২) non-trivial (অন্তত একটা প্রোগ্রাম “হ্যাঁ”, অন্তত একটা “না”) হলেই সরাসরি undecidable — কোনো নতুন প্রমাণ ছাড়াই।
প্রমাণ আগের লেসনের reduction টেমপ্লেটের সাধারণীকরণ — HALT-এর
instance ⟨M, w⟩-কে এমন M'-এ রূপান্তর করা যা M থামলে
property-satisfying আচরণ দেখায়, না থামলে না।
সরাসরি বাস্তব পরিণতি — sound-vs-complete trade-off: কোনো static analysis টুল (linter, type checker, malware detector) একসাথে সব সমস্যা ধরতে (sound) এবং কখনো false positive না দিতে (complete) পারে না। “M কি null রিটার্ন করে”, “M কি resource leak করে” — সবই এই তালিকায়।