এই পর্বে যা শিখবেন
- গণনার তত্ত্বের তিন মূল প্রশ্ন আর তিন স্তম্ভ, একই সমস্যাকে তিন দৃষ্টিতে দেখা
- একটি ছোট DFA চালানো, তার সঠিকতা প্রমাণ করা আর brute force দিয়ে যাচাই করা
- “এটা করা অসম্ভব” কীভাবে প্রমাণ করা হয়: pigeonhole যুক্তি আর halting problem-এর রূপরেখা
- Regex, parser, compiler, protocol আর cryptography-তে এই তত্ত্বের ভূমিকা
- ১৯২৮ থেকে ১৯৭০-এর দশকের ইতিহাস, ১৪ মডিউলের মানচিত্র আর আপনার জন্য সঠিক পথ
১ · গণনার তত্ত্ব কোন প্রশ্ন করে
“বাজারঘর” নামের একটি কাল্পনিক অনলাইন দোকানের কথা ভাবুন। এই কোর্সজুড়ে বাজারঘর আমাদের সঙ্গী থাকবে। দোকানের প্রোগ্রামারদের সামনে প্রতিদিন নানা রকম প্রশ্ন আসে:
- গ্রাহক যে অর্ডার-কোড লিখলেন (যেমন
BG-0042), সেটি কি সঠিক format-এ আছে? - অর্ডার খোঁজার ছোট query ভাষায় প্রতিটি খোলা বন্ধনীর কি একটি করে বন্ধ বন্ধনী আছে?
- ৩০টি ঠিকানায় মাল পৌঁছাতে সবচেয়ে ছোট রুট কোনটি?
- নতুন লেখা একটি validator প্রোগ্রাম কি যেকোনো input-এ একসময় থামবে, নাকি কোনো input-এ চিরকাল ঘুরতে থাকবে?
চারটি প্রশ্নই শুনতে সাধারণ প্রোগ্রামিংয়ের কাজ। কিন্তু এদের ভেতরের চরিত্র একেবারে আলাদা। প্রথমটি খুব ছোট একটি যন্ত্র দিয়েই হয়, যার স্মৃতি কয়েকটি অবস্থার বেশি নয়। দ্বিতীয়টির জন্য গুনতে পারে এমন স্মৃতি লাগে। তৃতীয়টির উত্তর আছে, কিন্তু জানা কোনো পদ্ধতিই সব ক্ষেত্রে দ্রুত নয়। আর চতুর্থটির ক্ষেত্রে প্রমাণ করা যায়: সব প্রোগ্রামের জন্য সঠিক উত্তর দিতে পারে এমন কোনো algorithm নেই, কখনো হবেও না।
এই পার্থক্যগুলো বোঝার বিজ্ঞানই Theory of Computation, বাংলায় গণনার তত্ত্ব। এর তিনটি মূল প্রশ্ন:
রেলস্টেশনের টিকিট কাউন্টারের কথা ভাবুন। একজন কর্মী যদি শুধু মনে রাখতে পারেন “এখন কাউন্টার খোলা না বন্ধ”, তিনি কিছু কাজ পারবেন, কিন্তু লাইনে কতজন দাঁড়িয়ে আছেন তা গুনতে পারবেন না। খাতা-কলম দিলে গুনতে পারবেন। কিন্তু খাতা-কলম থাকলেও কিছু প্রশ্নের উত্তর তিনি কখনো দিতে পারবেন না, আর কিছু প্রশ্নে উত্তর দিতে এত সময় লাগবে যে ট্রেন ছেড়ে যাবে। গণনার তত্ত্ব ঠিক এই তিনটি সীমা মাপে: স্মৃতির সীমা, সম্ভবের সীমা আর সময়ের সীমা।
এখানে “গণনা” মানে শুধু যোগ-গুণ নয়। যেকোনো যান্ত্রিক, ধাপে ধাপে, নিয়মমাফিক তথ্য-প্রক্রিয়াকেই গণনা বলা হয়: একটি string পড়ে হ্যাঁ বা না বলা, একটি প্রোগ্রাম অনুবাদ করা, একটি রুট খোঁজা। আর গণনার তত্ত্ব কোনো নির্দিষ্ট ভাষা, CPU বা কম্পিউটার নিয়ে কথা বলে না। এটি কথা বলে গাণিতিক মডেল নিয়ে, যাতে প্রমাণ করা ফল আজকের ল্যাপটপে যেমন সত্য, পঞ্চাশ বছর পরের কম্পিউটারেও তেমনি সত্য থাকে।
এই কোর্সের প্রায় প্রতিটি প্রশ্নকে একটি হ্যাঁ/না প্রশ্নে বদলানো হবে: “এই string কি এই নিয়ম মানে?” যে string-গুলোর উত্তর “হ্যাঁ”, তাদের সেটকে বলে একটি language. তাই “সমস্যা সমাধান করা” মানে দাঁড়ায় “একটি language-এর সদস্যপদ নির্ণয় করা”। এই সেতুটি পর্ব ০৫ (সমস্যাকে language হিসেবে দেখা)-এ পুরোপুরি গড়ে তোলা হবে।
২ · তিন স্তম্ভ: automaton, computability আর complexity
গণনার তত্ত্বকে তিনটি বড় শাখায় ভাগ করা হয়। তিনটি শাখা একই প্রশ্নকে তিনটি আলাদা চশমায় দেখে।
⚙️ Automaton ও language
সীমিত স্মৃতির যন্ত্র কোন language চিনতে পারে? Finite automaton, regular expression, grammar, pushdown automaton. Regex আর parser-এর তত্ত্ব এখানেই।
মডিউল ২–৭🚫 Computability
কোনো algorithm-ই কি সমস্যাটি সমাধান করতে পারে? Turing machine, decidable আর undecidable সমস্যা, halting problem, reduction.
মডিউল ৮–৯⏳ Complexity
সমাধান করা গেলে কত সময় আর কত জায়গা লাগে? P, NP, NP-complete, PSPACE, randomized আর quantum complexity.
মডিউল ১০–১২প্রথম স্তম্ভ যন্ত্রকে দুর্বল রেখে দেখে সে কী পারে। দ্বিতীয় স্তম্ভ যন্ত্রকে সবচেয়ে শক্তিশালী করে দেখে, তবুও কী পারে না। তৃতীয় স্তম্ভ শক্তিশালী যন্ত্রকে সময় ও স্মৃতির বাজেট দেয়, তারপর দেখে বাজেটের ভেতরে কী পারে। নিচের stepper বাজারঘরের তিনটি প্রশ্নকে এই তিন চশমায় দেখে। “পরে” চাপুন।
| প্রশ্ন | |
| algorithm আছে? | |
| সসীম স্মৃতিতে? | |
| কত দ্রুত? |
- প্রশ্ন ১, প্রথম চশমা। অর্ডার-কোড কি “BG-” আর তারপর ঠিক ৪টি অঙ্ক? কোনো algorithm আছে কি না জিজ্ঞেস করলে উত্তর স্পষ্ট: হ্যাঁ, অক্ষরগুলো একে একে মিলিয়ে দেখলেই হয়।
- প্রশ্ন ১, বাকি দুই চশমা। কাজটি সসীম স্মৃতিতেই হয়: “এ পর্যন্ত কয়টি অক্ষর ঠিক মিলেছে” (০ থেকে ৭) আর একটি “বাতিল” অবস্থা, মোট ৯টি state. প্রতিটি অক্ষরে একবার তাকানো, তাই n দৈর্ঘ্যের input-এ n ধাপ। এটি একটি regular language.
- প্রশ্ন ২, প্রথম চশমা। Query-র বন্ধনী সুষম কি না, তা বলার algorithm সহজ: একটি counter রাখুন, “(” পেলে বাড়ান, “)” পেলে কমান, কখনো শূন্যের নিচে না নামলে আর শেষে শূন্য হলে সুষম।
- প্রশ্ন ২, বাকি দুই চশমা। সময় এখনো n ধাপ, কিন্তু counter যত বড় হতে পারে তার কোনো সীমা নেই। অংশ ৪-এ প্রমাণ করা হবে: কোনো সসীম যন্ত্র এটি পারে না। লাগে stack, অর্থাৎ pushdown automaton.
- প্রশ্ন ৩। “B কিমি-র মধ্যে সব ঠিকানা ঘুরে আসার রুট আছে কি?” Algorithm আছে: সব ক্রম পরীক্ষা করা। কিন্তু n ঠিকানায় ক্রম n!-টি। আজ পর্যন্ত জানা কোনো algorithm সব ক্ষেত্রে polynomial সময়ে চলে না; দ্রুত algorithm আছে কি না, সেটিই P বনাম NP প্রশ্নের অংশ।
- প্রশ্ন ৪। “যেকোনো validator প্রোগ্রাম সব input-এ থামবে কি?” এখানে প্রথম চশমাতেই উত্তর “না”: এমন কোনো algorithm নেই যা সব প্রোগ্রামের জন্য সঠিক উত্তর দেয়। গতি বা স্মৃতির প্রশ্ন তাই আর ওঠেই না। এটিই halting problem-এর পরিবার।
খেয়াল করুন, চশমাগুলো একটি ক্রমে কাজ করে। আগে computability জিজ্ঞেস করে “আদৌ সম্ভব?”; সম্ভব হলে automaton-তত্ত্ব জিজ্ঞেস করে “কতটা দুর্বল যন্ত্রেই সম্ভব?”; আর complexity জিজ্ঞেস করে “কত খরচে?” একজন অভিজ্ঞ প্রোগ্রামার নতুন সমস্যা দেখলে মনে মনে এই তিনটি প্রশ্নই করেন, যদিও প্রায়ই নাম ধরে নয়।
৩ · প্রথম যন্ত্র: সসীম স্মৃতির state machine
অফিস ভবনের লিফটের কথা ভাবুন। লিফট পুরো দিনের ইতিহাস মনে রাখে না; সে শুধু জানে “আমি এখন কোন তলায়”। এই “এখনকার অবস্থা”-কেই বলে state. বাজারঘরের ছোট গুদাম-ভবনে তিনটি তলা: G (নিচতলা), 1 আর 2. বোতাম দুটি: U (ওপরে) আর D (নিচে)। সবচেয়ে ওপরের তলায় U চাপলে কিছু হয় না, নিচতলায় D চাপলেও না। অফিসঘর 1 তলায়, তাই প্রশ্ন: বোতাম-চাপার একটি ক্রম শেষে লিফট কি 1 তলায় থামে?
1q = G (start)2read U: G → 13read U: 1 → 24read U: 2 → 2 (top)5read D: 2 → 16q = 1 ∈ F → accept
| পড়া অংশ | |
| বাকি অংশ | |
| state (তলা) |
- শুরু। লিফট নিচতলা G-তে, কোনো বোতাম পড়া হয়নি। পড়া অংশ ফাঁকা string ε। যন্ত্রের পুরো “স্মৃতি” এই একটি তথ্য: এখন G.
- U পড়ল। নিয়ম: G-তে U মানে 1. যন্ত্র আগের কিছু মনে রাখে না, শুধু নতুন state 1.
- আবার U. 1-এ U মানে 2. এখন লিফট সবচেয়ে ওপরের তলায়।
- তৃতীয় U. 2-এ U চাপলে লিফট নড়ে না: state 2-ই থাকে। নিয়মের টেবিলে এই ঘরটিও লেখা আছে; প্রতিটি state আর প্রতিটি বোতামের জন্য ঠিক একটি করে পরের state.
- D পড়ল। 2-এ D মানে 1. পুরো input পড়া শেষ।
- সিদ্ধান্ত। শেষ state 1, যা গ্রহণযোগ্য state-এর সেট F = {1}-এর সদস্য। তাই যন্ত্র UUUD গ্রহণ করে। “UU” দিলে শেষ state 2 হতো, আর যন্ত্র বাতিল করত।
এই লিফটই একটি finite automaton: সসীম সংখ্যক state, একটি শুরুর state, কিছু গ্রহণযোগ্য state, আর প্রতিটি (state, চিহ্ন) জোড়ার জন্য ঠিক একটি পরের state. শেষ শর্তটির জন্য একে বলে DFA (deterministic finite automaton). এবার বাজারঘরের একটি সেন্সর-লাইনের উদাহরণ নিই। লাইনটি 0 আর 1 পাঠায়, আর একটি সাধারণ parity check চায় যে 1-এর সংখ্যা জোড় হোক। দুটি state যথেষ্ট: E (এ পর্যন্ত জোড় সংখ্যক 1) আর O (বিজোড়)।
“1-এর সংখ্যা জোড়”-এর DFA
বৃত্ত = state, তীর = transition, তীরের গায়ের চিহ্ন পড়লে সেই তীর ধরে যেতে হয়। বাঁ দিকের খোলা তীর শুরুর state, দুই দাগের বৃত্ত গ্রহণযোগ্য state.
এখানে কয়েকটি শব্দ এই কোর্সজুড়ে একই অর্থে চলবে। Alphabet Σ হলো চিহ্নের একটি সসীম, অশূন্য সেট; এখানে Σ = {0, 1}। String হলো Σ-এর চিহ্নের সসীম ক্রম, যেমন 0110. কোনো চিহ্ন নেই এমন string-কে বলে ফাঁকা string, এর চিহ্ন ε (কিছু বই λ লেখে; এই কোর্সে সবসময় ε)। Σ∗ মানে Σ-এর ওপর সব string-এর সেট, ε-সহ। আর language হলো Σ∗-এর যেকোনো উপসেট, L ⊆ Σ∗। এসবের পূর্ণ নিয়ম পর্ব ০৩-এ। DFA-কে গাণিতিকভাবে একটি ৫-tuple হিসেবে লেখা হয়:
Q হলো state-এর সসীম সেট, এখানে {E, O}; Σ alphabet; δ: Q × Σ → Q হলো transition function, অর্থাৎ নিয়মের টেবিল; q0 = E শুরুর state; আর F = {E} গ্রহণযোগ্য state-এর সেট। δ-কে একটি string-এর ওপর বাড়িয়ে লেখা হয় δ̂ (কিছু বইয়ে δ∗): δ̂(q, ε) = q, আর δ̂(q, wa) = δ(δ̂(q, w), a). অর্থাৎ w পড়ে যেখানে পৌঁছালেন, সেখান থেকে শেষ চিহ্ন a পড়ে এক ধাপ। M একটি string w গ্রহণ করে ঠিক তখন, যখন δ̂(q0, w) ∈ F. পূর্ণ সংজ্ঞা আর অনেক উদাহরণ পর্ব ০৭ (DFA — formal definition)-এ।
| δ | 0 | 1 |
|---|---|---|
| → ∗E (শুরু, গ্রহণযোগ্য) | E | O |
| O | O | E |
যন্ত্রটি যে ঠিক কাজ করে, তার প্রমাণ
কয়েকটি string-এ চালিয়ে “ঠিক আছে” বলা প্রমাণ নয়; অসীম সংখ্যক string-এর প্রত্যেকটির জন্য দাবিটি দেখাতে হবে। এখানে কাজে লাগে string-এর দৈর্ঘ্যের ওপর induction. #1(w) দিয়ে বোঝাই w-তে 1-এর সংখ্যা। (Induction-এর মূল ধারণা ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১০-এ আছে।)
সব w ∈ {0, 1}∗-এর জন্য: δ̂(E, w) = E যদি #1(w) জোড় হয়, আর δ̂(E, w) = O যদি #1(w) বিজোড় হয়। ফলে M ঠিক সেই string-গুলো গ্রহণ করে, যাদের 1-এর সংখ্যা জোড়।
- ভিত্তি: |w| = 0, অর্থাৎ w = ε। δ̂(E, ε) = E, আর #1(ε) = 0, যা জোড়। দাবি সত্য। — δ̂-এর সংজ্ঞা
- আরোহ-অনুমান: ধরি দৈর্ঘ্য k-এর প্রতিটি string w-এর জন্য দাবি সত্য। — |w|-এর ওপর induction
- ধাপ: দৈর্ঘ্য k + 1-এর যেকোনো string-কে লেখা যায় wa, যেখানে |w| = k আর a ∈ {0, 1}। সংজ্ঞায় δ̂(E, wa) = δ(δ̂(E, w), a). — δ̂-এর সংজ্ঞা
- a = 0 হলে #1(wa) = #1(w), parity বদলায় না; আর টেবিলে δ(E, 0) = E, δ(O, 0) = O, state-ও বদলায় না। — আরোহ-অনুমান আর টেবিল
- a = 1 হলে #1(wa) = #1(w) + 1, parity উল্টে যায়; আর δ(E, 1) = O, δ(O, 1) = E, state-ও উল্টে যায়। — আরোহ-অনুমান আর টেবিল
- দুই ক্ষেত্রেই দৈর্ঘ্য k + 1-এ দাবি সত্য। যেহেতু F = {E}, M গ্রহণ করে ঠিক তখন যখন #1(w) জোড়। ∎
এই প্রমাণের ধাঁচটি মনে রাখুন: “প্রতিটি state একটি বক্তব্য বহন করে, আর প্রতিটি transition সেই বক্তব্য রক্ষা করে।” কোর্সের প্রায় প্রতিটি automaton-এর সঠিকতা এভাবেই প্রমাণ হবে। এবার যন্ত্রটি নিজে চালিয়ে দেখুন। নিচের JavaScript ব্লক দুটি DFA চালায়: parity DFA আর বাজারঘরের অর্ডার-কোড DFA (“BG-” আর ঠিক ৪টি অঙ্ক)। Test string-এর তালিকা বদলে আবার “চালান” চাপলে আপনার নিজের string-ও পরীক্ষা হবে।
// A tiny DFA runner. Edit the test strings and press Run again.
function run(dfa, w) {
let q = dfa.start, path = [q];
for (const ch of w) {
q = dfa.delta(q, ch); // exactly one next state
path.push(q);
}
const ok = dfa.accept.has(q);
console.log(JSON.stringify(w).padEnd(11) + (ok ? "ACCEPT " : "reject ") + path.join(">"));
}
// 1) Sensor line: accept when the number of 1s is even
const parity = {
start: "E", accept: new Set(["E"]),
delta: (q, ch) => ch === "1" ? (q === "E" ? "O" : "E") : q
};
// 2) Order code: "BG-" followed by exactly 4 digits
const pattern = "BG-dddd"; // d = any digit 0-9
const order = {
start: 0, accept: new Set([7]),
delta: (q, ch) => {
if (q === "X" || q === 7) return "X"; // X = dead state
const need = pattern[q];
const fits = need === "d" ? ch >= "0" && ch <= "9" : ch === need;
return fits ? q + 1 : "X";
}
};
console.log("-- parity DFA (states E, O) --");
for (const w of ["", "1", "1011", "0110"]) run(parity, w);
console.log("-- order-code DFA (states 0..7, X) --");
for (const w of ["BG-0042", "BG-42", "bg-0042", "BG-00421"]) run(order, w);আসল আউটপুট (ব্রাউজারের JavaScript):
-- parity DFA (states E, O) --
"" ACCEPT E
"1" reject E>O
"1011" reject E>O>O>E>O
"0110" ACCEPT E>E>O>E>E
-- order-code DFA (states 0..7, X) --
"BG-0042" ACCEPT 0>1>2>3>4>5>6>7
"BG-42" reject 0>1>2>3>4>5
"bg-0042" reject 0>X>X>X>X>X>X>X
"BG-00421" reject 0>1>2>3>4>5>6>7>X
প্রতিটি লাইনে পুরো state-পথ দেখা যাচ্ছে। ফাঁকা string-ও গৃহীত, কারণ শূন্যটি 1 জোড় সংখ্যা; AI-এর বানানো DFA প্রায়ই এই ক্ষেত্রটি ভুল করে। অর্ডার-কোডের যন্ত্রে X হলো dead state: একবার ঢুকলে আর বের হওয়া যায় না, আর সেটি গ্রহণযোগ্য নয়। ছোট হাতের “bg” প্রথম চিহ্নেই X-এ যায়; “BG-42” পাঁচ চিহ্নে state 5-এ থেমে যায়, ৭-এ পৌঁছায় না; আর “BG-00421”-এর বাড়তি অঙ্ক state 7 থেকেও X-এ ঠেলে দেয়।
প্রমাণ সব দৈর্ঘ্যের জন্য, কিন্তু প্রমাণ লিখতে গিয়েও ভুল হয়। তাই এই কোর্সের দ্বিতীয় অভ্যাস: ছোট সব ক্ষেত্রে brute force. নিচের Python ব্লক দৈর্ঘ্য 0 থেকে 4-এর সব binary string shortlex ক্রমে (আগে দৈর্ঘ্য, তারপর অভিধানের ক্রম) তৈরি করে, DFA-তে চালায় আর সংজ্ঞার সঙ্গে মেলায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।
from itertools import product
# parity DFA: state E = "even number of 1s so far", O = "odd"
DELTA = {("E", "0"): "E", ("E", "1"): "O",
("O", "0"): "O", ("O", "1"): "E"}
def accepts(w):
q = "E"
for ch in w:
q = DELTA[q, ch]
return q == "E"
N = 4
accepted, mismatches = [], 0
for n in range(N + 1): # shortlex: by length, then 0 < 1
for t in product("01", repeat=n):
w = "".join(t)
if accepts(w):
accepted.append(w if w else "ε")
mismatches += accepts(w) != (w.count("1") % 2 == 0)
print("accepted up to length", N, ":", len(accepted), "strings")
print(" ".join(accepted))
for n in range(N + 1):
k = sum(accepts("".join(t)) for t in product("01", repeat=n))
print("length", n, ": accepted", k, "of", 2 ** n)
print("disagreements with 'count of 1s is even':", mismatches)আসল আউটপুট (ব্রাউজারের Python):
accepted up to length 4 : 16 strings
ε 0 00 11 000 011 101 110 0000 0011 0101 0110 1001 1010 1100 1111
length 0 : accepted 1 of 1
length 1 : accepted 1 of 2
length 2 : accepted 2 of 4
length 3 : accepted 4 of 8
length 4 : accepted 8 of 16
disagreements with 'count of 1s is even': 0
দৈর্ঘ্য 4 পর্যন্ত মোট 31টি string-এর 16টি গৃহীত, আর সংজ্ঞার সঙ্গে একটিও অমিল নেই। গণনা থেকে একটি নতুন দাবিও চোখে পড়ে: n ≥ 1 হলে দৈর্ঘ্য n-এর ঠিক 2n−1টি string গৃহীত, অর্থাৎ ঠিক অর্ধেক। কারণ প্রথম n − 1টি বিট যা-ই হোক, শেষ বিটের দুই বিকল্পের ঠিক একটি parity জোড় করে। লক্ষ করুন: গণনা দাবিটি দেখায়, আর এক লাইনের এই যুক্তি তা প্রমাণ করে। এই কোর্সে দুটোই করা হবে।
৪ · “এটা অসম্ভব” কীভাবে প্রমাণ করা হয়
প্রোগ্রামিংয়ে আমরা সাধারণত দেখাই কোনো কিছু করা যায়: একটি প্রোগ্রাম লিখে চালিয়ে দিই। গণনার তত্ত্বের সবচেয়ে চমকপ্রদ দিক উল্টোটা: এটি প্রমাণ করে কোনো কিছু করা যায় না, কোনো যন্ত্রেই, কোনো চতুর কৌশলেই। এমন প্রমাণ “আমি চেষ্টা করে পারিনি” নয়; এটি এমন যুক্তি, যা ভবিষ্যতের সব চেষ্টাকেও বাতিল করে দেয়।
সীমা ১: সসীম স্মৃতি সুষম বন্ধনী চেনে না
বাজারঘরের query ভাষায় বন্ধনী থাকে, যেমন (price>500) বা ((a)(b)). শুধু বন্ধনীগুলো রাখলে প্রশ্নটি দাঁড়ায় Σ = {(, )}-এর ওপর language BAL: যে string-এ পড়ার সময় কখনো “)” বেশি হয়ে যায় না আর শেষে দুটির সংখ্যা সমান। BAL একটি context-free language. নিচের উপপাদ্যটি বলে কোনো DFA এটি চিনতে পারে না, অর্থাৎ BAL কোনো regular language নয়।
এমন কোনো DFA নেই, যার language ঠিক BAL.
- বিরোধের জন্য ধরি কোনো DFA M-এর language ঠিক BAL, আর M-এর state k-টি। — প্রমাণ by contradiction
- k + 1টি string নিই: (0, (1, …, (k, যেখানে (i মানে পরপর i-টি “(”। M এদের প্রত্যেকটি পড়ে কোনো একটি state-এ পৌঁছায়। — DFA-র প্রতিটি string-এ একটিই শেষ state
- string k + 1টি, state k-টি; তাই কোনো i < j-এর জন্য (i আর (j একই state q-তে পৌঁছায়। — pigeonhole principle
- এবার দুটির পরেই একই string )i পড়ি। দুজনেই q থেকে একই চিহ্ন পড়ছে, তাই (i)i আর (j)i একই শেষ state-এ পৌঁছায়, আর M দুটির ব্যাপারে একই সিদ্ধান্ত দেয়। — δ̂(q, )i) শুধু q আর )i-এর ওপর নির্ভর করে
- কিন্তু (i)i ∈ BAL, আর i < j বলে (j)i-তে “(” বেশি, তাই (j)i ∉ BAL. M একটি গ্রহণ আর অন্যটি বাতিল করার কথা, অথচ দুটির সিদ্ধান্ত একই। বিরোধ। ∎
নিচের stepper k = 3 নিয়ে যুক্তিটি সংখ্যা বসিয়ে দেখায়। ধরে নেওয়া হয়েছে pigeonhole যে জোড়াটি দিয়েছে তা i = 1, j = 3; অন্য যেকোনো জোড়াতেও যুক্তি হুবহু এক।
| string-গুলো | |
| state | |
| সিদ্ধান্ত |
- ধরে নেওয়া। কেউ দাবি করলেন, 3 state-এর একটি DFA M ঠিক BAL চেনে। M-এর ভেতরে কী আছে আমরা জানি না, জানার দরকারও নেই।
- চারটি string. ε, (, ((, (((: k + 1 = 4টি string. প্রত্যেকটি পড়ে M তিনটি state-এর কোনো একটিতে থামে। চারটি কবুতর, তিনটি খোপ।
- একই খোপ। Pigeonhole বলে অন্তত দুটি string একই state-এ থামে। ধরুন সেগুলো “(” আর “(((”, দুটিই state q-তে।
- একই লেজ জোড়া। দুটির পরে একই “)” পড়ি। DFA-র পরের পথ শুধু বর্তমান state আর বাকি input-এর ওপর নির্ভর করে, অতীতের ওপর নয়। দুজনেই q-তে, দুজনেই “)” পড়ছে, তাই দুজনের শেষ state একই।
- বিরোধ। “()” সুষম, তাই M-কে গ্রহণ করতে হবে; “((()” সুষম নয়, তাই বাতিল করতে হবে। কিন্তু দুটির শেষ state একই, সিদ্ধান্তও একই। M দাবি অনুযায়ী কাজ করতে পারে না। k যত বড়ই হোক, k + 1টি string নিয়ে একই যুক্তি চলে।
এই যুক্তির সাধারণ রূপ পরে দুটি বড় হাতিয়ার হবে: পর্ব ১৭-এর pumping lemma আর পর্ব ১৮-এর Myhill–Nerode theorem. প্রমাণটি হাতে-কলমেও দেখা যায়। ধরুন কেউ (বা কোনো AI) একটি “সমাধান” দিলেন: একটি counter থাকবে, কিন্তু counter 3-এর বেশি উঠবে না, কারণ DFA-র state সসীম রাখতে হবে। নিচের ব্লক shortlex ক্রমে সব string খুঁজে প্রথম যে string-এ এই যন্ত্র ভুল করে সেটি বের করে।
from itertools import product
def balanced(w): # the true definition, with an unbounded counter
depth = 0
for ch in w:
depth += 1 if ch == "(" else -1
if depth < 0:
return False
return depth == 0
def capped_dfa(w, cap=3): # a 5-state "DFA": counter 0..cap plus dead
q = 0
for ch in w:
if q == "dead":
break
if ch == "(":
q = min(q + 1, cap) # cannot count beyond cap
else:
q = q - 1 if q > 0 else "dead"
return q == 0
for n in range(11): # shortlex search for a counterexample
bad = [w for w in map("".join, product("()", repeat=n))
if capped_dfa(w) != balanced(w)]
if bad:
print("first disagreement at length", n, ":", bad[0])
print(" DFA says", capped_dfa(bad[0]), "| truth says", balanced(bad[0]))
print(" all disagreements of this length:", bad)
break
w = "(((())))"
print(w, "DFA:", capped_dfa(w), "truth:", balanced(w))আসল আউটপুট (ব্রাউজারের Python):
first disagreement at length 7 : (((()))
DFA says True | truth says False
all disagreements of this length: ['(((()))']
(((()))) DFA: False truth: True
দৈর্ঘ্য 6 পর্যন্ত যন্ত্রটি নিখুঁত, তাই হাতে কয়েকটি উদাহরণ চালিয়ে কেউ সন্তুষ্ট হয়ে যেতে পারেন। দৈর্ঘ্য 7-এ প্রথম ভুল: “(((()))”-তে চারটি “(” কিন্তু তিনটি “)”, তবুও যন্ত্র গ্রহণ করে, কারণ চতুর্থ “(” গোনা হয়নি। আর সুষম “(((())))” সে বাতিল করে। Cap 3-এর বদলে 1000 দিলেও ভুল থাকবে, শুধু আরও লম্বা string-এ; উপপাদ্য ১.২ ঠিক এটাই বলে। কোনো counterexample খুঁজে পাওয়া মানে দাবিটি ভুল; কিন্তু counterexample না পাওয়া মানেই দাবিটি সত্য, তা নয়; সেজন্য প্রমাণ লাগে।
সীমা ২: কোনো প্রোগ্রামই সব প্রোগ্রামের থামা বলতে পারে না
DFA দুর্বল যন্ত্র; তার সীমা থাকা অবাক করার মতো নয়। আসল চমক হলো সবচেয়ে শক্তিশালী মডেল Turing machine-এরও সীমা আছে, যে মডেল আমাদের যেকোনো কম্পিউটার আর যেকোনো প্রোগ্রামিং ভাষার সমান শক্তিশালী বলে ধরা হয়। এর সবচেয়ে বিখ্যাত উদাহরণ halting problem: একটি প্রোগ্রাম P আর input x দেখে বলা, P(x) কখনো থামবে কি না।
প্রমাণের রূপরেখা (পূর্ণ প্রমাণ পর্ব ৫১-এ): ধরি এমন একটি প্রোগ্রাম H আছে, যা যেকোনো (P, x)-এ থেমে সঠিক বলে “P(x) থামে” বা “থামে না”। এবার H ব্যবহার করে একটি প্রোগ্রাম D লিখি: D একটি প্রোগ্রাম P নেয়, H-কে জিজ্ঞেস করে “P নিজের কোডকে input হিসেবে পেলে থামবে?” H “থামবে” বললে D ইচ্ছা করে চিরকাল ঘোরে; H “থামবে না” বললে D সঙ্গে সঙ্গে থামে। এবার D-কে তার নিজের কোড দিন। D(D) থামলে H বলেছিল “থামবে”, তাই D ঘুরতে থাকে, বিরোধ; D(D) না থামলে H বলেছিল “থামবে না”, তাই D থামে, আবারও বিরোধ। তাই H থাকতে পারে না। এই “নিজের ওপর প্রয়োগ” কৌশলের নাম diagonalization, Cantor-এর যুক্তি থেকে আসা (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১৮)।
বাজারঘরের চতুর্থ প্রশ্নের উত্তর তাই: কোনো সাধারণ tool সব validator-এর জন্য “এটি সবসময় থামবে” সঠিকভাবে বলতে পারবে না। তার মানে এই নয় যে কোনো প্রোগ্রাম নিয়েই কিছু বলা যায় না। নির্দিষ্ট প্রোগ্রামে, বা “হয়তো জানি না” উত্তর দেওয়ার অনুমতি থাকলে, বাস্তব tool অনেক কাজের কথা বলে। পর্ব ৫৫ (বাস্তবে undecidability) আর পর্ব ৭৮ (program analysis-এর সীমা) এই সূক্ষ্ম পার্থক্যটি দেখাবে। যে language-এর জন্য সব input-এ থেমে সঠিক উত্তর দেওয়া যন্ত্র আছে, তাকে বলে decidable; halting problem decidable নয়, অর্থাৎ এটি undecidable.
৫ · সম্ভব, কিন্তু কত দ্রুত? Complexity আর P বনাম NP
বাজারঘরের তৃতীয় প্রশ্নে ফিরি। গুদাম থেকে বের হয়ে কয়েকটি ঠিকানায় মাল দিয়ে আবার গুদামে ফেরার সবচেয়ে ছোট রুট কোনটি? এটি বিখ্যাত traveling salesperson problem (TSP)-এর একটি রূপ। এর হ্যাঁ/না রূপ, অর্থাৎ decision problem: “B কিমি-র মধ্যে সব ঠিকানা ঘোরার রুট আছে কি?” Algorithm খুঁজে পাওয়া কঠিন নয়: সব ক্রম পরীক্ষা করুন। নিচের ব্লক ঠিক তাই করে ৭টি ঠিকানার জন্য, তারপর দেখায় ধাপের সংখ্যা কীভাবে বাড়ে।
import random
from itertools import permutations
from math import factorial
random.seed(7) # same "map" on every run
n = 7 # delivery stops; 0 is the warehouse
pts = [(random.randint(0, 20), random.randint(0, 20)) for _ in range(n + 1)]
def d(a, b): # Manhattan distance, like city blocks
return abs(pts[a][0] - pts[b][0]) + abs(pts[a][1] - pts[b][1])
best, best_route, checked = None, None, 0
for route in permutations(range(1, n + 1)): # try EVERY order of the stops
stops = (0,) + route + (0,)
cost = sum(d(stops[i], stops[i + 1]) for i in range(len(stops) - 1))
checked += 1
if best is None or cost < best:
best, best_route = cost, stops
print("stops:", n, "| routes checked:", checked, "| shortest length:", best)
print("best route:", best_route)
print("route with length <= 80?", best <= 80, "| <= 70?", best <= 70)
print()
print(f"{'n':>3} {'n^2':>6} {'2^n':>10} {'n!':>20}")
for m in (5, 10, 20):
print(f"{m:>3} {m*m:>6} {2**m:>10} {factorial(m):>20}")আসল আউটপুট (ব্রাউজারের Python):
stops: 7 | routes checked: 5040 | shortest length: 74
best route: (0, 3, 1, 4, 5, 7, 2, 6, 0)
route with length <= 80? True | <= 70? False
n n^2 2^n n!
5 25 32 120
10 100 1024 3628800
20 400 1048576 2432902008176640000
৭টি ঠিকানায় 7! = 5040টি ক্রম, চোখের পলকে শেষ। সবচেয়ে ছোট রুট 74 একক, তাই B = 80-এর প্রশ্নে উত্তর “হ্যাঁ”, B = 70-এ “না”। কিন্তু টেবিলটি দেখুন: n = 20-এ n! প্রায় 2.4 × 1018. প্রতি সেকেন্ডে একশো কোটি রুট পরীক্ষা করলেও লাগবে প্রায় ৭৭ বছর। অথচ n2 মাত্র 400. Polynomial time (n2, n3-এর মতো) আর exponential time (2n, n!-এর মতো)-এর এই ফাঁকই complexity তত্ত্বের কেন্দ্রে।
এখানে একটি অদ্ভুত অসমতা আছে। কেউ যদি একটি রুট হাতে দিয়ে বলেন “এই দেখুন, 80-এর মধ্যে”, তা যাচাই করা সহজ: দূরত্বগুলো যোগ করুন, n ধাপ। কিন্তু নিজে সেই রুট খুঁজে বের করার দ্রুত পদ্ধতি কারও জানা নেই। যেসব হ্যাঁ/না সমস্যার “হ্যাঁ”-উত্তরের প্রমাণ polynomial সময়ে যাচাই করা যায়, তাদের শ্রেণির নাম NP; আর যেগুলো polynomial সময়ে সমাধানই করা যায়, তাদের শ্রেণি P. P ⊆ NP সহজেই প্রমাণ হয়। কিন্তু P = NP কি না, এই P বনাম NP প্রশ্নটি আজও খোলা।
সৎ সতর্কতা: “TSP-র দ্রুত algorithm নেই” কথাটি প্রমাণিত নয়। প্রমাণিত কথাটি হলো: রুটের decision রূপটি NP-complete, অর্থাৎ এর polynomial-time algorithm পাওয়া গেলে NP-এর সব সমস্যারই পাওয়া যাবে (তখন P = NP). আর বেশিরভাগ বিশেষজ্ঞ বিশ্বাস করেন P ≠ NP, কিন্তু বিশ্বাস প্রমাণ নয়। ইন্টারনেটে মাঝে মাঝে “P বনাম NP সমাধান হয়েছে” দাবি দেখা যায়; এখন পর্যন্ত এমন কোনো দাবি বিশেষজ্ঞদের যাচাইয়ে টেকেনি।
নিচের ছবিটি পুরো কোর্সের ভূখণ্ড। প্রতিটি ঘর একটি language-শ্রেণি, ভেতরের ঘর বাইরের ঘরের অংশ, আর প্রতিটি ঘরে এমন একটি উদাহরণ যা ঠিক সেই স্তরের। ছবির প্রতিটি সীমারেখা কোনো না কোনো পর্বে প্রমাণ হবে, শুধু P আর NP-এর মাঝের সীমারেখাটি ছাড়া: সেটি আছে কি না, অজানা।
গণনার ভূখণ্ড — এই কোর্সের মানচিত্র
ভেতরের প্রতিটি শ্রেণি বাইরেরটির উপসেট। কালো সীমারেখা মানে অন্তর্ভুক্তি প্রমাণিত ও কঠোর; ড্যাশ দেওয়া সীমা (P আর NP) আলাদা কি না অজানা।
দুটি বিষয় খেয়াল করুন। প্রথমত, সবচেয়ে বাইরের ঘরে লেখা “বেশিরভাগই চেনা যায় না”: প্রোগ্রাম গোনা যায় (countable) অসীম সংখ্যক, কিন্তু language অগণনীয় (uncountable) অসীম সংখ্যক, তাই বেশিরভাগ language-এর জন্য কোনো প্রোগ্রামই নেই। পর্ব ০২-এ এর গণিত, পর্ব ৫১-এ পূর্ণ প্রমাণ। দ্বিতীয়ত, ছবিটি সরল করা: context-sensitive language, PSPACE বা BPP-এর মতো শ্রেণি এখানে নেই। এরা আসবে পর্ব ০৬ (Chomsky hierarchy-র মানচিত্র) আর মডিউল ১১-এ।
৬ · প্রোগ্রামারের কাজে এই তত্ত্ব কোথায় লাগে
“তত্ত্ব” শুনলে অনেকে ভাবেন এটি শুধু পরীক্ষার জন্য। বাস্তবে আপনার প্রতিদিনের অনেক tool এই তত্ত্বের ওপর দাঁড়িয়ে আছে, আর কিছু ভুলের কারণ এই তত্ত্ব না জানা।
| যেখানে দেখবেন | ভেতরের তত্ত্ব | কোথায় শিখবেন |
|---|---|---|
| Regex দিয়ে ফোন নম্বর, অর্ডার-কোড, email-এর format যাচাই | Regular expression = finite automaton (Kleene-এর theorem) | মডিউল ২–৩ |
| একটি regex হঠাৎ সার্ভার আটকে দেয় (ReDoS) | Backtracking engine বনাম automaton-ভিত্তিক engine | পর্ব ২১ |
| Compiler-এর প্রথম ধাপ: শব্দ ভাগ করা (lexer) | Regex থেকে DFA | পর্ব ২২ |
| JSON, SQL, প্রোগ্রামিং ভাষা পড়া (parser) | Context-free grammar, LL আর LR parsing | মডিউল ৫–৭ |
| Network protocol, UI আর checkout workflow | State machine | পর্ব ২৪ |
| Hardware বা protocol নিখুঁত কি না যাচাই | Model checking, Büchi automaton | পর্ব ৭৭ |
| “এই static analyzer সব bug ধরতে পারবে” দাবি | Undecidability, Rice-এর theorem | পর্ব ৫৩, ৭৮ |
| Scheduling, routing, timetable তৈরি | NP-completeness, SAT solver, approximation | মডিউল ১০, ১২ |
| Password আর encryption কেন নিরাপদ বলে ধরা হয় | Computational hardness, one-way function | পর্ব ৭৬ |
সবচেয়ে মূল্যবান দক্ষতাটি সম্ভবত শেষ সারির মতো যুক্তি: “এই সমস্যা কঠিন, তাই নিখুঁত সমাধানের পেছনে না ছুটে ভালো-যথেষ্ট সমাধান খুঁজি।” কেউ যখন বলেন “সব ক্ষেত্রে নিখুঁত, দ্রুত সমাধান দেব”, তখন গণনার তত্ত্ব জানা একজন প্রোগ্রামার বুঝতে পারেন দাবিটি অসম্ভব কি না, আর সময় বাঁচান। একটি reduction দেখিয়ে বলা যায়, “এটি সমাধান করতে পারলে আপনি একটি বিখ্যাত কঠিন সমস্যাও সমাধান করে ফেলবেন।”
অন্য কোর্সের সঙ্গে সম্পর্ক: এই কোর্স যন্ত্র, language আর complexity-শ্রেণি দেয়; algorithm আর কোড দেয় DSA কোর্স (Big-O তার পর্ব ০৪-এ, NP-hardness-এর algorithm-দিক তার পর্ব ৬৪-এ)। গণিতের পটভূমি (logic, set, induction, graph) আছে ডিসক্রিট ম্যাথমেটিক্স কোর্সে, যার পর্ব ৭৪ আর পর্ব ৭৫ এই কোর্সের ছোট পূর্বসূরি। আর compiler তৈরির খুঁটিনাটি পরে আসা Programming Languages & Compilers কোর্সে বিস্তারিত হবে।
৭ · এক নজরে ইতিহাস: ১৯২৮ থেকে ১৯৭০-এর দশক
মজার ব্যাপার হলো, গণনার তত্ত্ব কম্পিউটারের আগে জন্মেছে। ১৯৩০-এর দশকে গণিতবিদরা একটি দার্শনিক প্রশ্নের উত্তর খুঁজছিলেন: “যান্ত্রিক পদ্ধতি” বা algorithm বলতে ঠিক কী বোঝায়? সেই প্রশ্নের উত্তর থেকেই পরে আধুনিক কম্পিউটারের ধারণা এসেছে।
| সাল | কে | কী |
|---|---|---|
| ১৯২৮ | David Hilbert, Wilhelm Ackermann | Entscheidungsproblem-কে স্পষ্ট রূপ দেন: প্রথম-ক্রম logic-এর কোনো বক্তব্য সত্য কি না, যান্ত্রিকভাবে নির্ণয়ের পদ্ধতি কি আছে? |
| ১৯৩১ | Kurt Gödel | Incompleteness theorem: যথেষ্ট শক্তিশালী গাণিতিক তত্ত্বে এমন সত্য বক্তব্য থাকে যা তত্ত্বের ভেতরে প্রমাণ করা যায় না। |
| ১৯৩৬ | Alonzo Church; Alan Turing | দুজন আলাদাভাবে, lambda calculus আর Turing machine দিয়ে, দেখান Entscheidungsproblem-এর উত্তর “না”। Turing-এর প্রবন্ধে universal machine-এর ধারণাও আসে। |
| ১৯৪৩ | Warren McCulloch, Walter Pitts | নিউরনের যুক্তিভিত্তিক গাণিতিক মডেল, যা পরে finite automaton-এর অনুপ্রেরণা হয়। |
| ১৯৫৬ | Stephen Kleene | McCulloch–Pitts নেটের “event” বিশ্লেষণ করে regular expression দেন আর দেখান এরা finite automaton-এর সমান (Kleene-এর theorem). |
| ১৯৫৬, ১৯৫৯ | Noam Chomsky | ভাষার grammar-কে নিয়মের আকার অনুযায়ী স্তরে ভাগ করেন, যা পরে Chomsky hierarchy নামে পরিচিত। |
| ১৯৫৯ | Michael Rabin, Dana Scott | Nondeterministic finite automaton আর subset construction; এই কাজের জন্য পরে (১৯৭৬) Turing Award. |
| ১৯৬৫ | Juris Hartmanis, Richard Stearns | Algorithm-এর সময়কে input-এর আকারের ফাংশন হিসেবে মাপার কাঠামো; complexity theory-র সূচনা হিসেবে গণ্য। |
| ১৯৭১, ১৯৭৩ | Stephen Cook; Leonid Levin | আলাদাভাবে দেখান SAT NP-complete (Cook–Levin theorem). |
| ১৯৭২ | Richard Karp | ২১টি পরিচিত combinatorial সমস্যা NP-complete দেখান; NP-completeness-কে কেন্দ্রীয় ধারণা বানান। |
সাল নিয়ে একটি সতর্কতা: অনেক সময় একটি ধারণা আগে কোনো প্রতিবেদন বা বক্তৃতায় আসে, পরে প্রবন্ধে ছাপা হয়। যেমন Kleene-এর ফলাফল ১৯৫১ সালের একটি RAND প্রতিবেদনে আগে এসেছিল বলে জানা যায়, প্রকাশ ১৯৫৬-তে; Turing-এর প্রবন্ধ ১৯৩৬-এ জমা পড়ে, ছাপা হয় ১৯৩৬–৩৭-এ; আর Entscheidungsproblem-এর ধারণা Hilbert-এর আগের কাজেও ছিল। তাই এখানে সাধারণভাবে স্বীকৃত সালটি দেওয়া হয়েছে। Levin-এর কাজ সোভিয়েত ইউনিয়নে স্বাধীনভাবে হয়েছিল, পশ্চিমে পরিচিত হয় পরে।
এই সময়রেখায় একটি নকশা চোখে পড়ে। প্রথমে সবচেয়ে বড় প্রশ্ন (কী গণনা করা যায়) আর তার উত্তর (Turing machine, undecidability), তারপর দুর্বল যন্ত্রের সূক্ষ্ম তত্ত্ব (finite automaton, grammar), আর শেষে খরচের প্রশ্ন (complexity). এই কোর্স অবশ্য উল্টো দিক থেকে হাঁটে: সহজ যন্ত্র থেকে শক্তিশালী যন্ত্রে, তারপর খরচে। কারণ ছোট যন্ত্রে প্রমাণের কৌশল শেখা সহজ, আর সেই কৌশলই পরে বড় যন্ত্রে কাজে লাগে।
আরও গভীরে: এই কোর্সের অনেক প্রশ্ন আজও গবেষণার বিষয়। P বনাম NP ছাড়াও NP বনাম coNP আর L বনাম NL খোলা, যদিও NL = coNL প্রমাণিত (Immerman ও Szelepcsényi, ১৯৮৭–৮৮)। Busy Beaver সংখ্যা BB(5)-এর মান ২০২৪ সালে bbchallenge নামের একটি অনলাইন সহযোগী দল যাচাইযোগ্য কম্পিউটার-প্রমাণসহ নির্ধারণ করে বলে জানানো হয়েছে। আর transformer-এর মতো neural network কোন formal language শিখতে পারে, সেই প্রশ্ন automaton তত্ত্বকে নতুন করে আলোচনায় এনেছে (পর্ব ৭৯)।
৮ · কোর্সের মানচিত্র, তিনটি পথ আর কীভাবে পড়বেন
কোর্সে মোট ৮৫টি পর্ব, ১৪টি মডিউলে। সবাইকে সব পর্ব একসঙ্গে পড়তে হবে না। নিচের stepper মডিউলগুলোকে ছয়টি বড় ধাপে সাজিয়ে দেখায়, আর প্রতিটি ধাপ কোন পথের অংশ তা বলে।
- ভিত্তি
মডিউল ১পর্ব ০১–০৬ - Regular
মডিউল ২–৪পর্ব ০৭–২৪ - Context-free
মডিউল ৫–৭পর্ব ২৫–৪২ - Turing ও computability
মডিউল ৮–৯পর্ব ৪৩–৫৬ - Complexity
মডিউল ১০–১২পর্ব ৫৭–৭৬ - প্রয়োগ ও প্রস্তুতি
মডিউল ১৩–১৪পর্ব ৭৭–৮৫
- ভিত্তি (মডিউল ১)। এই পর্ব, প্রয়োজনীয় গণিত, string আর language-এর notation, প্রমাণের কৌশল, সমস্যাকে language হিসেবে দেখা আর Chomsky hierarchy-র প্রথম ঝলক। সব পথের শুরু এখানে।
- Regular জগৎ (মডিউল ২–৪)। DFA, NFA, regular expression, pumping lemma, Myhill–Nerode, minimization; তারপর বাস্তবে regex engine, lexer, KMP আর software-এর state machine. মৌলিক পথের মূল অংশ।
- Context-free জগৎ (মডিউল ৫–৭)। Grammar, parse tree, ambiguity, normal form, CYK, pushdown automaton; আর মডিউল ৭-এ বাস্তব parsing: LL, LR, parser generator. মডিউল ৫–৬ মৌলিক পথে, মডিউল ৭ মাঝারি পথে।
- Turing machine আর computability (মডিউল ৮–৯)। Turing machine, Church–Turing thesis, universal machine, decidable আর undecidable, halting problem, reduction, Rice-এর theorem. মাঝারি পথের কেন্দ্র।
- Complexity (মডিউল ১০–১২)। মডিউল ১০-এ P, NP, Cook–Levin আর NP-complete সমস্যা (মাঝারি পথ)। মডিউল ১১–১২-এ space, hierarchy, randomized, circuit, PCP, interactive proof আর quantum complexity (উন্নত পথ)।
- প্রয়োগ ও প্রস্তুতি (মডিউল ১৩–১৪)। মডিউল ১৩-এ model checking, program analysis-এর সীমা, formal language আর machine learning, আর ক্যাপস্টোন (উন্নত পথ)। মডিউল ১৪ পরীক্ষা ও ইন্টারভিউর অনুশীলন, যেকোনো পথের শেষে।
| পথ | মডিউল | কার জন্য |
|---|---|---|
| মৌলিক | ১–৬ | Regex, state machine আর grammar ভালো করে বুঝতে চান; চাকরির লিখিত পরীক্ষায় automaton ও grammar-এর প্রশ্নের প্রস্তুতি |
| মাঝারি | ১–৬, তারপর ৭–১০ | বিশ্ববিদ্যালয়ের পূর্ণ Theory of Computation; parsing, computability আর NP-completeness সহ |
| উন্নত | ১–১০, তারপর ১১–১৩ | গবেষণা, উচ্চশিক্ষা, cryptography বা formal methods-এ আগ্রহী |
| অনুশীলন | ১৪ | যেকোনো পথ শেষে: নকশা, MCQ, লিখিত, ভাইভা আর ইন্টারভিউর প্রশ্ন |
প্রতিটি পর্ব যেভাবে সাজানো
- আগে অনুভব, তারপর সংজ্ঞা: একটি বাজারঘরের উদাহরণ বা দৈনন্দিন উপমা, তারপর tuple আর notation দিয়ে নিখুঁত সংজ্ঞা।
- প্রমাণ: মূল উপপাদ্যগুলোর প্রমাণ সংখ্যাযুক্ত ধাপে, প্রতিটি ধাপের কারণসহ, শেষে ∎। যেখানে শুধু রূপরেখা, সেখানে স্পষ্ট লেখা থাকবে “প্রমাণের রূপরেখা”।
- Stepper: একটি যন্ত্রের প্রতিটি ধাপ, একটি construction-এর প্রতিটি সারি, একটি প্রমাণের প্রতিটি বাছাই।
- পাতাতেই Python আর JavaScript: DFA, PDA, Turing machine চালানো, সব ছোট string-এ brute force, counterexample খোঁজা। যেখানে পাতার বাইরের tool লাগে (যেমন parser generator বা SAT solver), সেখানে আসল run-এর আসল আউটপুট দেখানো হবে।
- শেষে: ভাবনার প্রশ্ন, অনুশীলন (নকশা, প্রমাণ, trace), MCQ আর শব্দকোষ।
পূর্বশর্ত সামান্য: স্কুলের গণিত, আর set, function, relation, induction ও graph-এর প্রাথমিক ধারণা। পর্ব ০২ এগুলো দ্রুত ঝালিয়ে নেবে। আর একটি পরামর্শ: প্রমাণগুলো কাগজ-কলমে নিজে লিখে দেখুন। শুধু পড়ে গেলে প্রমাণ সহজ লাগে; নিজে লিখতে গেলেই বোঝা যায় কোন ধাপটি আসলে বোঝা হয়নি।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- গণনার তত্ত্বের তিন শাখা কী কী? Automata ও formal language, computability, complexity.
- DFA-র ৫-tuple লিখুন। (Q, Σ, δ, q0, F); δ: Q × Σ → Q.
- Finite automaton কি সুষম বন্ধনী চিনতে পারে? না; pigeonhole যুক্তিতে প্রমাণ হয়, লাগে pushdown automaton.
- Halting problem decidable? না; Turing ১৯৩৬ সালে diagonalization দিয়ে প্রমাণ করেন।
- P = NP কি প্রমাণিত? না; P ⊆ NP জানা, সমতা বা অসমতা দুটোই অজানা।
৯ · AI-এর যুগে গণনার তত্ত্ব
AI assistant আজ এক মুহূর্তে DFA আঁকে, regex লেখে, এমনকি “প্রমাণ”ও লিখে দেয়। এই বিষয়ে AI খুব কাজের সহকারী, কিন্তু এখানে তার ভুলগুলো বিশেষ ধরনের: উত্তর দেখতে নিখুঁত, ভেতরে সূক্ষ্ম ভুল। আর এই কোর্সের মূল দক্ষতাই হলো সেই ভুল ধরা: যন্ত্রকে সব ছোট string-এ চালানো, প্রমাণের প্রতিটি ধাপ পরীক্ষা করা।
যাচাইয়ের দুই হাতিয়ার: প্রমাণ আর brute force.
এই বিষয়ে AI যেসব ভুল প্রায়ই করে
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| DFA ভুল language গ্রহণ করে: গণনায় এক বেশি-কম, ε ভুলে যাওয়া, dead state বাদ | দৈর্ঘ্য n পর্যন্ত সব string-এ চালিয়ে সংজ্ঞার সঙ্গে মেলান |
| Pumping lemma-র “প্রমাণে” বিভাজন নিজেই বেছে নেয়, বা একটি ক্ষেত্রই pump করে | প্রতিটি ধাপে জিজ্ঞেস করুন: এই বাছাইয়ের অধিকার কার, “কোনো একটি” না “প্রতিটি”? |
| Decidable আর recognizable গুলিয়ে ফেলে; reduction উল্টো দিকে করে | A ≤ B দেখালে B-এর কাঠিন্য প্রমাণ হয়, A-এর নয়; দিক মিলিয়ে নিন |
| Theorem-এর শর্ত বাদ দিয়ে বলে, খোলা প্রশ্নকে মীমাংসিত বলে | Sipser বা Hopcroft–Motwani–Ullman-এর মতো বিশ্বস্ত বইয়ের সঙ্গে মেলান |
| অস্তিত্বহীন প্রবন্ধ বা বইয়ের পাতা উল্লেখ করে | সূত্রটি নিজে খুঁজে বের করুন; না পেলে বিশ্বাস করবেন না |
AI-কে automaton চাইলে শুধু উত্তর নয়, যাচাইয়ের উপকরণও চেয়ে নিন। নিচের prompt-এর শেষ অংশটি খেয়াল করুন: AI-কে নিজের উত্তর পরীক্ষার কোডও দিতে বলা হয়েছে, যা আপনি নিজে চালাবেন।
AI-এর দেওয়া automaton বা প্রমাণ হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১“কোনো algorithm নেই” প্রমাণ করতে হলে আগে “algorithm” কী, তার সংজ্ঞা লাগে কেন? Hilbert-এর প্রশ্নের উত্তর দিতে Church আর Turing-কে কী করতে হয়েছিল?
কোনো কিছু আছে দেখাতে সংজ্ঞা লাগে না: একটি পদ্ধতি দেখিয়ে দিলেই সবাই মেনে নেন যে সেটি যান্ত্রিক। কিন্তু “কোনো পদ্ধতিই নেই” দেখাতে হলে সম্ভাব্য সব পদ্ধতির ওপর একটি বক্তব্য প্রমাণ করতে হয়। আর সব কিছুর ওপর প্রমাণ করতে হলে সেই “সব কিছু” কী, তা গাণিতিকভাবে নির্দিষ্ট থাকা চাই। “যান্ত্রিক পদ্ধতি” কথাটি ১৯৩০-এর আগে ছিল একটি অনানুষ্ঠানিক ধারণা।
Hilbert আর Ackermann ১৯২৮ সালে Entscheidungsproblem-কে স্পষ্ট রূপ দেন: প্রথম-ক্রম logic-এর যেকোনো সূত্র সব ক্ষেত্রে সত্য কি না, নির্ণয়ের একটি সাধারণ পদ্ধতি চাই। অনেকে আশা করেছিলেন উত্তর “হ্যাঁ”। ১৯৩১ সালে Gödel-এর incompleteness theorem সেই আশাবাদে প্রথম বড় ধাক্কা দেয়, যদিও এটি সরাসরি Entscheidungsproblem-এর উত্তর ছিল না।
১৯৩৬ সালে Church lambda calculus দিয়ে “কার্যকরভাবে গণনাযোগ্য”-এর একটি সংজ্ঞা প্রস্তাব করেন, আর Turing প্রায় একই সময়ে আলাদাভাবে তাঁর যন্ত্র-মডেল দেন। Turing-এর যুক্তির বিশেষত্ব ছিল: তিনি কাগজ-কলম নিয়ে হিসাব করা একজন মানুষের কাজ বিশ্লেষণ করে দেখান যে সেই কাজ তাঁর যন্ত্রের সরল ধাপে ভাঙা যায়। তারপর দুজনেই দেখান, তাঁদের সংজ্ঞায় Entscheidungsproblem সমাধানযোগ্য নয়। পরে প্রমাণ হয় দুটি সংজ্ঞা একই শ্রেণির ফাংশন দেয়। এই সমতা থেকেই Church–Turing thesis-এর দাবি: অনানুষ্ঠানিক “algorithm” ধারণাটি ঠিক এই গাণিতিক সংজ্ঞার সমান। এটি theorem নয়, কারণ একদিকে একটি অনানুষ্ঠানিক ধারণা; তবে আজ পর্যন্ত এর বিরুদ্ধে কোনো গ্রহণযোগ্য প্রমাণ মেলেনি।
মূল উপলব্ধি: অসম্ভবতা প্রমাণের প্রথম শর্ত হলো যা অসম্ভব, তার পরিসর নিখুঁতভাবে বেঁধে দেওয়া। Turing machine ঠিক সেই কাজটিই করে, আর সেজন্য এটি কম্পিউটারের চেয়েও বেশি একটি গাণিতিক সংজ্ঞা।
প্র ০২Turing machine সবচেয়ে শক্তিশালী মডেল হলে finite automaton-এর মতো দুর্বল মডেল পড়ার দরকার কী?
শক্তির একটি দাম আছে: যত শক্তিশালী মডেল, তার আচরণ নিয়ে প্রশ্নের উত্তর তত কম পাওয়া যায়। DFA-র ক্ষেত্রে প্রায় সব স্বাভাবিক প্রশ্ন algorithm দিয়ে সমাধান করা যায়: দুটি DFA একই language চেনে কি না, কোনো string আদৌ গ্রহণ করে কি না, সবচেয়ে ছোট সমতুল্য DFA কোনটি। পর্ব ১৯ আর ২০-এ এগুলোর algorithm আসবে। Turing machine-এর ক্ষেত্রে এই প্রশ্নগুলোর প্রায় সবই undecidable; Rice-এর theorem (পর্ব ৫৩) বলে প্রোগ্রামের আচরণ নিয়ে যেকোনো non-trivial প্রশ্নই undecidable.
বাস্তবে এর অর্থ বিশাল। Network-এর firewall নিয়ম, lexer-এর token নিয়ম বা hardware controller-কে finite automaton হিসেবে লেখা গেলে সেগুলো পুরোপুরি বিশ্লেষণ করা যায়, এমনকি স্বয়ংক্রিয়ভাবে প্রমাণ করা যায় যে কোনো খারাপ অবস্থায় পৌঁছানো অসম্ভব। Model checking (পর্ব ৭৭) এই চিন্তা থেকেই এসেছে। আর খরচও নির্দিষ্ট: DFA প্রতিটি চিহ্নে একবার টেবিল দেখে, input যত লম্বাই হোক স্মৃতি বাড়ে না।
উল্টো দিকের বিপদও আছে। আধুনিক অনেক regex engine backtracking ব্যবহার করে, যাতে back-reference-এর মতো সুবিধা দেওয়া যায় যা regular language-এর বাইরে যায়। এর মূল্য হলো কিছু pattern-এ সময় exponential হয়ে যাওয়া, যাকে বলে ReDoS. পর্ব ২১-এ এর আসল উদাহরণ আর automaton-ভিত্তিক engine দিয়ে এড়ানোর উপায় দেখবেন।
আরেকটি কারণ শিক্ষাগত। ছোট যন্ত্রে প্রমাণের কৌশল (invariant, pigeonhole, construction, simulation) পরিষ্কারভাবে দেখা যায়। এই পর্বের দুটি উপপাদ্যই তার উদাহরণ। একই কৌশল পরে Turing machine আর complexity-তে বড় আকারে ফিরে আসে।
মূল উপলব্ধি: প্রকৌশলে প্রায়ই সবচেয়ে দুর্বল যে মডেলে কাজটি হয়, সেটিই সবচেয়ে ভালো, কারণ দুর্বল মডেল বিশ্লেষণযোগ্য, পূর্বানুমেয় আর সস্তা।
প্র ০৩P বনাম NP এত বিখ্যাত কেন, আর প্রায় পঞ্চাশ বছরেও কেন সমাধান হয়নি?
প্রশ্নটি সহজ ভাষায়: যার সমাধান দ্রুত যাচাই করা যায়, তার সমাধান কি সবসময় দ্রুত খুঁজেও পাওয়া যায়? Cook (১৯৭১) আর Levin (১৯৭৩) আলাদাভাবে দেখান SAT নামের একটি logic-সমস্যা NP-এর “সবচেয়ে কঠিন”, আর Karp (১৯৭২) দেখান scheduling, routing, graph coloring-এর মতো ২১টি পরিচিত সমস্যাও তাই। পরে হাজারো সমস্যা এই তালিকায় যোগ হয়েছে। এদের যেকোনো একটির polynomial-time algorithm পাওয়া গেলে সবগুলোর পাওয়া যাবে। আরও আগে, ১৯৫৬ সালে Gödel John von Neumann-কে লেখা একটি চিঠিতে প্রায় এই প্রশ্নই তুলেছিলেন বলে চিঠিটি পরে আবিষ্কৃত হলে জানা যায়।
২০০০ সালে Clay Mathematics Institute একে সাতটি Millennium Prize Problem-এর একটি হিসেবে ঘোষণা করে। গুরুত্বের কারণ দুই দিকে। P = NP হলে বহু optimization সমস্যা দ্রুত সমাধানযোগ্য হতো, কিন্তু আজকের cryptography-র অনেক ভিত্তিও (যা ধরে নেয় কিছু সমস্যা কঠিন) ভেঙে পড়ত। P ≠ NP প্রমাণ হলে নিশ্চিতভাবে জানা যেত হাজারো সমস্যায় নিখুঁত দ্রুত সমাধান খোঁজা বৃথা।
সমাধান না হওয়ার একটি গভীর কারণ: গবেষকরা প্রমাণ করেছেন যে কয়েকটি স্বাভাবিক প্রমাণ-কৌশল এই প্রশ্নের উত্তর দিতে পারবে না। Baker, Gill আর Solovay (১৯৭৫) দেখান diagonalization-এর মতো “relativize করে” এমন যুক্তি যথেষ্ট নয়; Razborov আর Rudich (১৯৯০-এর দশক) “natural proofs” নামের আরেক শ্রেণির যুক্তির সীমা দেখান; আর Aaronson ও Wigderson (২০০৮) “algebrization” নামে তৃতীয় একটি বাধা দেন। অর্থাৎ প্রশ্নটি সমাধানের জন্য সম্ভবত নতুন ধরনের গণিত লাগবে। এসব বাধার বিস্তারিত পর্ব ৬৩ আর ৬৮-এ।
মূল উপলব্ধি: P বনাম NP শুধু একটি খোলা প্রশ্ন নয়, এটি “সৃষ্টি কি যাচাইয়ের চেয়ে কঠিন?” এই মৌলিক প্রশ্নের গাণিতিক রূপ। আর গবেষকরা প্রমাণ করেছেন কোন পথে এর উত্তর পাওয়া যাবে না, যা নিজেই একটি বড় অর্জন।
প্র ০৪Finite automaton-এর জন্ম নিউরনের মডেল থেকে, আর আজ neural network নিয়ে আবার automaton-এর প্রশ্ন উঠছে। এই সংযোগটি কী?
১৯৪৩ সালে স্নায়ুবিজ্ঞানী Warren McCulloch আর যুক্তিবিদ Walter Pitts নিউরনের একটি অত্যন্ত সরল গাণিতিক মডেল প্রস্তাব করেন: প্রতিটি “নিউরন” হয় চালু, নয় বন্ধ, আর তার ইনপুটগুলোর একটি যুক্তিভিত্তিক শর্ত পূরণ হলে চালু হয়। এমন নিউরনের একটি জাল যেকোনো মুহূর্তে সসীম সংখ্যক সম্ভাব্য অবস্থার একটিতে থাকে। সময়ের সঙ্গে ইনপুট এলে জালটি এক অবস্থা থেকে আরেক অবস্থায় যায়।
Stephen Kleene প্রশ্ন করেন: এমন জাল ঠিক কোন ধরনের ইনপুট-ক্রম (“event”) চিনতে পারে? উত্তর খুঁজতে গিয়ে তিনি regular expression-এর ধারণা দেন আর দেখান ঠিক regular expression দিয়ে বর্ণনা করা যায় এমন event-গুলোই সসীম জাল চেনে। এই ফলাফল ১৯৫৬ সালে প্রকাশিত হয়, আগে ১৯৫১ সালে একটি RAND প্রতিবেদনে এসেছিল বলে জানা যায়। পরে Rabin আর Scott (১৯৫৯) নিউরনের পটভূমি বাদ দিয়ে বিমূর্ত finite automaton আর nondeterminism-এর ধারণা দেন। এভাবে স্নায়ুবিজ্ঞানের প্রশ্ন থেকে জন্ম নিল আজকের regex.
আজ প্রশ্নটি উল্টো দিক থেকে ফিরে এসেছে। Recurrent neural network বা transformer আসলে কোন formal language শিখতে পারে? সসীম precision-এর একটি recurrent network কার্যত একটি finite automaton; তাহলে সে কি সুষম বন্ধনী চিনতে পারবে? Transformer-এর ক্ষমতাকে কোন circuit-শ্রেণি দিয়ে বাঁধা যায়? এগুলো সক্রিয় গবেষণার বিষয়, আর এখানে অনেক ফলাফল মডেলের নিখুঁত অনুমানের (precision, input দৈর্ঘ্য) ওপর নির্ভর করে, তাই সাধারণীকরণে সতর্ক থাকতে হয়। পর্ব ৭৯-এ এর পরিচয় পাবেন।
মূল উপলব্ধি: গণনার তত্ত্বের মৌলিক প্রশ্ন, “এই যন্ত্র কোন pattern চিনতে পারে, আর কোনটি কখনো পারবে না”, নতুন প্রযুক্তি এলেও পুরোনো হয় না; বরং প্রতিটি নতুন যন্ত্রের জন্য নতুন করে জিজ্ঞাসা করতে হয়।
প্র ০৫Halting problem undecidable হলে বাস্তবের compiler আর static analyzer কীভাবে infinite loop-এর সতর্কবার্তা দেয়? তত্ত্ব কি বাস্তবের সঙ্গে বিরোধ করে?
বিরোধ নেই, কারণ undecidability-র বক্তব্যটি খুব নির্দিষ্ট। এটি বলে: এমন কোনো একক প্রোগ্রাম নেই যা সব (প্রোগ্রাম, input) জোড়ায় থামে এবং সবসময় সঠিক উত্তর দেয়। তিনটি শর্তের যেকোনো একটি ছাড়লেই কাজের tool বানানো যায়।
- সব প্রোগ্রাম নয়: নির্দিষ্ট ধরনের প্রোগ্রামে, যেমন যেখানে প্রতিটি loop একটি সসীম সীমা পর্যন্ত গোনে, থামা প্রমাণ করা সহজ। অনেক ভাষার type system বা proof assistant এভাবে শুধু “নিশ্চিতভাবে থামে” এমন কোড গ্রহণ করে।
- তিন রকম উত্তর: Tool বলতে পারে “থামে”, “থামে না” বা “জানি না”। যতক্ষণ প্রথম দুটি উত্তর সবসময় সঠিক, ততক্ষণ কোনো theorem ভাঙে না; শুধু কিছু প্রোগ্রামে “জানি না” আসবেই।
- সতর্কবার্তায় ভুলের অনুমতি: Linter কিছু ক্ষেত্রে মিথ্যা সতর্কবার্তা দেয়, কিছু ক্ষেত্রে আসল সমস্যা ধরতে পারে না। ব্যবহারকারীরা এটা মেনে নেন।
তত্ত্ব এখানে সীমারেখাটি দেখিয়ে দেয়: কোনো tool নির্মাতা যদি দাবি করেন তাঁর analyzer সব প্রোগ্রামে সব infinite loop নিখুঁতভাবে ধরে, আর কখনো ভুল সতর্কবার্তা দেয় না, তাহলে আপনি নিশ্চিত জানেন দাবিটি ভুল। Rice-এর theorem (পর্ব ৫৩) এই সীমাকে থামা ছাড়াও প্রোগ্রামের যেকোনো non-trivial আচরণগত প্রশ্নে বাড়িয়ে দেয়, আর পর্ব ৭৮ দেখাবে abstract interpretation কীভাবে “নিরাপদ দিকে ভুল” করে কাজের উত্তর দেয়।
মূল উপলব্ধি: Undecidability মানে “কিছুই করা যায় না” নয়; মানে “সবকিছু, সবসময়, নিখুঁতভাবে করা যায় না”। ভালো প্রকৌশল জানে কোন শর্তটি ছাড়তে হবে।
অনুশীলন
কাগজ-কলমে করুন, তারপর উত্তর মিলিয়ে নিন। চাইলে উপরের Python ব্লক বদলে নিজের উত্তর যাচাই করুন।
-
নকশা: বাজারঘরের অর্ডার-কোড language নিন: “BG-” আর তারপর ঠিক ৪টি অঙ্ক (যেমন BG-0042). Σ ধরুন B, G, “-” আর 0–9 অঙ্ক। এর জন্য একটি সম্পূর্ণ DFA নকশা করুন (প্রতিটি state আর প্রতিটি চিহ্নে পরের state সংজ্ঞায়িত)। কয়টি state লাগে? কেন এর কম state-এ হবে না, এক লাইনে যুক্তি দিন।
State 0 থেকে 7: “এ পর্যন্ত কয়টি চিহ্ন ঠিক মিলেছে”। 0 থেকে B পড়লে 1, 1 থেকে G পড়লে 2, 2 থেকে “-” পড়লে 3, আর 3, 4, 5, 6 থেকে যেকোনো অঙ্কে পরের সংখ্যার state. গ্রহণযোগ্য F = {7}। বাকি সব ঘর, আর 7 থেকে যেকোনো চিহ্ন, যায় dead state X-এ, যেখান থেকে সব চিহ্নে X. মোট ৯টি state.
কম state-এ কেন নয়: দুটি state i < j (দুটিই 0–7) নিন। j থেকে কোডটি শেষ করার লেজ (দৈর্ঘ্য 7 − j) j-কে 7-এ নেয়, কিন্তু i থেকে একই লেজ পড়লে মোট মিলে কম চিহ্ন হয়, তাই 7-এ পৌঁছায় না। আর X থেকে কোনো লেজই গ্রহণ হয় না, অথচ 0–7-এর প্রত্যেকটি থেকে কোনো লেজ গ্রহণ হয়। তাই নয়টি state-ই একে অপরের থেকে আলাদা করা যায়। (Partition refinement চালিয়েও ঠিক ৯টি শ্রেণি পাওয়া যায়; এই পদ্ধতি পর্ব ১৯-এ।)
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “LN = {(n)n : n ≤ N} সসীম language, তাই প্রতিটি N-এর জন্য এর একটি DFA আছে। N যত খুশি বড় নেওয়া যায়, তাই সব n-এর জন্য {(n)n : n ≥ 0}-এরও একটি DFA আছে। ∎” ভুলটি কোথায়?
প্রথম বাক্যটি সত্য: প্রতিটি সসীম language regular. ভুল দ্বিতীয় বাক্যে। প্রতিটি N-এর জন্য একটি আলাদা DFA আছে, আর N বাড়লে তার state-সংখ্যাও বাড়ে (মোটামুটি N-এর অনুপাতে)। কিন্তু “সব n-এর জন্য একটি DFA” মানে একটি নির্দিষ্ট k state-এর যন্ত্র, যা সব n-এ কাজ করে। “প্রতিটি N-এর জন্য একটি যন্ত্র আছে” থেকে “একটি যন্ত্র আছে যা সব N-এ কাজ করে” আসে না; এটি ∀∃ আর ∃∀-এর ক্রম গুলিয়ে ফেলা। উপপাদ্য ১.২-এর pigeonhole যুক্তি হুবহু এই language-এও খাটে: k state-এর যেকোনো যন্ত্র (i)i আর (j)i আলাদা করতে পারে না।
-
Trace আর ফল অনুমান: Parity DFA (E শুরু ও গ্রহণযোগ্য; 0-তে state একই, 1-এ E আর O অদলবদল) 110100 পড়লে state-ক্রম কী হবে, আর যন্ত্র গ্রহণ করবে কি? তারপর বলুন 0000 আর 1110111-এর ফল কী।
110100: E → O (1) → E (1) → E (0) → O (1) → O (0) → O (0). শেষ state O ∉ F, তাই বাতিল; সত্যিই এতে তিনটি 1, বিজোড়।
0000: কোনো 1 নেই, state সারাক্ষণ E, গ্রহণ। 1110111: ছয়টি 1, জোড়, তাই উপপাদ্য ১.১ অনুযায়ী শেষ state E, গ্রহণ। পুরো trace না করেও উত্তর দেওয়া গেল: প্রমাণিত invariant-এর এটাই সুবিধা। উপরের JavaScript ব্লকে string-গুলো বসিয়ে মিলিয়ে নিতে পারেন।
-
তিন চশমায় শ্রেণিবিন্যাস: নিচের প্রশ্নগুলো কোন স্তম্ভের মূল প্রশ্ন (automaton, computability না complexity)? (ক) “একটি regex আর একটি DFA কি একই language চেনে?” (খ) “বাজারঘরের ৫০০ অর্ডারের delivery schedule-এ কি ৮ ঘণ্টার মধ্যে সব শেষ করা যায়, আর তা বের করতে কত সময় লাগবে?” (গ) “যেকোনো প্রোগ্রাম কোনো input-এ কখনো ‘ERROR’ ছাপবে কি না, এমন সাধারণ checker কি বানানো যায়?”
(ক) Automaton ও language. Regex থেকে NFA, NFA থেকে DFA বানিয়ে দুটি DFA-র সমতা পরীক্ষা করা যায়; প্রশ্নটি decidable, পর্ব ২০-এ এর algorithm.
(খ) Complexity. সব schedule পরীক্ষা করে উত্তর পাওয়া যায়, তাই সম্ভব কি না প্রশ্ন নয়; প্রশ্ন হলো কত দ্রুত। এ ধরনের scheduling সমস্যার অনেক রূপ NP-hard, তাই বাস্তবে heuristic বা approximation লাগে (মডিউল ১২)।
(গ) Computability. এটি প্রোগ্রামের আচরণ নিয়ে একটি non-trivial প্রশ্ন; halting problem থেকে reduction দিয়ে দেখানো যায় এমন সাধারণ checker নেই (পর্ব ৫২–৫৩)।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএই ঘটনাগুলো সময়ের ক্রমে সাজান (▲▼ চেপে সরান)
- Hilbert ও Ackermann Entscheidungsproblem-কে স্পষ্ট রূপ দেন
- Gödel-এর incompleteness theorem
- Church ও Turing দেখান Entscheidungsproblem সমাধানযোগ্য নয়
- Kleene-এর regular expression আর finite automaton-এর সমতা প্রকাশিত
- Cook দেখান SAT NP-complete
গণনার তত্ত্বের তিন স্তম্ভের কোনটি জিজ্ঞেস করে “কোনো algorithm-ই কি এই সমস্যার সব ক্ষেত্রে সঠিক উত্তর দিতে পারে?”
- Automaton ও formal language
- Computability
- Complexity
- Cryptography
Σ = {0, 1}-এর ওপর DFA M-এর state E (শুরু ও একমাত্র গ্রহণযোগ্য) আর O; δ(E, 0) = E, δ(E, 1) = O, δ(O, 0) = O, δ(O, 1) = E. M নিচের কোন string বাতিল করে?
- ε (ফাঁকা string)
- 0110
- 1011
- 1111
“কোনো DFA সুষম বন্ধনীর language চিনতে পারে না” — এর প্রমাণে মূল যুক্তি কোনটি?
- Pigeonhole: k + 1টি “(”-এর string-এর দুটি একই state-এ যায়
- কয়েকটি DFA চেষ্টা করে দেখা গেছে সবগুলো ব্যর্থ
- Language-টি অসীম, আর DFA শুধু সসীম language চেনে
- Halting problem থেকে reduction
P আর NP নিয়ে কোন বক্তব্যটি আজকের জ্ঞান অনুযায়ী সঠিক?
- P ≠ NP প্রমাণিত
- P = NP প্রমাণিত
- P আর NP-এর সম্পর্ক নিয়ে কিছুই জানা নেই
- P ⊆ NP প্রমাণিত, কিন্তু P = NP কি না অজানা
৭টি delivery ঠিকানার সব ক্রম brute force-এ পরীক্ষা করলে 5040টি রুট দেখতে হয়। একই পদ্ধতিতে ঠিকানা 20টি হলে মোট ক্রমের সংখ্যা মোটামুটি কত?
- 400
- প্রায় 2.4 × 10¹⁸
- প্রায় 10 লাখ
- 5040 × 3 = 15120
একটি AI বলল: “আমার DFA সব সুষম বন্ধনী চেনে; দৈর্ঘ্য 6 পর্যন্ত সব string-এ পরীক্ষা করেছি, কোনো ভুল নেই।” সবচেয়ে সঠিক প্রতিক্রিয়া কোনটি?
- দৈর্ঘ্য 6 পর্যন্ত মিলেছে, তাই যন্ত্রটি ঠিক
- দৈর্ঘ্য 10 পর্যন্ত পরীক্ষা করলে নিশ্চিত হওয়া যাবে
- দাবিটি অসম্ভব; কোনো DFA এটি পারে না, তাই লম্বা string-এ ভুল থাকবেই
- State-সংখ্যা যথেষ্ট বেশি হলে দাবিটি সত্য হতে পারে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- গণনার তত্ত্বের তিন প্রশ্ন: কী গণনা করা যায়, কোন যন্ত্রে, কত দ্রুত; তিন স্তম্ভ automaton, computability, complexity.
- DFA = (Q, Σ, δ, q0, F); প্রতিটি state আর চিহ্নে ঠিক একটি পরের state. সঠিকতা প্রমাণ হয় invariant আর induction দিয়ে।
- “অসম্ভব”-ও প্রমাণ করা যায়: pigeonhole দেখায় DFA সুষম বন্ধনী চেনে না, diagonalization দেখায় halting problem undecidable.
- Polynomial আর exponential বৃদ্ধির ফাঁক complexity-র কেন্দ্রে; P ⊆ NP প্রমাণিত, P = NP অজানা।
- প্রতিটি দাবি দুইভাবে যাচাই: প্রমাণ আর ছোট সব ক্ষেত্রে brute force. AI-এর উত্তরেও তাই।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০২ · প্রয়োজনীয় গণিত — set, relation, function, graph আর countabilityপরবর্তী পর্বএই কোর্সের জন্য দরকারি গণিত, দ্রুত ঝালাই।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্বপুরো কোর্সের মানচিত্র আর সব পর্বের তালিকা।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৪ · Finite automaton আর regular expression-এর পরিচয়পটভূমিএই কোর্সের মডিউল ২–৩-এর ছোট পূর্বসূরি।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৫ · Turing machine-এর পরিচয়পটভূমিComputability আর halting problem-এর প্রথম ঝলক।
- DSA · পর্ব ৬৪ · P বনাম NP — NP-complete আর reductionপাশের ট্র্যাকNP-hardness-কে algorithm আর কোডের দিক থেকে দেখা।