এই পর্বে যা শিখবেন
- একটি Turing machine-কে নির্দিষ্ট নিয়মে binary string ⟨M⟩ আর ⟨M, w⟩-এ লেখা, আর encoding-টি কেন injective
- Universal Turing machine U-এর সংজ্ঞা, তিন tape-এর গঠন আর এক ধাপের অনুকরণের প্রতিটি কাজ
- U যে সঠিক, তার invariant-ভিত্তিক প্রমাণ, আর অনুকরণে কত বাড়তি সময় লাগে
- ATM কেন recognizable, আর U কেন decider নয়
- Python-এ U লিখে সরাসরি simulation-এর সঙ্গে হাজার হাজার input-এ মেলানো, আর stored-program, interpreter ও VM-এর সঙ্গে সম্পর্ক
১ · একটি যন্ত্র, সব যন্ত্র — Turing-এর বড় ধারণা
আগের পর্বগুলোতে প্রতিটি কাজের জন্য আলাদা যন্ত্র বানিয়েছেন। পর্ব ৪৩-এ anbncn-এর যন্ত্র, পর্ব ৪৪-এ binary increment-এর যন্ত্র INC. প্রতিটি যন্ত্রের নিয়ম তার state-নিয়ন্ত্রণে “তারের মতো” বাঁধা: নতুন কাজ মানে নতুন যন্ত্র। এখন একটি প্রশ্ন করুন: এমন একটি নির্দিষ্ট যন্ত্র কি বানানো যায়, যাকে অন্য যেকোনো যন্ত্রের নিয়মের তালিকা আর একটি input দিলে, সে নিজেই সেই যন্ত্রের মতো আচরণ করবে?
একজন অভিজ্ঞ রাঁধুনির কথা ভাবুন। তিনি বিরিয়ানি, খিচুড়ি বা পিঠার জন্য আলাদা রাঁধুনি নন। তাঁকে যেকোনো রেসিপির কাগজ আর বাজারের উপকরণ দিন; তিনি কাগজের নির্দেশ এক লাইন করে পড়বেন আর হুবহু সেটাই করবেন। রেসিপি-কাগজটি হলো ⟨M⟩, উপকরণ হলো w, আর রাঁধুনি হলো U. মূল কথা: রাঁধুনির নিজের দক্ষতা সসীম ও স্থির (পড়া, মাপা, নাড়া), কিন্তু তিনি যত লম্বা রেসিপিই অনুসরণ করতে পারেন, কারণ রেসিপি তাঁর মাথায় নয়, কাগজে লেখা।
এই প্রশ্নের উত্তর Alan Turing দেন তাঁর ১৯৩৬ সালের প্রবন্ধেই, যেখানে Turing machine প্রথম সংজ্ঞায়িত হয়। তিনি দেখান, প্রতিটি যন্ত্রের নিয়ম একটি নির্দিষ্ট format-এ লিখে (তাঁর ভাষায় “standard description”), সেটিকে একটি পূর্ণসংখ্যায় রূপ দেওয়া যায়, যার নাম তিনি দেন description number. তারপর তিনি একটি “universal computing machine” বর্ণনা করেন, যা tape-এ অন্য যন্ত্রের বর্ণনা পড়ে তার কাজ অনুকরণ করে। এটিই ইতিহাসের প্রথম সুস্পষ্ট “program পড়ে চলা” যন্ত্রের তাত্ত্বিক বর্ণনা।
ইতিহাস: Turing-এর “On Computable Numbers, with an Application to the Entscheidungsproblem” ১৯৩৬ সালে জমা পড়ে আর ১৯৩৬–৩৭ সালে ছাপা হয়। Universal machine সেখানে একটি হাতিয়ার: Turing এটি ব্যবহার করে দেখান, “একটি যন্ত্র কখনো থামবে কি না” ধরনের কিছু প্রশ্ন কোনো যন্ত্র সমাধান করতে পারে না, আর সেখান থেকে Entscheidungsproblem-এর নেতিবাচক উত্তর আসে। মূল প্রবন্ধে universal machine-এর বিস্তারিত নকশায় কিছু ত্রুটি ছিল, যা পরে Emil Post (১৯৪৭) সহ অন্যরা দেখিয়ে সংশোধনের পথ দেন বলে উল্লেখ করা হয়; ধারণাটি অবশ্য অক্ষত থাকে।
এই পর্বে আমরা ধারণাটি পুরো গাণিতিকভাবে গড়ব: প্রথমে যন্ত্রকে string-এ লেখার একটি নির্দিষ্ট নিয়ম, তারপর U-এর নকশা ও তার সঠিকতার প্রমাণ, তারপর Python-এ U চালিয়ে যাচাই। শেষে দেখব, আপনার ফোন, ব্রাউজার আর Python interpreter কেন এই একই ধারণার উত্তরসূরি। পর্ব ৪৭-এর Church–Turing thesis মেনে নিলে কথাটি আরও বড়: যেকোনো algorithm একটি Turing machine, তাই একটি U যেকোনো algorithm চালাতে পারে। ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৫-এ universal machine-এর এক অনুচ্ছেদের পরিচয় আছে; এখানে নির্মাণ আর প্রমাণে অনেক গভীরে যাব।
২ · ⟨M⟩ — Turing machine-কে string-এ লেখা
পর্ব ০৫-এ দেখেছেন, যন্ত্র শুধু string পড়ে, তাই graph বা DFA-কেও আগে একটি encoding ⟨·⟩ দিয়ে string-এ লিখতে হয়। Turing machine-এর ক্ষেত্রেও একই কাজ। এই কোর্সের রীতি পর্ব ৪৩-এর মতোই: M = (Q, Σ, Γ, δ, q0, qaccept, qreject), এক দিকে অসীম tape, বাঁ প্রান্তে L দিলে head জায়গায় থাকে, আর সারণিতে না থাকা নিয়ম qreject-এ যায়। এবার এর জন্য একটি নির্দিষ্ট format ঠিক করি।
১. নম্বর দেওয়া: state-গুলোকে নম্বর দিন: q0 = 1, qaccept = 2, qreject = 3, বাকি state-গুলো নামের ক্রমে 4, 5, …. Tape-চিহ্ন: ␣ = 1, বাকি চিহ্ন ক্রমে 2, 3, …. দিক: L = 1, R = 2.
২. সংখ্যা লেখা: সংখ্যা n লেখা হয় 0n, অর্থাৎ n টি 0 (n ≥ 1 বলে কোনো ঘর ফাঁকা থাকে না)।
৩. একটি নিয়ম: δ(qi, sj) = (qk, sl, Dm) লেখা হয় 0i 1 0j 1 0k 1 0l 1 0m.
৪. পুরো যন্ত্র: ⟨M⟩ = সব নিয়ম (i, j)-এর ক্রমে সাজিয়ে, মাঝে 11 বসিয়ে জোড়া।
৫. যন্ত্র আর input: w = c1c2…cn হলে ⟨w⟩ = প্রতিটি চিহ্নের 0-ব্লক, মাঝে একটি 1; আর ⟨M, w⟩ = ⟨M⟩ 111 ⟨w⟩.
তিন রকম বিভাজক কেন কাজ করে, দেখুন। প্রতিটি সংখ্যা অন্তত একটি 0, তাই ⟨M⟩-এর ভেতরে একটানা 1 বড়জোর দুটি (11, নিয়মের সীমানায়)। তাই 111 প্রথম যেখানে আসে, ⟨M⟩ ঠিক সেখানেই শেষ। এই কোর্সের unary রীতিতে দৈর্ঘ্য কিছুটা বাড়ে, কিন্তু পড়া খুব সহজ: 1 দিয়ে ভাগ করে প্রতিটি টুকরোর দৈর্ঘ্যই সংখ্যা। Turing-এর নিজের রীতি ভিন্ন ছিল (D, A, C, L, R, N আর সেমিকোলনের মতো অক্ষর, পরে অঙ্কে বদল), আর Hopcroft–Motwani–Ullman বইয়ে প্রায় এই কোর্সের মতোই 0-ব্লক আর 1-বিভাজক ব্যবহার করা হয়। Format যা-ই হোক, শর্ত একটাই: reasonable, অর্থাৎ injective আর যন্ত্র দিয়ে পড়া-লেখা যায়।
দুটি সরলীকরণ: (১) Formal 7-tuple-এ Q আর Γ-এর আকারও থাকে। যে state বা চিহ্ন কোনো নিয়মে নেই, তা যন্ত্রের আচরণে কোনো প্রভাব ফেলে না; চাইলে শুরুতে একটি header, যেমন 0|Q| 1 0|Γ| 11, যোগ করে সেগুলোও লেখা যায়। (২) সারণিতে না থাকা নিয়ম লেখা হয় না, কারণ কোর্সের রীতিতে সেগুলো qreject-এ যায়, আর U-ও ঠিক তা-ই করবে।
একটি উদাহরণ নিন: বাজারঘরের সেন্সর-লাইনের parity যাচাই (পর্ব ০৫-এর EVEN-এর Turing machine রূপ)। PAR-এর input alphabet {0, 1}; যন্ত্রটি ডানে হাঁটে, state q0 মানে “এ পর্যন্ত জোড় সংখ্যক 1”, q1 মানে “বিজোড়”, আর ␣ পেলে q0 হলে গ্রহণ, q1 হলে নিয়ম নেই, তাই বর্জন। নিয়ম পাঁচটি: q0: 0 → R, 1 → R (q1), ␣ → R (qacc); q1: 0 → R, 1 → R (q0). এর তিনটি state (q0, q1, qacc), সঙ্গে নীরব qreject. নিচের stepper PAR-এর ⟨M⟩ আর ⟨PAR, 101⟩ ধাপে ধাপে গড়ে।
1q0=1 qacc=2 qrej=3 q1=42␣=1 0=2 1=3 · L=1 R=23δ(q0, ␣) = (qacc, ␣, R)4δ(q0, 0) = (q0, 0, R)5δ(q0, 1) = (q1, 1, R)6δ(q1, 0) = (q1, 0, R)7δ(q1, 1) = (q0, 1, R)
| সংখ্যার tuple | |
| code | |
| মোট দৈর্ঘ্য |
- নম্বর দেওয়া। রীতি অনুযায়ী q0 = 1, qacc = 2, qrej = 3, আর বাকি state q1 = 4. চিহ্ন ␣ = 1, 0 = 2, 1 = 3; দিক L = 1, R = 2. এখনো কোনো ঘর লেখা হয়নি।
- প্রথম নিয়ম। (i, j)-এর ক্রমে সবচেয়ে ছোট (1, 1): δ(q0, ␣) = (qacc, ␣, R), অর্থাৎ (1, 1, 2, 1, 2). প্রতিটি সংখ্যা 0-ব্লক: 0 1 0 1 00 1 0 1 00, একসঙ্গে ১১টি ঘর।
- দ্বিতীয় নিয়ম। (1, 2, 1, 2, 2) থেকে 010010100100 (১২টি ঘর)। আগের নিয়মের সঙ্গে মাঝে 11, তাই মোট 11 + 2 + 12 = 25.
- তৃতীয় নিয়ম। δ(q0, 1) = (q1, 1, R) = (1, 3, 4, 3, 2): 0 1 000 1 0000 1 000 1 00, ১৭টি ঘর। মোট 25 + 2 + 17 = 44.
- চতুর্থ নিয়ম। q1-এর নম্বর 4, তাই নিয়মটি 0000 দিয়ে শুরু: (4, 2, 4, 2, 2), ১৮টি ঘর। মোট 64.
- পঞ্চম নিয়ম। (4, 3, 1, 3, 2), ১৭টি ঘর। পুরো ⟨PAR⟩-এর দৈর্ঘ্য 64 + 2 + 17 = 83. একটি নিয়ম (i, j, k, l, m)-এর দৈর্ঘ্য i + j + k + l + m + 4, কারণ চারটি 1 বিভাজক।
- Input জোড়া। w = 101-এর চিহ্নের নম্বর 3, 2, 3, তাই ⟨w⟩ = 000 1 00 1 000 = 0001001000 (১০টি ঘর)। ⟨PAR, 101⟩ = ⟨PAR⟩ 111 ⟨101⟩, দৈর্ঘ্য 83 + 3 + 10 = 96.
একই কাজ এবার কোডে। নিচের ব্লক নিয়মগুলো পর্ব ৪৪-এর ছোট format-এ নেয় (q0 1 q1 = R মানে δ(q0, 1) = (q1, 1, R); “=” মানে পড়া চিহ্নটিই লেখা; কোডে ␣ ছাপা হয় _), নম্বর দেয়, আর ⟨M⟩ ও ⟨M, w⟩ বানায়। পরের ব্লক একই namespace ব্যবহার করবে।
from itertools import product
B = "_" # blank (printed as _)
def T(table): # rules "q read next write move", ";"-separated
d = {}
for rule in table.replace("\n", ";").split(";"):
q, reads, r, w, mv = rule.split()
for s in reads.split(","): # "=" means: write back what was read
d[(q, s)] = (r, s if w == "=" else w, mv)
return d
PAR = T("q0 0 q0 = R; q0 1 q1 = R; q0 _ qacc = R; q1 0 q1 = R; q1 1 q0 = R")
def numbering(d): # states: q0=1, qacc=2, qrej=3, rest 4,5,.. symbols: _=1, rest 2,3,..
qs = {x for (q, _), (r, _, _) in d.items() for x in (q, r)} - {"q0", "qacc", "qrej"}
ss = {x for (_, a), (_, b, _) in d.items() for x in (a, b)} - {B}
st = {s: i for i, s in enumerate(["q0", "qacc", "qrej"] + sorted(qs), 1)}
sy = {s: j for j, s in enumerate([B] + sorted(ss), 1)}
return st, sy
def encode(d, w=None): # <M> or <M, w>; every number n is written as n zeros
st, sy = numbering(d)
rules = sorted((st[q], sy[a], st[r], sy[b], 1 if mv == "L" else 2)
for (q, a), (r, b, mv) in d.items())
code = "11".join("1".join("0" * n for n in rule) for rule in rules)
return code if w is None else code + "111" + "1".join("0" * sy[c] for c in w)
st, sy = numbering(PAR)
print("states :", st)
print("symbols:", sy)
code = encode(PAR)
for rule in code.split("11"): print(" ", rule)
print("<PAR> length", len(code))
print("<PAR, 101> =", encode(PAR, "101"))আসল আউটপুট (ব্রাউজারের Python):
states : {'q0': 1, 'qacc': 2, 'qrej': 3, 'q1': 4}
symbols: {'_': 1, '0': 2, '1': 3}
01010010100
010010100100
01000100001000100
000010010000100100
00001000101000100
<PAR> length 83
<PAR, 101> = 010100101001101001010010011010001000010001001100001001000010010011000010001010001001110001001000
নম্বরগুলো stepper-এর প্রথম ধাপের সঙ্গে মেলে। code.split("11") ⟨PAR⟩-কে আবার পাঁচটি নিয়মে ভাঙে, আর প্রতিটি লাইন stepper-এর একটি ধাপের code. দৈর্ঘ্য ৮৩, আর শেষ লাইনের ৯৬ ঘরের string-এ 1110001001000 অংশে দেখুন: 111 বিভাজক, তারপর 000 (চিহ্ন 1), 00 (চিহ্ন 0), 000 (চিহ্ন 1). লক্ষ করুন, ⟨M, w⟩ নিজে একটি সাধারণ binary string; যে যন্ত্র এটি পড়বে, তার কাছে “যন্ত্র” আর “input” দুটোই কেবল 0 আর 1.
সংজ্ঞা ২.১-এর ⟨M, w⟩ থেকে M-এর নিয়মের সারণি (নম্বরে) আর w একটি algorithm দিয়ে হুবহু ফেরত আনা যায়। তাই ভিন্ন (নিয়ম-সারণি, input) জোড়ার string ভিন্ন।
প্রমাণ:
- ⟨M⟩-এর প্রতিটি সংখ্যা ≥ 1, তাই ⟨M⟩-এ কোথাও 111 নেই; ⟨M, w⟩-এ প্রথম 111-এর আগের অংশই ⟨M⟩, পরের অংশ ⟨w⟩. — বিভাজকের গঠন
- ⟨M⟩-এ 11 শুধু নিয়মের সীমানায় আসে (একটি নিয়মের ভেতরে প্রতিটি 1-এর দুই পাশে 0). তাই 11 দিয়ে ভাগ করলে ঠিক নিয়মগুলো পাওয়া যায়। — একই যুক্তি
- প্রতিটি নিয়মকে 1 দিয়ে ভাগ করলে পাঁচটি 0-ব্লক; তাদের দৈর্ঘ্যই (i, j, k, l, m). ⟨w⟩-কে 1 দিয়ে ভাগ করলে প্রতিটি চিহ্নের নম্বর। — unary পড়া
- ধাপ ১–৩-এর প্রতিটি সিদ্ধান্ত একমাত্র, তাই দুটি ভিন্ন জোড়া একই string দিলে decode করে একই জোড়া পাওয়া যেত, যা অসম্ভব। ∎ — decode একটি function
৩ · Universal Turing machine U — সংজ্ঞা আর তিন tape-এর গঠন
একটি নির্দিষ্ট Turing machine U আছে, যাতে প্রতিটি Turing machine M আর প্রতিটি string w-এর জন্য:
১. M w গ্রহণ করলে U ⟨M, w⟩ গ্রহণ করে;
২. M w বর্জন করলে U ⟨M, w⟩ বর্জন করে;
৩. M w-এ loop করলে U ⟨M, w⟩-এ loop করে।
যে string কোনো ⟨M, w⟩-এর বৈধ রূপ নয়, U তা বর্জন করে।
লক্ষ করুন, “নির্দিষ্ট” শব্দটি সবচেয়ে গুরুত্বপূর্ণ। U-এর state আর tape-চিহ্নের set একবারই ঠিক হয়, আর একই U দশ state-এর যন্ত্রও চালায়, দশ লাখ state-এর যন্ত্রও। এটি সম্ভব, কারণ M-এর state U-এর state-এ রাখা হয় না; রাখা হয় tape-এ, একটি 0-ব্লক হিসেবে। U-এর high-level বর্ণনা (পর্ব ৪৩-এর তিন স্তরের ভাষায়):
Implementation-স্তরে U-কে তিন tape-এর যন্ত্র হিসেবে ভাবা সবচেয়ে সহজ। একাধিক tape-এর যন্ত্র এক tape-এর যন্ত্রের সমান ক্ষমতার, এর প্রমাণ পর্ব ৪৫-এ; তাই শেষে এক tape-এর U-ও পাওয়া যায়।
U-এর তিন tape, ⟨PAR, 101⟩-এর শুরুতে
Tape ১-এ নিয়মের তালিকা, tape ২-এ M-এর tape-এর code, tape ৩-এ M-এর state. ত্রিভুজ = U-এর head.
শুরুতে U input tape থেকে ⟨M⟩ রেখে দেয় tape ১-এ, ⟨w⟩ কপি করে tape ২-এ, আর tape ৩-এ লেখে 0 (q0-এর নম্বর 1). তারপর একটি চক্র চলে, যার প্রতিটি পাক M-এর ঠিক একটি move অনুকরণ করে। নিচের stepper একটি পাকের ভেতরের প্রতিটি কাজ দেখায়: ⟨PAR, 101⟩-এ M-এর প্রথম move.
1tape ৩ থেকে state পড়া2tape ২-এর head-এর নিচের ব্লক পড়া3tape ১-এ মিলে যাওয়া নিয়ম খোঁজা4নতুন state tape ৩-এ লেখা5নতুন চিহ্ন tape ২-এ লেখা6tape ২-এর head এক ব্লক সরানো7state 00 বা 000? তবে থামা
| tape ৩ | |
| tape ২ | |
| tape ১-এ দেখা |
- শুরু। Tape ৩-এ 0 (q0), tape ২-এ ⟨101⟩ = 0001001000, head প্রথম ব্লকে ([ ] দিয়ে দেখানো)। এটি M-এর configuration q0 101-এর code.
- কী খুঁজব। U tape ৩-এর 0 আর tape ২-এর ব্লক 000 পড়ে। তাকে এমন নিয়ম খুঁজতে হবে, যা শুরু হয় 0 1 000 1 দিয়ে। U-এর নিজের state-এ এই ব্লকগুলো রাখা যায় না (দৈর্ঘ্য অসীম হতে পারে), তাই সে tape-এর ঘর পাশাপাশি মিলিয়ে দেখে।
- নিয়ম ১। State-অংশ 0, মিলেছে; কিন্তু চিহ্ন-অংশ 0, যা 000 নয়। U পরের 11 পর্যন্ত ডানে যায়।
- নিয়ম ২। চিহ্ন-অংশ 00, এবারও অমিল।
- নিয়ম ৩। 0 1 000 1: দুটি অংশই মিলেছে। নিয়মের বাকি তিনটি ব্লক: 0000 (q1), 000 (চিহ্ন 1), 00 (R). কোনো নিয়ম না মিললে U tape ৩-এ 000 লিখত, অর্থাৎ qreject.
- লেখা। Tape ৩-এ 0-এর জায়গায় 0000. Tape ২-এর ব্লক 000-এর জায়গায় 000 (এখানে চিহ্ন বদলায়নি)। দৈর্ঘ্য ভিন্ন হলে U-কে tape ২-এর বাকি অংশ ডানে বা বাঁয়ে সরাতে হতো (পর্ব ৪৪-এর shifting কৌশল)।
- সরানো আর যাচাই। দিক 00 = R, তাই head পরের 1 পেরিয়ে পরের ব্লকে: 0001[00]1000. Tape ৩-এ 0000, যা 00 (accept) বা 000 (reject) নয়, তাই পরের পাক। M-এর configuration এখন 1 q1 01: একটি move সম্পূর্ণ।
তুলনাগুলো হয় “ঘর মেলানো” দিয়ে: U দুটি 0-ব্লক পাশাপাশি পড়ে, দুটিই একসঙ্গে শেষ হলে মিল, ঠিক পর্ব ৪৩-এর {w#w} যন্ত্রের মতো। আর tape ২ সরানোর ঝামেলা এড়াতে অনেক বই সব চিহ্নকে সমান দৈর্ঘ্যের binary code দেয় (যেমন ৮টি চিহ্নের জন্য ৩ বিট); ক্ষমতায় পার্থক্য নেই, শুধু সময়ের হিসাব বদলায়।
৪ · U কেন সঠিক — invariant দিয়ে প্রমাণ
“U তো শুধু নিয়ম খুঁজে খুঁজে চালায়, ঠিক তো হবেই” বলা প্রমাণ নয়। বিশেষ করে loop-এর ক্ষেত্রটি সূক্ষ্ম: দেখাতে হবে, M না থামলে U-ও থামে না, আর M থামলে U একই রায় দেয়। এটি একটি simulation argument, পর্ব ০৪-এর ধাঁচে।
প্রমাণের রূপরেখা (উপপাদ্য ৩.১, তিন tape-এর U-এর জন্য): ধরুন M-এর computation q0 w = C0 ⊢ C1 ⊢ C2 ⊢ ⋯. C-এর code বলতে বুঝব: tape ২-এ C-এর tape-এর প্রতিটি চিহ্নের 0-ব্লক (মাঝে 1), U-এর tape ২-এর head C-এর head-এর ঘরের ব্লকের শুরুতে, আর tape ৩-এ C-এর state-এর 0-ব্লক।
- Input বৈধ ⟨M, w⟩ কি না, U একবার বাঁ থেকে ডানে পড়ে যাচাই করে (তিন রকম বিভাজক আর প্রতিটি নিয়মে পাঁচটি ব্লক আছে কি না, আর কোনো (i, j) জোড়া দুবার নেই কি না)। এটি সসীম কাজ; অবৈধ হলে বর্জন। — উপপাদ্য ২.২-এর decode
- Invariant: U-এর k-তম পাক শুরুর মুহূর্তে tape ২ আর tape ৩-এ Ck-এর code, আর tape ১-এ অপরিবর্তিত ⟨M⟩. k = 0-তে এটি শুরুর কপি থেকে সত্য। — ভিত্তি
- ধরুন k-তম পাকের শুরুতে invariant সত্য আর Ck halting configuration নয়। Ck-এর state q আর head-এর চিহ্ন s হলে U tape ১-এ ঠিক সেই নিয়ম পায় যার শুরু (q, s), কারণ δ একটি function আর encoding-এ প্রতিটি (i, j) একবার। নিয়ম না থাকলে কোর্সের রীতিতে δ(q, s) = (qreject, s, R), আর U ঠিক তা-ই লেখে। নতুন state, চিহ্ন আর head-সরানো ⊢-এর সংজ্ঞার হুবহু অনুকরণ (বাঁ প্রান্তের ব্লকে L হলে head জায়গায় থাকে; ডান প্রান্তে নতুন ␣-ব্লক যোগ হয়)। তাই পাক শেষে tape-এ Ck+1-এর code. — induction ধাপ
- প্রতিটি পাক সসীম: tape ১ সসীম দৈর্ঘ্যের, একবার পড়লেই হয়; tape ২-এর সরানো সসীম অংশে। তাই M-এর প্রতিটি move-এর জন্য U সসীম সময় নেয়। — সসীমতা
- M যদি k-তম move-এ qaccept-এ পৌঁছায়, ধাপ ৩ অনুযায়ী k পাক পরে tape ৩-এ 00, আর U গ্রহণ করে; qreject হলে 000, আর U বর্জন করে। — থামা ক্ষেত্র
- M যদি কখনো না থামে, তবে প্রতিটি k-এর জন্য Ck halting নয়, তাই U k-তম পাকে থামে না (U শুধু tape ৩-এ 00 বা 000 দেখলে, অথবা শুরুর যাচাইয়ে থামে)। ধাপ ৪ অনুযায়ী প্রতিটি পাক শেষ হয়, তাই U অসীম সংখ্যক পাক চালায়: loop. — loop ক্ষেত্র
- তিন tape-এর U-কে পর্ব ৪৫-এর অনুকরণে এক tape-এর যন্ত্রে নেওয়া যায়, যা গ্রহণ, বর্জন আর loop তিনটিই রক্ষা করে। ∎ — multi-tape = single-tape
খরচ কত? ধাপ ৩-এ একটি পাকে U tape ১ একবার পড়ে, অর্থাৎ বড়জোর |⟨M⟩|-এর অনুপাতে move, আর চিহ্নের ব্লক সমান দৈর্ঘ্যের হলে tape ২ সরাতে হয় না। তাই M t টি move নিলে তিন tape-এর U নেয় মোটামুটি cM · t move, যেখানে cM শুধু M-এর ওপর নির্ভর করে, w-এর ওপর নয়। এক tape-এর U-তে tape-গুলো পাশাপাশি রাখতে হয় বলে খরচ বেড়ে প্রায় বর্গ হয়। আরও দক্ষ নির্মাণে U মাত্র cM · t log t move-এ অনুকরণ করে (Hennie আর Stearns-এর ১৯৬৬ সালের কৌশলের ওপর দাঁড়িয়ে; Arora–Barak-এর বইয়ে প্রমাণ আছে)। এই “লগারিদমিক দাম” পর্ব ৬৭-এর time hierarchy theorem-এ কাজে লাগবে।
৫ · Python-এ U — শুধু string পড়ে চালানো, সরাসরি simulation-এর সঙ্গে মেলানো
এবার U-কে কোডে লিখি, আর একটি কঠোর শর্ত মানি: U function পায় শুধু ⟨M, w⟩ string, কোনো Python dict বা state-এর নাম নয়। ভেতরে tape১ (নিয়মের সংখ্যা-tuple-এর তালিকা), tape২ (চিহ্নের নম্বরের list), tape৩ (state-এর নম্বর)। প্রতিটি move-এ U tape১-এর নিয়ম একে একে পরীক্ষা করে, আর কতগুলো নিয়ম পড়ল (scans) গুনে রাখে। সঙ্গে পর্ব ৪৩-এর মতো সরাসরি simulator run, যাতে দুটোর ফল মেলানো যায়। পর্ব ৪৩-এর anbncn যন্ত্র ABC আর loop-করা যন্ত্র LOOP-ও যোগ হলো। দুই simulator-এই step cap 1000: cap ছোঁয়া মানে “রায় নেই”।
def U(code, cap=1000): # the universal machine: it sees ONLY the string <M, w>
desc, _, win = code.partition("111")
tape1 = [tuple(len(z) for z in r.split("1")) for r in desc.split("11")]
tape2 = [len(z) for z in win.split("1")] if win else [1] # simulated tape
tape3, h, scans = 1, 0, 0 # simulated state
for step in range(cap + 1):
if tape3 in (2, 3): return ("acc" if tape3 == 2 else "rej"), step, scans
if step == cap: return "cap", step, scans
for rule in tape1: # search tape 1 for (state, symbol)
scans += 1
if rule[:2] == (tape3, tape2[h]): break
else: rule = (tape3, tape2[h], 3, tape2[h], 2) # no rule: go to qrej
tape3, tape2[h], mv = rule[2], rule[3], rule[4]
h = h + 1 if mv == 2 else max(h - 1, 0) # left end: stay put
if h == len(tape2): tape2.append(1)
def run(d, w, cap=1000): # direct simulation of M itself, for comparison
q, tape, h = "q0", list(w) or [B], 0
for step in range(cap + 1):
if q in ("qacc", "qrej"): return q[1:], step
if step == cap: return "cap", step
q, tape[h], mv = d.get((q, tape[h]), ("qrej", tape[h], "R"))
h = h + 1 if mv == "R" else max(h - 1, 0)
if h == len(tape): tape.append(B)
ABC = T("""q0 a q1 X R; q0 Y q4 = R; q0 _ qacc = R; q1 a,Y q1 = R; q1 b q2 Y R
q2 b,Z q2 = R; q2 c q3 Z L; q3 a,b,Y,Z q3 = L; q3 X q0 = R
q4 Y q4 = R; q4 Z q5 = R; q5 Z q5 = R; q5 _ qacc = R""")
LOOP = T("q0 a qacc = R; q0 b q1 = R; q1 a,b,_ q0 = L")
print("U on <PAR, 101> :", U(encode(PAR, "101")))
print("U on <LOOP, ba> :", U(encode(LOOP, "ba")))
for name, M, sigma in [("PAR", PAR, "01"), ("ABC", ABC, "abc"), ("LOOP", LOOP, "ab")]:
words = ["".join(t) for k in range(8) for t in product(sigma, repeat=k)]
pairs = [(U(encode(M, w)), run(M, w)) for w in words]
print(f"{name:4} |<M>|={len(encode(M)):3} agree {sum(u[:2] == r for u, r in pairs)}"
f"/{len(words)} cap {sum(r[0] == 'cap' for _, r in pairs):3}"
f" scans per move {sum(u[2] for u, _ in pairs) / sum(r[1] for _, r in pairs):.2f}")আসল আউটপুট (ব্রাউজারের Python):
U on <PAR, 101> : ('acc', 4, 13)
U on <LOOP, ba> : ('cap', 1000, 3000)
PAR |<M>|= 83 agree 255/255 cap 0 scans per move 3.29
ABC |<M>|=454 agree 3280/3280 cap 0 scans per move 11.62
LOOP |<M>|= 80 agree 255/255 cap 127 scans per move 3.24
প্রথম লাইন: U ⟨PAR, 101⟩-এ ৪টি অনুকৃত move-এ গ্রহণ করে, মোট ১৩টি নিয়ম পড়ে (3 + 4 + 5 + 1, নিচের stepper-এ ধাপে ধাপে)। দ্বিতীয় লাইন: LOOP ba-তে চিরকাল দোলে, তাই U-ও ১০০০ move-এ cap ছোঁয়, কোনো রায় ছাড়া; এটিই উপপাদ্য ৩.১-এর তৃতীয় ক্ষেত্র। তারপর তিন যন্ত্রের প্রতিটিতে দৈর্ঘ্য ০ থেকে ৭ পর্যন্ত সব input (দুই চিহ্নে ২৫৫টি, তিন চিহ্নে ৩২৮০টি): U আর সরাসরি simulator-এর (রায়, move-সংখ্যা) জোড়া প্রতিটিতে হুবহু এক, cap-ছোঁয়া ১২৭টি ক্ষেত্রসহ (LOOP-এর b দিয়ে শুরু হওয়া সব input). শেষ কলামটি খরচের হিসাব: M-এর প্রতিটি move-এ U গড়ে কয়টি নিয়ম পড়ে। PAR আর LOOP-এর ৫টি নিয়মে প্রায় ৩.৩, ABC-এর ১৮টি নিয়মে প্রায় ১১.৬. অর্থাৎ বাড়তি খরচ input-এর দৈর্ঘ্যে নয়, যন্ত্রের আকারে বাড়ে, অংশ ৪-এর cM · t হিসাবের সঙ্গে মিলে।
নিচের stepper U-এর পুরো run দেখায়: ⟨PAR, 101⟩ থেকে গ্রহণ পর্যন্ত, প্রতিটি পাকের শেষে tape ২ আর tape ৩, আর পাশে M-এর সংশ্লিষ্ট configuration.
1নিয়ম ১: (q0, ␣) → qacc, ␣, R2নিয়ম ২: (q0, 0) → q0, 0, R3নিয়ম ৩: (q0, 1) → q1, 1, R4নিয়ম ৪: (q1, 0) → q1, 0, R5নিয়ম ৫: (q1, 1) → q0, 1, R
| M-এর configuration | |
| tape ৩ | |
| tape ২ | |
| মোট পড়া নিয়ম |
- পাক ১-এর শুরু। M-এর configuration q0 101: tape ৩ = 0, head-এর নিচে 000 (চিহ্ন 1). U নিয়ম ১, ২, ৩ পড়ে, নিয়ম ৩-এ মিল পায়।
- পাক ২। নিয়ম ৩ প্রয়োগের পরে state q1 (0000), head পরের ব্লক 00 (চিহ্ন 0)-এ। (q1, 0)-এর নিয়ম চতুর্থ, তাই এবার ৪টি পড়া; মোট এখন 3.
- পাক ৩। নিয়ম ৪-এ q1 অপরিবর্তিত, head শেষ ব্লক 000-এ। (q1, 1) মেলে নিয়ম ৫-এ: ৫টি পড়া। এ পর্যন্ত মোট 3 + 4 = 7.
- পাক ৪। নিয়ম ৫ state ফিরিয়ে দেয় q0-তে (0), আর head ডানে সরে নতুন একটি ␣-ব্লক (0)-এর ওপর, যা U নিজেই যোগ করেছে। (q0, ␣) প্রথম নিয়মেই মেলে। মোট 7 + 5 = 12.
- গ্রহণ। নিয়ম ১ tape ৩-এ 00 (qacc) লেখে; U পাকের শুরুতে 00 দেখে গ্রহণ করে। মোট ৪টি অনুকৃত move আর 12 + 1 = 13টি পড়া নিয়ম, ঠিক কোডের ('acc', 4, 13). 101-এ দুটি 1, জোড় সংখ্যা, তাই PAR-ও গ্রহণ করত।
- তুলনা: 111. ⟨PAR, 111⟩-এ তিন move পরে configuration 111 q1 ␣, tape ৩ = 0000, head-এর নিচে 0. পাঁচটি নিয়মের কোনোটি (4, 1) দিয়ে শুরু হয় না, তাই সব পড়ে U qreject লেখে: ৪ move, মোট ১৬টি পড়া, বর্জন। বিজোড় সংখ্যক 1, তাই এটাই ঠিক।
৬ · ATM recognizable — আর U কেন decider নয়
পর্ব ০৫-এ সমস্যাটির নাম দেওয়া হয়েছিল:
ATM Turing-recognizable; বিশেষত L(U) = ATM.
প্রমাণ:
- x ∈ ATM হলে x = ⟨M, w⟩ বৈধ আর M w গ্রহণ করে, তাই উপপাদ্য ৩.১-এর (১) অনুযায়ী U x গ্রহণ করে। — ATM ⊆ L(U)
- U x গ্রহণ করলে x বৈধ (অবৈধ string U বর্জন করে), x = ⟨M, w⟩, আর (২), (৩) অনুযায়ী M w-এ বর্জন বা loop করলে U গ্রহণ করত না; তাই M w গ্রহণ করে। — L(U) ⊆ ATM
- অতএব L(U) = ATM, আর একটি Turing machine এটি recognize করে। ∎
U কিন্তু decider নয়: ⟨LOOP, ba⟩-এ সে থামে না। একটি recognizer-এর কাছে “হ্যাঁ” একসময় আসে, “না” হয়তো কখনো আসে না। U-কে loop ধরে বর্জন করানো যায় না? Configuration ফিরে আসা দেখে কিছু loop ধরা যায়, কিন্তু ডানে অনন্তকাল হাঁটা যন্ত্রের configuration কখনো ফেরে না, আর “নির্দিষ্ট সংখ্যক ধাপ পর্যন্ত চালাই” নিয়মও ব্যর্থ (অনুশীলন ২)। পর্ব ৫১-এ diagonalization দিয়ে প্রমাণ হবে, ATM-এর কোনো decider নেই; আর পর্ব ৫০-এ দেখবেন, তাহলে ATM-এর complement recognizable-ও নয়। একই কৌশলে HALTTM = {⟨M, w⟩ : M w-এ থামে}-ও recognizable: U-এর মতো চালিয়ে M বর্জন করলেও গ্রহণ করুন।
সাধারণ বিভ্রান্তি: “U সব যন্ত্র চালাতে পারে, তাই U সব প্রশ্নের উত্তর দিতে পারে” — না। U যেকোনো যন্ত্রের আচরণ পুনরাবৃত্তি করে, তার বেশি কিছু নয়; M যেখানে উত্তর দেয় না, U-ও সেখানে দেয় না। Universality আর undecidability একই মুদ্রার দুই পিঠ: যন্ত্রকে data হিসেবে নিতে পারা মানে নিজের বর্ণনা নিয়েও প্রশ্ন করা যায়, আর ঠিক সেখান থেকেই পর্ব ৫১-এর স্ববিরোধ আসে।
৭ · Program-ই data বাস্তবে — stored-program, interpreter আর virtual machine
১৯৪০-এর দশকের প্রথম দিকের কিছু ইলেকট্রনিক কম্পিউটারে, যেমন ENIAC-এ, নতুন হিসাবের জন্য তার আর সুইচ নতুন করে জুড়তে হতো: program ছিল hardware-এর গঠনে, ঠিক এই পর্বের শুরুর “প্রতি কাজে আলাদা যন্ত্র”-এর মতো। ১৯৪৫ সালে John von Neumann EDVAC-এর জন্য যে খসড়া প্রতিবেদন লেখেন, তাতে program-কে সংখ্যা হিসেবে data-র সঙ্গে একই memory-তে রাখার নকশা বর্ণিত হয়; এই ধাঁচ আজ von Neumann architecture নামে পরিচিত। ধারণাটির কৃতিত্ব নিয়ে বিতর্ক আছে: ENIAC দলের Eckert আর Mauchly-ও এর দাবিদার, আর von Neumann Turing-এর ১৯৩৬ সালের প্রবন্ধ জানতেন বলে কয়েকজন সহকর্মীর স্মৃতিচারণে উল্লেখ আছে। Turing নিজেও ১৯৪৫–৪৬ সালে ACE নামের একটি stored-program কম্পিউটারের বিস্তারিত নকশা দেন। এই ইতিহাস কম্পিউটার আর্কিটেকচার কোর্সের পর্ব ০২-এ বিস্তারিত আছে; এখানে মূল কথা একটি: stored-program কম্পিউটার হলো universal machine-এর প্রকৌশল-রূপ। CPU-র নিয়ন্ত্রণ-circuit স্থির (U-এর সসীম নিয়ন্ত্রণ), memory-তে program (tape ১) আর data (tape ২), আর program counter মনে রাখে কোথায় আছি (tape ৩-এর মতো)।
Interpreter
Python interpreter আপনার program-কে bytecode-এ বদলে একটি একটি করে পড়ে চালায় (Python কোর্সের পর্ব ০৫)। কাঠামো U-এর মতোই: “পরের নির্দেশ পড়ো, মিলিয়ে কাজ করো, আবার”। পার্থক্য শুধু format-এ।
Virtual machine আর emulator
একটি কাল্পনিক যন্ত্রের নির্দেশ-set সফটওয়্যারে অনুকরণ করে, যেমন bytecode চালানোর VM, বা পুরোনো game console-এর emulator. একটি কম্পিউটার আরেকটি কম্পিউটার “হয়ে” যায়: universality-র সরাসরি প্রয়োগ।
Compiler
Program-কে input নিয়ে আরেকটি program output দেয়; অর্থাৎ program-কে data হিসেবে রূপান্তর করে। Lexer আর parser (পর্ব ২২, ৩৮–৪০) এই কাজের প্রথম অংশ।
Self-interpreter
একটি ভাষায় লেখা সেই ভাষারই interpreter. John McCarthy ১৯৬০ সালের Lisp-এর প্রবন্ধে Lisp-এর একটি eval function Lisp-এই বর্ণনা করেন, যাকে প্রায়ই “Lisp-এর universal function” বলা হয়।
নিচের JavaScript ব্লকে তিনটি স্তর একসঙ্গে চলে: আপনার ব্রাউজারের JavaScript engine (নিজেও একটি interpreter) U চালায়, আর U চালায় string-এর ভেতরের M-কে। U এখানে পুরোপুরি স্বাধীন: শুধু দুটি binary string (⟨PAR, 101⟩ আর ⟨LOOP, ba⟩, আগের Python ব্লক থেকে কপি করা) জানে। প্রতিটি লাইনে U-এর tape ৩ আর tape ২ ([ ] = head-এর ব্লক), আর কোন নিয়ম ব্যবহৃত হলো।
// U in JavaScript. It gets only the string <M, w> and a step cap.
// Three layers: the browser's JS engine runs U, and U runs the M inside the string.
const PAR_101 = "0101001010011010010100100110100010000100010011" +
"00001001000010010011000010001010001001110001001000";
const LOOP_ba = "0100100100100110100010000100010011000010101010110000" +
"1001010010110000100010100010111000100";
function U(code, cap) {
const [desc, win] = code.split("111");
const tape1 = desc.split("11").map(r => r.split("1").map(z => z.length));
const tape2 = win ? win.split("1").map(z => z.length) : [1];
let tape3 = 1, h = 0;
const show = (k, note) => console.log(String(k).padStart(2) +
" tape3=" + "0".repeat(tape3).padEnd(4) + " tape2=" +
tape2.map((s, i) => i === h ? `[${"0".repeat(s)}]` : "0".repeat(s)).join("1") +
note);
console.log(`tape1: ${tape1.length} rules, ${desc.length} cells`);
for (let k = 0; k <= cap; k++) {
if (tape3 === 2 || tape3 === 3) return show(k, tape3 === 2 ? " ACCEPT" : " REJECT");
if (k === cap) return show(k, ` STOPPED by the cap (${cap}), no verdict`);
const i = tape1.findIndex(r => r[0] === tape3 && r[1] === tape2[h]);
const r = i >= 0 ? tape1[i] : [tape3, tape2[h], 3, tape2[h], 2]; // no rule: qrej
show(k, i >= 0 ? ` uses rule ${i + 1}` : " no rule");
tape3 = r[2]; tape2[h] = r[3];
h = r[4] === 2 ? h + 1 : Math.max(h - 1, 0); // left end: stay put
if (h === tape2.length) tape2.push(1); // new blank cell
}
}
U(PAR_101, 100);
U(LOOP_ba, 4);আসল আউটপুট (ব্রাউজারের JavaScript):
tape1: 5 rules, 83 cells
0 tape3=0 tape2=[000]1001000 uses rule 3
1 tape3=0000 tape2=0001[00]1000 uses rule 4
2 tape3=0000 tape2=0001001[000] uses rule 5
3 tape3=0 tape2=00010010001[0] uses rule 1
4 tape3=00 tape2=0001001000101[0] ACCEPT
tape1: 5 rules, 80 cells
0 tape3=0 tape2=[000]100 uses rule 2
1 tape3=0000 tape2=0001[00] uses rule 4
2 tape3=0 tape2=[000]100 uses rule 2
3 tape3=0000 tape2=0001[00] uses rule 4
4 tape3=0 tape2=[000]100 STOPPED by the cap (4), no verdict
প্রথম অংশ Python-এর U আর stepper-এর সঙ্গে হুবহু মেলে: নিয়ম ৩, ৪, ৫, ১, তারপর tape3 = 00, গ্রহণ। Move 3-এ head শেষ ব্লকের ডানে যায়, তাই U tape২-তে নতুন একটি ␣-ব্লক (একটি 0) যোগ করে। দ্বিতীয় অংশে ⟨LOOP, ba⟩ (৮০ ঘরের ⟨LOOP⟩; LOOP-এ ␣ = 1, a = 2, b = 3): নিয়ম ২ (q0, b) আর নিয়ম ৪ (q1, a) পালা করে খাটে, U-এর tape হুবহু আগের অবস্থায় ফেরে, আর cap ৪-এ থামানো হয়। লক্ষ করুন, ভেতরের যন্ত্র loop করলে বাইরের সবাই loop করে: শুধু সবচেয়ে বাইরের স্তরের cap আমাদের ব্রাউজারকে বাঁচায়।
Program-কে data হিসেবে নেওয়ার একটি অন্ধকার দিকও আছে। Input-এর data যদি ভুল করে program হিসেবে চলে যায়, তা-ই SQL injection বা code injection-এর মূল কারণ: data আর code-এর সীমানা ভেঙে যাওয়া। এর প্রতিরোধ (parameterized query, input যাচাই) সাইবার নিরাপত্তা কোর্সের পর্ব ৩৯-এ আছে। তাত্ত্বিক দিক থেকে কথাটি সহজ: universal যন্ত্রে “কোনটা program, কোনটা data” কেবল একটি রীতি, যন্ত্রের কাছে সবই চিহ্ন।
৮ · সবচেয়ে ছোট universal machine আর পরীক্ষার প্রস্তুতি
U-এর সঠিক state-সংখ্যা কত? অংশ ৩-এর তিন tape-এর নকশা এক tape-এ নিলে কয়েকশো state লাগতে পারে। কিন্তু চতুর নকশায় অবিশ্বাস্য ছোট universal machine বানানো যায়। Claude Shannon (১৯৫৬), Marvin Minsky (১৯৬২, ৭টি state আর ৪টি চিহ্ন) আর Yurii Rogozhin (১৯৯৬)-এর মতো গবেষকেরা ক্রমে ছোট universal machine দেখান; বিস্তারিত ভাবনার প্রশ্ন ০৪-এ। এই ছোট যন্ত্রগুলোর অনেকে সরাসরি M অনুকরণ করে না; তারা “tag system” নামের আরেকটি গণনা-মডেল অনুকরণ করে, যা নিজে universal (পর্ব ৪৯)।
আরও গভীরে: Universal machine-এর গাণিতিক যমজ হলো recursion theory-র universal function আর Kleene-এর normal form theorem (১৯৩০-এর দশক): সব computable function-এর একটি গণনাযোগ্য তালিকা φ0, φ1, … আছে, আর একটি computable function u(e, x) = φe(x). Complexity-তে “efficient universality” আরও গুরুত্বপূর্ণ: U মাত্র cM · t log t move-এ অনুকরণ করতে পারে বলেই প্রমাণ করা যায়, যথেষ্ট বেশি সময় দিলে কঠোরভাবে বেশি সমস্যা সমাধান হয় (পর্ব ৬৭)। ছোট universal machine-এর গবেষণা আরেকটি প্রশ্নের সঙ্গে জড়িত: কত ছোট যন্ত্রের halting প্রশ্ন এখনো decidable, আর কোথা থেকে undecidable শুরু হয়; সেই সীমানা পুরোপুরি জানা নেই।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Universal Turing machine কী? একটি নির্দিষ্ট TM U, যা ⟨M, w⟩ পেয়ে M-কে w-এর ওপর অনুকরণ করে আর M-এর রায় (গ্রহণ, বর্জন বা loop) হুবহু দেয়।
- একটি TM-কে binary string-এ encode করুন। State, চিহ্ন, দিককে সংখ্যা দিয়ে 0n; নিয়ম 0i10j10k10l10m; নিয়মের মাঝে 11; input-এর আগে 111.
- ATM কি recognizable? Decidable? Recognizable, কারণ L(U) = ATM; decidable নয় (diagonalization, পর্ব ৫১)।
- U-এর state-সংখ্যা কি M-এর ওপর নির্ভর করে? না; M-এর state tape-এ লেখা থাকে, U-এর নিয়ন্ত্রণ স্থির।
- Stored-program কম্পিউটারের সঙ্গে সম্পর্ক কী? Program memory-তে data হিসেবে থাকে আর স্থির hardware তা পড়ে চালায়: U-এর প্রকৌশল-রূপ।
৯ · AI-এর যুগে universal machine নিয়ে কাজ
AI assistant-কে “Turing machine-এর একটি encoding দাও” বললে প্রায়ই সুন্দর কিন্তু ভাঙা একটি format আসে। সবচেয়ে সাধারণ ভুল: সংখ্যাগুলো দশমিকে পাশাপাশি লেখা, কোনো বিভাজক ছাড়া, যেমন δ(q1, s12) = (q1, s1, L)-কে “112111”. দেখতে নিরীহ, কিন্তু তাহলে encoding injective থাকে না, আর U ভুল নিয়ম চালাতে পারে। নিচের ব্লক এমন একটি খসড়া (AI-এর উত্তরের ধাঁচে বানানো উদাহরণ) brute force দিয়ে পরীক্ষা করে: সব নম্বর 1 থেকে 12-এর মধ্যে, দুই দিক, মোট 124 × 2 = 41472টি এক-নিয়মের যন্ত্র।
from itertools import product
from collections import defaultdict
# One rule delta(q_i, s_j) = (q_k, s_l, D) as five numbers (D: 1 = L, 2 = R)
rules = [(i, j, k, l, D) for i, j, k, l in product(range(1, 13), repeat=4) for D in (1, 2)]
def ai_draft(rule): # AI draft: "write the numbers one after another"
return "".join(str(n) for n in rule)
def unary(rule): # this course: n zeros per number, "1" between them
return "1".join("0" * n for n in rule)
for name, enc in [("AI draft", ai_draft), ("unary ", unary)]:
seen = defaultdict(list)
for r in rules: seen[enc(r)].append(r)
clash = [v for v in seen.values() if len(v) > 1]
print(f"{name}: {len(rules)} rules -> {len(seen)} codes, {len(clash)} clashes")
if clash: print(" e.g.", enc(clash[0][0]), "=", clash[0][0], "and", clash[0][1])
def decode(code): # unary is easy to read back: split on "1"
return tuple(len(z) for z in code.split("1"))
print("decode check:", all(decode(unary(r)) == r for r in rules))আসল আউটপুট (ব্রাউজারের Python):
AI draft: 41472 rules -> 39588 codes, 1664 clashes
e.g. 111111 = (1, 1, 1, 11, 1) and (1, 1, 11, 1, 1)
unary : 41472 rules -> 41472 codes, 0 clashes
decode check: True
খসড়া format-এ ৪১৪৭২টি নিয়ম মাত্র ৩৯৫৮৮টি আলাদা string দেয়: ১৬৬৪টি string একাধিক নিয়মের ভাগে পড়ে। উদাহরণটি দেখুন: “111111” হতে পারে δ(q1, s1) = (q1, s11, L), আবার δ(q1, s1) = (q11, s1, L). প্রথমটি চিহ্ন s11 লিখে একই state-এ থাকে, দ্বিতীয়টি state বদলায়: সম্পূর্ণ ভিন্ন আচরণ, একই code. U এমন string থেকে কোন যন্ত্র চালাবে, বলার উপায় নেই। এই কোর্সের unary format-এ কোনো সংঘর্ষ নেই, আর প্রতিটি code থেকে নিয়মটি হুবহু ফেরত আসে, যা উপপাদ্য ২.২-এর সঙ্গে মেলে (brute force প্রমাণ নয়, সমর্থন; প্রমাণ অংশ ২-এ)। ছোট উদাহরণে (সব নম্বর ১ অঙ্কের) খসড়াটিও কাজ করত, তাই “PAR-এ চালিয়ে দেখলাম, ঠিক আছে” বলে ভুলটি ধরা যেত না।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| বিভাজকহীন বা দ্ব্যর্থক encoding; ⟨M⟩ আর ⟨w⟩-এর সীমানা অস্পষ্ট | দুই অঙ্কের নম্বরসহ সব ছোট নিয়মে brute force: encode → decode হুবহু ফেরে কি না, সংঘর্ষ শূন্য কি না |
| “U সব যন্ত্র চালায়, তাই U একটি decider” বা “ATM decidable” | একটি loop-করা M দিয়ে U চালান; U থামে না। Recognizable আর decidable-এর সংজ্ঞা আলাদা করে লিখুন |
| U-এর state-সংখ্যা M-এর ওপর নির্ভর করে, বা M-এর state U-এর state-এ রাখা হয় | প্রশ্ন করুন: হাজার state-এর M এলে U কি নতুন state পাবে? U-এর নিয়ন্ত্রণ স্থির, M-এর state tape-এ |
| Simulator-এ step cap নেই, বা “cap ছুঁয়েছে, তাই loop করে” রায় | Cap ছোঁয়াকে আলাদা ফল হিসেবে ছাপুন; cap-ছোঁয়া সংখ্যা গুনুন |
| বানানো ইতিহাস: ভুল সাল, “von Neumann একাই আবিষ্কার করেন”, অস্তিত্বহীন রেফারেন্স | Sipser বা Hopcroft–Motwani–Ullman আর মূল প্রবন্ধের সাল নিজে মিলিয়ে নিন; বিতর্কিত কৃতিত্বে সতর্ক ভাষা খুঁজুন |
AI-কে কাজে লাগানোর ভালো উপায়: encoding, decode-এর যুক্তি, ছোট উদাহরণের পুরো trace আর একটি পরীক্ষা-কোড একসঙ্গে চাওয়া, যা আপনি নিজে চালাবেন।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১U-এর state-সংখ্যা স্থির ও সসীম, অথচ সে যেকোনো বড় যন্ত্র অনুকরণ করে, যার state U-এর চেয়েও অনেক বেশি। এটি কীভাবে সম্ভব, আর এখান থেকে “সসীম নিয়ন্ত্রণ” সম্পর্কে কী শেখা যায়?
প্রথম দেখায় এটি গণনার নিয়ম ভাঙার মতো লাগে: দশ state-এর যন্ত্র কীভাবে দশ লাখ state-এর যন্ত্রের “মনের অবস্থা” মনে রাখবে? উত্তর হলো, U সেই অবস্থা মনে রাখে না, লিখে রাখে। M-এর state qk U-এর tape-এ একটি 0k ব্লক। U-এর নিজের state শুধু বলে “আমি এখন কোন কাজে আছি”: নিয়ম খুঁজছি, ঘর মেলাচ্ছি, লিখছি, head সরাচ্ছি। এই কাজগুলোর তালিকা সসীম, M যত বড়ই হোক। Turing-এর নিজের যুক্তিও এমন ছিল: একজন হিসাবকারী সীমাহীন জটিল হিসাব করতে পারেন, কারণ তাঁর মনের অবস্থা সসীম হলেও কাগজ সীমাহীন।
একই ঘটনা আপনার কম্পিউটারে প্রতিদিন ঘটে। একটি CPU-র নিয়ন্ত্রণ-circuit কারখানায় একবার তৈরি হয়, আর তাতে নির্দিষ্ট সংখ্যক transistor. তবু সেই CPU একটি ছোট calculator app আর একটি বিশাল database server, দুটোই চালায়, কারণ program-এর “state”, অর্থাৎ variable-এর মান, function call-এর stack, program counter, সবই memory-তে থাকে। CPU-র স্থির নিয়ন্ত্রণ কেবল fetch–decode–execute চক্র চালায়, ঠিক U-এর “খোঁজা, লেখা, সরানো” চক্রের মতো।
এখান থেকে একটি গভীর শিক্ষা আসে। DFA-র স্মৃতি শুধু state, তাই সে সসীম কয়েকটি জিনিস মনে রাখতে পারে (পর্ব ১৭-এর pumping lemma এই সীমার ফল)। Turing machine-এরও state সসীম, কিন্তু tape তাকে সীমাহীন বাইরের স্মৃতি দেয়। Universality দেখায়, এই বাইরের স্মৃতিতে শুধু data নয়, “অন্য যন্ত্রের নিয়ন্ত্রণ” পর্যন্ত রাখা যায়। তাই “কত state” প্রশ্নটি যন্ত্রের ক্ষমতা নির্ধারণ করে না; একটি নির্দিষ্ট ছোট নিয়ন্ত্রণ আর সীমাহীন tape-ই সব গণনার জন্য যথেষ্ট। এ কারণেই অংশ ৮-এ দেখা ৭-state ৪-চিহ্নের মতো ছোট যন্ত্রও universal হতে পারে।
মূল উপলব্ধি: সসীম নিয়ন্ত্রণ আর সীমাহীন tape মিলে universality আসে; যন্ত্রের “প্রোগ্রাম” নিয়ন্ত্রণে নয়, tape-এ রাখলেই একটি স্থির যন্ত্র সব যন্ত্র হয়ে উঠতে পারে।
প্র ০২Stored-program কম্পিউটারের ধারণার কৃতিত্ব কার: Turing, von Neumann, নাকি ENIAC দলের? এই প্রশ্নে তত্ত্ব আর প্রকৌশলের সম্পর্ক কীভাবে দেখা উচিত?
সৎ উত্তর হলো, কোনো একজনের একক কৃতিত্ব বলা কঠিন। ১৯৩৬ সালে Turing তত্ত্বে দেখান, একটি নির্দিষ্ট যন্ত্র tape-এ লেখা অন্য যন্ত্রের বর্ণনা পড়ে তা চালাতে পারে। কিন্তু তাঁর প্রবন্ধ ছিল গণিতের logic-এর প্রশ্নের উত্তর, কোনো যন্ত্র বানানোর নকশা নয়। ১৯৪০-এর দশকে ENIAC তৈরির সময় J. Presper Eckert আর John Mauchly-র দল বুঝতে পারে, program তার জুড়ে বদলানো খুব ধীর, আর memory-তে নির্দেশ রাখার ধারণা নিয়ে আলোচনা শুরু হয়। ১৯৪৫ সালের জুনে von Neumann EDVAC-এর জন্য যে “First Draft” লেখেন, তা শুধু তাঁর নামে ছড়িয়ে পড়ে, আর পরে Eckert ও Mauchly এ নিয়ে আপত্তি তোলেন। কয়েকজন সহকর্মীর পরবর্তী স্মৃতিচারণে বলা হয়, von Neumann Turing-এর প্রবন্ধ জানতেন আর তার গুরুত্বের কথা বলতেন; তবে এই প্রভাব ঠিক কতটা ছিল, ঐতিহাসিকরা একমত নন।
Turing নিজে যুদ্ধের পরে ১৯৪৫–৪৬ সালে ACE (Automatic Computing Engine)-এর একটি বিস্তারিত নকশা দেন, যা একটি পূর্ণ stored-program কম্পিউটারের প্রস্তাব। প্রথম যে যন্ত্রে memory-তে রাখা program সত্যিই চলে, তা ১৯৪৮ সালের Manchester “Baby” বলে সাধারণত ধরা হয়, আর ১৯৪৯ সালে Cambridge-এর EDSAC নিয়মিত কাজে লাগে। অর্থাৎ ধারণা, নকশা আর বাস্তবায়ন আলাদা মানুষ আর দলের হাতে, কয়েক বছরের মধ্যে, একে অপরের প্রভাবে গড়ে ওঠে।
তত্ত্ব আর প্রকৌশলের সম্পর্ক এখানে দুই দিকেই চলে। Universal machine দেখায় যে একটি সাধারণ-উদ্দেশ্যের যন্ত্র নীতিগতভাবে সম্ভব, আর সেই যন্ত্র কী পারবে না (halting problem), তাও আগেই বলে দেয়। কিন্তু দ্রুত memory, নির্ভরযোগ্য circuit আর সুবিধাজনক নির্দেশ-set বানানো সম্পূর্ণ আলাদা প্রকৌশল সমস্যা, যা তত্ত্ব সমাধান করে না। কম্পিউটার আর্কিটেকচার কোর্সের পর্ব ০২-এ এই প্রকৌশলের ইতিহাস বিস্তারিত।
মূল উপলব্ধি: Universal machine stored-program কম্পিউটারের তাত্ত্বিক ভিত্তি, কিন্তু বাস্তব কম্পিউটার বহু মানুষের সম্মিলিত প্রকৌশল; কৃতিত্বের প্রশ্নে সতর্ক, প্রমাণনির্ভর ভাষা ব্যবহার করাই সঠিক।
প্র ০৩Interpreter-এ চলা program সরাসরি চলা program-এর চেয়ে ধীর। Universal simulation-এর এই “দাম” কত, তা কেন গুরুত্বপূর্ণ, আর বাস্তবে কীভাবে কমানো হয়?
অংশ ৫-এর কোডে দাম সরাসরি মাপা হয়েছে: M-এর প্রতিটি move-এ U গড়ে কয়েকটি নিয়ম পড়ে, PAR-এ প্রায় ৩.৩, ABC-এ প্রায় ১১.৬. এই গুণক যন্ত্রের আকারের ওপর নির্ভর করে, input-এর দৈর্ঘ্যের ওপর নয়। Tape ২-এর ব্লক সরানো আর এক tape-এ নেওয়ার খরচ যোগ করলে সরল U-এর দাম আরও বাড়ে। তাত্ত্বিকভাবে সবচেয়ে ভালো জানা ফল: একটি নির্দিষ্ট U আছে, যা t move-এর M-কে cM · t log t move-এ অনুকরণ করে, যেখানে cM শুধু M-এর state, চিহ্ন আর tape-সংখ্যার ওপর নির্ভর করে। এই log t গুণক Hennie আর Stearns-এর ১৯৬৬ সালের multi-tape অনুকরণের কৌশল থেকে আসে।
দামটি কেন গুরুত্বপূর্ণ? Complexity তত্ত্বের অনেক প্রমাণ diagonalization-এর মাধ্যমে U-কে ব্যবহার করে: “প্রতিটি যন্ত্রকে নিজের বর্ণনার ওপর সীমিত সময় চালাও, আর উল্টো উত্তর দাও”। অনুকরণ যত সস্তা, এই যুক্তি তত সূক্ষ্ম সময়-পার্থক্য আলাদা করতে পারে। Time hierarchy theorem (পর্ব ৬৭)-এর “log” অংশটি ঠিক এই অনুকরণ-খরচ থেকে আসে। দাম polynomial বলেই P-এর মতো শ্রেণি মডেল বদলালেও একই থাকে; exponential হলে আমাদের সব শ্রেণির সংজ্ঞা টলে যেত।
বাস্তবে interpreter-এর দাম কমানোর পরিচিত কৌশল: পুরো তালিকা না পড়ে সারণি-সূচি (jump table) দিয়ে এক ধাপে সঠিক নির্দেশে পৌঁছানো, বারবার চলা অংশকে চলার সময়েই machine code-এ অনুবাদ করা (JIT compilation), আর virtualization-এর জন্য CPU-র বিশেষ নির্দেশ। এগুলো দাম কমায়, কিন্তু “বর্ণনা পড়ে আচরণ পুনরাবৃত্তি” কাঠামো বদলায় না।
মূল উপলব্ধি: Universal simulation-এর দাম যন্ত্রের আকারের ওপর ধ্রুবক গুণক আর বড়জোর একটি log গুণক; এই সস্তা দামই complexity-র hierarchy প্রমাণ আর বাস্তবের VM, interpreter-এর ভিত্তি।
প্র ০৪সবচেয়ে ছোট universal Turing machine খোঁজার গবেষণা কেন হয়? একটি যন্ত্র “universal” কি না, সেই সংজ্ঞায় কোন সূক্ষ্ম প্রশ্ন ওঠে?
Turing-এর মূল universal machine বড় আর জটিল ছিল। ১৯৫০-এর দশকে প্রশ্ন ওঠে: সবচেয়ে কম state আর চিহ্নে universality সম্ভব কি? Claude Shannon ১৯৫৬ সালে দেখান, দুটি state যথেষ্ট (চিহ্ন অনেক লাগে), আর দুটি চিহ্নও যথেষ্ট (state অনেক লাগে); অর্থাৎ state আর চিহ্ন একে অপরের বিনিময়ে কেনা যায়। Marvin Minsky ১৯৬২ সালে ৭টি state আর ৪টি চিহ্নের একটি universal machine দেন, যা tag system নামের একটি সরল মডেল অনুকরণ করে। Yurii Rogozhin ১৯৯৬ সালে কয়েকটি (state, চিহ্ন) জোড়ায় আরও ছোট যন্ত্র প্রকাশ করেন, আর পরে অন্য গবেষকরাও সীমা ঠেলেছেন।
এই গবেষণার একটি গভীর উদ্দেশ্য আছে: universality আর undecidability-র সীমানা খোঁজা। খুব ছোট যন্ত্রের (যেমন এক state-এর) আচরণ এত সরল যে তাদের halting প্রশ্ন decidable বলে জানা আছে। আবার যে আকারে একটি universal machine আছে, সেই আকারের যন্ত্রের জন্য halting প্রশ্ন সাধারণভাবে undecidable হয়ে যায়, কারণ universal machine-এর halting প্রশ্নেই সব যন্ত্রের halting প্রশ্ন লুকিয়ে থাকে। মাঝখানের আকারগুলোর জন্য উত্তর এখনো পুরোপুরি জানা নেই। Busy Beaver গবেষণাও এই সীমানার সঙ্গে জড়িত (পর্ব ৫৫)।
সংজ্ঞার সূক্ষ্মতা আসে input কীভাবে দেওয়া হয়, সেখান থেকে। আদর্শ সংজ্ঞায় tape-এ সসীম একটি input, বাকি সব blank. কিছু ছোট যন্ত্র শুধু তখনই universal, যখন tape-এর বাকি অংশ একটি পুনরাবৃত্ত নকশায় ভরা থাকে, বা input-এর encoding নিজেই অনেক কাজ করে দেয়। তখন প্রশ্ন ওঠে: আসল গণনা কি যন্ত্র করছে, না encoding? Stephen Wolfram-এর প্রস্তাবিত ২-state ৩-চিহ্নের একটি যন্ত্রের universality নিয়ে ২০০৭ সালে Alex Smith-এর প্রমাণ এমন আলোচনার জন্ম দেয়, আর বিশেষজ্ঞদের মধ্যে এর গ্রহণযোগ্যতা নিয়ে ভিন্নমত রয়েছে বলে জানা যায়। তাই “universal” দাবি পড়লে সবসময় দেখুন, encoding আর শুরুর tape-এর শর্ত কী।
মূল উপলব্ধি: ছোট universal machine দেখায় universality কত সস্তা; আর সংজ্ঞার সূক্ষ্মতা মনে করিয়ে দেয়, encoding যেন নিজেই গণনার কাজ না করে, যা পর্ব ০৫-এর “reasonable encoding”-এর শর্তের সঙ্গে মেলে।
প্র ০৫“Program-ই data” ধারণা একদিকে সাধারণ-উদ্দেশ্যের কম্পিউটার সম্ভব করে, অন্যদিকে undecidability-র দরজা খোলে। একটি ধারণা কীভাবে একসঙ্গে শক্তি আর সীমা দুটোই আনে?
শক্তির দিকটি এই পর্বে দেখেছেন। একটি যন্ত্রকে string-এ লেখা গেলে একটি নির্দিষ্ট যন্ত্র সেই string পড়ে তার আচরণ পুনরাবৃত্তি করতে পারে। তাই প্রতিটি নতুন কাজের জন্য নতুন hardware লাগে না, শুধু নতুন program লাগে। আজকের সফটওয়্যার শিল্প, app store, browser-এ চলা JavaScript, সবই এর ওপর দাঁড়িয়ে। আর যন্ত্র যখন data, তখন যন্ত্র নিয়ে কাজ করা যন্ত্রও বানানো যায়: compiler, debugger, virus scanner, আর IDE-র “এই variable কখনো ব্যবহার হয়নি” সতর্কবার্তা।
সীমার দিকটি আসে একই জায়গা থেকে। যন্ত্র যদি যন্ত্রের বর্ণনা পড়তে পারে, তবে একটি যন্ত্রকে তার নিজের বর্ণনাও দেওয়া যায়। ধরুন কেউ দাবি করলেন, H নামের একটি decider আছে, যা যেকোনো ⟨M, w⟩ দেখে বলে M w গ্রহণ করে কি না। তাহলে এমন একটি যন্ত্র D বানানো যায়, যা ⟨M⟩ পেলে H-কে জিজ্ঞেস করে “M নিজের বর্ণনা ⟨M⟩ গ্রহণ করে কি?” আর ঠিক উল্টো কাজ করে। D-কে ⟨D⟩ দিলে বিরোধ আসে। এই diagonalization-এর পুরো প্রমাণ পর্ব ৫১-এ; এখানে লক্ষ করার বিষয়, যুক্তিটি দাঁড়িয়ে আছে দুটি স্তম্ভে, encoding আর universal simulation, ঠিক যে দুটি জিনিস এই পর্বে গড়েছেন। Cantor-এর diagonal যুক্তি (পর্ব ০২) আর Gödel-এর ১৯৩১ সালের incompleteness theorem-এও একই ধাঁচ: একটি ব্যবস্থা নিজের সম্পর্কে কথা বলতে পারলে কিছু প্রশ্ন তার নাগালের বাইরে চলে যায়।
বাস্তবের প্রকৌশলীর জন্য শিক্ষা হলো: কোনো general-purpose ভাষার program সম্পর্কে “এটি কি সবসময় থামবে” বা “এটি কি কখনো এই লাইনে পৌঁছাবে” ধরনের প্রশ্নের নিখুঁত, সবসময় থামা যাচাইকারী বানানো যায় না। তাই static analysis tool আনুমানিক উত্তর দেয়: কখনো মিথ্যা সতর্কবার্তা, কখনো ভুল এড়িয়ে যাওয়া (পর্ব ৭৮)। বাজারঘরের দল যদি এমন একটি “সব discount-script নিরাপদ কি না যাচাইকারী” কিনতে চায়, যা সবসময় সঠিক উত্তর দেয় বলে দাবি করে, এই তত্ত্ব আগেই বলে দেয় দাবিটি অতিরঞ্জিত।
মূল উপলব্ধি: যন্ত্রকে data হিসেবে নিতে পারাই universality দেয়, আর সেই একই ক্ষমতা নিজের সম্পর্কে প্রশ্ন তুলতে দেয়, যেখান থেকে undecidability অনিবার্য হয়।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। encode_tm.py আর universal_tm.py ব্লকে নিজের যন্ত্র লিখে encode আর U দিয়ে উত্তর যাচাইও করতে পারেন।
-
নির্মাণ: U-কে subroutine হিসেবে ব্যবহার করে E2 = {⟨M⟩ : M ε গ্রহণ করে অথবা M a গ্রহণ করে}-এর একটি recognizer R-এর high-level বর্ণনা দিন, আর প্রমাণ করুন L(R) = E2. সতর্ক থাকুন: “প্রথমে ε-তে চালান, তারপর a-তে” কেন কাজ করে না?
ভুল পথ: M যদি ε-তে loop করে কিন্তু a গ্রহণ করে, তবে “প্রথমে ε” অংশ কখনো শেষ হয় না, আর R কখনো a পর্যন্ত পৌঁছায় না; ⟨M⟩ ∈ E2 হলেও R গ্রহণ করে না।
ঠিক নির্মাণ (পালা করে চালানো, ইংরেজিতে dovetailing): R = “input ⟨M⟩-এর ওপর: (বৈধ না হলে বর্জন) k = 1, 2, 3, …-এর জন্য: U দিয়ে M-কে ε-এর ওপর k ধাপ চালান, আর a-এর ওপর k ধাপ চালান। কোনোটিতে M গ্রহণ করলে গ্রহণ করুন।” ধাপ-সীমা দেওয়া অনুকরণ সবসময় থামে, তাই প্রতিটি k-এর কাজ সসীম।
প্রমাণ: ১. ⟨M⟩ ∈ E2 হলে ধরুন M দুটির একটিকে t ধাপে গ্রহণ করে; k = t পাকে R তা দেখে গ্রহণ করে। ২. R গ্রহণ করলে কোনো k-তে M ε বা a গ্রহণ করেছে, তাই ⟨M⟩ ∈ E2. ৩. ⟨M⟩ ∉ E2 হলে R কখনো গ্রহণ করে না (loop করতে পারে), যা recognizer-এর জন্য অনুমোদিত। ∎ এই পালা করে চালানোর কৌশল পর্ব ৫০-এও আসবে।
-
প্রমাণ (ভুল খুঁজুন): একজন লিখেছেন: “ATM decidable. যন্ত্র D: input x = ⟨M, w⟩ পেলে U দিয়ে M-কে w-এর ওপর 2|x| ধাপ চালান; এর মধ্যে গ্রহণ করলে গ্রহণ, না হলে বর্জন। প্রতিটি input-এ D সসীম সময়ে থামে, তাই D decider, আর D ATM decide করে।” কোন দাবিটি ঠিক, কোনটি ভুল? ভুলটি একটি নির্দিষ্ট ধরনের যন্ত্র দিয়ে দেখান।
ঠিক অংশ: D সত্যিই একটি decider; ধাপ-সীমা থাকায় প্রতিটি input-এ থামে। ভুল অংশ: “D ATM decide করে”, অর্থাৎ নীরব অনুমান “M w গ্রহণ করলে 2|x| ধাপের মধ্যেই করে”। এর কোনো প্রমাণ নেই, আর এটি মিথ্যা।
প্রতি-উদাহরণ: Mslow = “input w (দৈর্ঘ্য n)-এর ওপর: 2n ঘরের একটি binary counter বানান (বারবার দ্বিগুণ করে), সেটি 0 থেকে সব 1 পর্যন্ত বাড়ান, তারপর গ্রহণ করুন।” Counter 22n − 1 বার বাড়ে, তাই Mslow অন্তত 22n ধাপ নিয়ে গ্রহণ করে। অন্যদিকে |x| = |⟨Mslow⟩| + 3 + |⟨w⟩|, যা n-এর রৈখিক (⟨Mslow⟩ স্থির)। তাই বড় n-এ 2|x| < 22n: D ⟨Mslow, w⟩ বর্জন করে, অথচ এটি ATM-এর সদস্য। যেকোনো গণনাযোগ্য ধাপ-সীমার জন্য এমন একটি ধীর যন্ত্র বানানো যায়; আর ATM-এর কোনো decider-ই যে নেই, তা পর্ব ৫১-এ।
-
Decode আর ফল অনুমান: এই কোর্সের encoding-এ (q0 = 1, qacc = 2, qrej = 3; ␣ = 1, 0 = 2, 1 = 3; L = 1, R = 2) একটি string হলো 01010010100 11 010010100100 11 0100010001000100 111 00 1 00 1 000 (পড়ার সুবিধায় ফাঁক দেওয়া)। যন্ত্রটির নিয়ম আর language লিখুন, w কী বলুন, আর U কোন রায় দেবে, কয়টি অনুকৃত move-এ, আর মোট কয়টি নিয়ম পড়ে, অনুমান করুন।
111-এর আগে তিনটি নিয়ম: (1, 1, 2, 1, 2) = δ(q0, ␣) = (qacc, ␣, R); (1, 2, 1, 2, 2) = δ(q0, 0) = (q0, 0, R); (1, 3, 3, 3, 2) = δ(q0, 1) = (qrej, 1, R). যন্ত্রটি ডানে হাঁটে, 1 পেলে বর্জন, ␣ পেলে গ্রহণ: language = 0∗ (ε-সহ সব শুধু-0 string). 111-এর পরে 00, 00, 000, তাই w = 001.
U: move 0-এ (q0, 0): নিয়ম ২ (২টি পড়া); move 1-এ আবার নিয়ম ২ (২টি); move 2-এ (q0, 1): নিয়ম ৩ (৩টি), tape ৩-এ 000. পাকের শুরুতে 000 দেখে বর্জন: ৩টি অনুকৃত move, মোট 2 + 2 + 3 = 7টি পড়া নিয়ম। Scratch-এ
U(encode(X, "001"))চালিয়ে ঠিক ('rej', 3, 7) পাওয়া গেছে, আর পুরো string-এর দৈর্ঘ্য ৫৫। -
প্রমাণ (দৈর্ঘ্যের সূত্র): প্রমাণ করুন, r টি নিয়মের একটি যন্ত্রের জন্য |⟨M⟩| = Σ (i + j + k + l + m + 4) − 2 + 2r, যেখানে যোগফল প্রতিটি নিয়ম (i, j, k, l, m)-এর ওপর। তারপর PAR-এ যাচাই করুন, আর বলুন s টি state ও g টি চিহ্নের যন্ত্রে ⟨M⟩-এর দৈর্ঘ্য কোন আকারের।
প্রমাণ: ১. একটি নিয়মে পাঁচটি 0-ব্লক (দৈর্ঘ্য i, j, k, l, m) আর চারটি 1, তাই দৈর্ঘ্য i + j + k + l + m + 4. ২. r টি নিয়মের মাঝে r − 1টি “11”, যোগ করে 2(r − 1) = 2r − 2. ৩. দুটি যোগ করলে সূত্র। ∎
PAR: নিয়মগুলোর দৈর্ঘ্য 11, 12, 17, 18, 17 (যোগফল 75), r = 5, তাই 75 + 8 = 83, কোডের আউটপুটের সঙ্গে মেলে।
আকার: প্রতিটি সংখ্যা বড়জোর max(s, g), নিয়ম বড়জোর s · g টি, তাই |⟨M⟩| = O(s · g · (s + g)). Unary নম্বর এখানে দৈর্ঘ্য বাড়ায়, কিন্তু যন্ত্রের নিজের আকারের polynomial, তাই encoding reasonable থাকে। Binary নম্বর দিলে O(s · g · log(s + g)), যা অনেক বইয়ের রীতি।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমতিন tape-এর universal machine U যখন M-এর একটি move অনুকরণ করে, তার কাজগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Tape ৩ থেকে M-এর বর্তমান state-এর ব্লক পড়া
- Tape ২-এ head-এর নিচের চিহ্নের ব্লক পড়া
- Tape ১-এ সেই (state, চিহ্ন) দিয়ে শুরু হওয়া নিয়ম খোঁজা
- নিয়মের নতুন state tape ৩-এ আর নতুন চিহ্ন tape ২-এ লেখা
- Tape ২-এর head এক ব্লক বাঁয়ে বা ডানে সরানো
- নতুন state accept বা reject কি না দেখে থামা বা পরের পাক
Universal Turing machine U ইনপুট ⟨M, w⟩ পেয়ে M-কে w-এর ওপর অনুকরণ করে আর M-এর রায় হুবহু দেয়। কোন বিবৃতিটি সঠিক?
- U একটি decider, কারণ U সব যন্ত্রের আচরণ জানে
- L(U) = HALTTM
- L(U) = ATM, আর U একটি recognizer কিন্তু decider নয়
- M-এর state যত বেশি, U-এর state তত বেশি লাগে
একটি encoding-এ state নম্বর q0 = 1, qacc = 2, qrej = 3, q1 = 4; চিহ্ন ␣ = 1, 0 = 2, 1 = 3; দিক L = 1, R = 2; সংখ্যা n লেখা হয় n টি 0, আর একটি নিয়মের পাঁচটি সংখ্যার মাঝে একটি 1. δ(q1, 0) = (qacc, 1, L)-এর code কোনটি?
- 00001001001000100
- 0000100100100010
- 0000100010010010
- 0100100100010
একটি TM encoding-এ প্রতিটি সংখ্যা অন্তত একটি 0 দিয়ে লেখা হয়, একটি নিয়মের সংখ্যার মাঝে 1, নিয়মের মাঝে 11, আর যন্ত্রের code ও input-এর code-এর মাঝে 111. 111 বিভাজক কেন দ্ব্যর্থহীন?
- কারণ input-এর code-এ কখনো 1 থাকে না
- কারণ 111 সবসময় string-এর শেষে থাকে
- কারণ unary encoding সবসময় দ্ব্যর্থহীন
- কারণ যন্ত্রের code-এ একটানা দুটির বেশি 1 কখনো আসে না
একটি নির্দিষ্ট universal machine U, যার state-সংখ্যা স্থির, কীভাবে এমন যন্ত্র M অনুকরণ করে যার state U-এর চেয়েও অনেক বেশি?
- M-এর বর্তমান state U-এর tape-এ একটি string হিসেবে লেখা থাকে
- U চলার সময় দরকারমতো নতুন state তৈরি করে
- U শুধু U-এর চেয়ে কম state-এর যন্ত্র অনুকরণ করে
- U nondeterministic, তাই সব state একসঙ্গে মনে রাখে
Turing machine M input w-এ কখনো থামে না। Universal machine U-কে ⟨M, w⟩ দিলে কী হয়?
- U loop ধরে ফেলে বর্জন করে
- U গ্রহণ করে, কারণ ⟨M, w⟩ একটি বৈধ encoding
- U-ও চিরকাল চলে, কোনো রায় দেয় না
- U নির্দিষ্ট সংখ্যক ধাপের পরে বর্জন করে
Stored-program কম্পিউটার আর universal Turing machine-এর মিল কোথায়?
- দুটিতেই প্রতিটি নতুন কাজের জন্য নতুন hardware লাগে
- Program data-র মতো memory-তে থাকে আর একটি স্থির নিয়ন্ত্রণ সেটি পড়ে চালায়
- দুটিরই memory অসীম
- দুটিই halting problem সমাধান করতে পারে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- প্রতিটি TM একটি string ⟨M⟩: সংখ্যা n = 0n, নিয়মের ভেতরে 1, নিয়মের মাঝে 11, ⟨M, w⟩-তে 111. Encoding injective আর decode করা যায়।
- Universal TM U একটি নির্দিষ্ট যন্ত্র: ⟨M, w⟩-এ M-এর রায় হুবহু দেয়: গ্রহণ, বর্জন বা loop.
- গঠন: tape ১ = ⟨M⟩, tape ২ = M-এর tape-এর code, tape ৩ = M-এর state; প্রতি পাকে খোঁজা, লেখা, সরানো। U-এর নিয়ন্ত্রণ স্থির।
- L(U) = ATM, তাই ATM recognizable; U decider নয়, আর ATM-এর কোনো decider নেই (পর্ব ৫১)।
- অনুকরণের দাম যন্ত্রের আকারের গুণক (দক্ষ নির্মাণে cM · t log t); stored-program কম্পিউটার, interpreter আর VM হলো universality-র প্রকৌশল-রূপ।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০৫ · সমস্যাকে language হিসেবে দেখা — encoding আর decision problemপটভূমি⟨·⟩ চিহ্ন, reasonable encoding আর ATM-এর নাম।
- পর্ব ৪৩ · Turing machine — formal definition আর configurationফিরে দেখুনConfiguration, ⊢, তিন ফল আর decider বনাম recognizer.
- পর্ব ৪৪ · Turing machine নকশা — ধাপে ধাপে উদাহরণফিরে দেখুনTape সরানো, মেলানো আর copy-র subroutine, যা U-এর ভেতরে লাগে।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৪৯ গণনার অন্য মডেল।
- কম্পিউটার আর্কিটেকচার · পর্ব ০২ — ইতিহাস আর প্রবণতাপাশের ট্র্যাকENIAC থেকে stored-program কম্পিউটার আর কৃতিত্বের বিতর্ক।
- Python · পর্ব ০৫ — Python কীভাবে চলেপাশের ট্র্যাকInterpreter আর bytecode: বাস্তবের একটি universal machine.