সরাসরি পর্বে যান
পর্ব ৫৬ · ৮৫-এর মধ্যে · মডিউল ৯

Recursion theorem আর Kolmogorov complexity

The Recursion Theorem and Kolmogorov Complexity — Quines, Self-reference, Incompressible Strings and Why K Is Uncomputable

Taught in Bangla, this lesson builds a quine from a data part and a code part and checks it in in-page Python (Pyodide) and as a real file run. It states the recursion theorem, sketches the SELF machine, and applies it to a second proof that A_TM is undecidable, to show MIN_TM is not recognizable and to explain self-replication defensively. It then defines Kolmogorov complexity, proves incompressible strings exist and that K is uncomputable via the Berry paradox, and uses zlib and lzma as upper bounds only.

এই পর্বে যা শিখবেন

  • Quine-এর দুই অংশের গঠন, আর ব্রাউজারের Python-এ ও সত্যিকারের run-এ quine যাচাই
  • Recursion theorem-এর নিখুঁত বক্তব্য, SELF যন্ত্রের নির্মাণ আর প্রমাণের রূপরেখা, fixed-point রূপসহ
  • Recursion theorem দিয়ে ATM undecidable আর MINTM recognizable নয়, এই দুটির প্রমাণ
  • Kolmogorov complexity-র সংজ্ঞা, invariance theorem, সংকোচন-অযোগ্য string-এর গোনার প্রমাণ আর K-এর অগণনীয়তা
  • Compression দিয়ে K-এর ওপরের সীমা: zlib, lzma আর bz2-এর সত্যিকারের মাপ, আর এর সীমাবদ্ধতা

১ · নিজের ছবি নিজে আঁকা — program কি নিজের source ছাপতে পারে?

বাজারঘরের দল একটি মজার চ্যালেঞ্জ দিল: এমন একটি program লিখুন, যা চালালে ঠিক নিজের source code ছাপে, একটি অক্ষরও কম-বেশি নয়। শর্ত একটাই: program নিজের ফাইল খুলে পড়তে পারবে না, input-ও নেবে না। প্রথম চেষ্টাটি সাধারণত এমন হয়: print("print(...)"). কিন্তু এটি ছাপে print(...), নিজেকে নয়। ভেতরের অংশ ঠিক করতে গেলে আবার একটি print লাগে, তার ভেতরে আরেকটি, এভাবে অসীম পর্যন্ত। মনে হয়, একটি সসীম program-এর ভেতরে নিজের পুরো বর্ণনা রাখা অসম্ভব, কারণ বর্ণনাটি program-এর চেয়ে ছোট হতে হবে।

দুটি আয়না মুখোমুখি রাখলে ভেতরে অসীম ছবি দেখা যায়; নিজের ছবি সরাসরি নিজের ভেতরে রাখতে চাইলে এই অসীম সিঁড়িই আসে। কিন্তু একজন রাজমিস্ত্রি অন্যভাবে ভাবেন: তাঁর হাতে একটি নকশার কাগজ আর একটি নির্দেশ, “কাগজে যা আঁকা আছে তা বানাও, তারপর কাগজটির একটি ফটোকপি নতুন বাড়িতে রেখে দাও।” নকশায় নিজের ফটোকপি আঁকা নেই; কপি করার কাজটি নির্দেশ অংশ করে। এই পর্বের পুরো কৌশল এখানেই: একই লেখা একবার পড়ে মানতে হয় (নির্দেশ), আরেকবার শুধু নকল করতে হয় (তথ্য)।

প্রশ্নটি শুধু ধাঁধা নয়। পর্ব ৫১-এ diagonal যন্ত্র D-কে তার নিজের বর্ণনা ⟨D⟩ বাইরে থেকে input হিসেবে দেওয়া হয়েছিল। সেই পর্বের শেষ ভাবনার প্রশ্নে একটি প্রশ্ন খোলা ছিল: যন্ত্র কি নিজেই নিজের বর্ণনা জানতে পারে? এই পর্বের প্রথম অর্ধেক (অংশ ২–৪) তার উত্তর দেয়: পারে, আর সেটাই recursion theorem. দ্বিতীয় অর্ধেক (অংশ ৫–৮) একই “বর্ণনা” ধারণা দিয়ে তথ্যের পরিমাণ মাপে: একটি string-এর সবচেয়ে ছোট বর্ণনা কত বড়? সেই মাপের নাম Kolmogorov complexity, আর তার গল্পেও শেষে undecidability ফিরে আসে।

২ · Quine — তথ্য অংশ আর কাজ অংশ

নিজের source ছাপে এমন program-কে বলা হয় quine. নামটি Douglas Hofstadter-এর ১৯৭৯ সালের বই Gödel, Escher, Bach-এ দার্শনিক W. V. O. Quine-এর সম্মানে দেওয়া, যিনি নিজের সম্পর্কে কথা বলা বাক্য নিয়ে লিখেছিলেন। Python-এ সবচেয়ে প্রচলিত quine দুই লাইনের:

s = 's = %r\nprint(s %% s)'
print(s % s)

এখানে দুটি Python নিয়ম জানা দরকার। %r হলো একটি ফাঁকা ঘর, যেখানে একটি মানের repr, অর্থাৎ উদ্ধৃতিচিহ্নসহ Python-এর লেখার রূপ, বসে। আর %% বসানোর পরে একটি % হয়ে যায়। প্রথম লাইন হলো তথ্য অংশ: s-এ পুরো program-এর একটি ছাঁচ রাখা আছে, শুধু s-এর নিজের মানের জায়গায় একটি ফাঁকা ঘর। দ্বিতীয় লাইন হলো কাজ অংশ: s % s ছাঁচটির ফাঁকা ঘরে s-কেই বসায়। ফলে একই string s দুবার ব্যবহৃত হয়: একবার ছাঁচ হিসেবে, একবার ঘর ভরাটের উপাদান হিসেবে। নিচের stepper-এ ধাপগুলো দেখুন।

1s = 's = %r\nprint(s %% s)'2print(s % s)
এই ধাপে
অংশ
s-এ আছে
ছাপা হলো
  1. সরল চেষ্টা। print("print(...)") নিজেকে নয়, ভেতরের লেখাটি ছাপে। ভেতরের লেখায় পুরো program রাখতে গেলে সেটি program-এর চেয়ে বড় হয়ে যায়: অসীম সিঁড়ি।
  2. দুই ভাগ। Program-কে দুই ভাগ করুন। লাইন ১ (অংশ A) কোনো কাজ করে না, শুধু একটি string রাখে। পরের ধাপে দেখবেন, এই string-এ কাজ অংশের লেখা আর একটি ফাঁকা ঘর আছে।
  3. ছাঁচ। s-এর মান s = %r, তারপর একটি newline (\n), তারপর print(s %% s). অর্থাৎ পুরো program-এর লেখা, শুধু নিজের উদ্ধৃত মানের জায়গায় %r. ছাঁচটি নিজেকে ধারণ করে না, তাই অসীম সিঁড়ি নেই।
  4. ঘর ভরাট। লাইন ২ (অংশ B) s % s হিসাব করে: %r-এর জায়গায় repr(s) বসে, যা উদ্ধৃতিচিহ্নসহ s-এর লেখা। ফলে আউটপুটের প্রথম লাইন হুবহু source-এর লাইন ১।
  5. মিলে গেল। ছাঁচের বাকি অংশে %% একটি % হয়ে print(s % s) হয়, যা হুবহু লাইন ২। দুই লাইন মিলে আউটপুট ঠিক source. একই লেখা একবার ছাঁচ, একবার উপাদান: এটাই quine-এর মূল কৌশল।

দাবিটি চোখে না মেনে যাচাই করুন। নিচের ব্লক program-কে string হিসেবে রেখে exec দিয়ে চালায়, যা ছাপে তা ধরে, আর source-এর সঙ্গে মেলায়। তৃতীয় program selfie আরও এক ধাপ এগোয়: সে quine-এর কৌশলে নিজের source একটি চলক me-তে বানায়, তারপর ছাপার বদলে তার দৈর্ঘ্য আর লাইনসংখ্যা হিসাব করে।

import io, contextlib
def run(src):                                   # run a program, capture its output
    buf = io.StringIO()
    with contextlib.redirect_stdout(buf):
        exec(src, {})
    return buf.getvalue()

naive = 'print("print(...)")\n'                 # first try: it never ends
quine = "s = 's = %r\\nprint(s %% s)'\nprint(s % s)\n"
selfie = ("s = 's = %r\\nme = s %% s\\nprint(len(me), me.count(chr(10)) + 1)'\n"
          "me = s % s\n"
          "print(len(me), me.count(chr(10)) + 1)\n")

print("naive prints:", run(naive), end="")
print("naive == own source:", run(naive) == naive)
print("quine == own source:", run(quine) == quine)
print("quine of quine:     ", run(run(quine)) == quine)
print("selfie prints:", run(selfie), end="")
print("its real size:", len(selfie.rstrip("\n")), selfie.count("\n"))
print(quine, end="")

আসল আউটপুট (ব্রাউজারের Python):

naive prints: print(...)
naive == own source: False
quine == own source: True
quine of quine:      True
selfie prints: 113 3
its real size: 113 3
s = 's = %r\nprint(s %% s)'
print(s % s)

সরল চেষ্টা নিজেকে ছাপে না (False), quine ছাপে (True), আর quine-এর আউটপুট আবার চালালেও একই source আসে। selfie বলে তার দৈর্ঘ্য ১১৩ অক্ষর আর ৩ লাইন, আর বাইরে থেকে মাপলেও (শেষের newline বাদে) ঠিক তাই। selfie কোনো ফাইল বা input পড়েনি; নিজের বর্ণনা নিজে বানিয়ে তা নিয়ে হিসাব করেছে। এই ধাঁচটিই পরের অংশের theorem.

সত্যিকারের run. ব্রাউজারের exec ছাড়াও আসল ফাইল হিসেবে যাচাই করা হয়েছে: quine.py ফাইলে ওপরের দুই লাইন রেখে আলাদা একটি script দিয়ে program চালানো হয়েছে, তার আউটপুট ফাইলের লেখার সঙ্গে মেলানো হয়েছে, আর আউটপুটকে আবার program হিসেবে চালানো হয়েছে।

সত্যিকারের run (ডেস্কটপ, Python 3.14.4, uv দিয়ে বানানো প্রকল্প):

~/bazarghar-toc$ uv run python quine.py
s = 's = %r\nprint(s %% s)'
print(s % s)
~/bazarghar-toc$ uv run python verify_quine.py
source chars: 41 | output chars: 41
output == source: True
output of output == source: True
sha256 source: 2365292c4c424277
sha256 output: 2365292c4c424277

৪১ অক্ষরের ফাইল, ৪১ অক্ষরের আউটপুট, আর দুটির SHA-256 hash-এর প্রথম ১৬ ঘরও এক। খুঁটিনাটি: Windows-এ আউটপুটের লাইনের শেষে বাড়তি carriage return বসে, তাই যাচাই করা হয়েছে text mode-এ, byte ধরে নয়।

৩ · Recursion theorem — যন্ত্র নিজের বর্ণনা পায়

Python-এর কৌশল Turing machine-এ নিতে হলে একটি সাহায্যকারী function লাগে। যেকোনো string w-এর জন্য Pw হলো সেই সরল যন্ত্র, যা tape মুছে w লিখে থামে। আর q(w) = ⟨Pw⟩, অর্থাৎ w থেকে “w ছাপার যন্ত্র”-এর বর্ণনা। q একটি computable function: w-এর প্রতিটি অক্ষরের জন্য “এটি লেখো, ডানে যাও” ধরনের একটি state যোগ করলেই হয়। এখানে ⟨·⟩ মানে পর্ব ৪৮-এর encoding.

নির্মাণ ৩.১ (SELF — নিজের বর্ণনা ছাপে এমন যন্ত্র)

SELF দুই অংশের যন্ত্র, আগে A চলে, তারপর B:

  • B = “tape-এ একটি যন্ত্রের অংশের বর্ণনা ⟨M⟩ থাকলে: (১) q(⟨M⟩) হিসাব করুন; (২) ফলটির সঙ্গে ⟨M⟩ জুড়ে একটি পূর্ণ যন্ত্রের বর্ণনা বানান; (৩) সেটি tape-এ লিখে থামুন।”
  • A = P⟨B⟩, অর্থাৎ যে যন্ত্র tape-এ ⟨B⟩ লিখে থামে।

এখানে ক্রমটি গুরুত্বপূর্ণ: আগে B সংজ্ঞায়িত হয়, কারণ B A-এর ওপর নির্ভর করে না। তারপর A, যা শুধু B-এর বর্ণনা লেখে। চালালে A tape-এ ⟨B⟩ লেখে। B সেটি পড়ে q(⟨B⟩) = ⟨P⟨B⟩⟩ = ⟨A⟩ পায়, তারপর ⟨A⟩ আর ⟨B⟩ জুড়ে ⟨AB⟩ = ⟨SELF⟩ লেখে। A জানে B-কে, আর B তথ্য থেকে A-কে আবার বানায়; কেউ নিজের বর্ণনা সরাসরি ধারণ করে না, তাই কোনো অসীম সিঁড়ি নেই। Python quine-এ s = '…' হলো A, আর print(s % s) হলো B.

SELF = A · B — দুই অংশের যন্ত্র

A তথ্য লেখে, B সেই তথ্য দুভাবে ব্যবহার করে; ডান পাশে Python quine-এর মিল।

The two-part machine SELF = A then B যন্ত্র SELF অংশ A = P⟨B⟩ tape-এ ⟨B⟩ লিখে থামে s = '…' (তথ্য) tape: ⟨B⟩ অংশ B ১. tape থেকে ⟨B⟩ পড়ে ২. q(⟨B⟩) = ⟨A⟩ বানায় ৩. ⟨A⟩⟨B⟩ জুড়ে ছাপে print(s % s) (কাজ) আউটপুট: ⟨AB⟩ = ⟨SELF⟩ A জানে B-কে; B তথ্য থেকে A-কে বানায়
ছবি ৫৬.১ — কোনো অংশ নিজের বর্ণনা ধারণ করে না। A-তে আছে শুধু ⟨B⟩, আর ⟨A⟩ তৈরি হয় চলার সময়, q দিয়ে।

এবার SELF-কে সাধারণ করা যাক: শুধু নিজের বর্ণনা ছাপা নয়, সেটি নিয়ে যেকোনো computable কাজ করা।

Theorem ৩.২ (Recursion theorem)

ধরি T একটি Turing machine, যা একটি function t: Σ∗ × Σ∗ → Σ∗ হিসাব করে। তাহলে এমন একটি Turing machine R আছে, যা function r: Σ∗ → Σ∗ হিসাব করে, যেখানে প্রতিটি w-এর জন্য r(w) = t(⟨R⟩, w).

সহজ ভাষায়: “নিজের বর্ণনা আর input পেলে কী করতে হবে”, এমন যেকোনো নির্দেশ T লিখুন; তাহলে এমন একটি যন্ত্র R আছে, যা শুধু input পেয়েই সেই কাজ করে, নিজের বর্ণনা নিজে জোগাড় করে। এখানে ⟨R⟩ বাইরে থেকে আসে না।

প্রমাণের রূপরেখা।

  1. R তিন অংশের: A, B, T; চলার ক্রম A → B → T. q-কে একটু বদলানো হয়: q(w)-এর যন্ত্র Pw tape-এ আগে যা আছে তা না মুছে তার ডানে w লেখে। — input w রক্ষা
  2. A = P⟨BT⟩. Input w দিয়ে শুরু করলে A চলার পরে tape-এ থাকে w⟨BT⟩। — তথ্য অংশ
  3. B tape-এর শেষের ⟨BT⟩ পড়ে q(⟨BT⟩) = ⟨A⟩ হিসাব করে, তারপর ⟨A⟩, ⟨B⟩, ⟨T⟩ জুড়ে ⟨ABT⟩ = ⟨R⟩ বানায়। — নির্মাণ ৩.১-এর B
  4. B tape-কে ⟨R, w⟩ রূপে সাজায় আর T-কে নিয়ন্ত্রণ দেয়। — জোড়া encoding
  5. T সেই input-এ t(⟨R⟩, w) হিসাব করে। প্রতিটি অংশ computable, তাই R একটি বৈধ Turing machine, আর r(w) = t(⟨R⟩, w). ∎

এখন থেকে যন্ত্রের উচ্চস্তরের বর্ণনায় লেখা যায় “নিজের বর্ণনা জোগাড় করুন”, যেমন Python-এ me = s % s. এর একটি সমতুল্য রূপ গণিতে বেশি পরিচিত।

Theorem ৩.৩ (Fixed-point theorem)

ধরি t: Σ∗ → Σ∗ একটি computable function, যা যন্ত্রের বর্ণনাকে বদলায় (কোনো string বৈধ বর্ণনা না হলে ধরি সেটি “সব কিছু reject করে” এমন যন্ত্র বোঝায়)। তাহলে এমন একটি Turing machine F আছে, যার জন্য t(⟨F⟩) এমন একটি যন্ত্রের বর্ণনা, যা F-এর সমতুল্য (একই input-এ একই আচরণ)।

প্রমাণ। F = “input w পেলে: (১) recursion theorem দিয়ে ⟨F⟩ জোগাড় করুন; (২) t(⟨F⟩) হিসাব করে একটি যন্ত্র G-এর বর্ণনা পান; (৩) G-কে w-তে নকল করুন।” ধাপ (৩) অনুযায়ী প্রতিটি w-এ F ঠিক G-এর মতো আচরণ করে, আর G-এর বর্ণনা হলো t(⟨F⟩)। ∎ অর্থাৎ যন্ত্রের বর্ণনা বদলানোর কোনো computable নিয়মই সব যন্ত্রের আচরণ বদলাতে পারে না; অন্তত একটি যন্ত্র বদলের পরেও “একই” থাকে। পর্ব ৪৯-এর Y combinator একই ধারণার lambda calculus রূপ।

এই theorem সাধারণত Stephen Kleene-এর নামে পরিচিত, আর উৎস হিসেবে প্রায়ই তাঁর ১৯৩৮ সালের একটি প্রবন্ধ উল্লেখ করা হয়; recursive function-এর ভাষায় একে “Kleene-এর দ্বিতীয় recursion theorem” বলা হয়। এখানের Turing machine রূপ আর SELF-এর A/B নির্মাণ Sipser-এর Introduction to the Theory of Computation-এর উপস্থাপনা অনুসরণ করে। স্বতঃপুনরুৎপাদনশীল যন্ত্রের ধারণা নিয়ে John von Neumann ১৯৪০-এর দশকে কাজ করেন; তাঁর লেখা মৃত্যুর পরে ১৯৬৬ সালে Arthur Burks-এর সম্পাদনায় প্রকাশিত হয়। উৎসভেদে সাল আর খুঁটিনাটি একটু আলাদা হতে পারে।

৪ · প্রয়োগ — ATM-এর দ্বিতীয় প্রমাণ, MINTM আর self-replication

পর্ব ৫১-এ ATM undecidable প্রমাণ করা হয়েছে diagonal টেবিল দিয়ে। Recursion theorem হাতে থাকলে একই ফল প্রায় এক লাইনে আসে, কারণ যন্ত্রকে আর বাইরে থেকে নিজের বর্ণনা দিতে হয় না।

Theorem ৪.১

ATM = {⟨M, w⟩ : M w গ্রহণ করে} decidable নয়।

প্রমাণ (recursion theorem দিয়ে)।

  1. বিপরীতে ধরি, H একটি decider, যা ATM decide করে। — অনুমান
  2. B = “input w পেলে: (১) recursion theorem দিয়ে নিজের বর্ণনা ⟨B⟩ জোগাড় করুন; (২) ⟨B, w⟩-এ H চালান; (৩) H accept করলে reject, H reject করলে accept করুন।” — নির্মাণ, theorem ৩.২
  3. H সবসময় থামে, তাই B-ও সবসময় থামে। যেকোনো w নিন। H ⟨B, w⟩ accept করলে H-এর দাবি “B w গ্রহণ করে”, কিন্তু B তখন reject করে। H reject করলে দাবি “B w গ্রহণ করে না”, কিন্তু B accept করে। — দুই ক্ষেত্রেই H ভুল
  4. H সব input-এ ঠিক, এই অনুমানের সঙ্গে বিরোধ; তাই H নেই। ∎

পর্ব ৫১-এর D-এর সঙ্গে পার্থক্য: সেখানে D-কে input হিসেবে ⟨D⟩ দিতে হয়েছিল, আর স্ববিরোধ ঘটেছিল একটি বিশেষ input-এ। এখানে B নিজের বর্ণনা নিজে বানায়, তাই যেকোনো w-এ, এমনকি w = ε-তেও, স্ববিরোধ ঘটে। নিচের ব্লক এটি হাতে-কলমে দেখায়। Program R quine-এর কৌশলে নিজের source me-তে বানায়, তারপর একটি “দাবিকৃত checker” claimed-কে জিজ্ঞেস করে আর উল্টো উত্তর দেয়। পাঁচটি ভিন্ন checker দিয়ে R চালানো হয়েছে; input বাজারঘরের অর্ডার কোড BG-0042.

TEMPLATE = ("t = %r\n"
            "def main(w):\n"
            "    me = t %% t           # my own source, built inside\n"
            "    return not claimed(me, w)\n")
R = TEMPLATE % TEMPLATE                         # the program R itself
print(R)

def run_and_see(src, w):                        # "just run it and look"
    env = {"claimed": run_and_see}; exec(src, env)
    return env["main"](w)

claims = {
    "always accept": lambda src, w: True,
    "always reject": lambda src, w: False,
    "even input length": lambda src, w: len(w) % 2 == 0,
    "source has 'not'": lambda src, w: "not" in src,
    "run it and see": run_and_see,
}
w = "BG-0042"
for name, claimed in claims.items():
    env = {"claimed": claimed}; exec(R, env)
    assert env["t"] % env["t"] == R            # R really holds its own text
    try:
        says, does = claimed(R, w), env["main"](w)
        verdict = "WRONG" if says != does else "right"
        print(f"{name:18} says {says!s:5} R does {does!s:5} -> {verdict}")
    except RecursionError:
        print(f"{name:18} never answers (RecursionError)")

আসল আউটপুট (ব্রাউজারের Python):

t = 't = %r\ndef main(w):\n    me = t %% t           # my own source, built inside\n    return not claimed(me, w)\n'
def main(w):
    me = t % t           # my own source, built inside
    return not claimed(me, w)

always accept      says True  R does False -> WRONG
always reject      says False R does True  -> WRONG
even input length  says False R does True  -> WRONG
source has 'not'   says True  R does False -> WRONG
run it and see     never answers (RecursionError)

প্রথমে R-এর পুরো source: লাইন ১ তথ্য অংশ, বাকিটা কাজ অংশ। assert লাইন নিশ্চিত করে যে R-এর ভেতরে বানানো me হুবহু R-এর লেখা। তারপর প্রথম চারটি checker নিজের ভবিষ্যদ্বাণীতে ভুল করে, কারণ R ঠিক তাদের উত্তরের উল্টো করে। “চালিয়ে দেখি” checker R চালায়, R আবার checker-কে ডাকে, সে আবার R চালায়… Python-এর recursion সীমা ফুরিয়ে যায়, অর্থাৎ এই checker উত্তরই দেয় না, তাই decider নয়। পাঁচটি checker ভুল দেখানো প্রমাণ নয়; প্রমাণ হলো theorem ৪.১, যা প্রতিটি সম্ভাব্য H-এ খাটে।

ন্যূনতম যন্ত্র চেনা যায় না

একটি Turing machine M-কে minimal বলা হয়, যদি M-এর সমতুল্য (একই language) কোনো যন্ত্রের বর্ণনা ⟨M⟩-এর চেয়ে ছোট না হয়। MINTM = {⟨M⟩ : M minimal}. Programmer-এর ভাষায়: “এটিই কি এই কাজের সবচেয়ে ছোট program?”

Theorem ৪.২

MINTM Turing-recognizable নয়।

প্রমাণ।

  1. বিপরীতে ধরি, MINTM-এর একটি enumerator E আছে (recognizable ⇔ enumerable, পর্ব ৪৫)। — অনুমান
  2. MINTM অসীম: প্রতিটি recognizable language-এর অন্তত একটি minimal যন্ত্র আছে, আর recognizable language অসীম সংখ্যক। — অসীম তালিকা
  3. C = “input w পেলে: (১) নিজের বর্ণনা ⟨C⟩ জোগাড় করুন; (২) E চালান যতক্ষণ না এমন একটি যন্ত্র D ছাপা হয়, যার বর্ণনা ⟨C⟩-এর চেয়ে লম্বা; (৩) D-কে w-তে নকল করুন।” — নির্মাণ
  4. ধাপ ২-এর অনুযায়ী এমন D একসময় আসবেই, আর C সব input-এ D-এর মতো আচরণ করে, তাই L(C) = L(D). — সমতুল্য
  5. কিন্তু ⟨C⟩ ছোট, ⟨D⟩ বড়, তাই D minimal নয়, অথচ E শুধু minimal যন্ত্র ছাপে। স্ববিরোধ, তাই E নেই। ∎

এই ফলটির সঙ্গে পরের অংশের যোগ স্পষ্ট: “এই কাজের সবচেয়ে ছোট program কত বড়?” প্রশ্নটি নিজেই অগণনীয়তার দিকে নিয়ে যায়।

Self-replication — রক্ষকের চোখে

Recursion theorem বলে, নিজের কপি বানানো একটি সাধারণ, যান্ত্রিক কাজ; এর জন্য কোনো বিশেষ ক্ষমতা লাগে না। ক্ষতিকর computer virus ঠিক এই ধর্ম ব্যবহার করে নিজেকে অন্য ফাইলে জুড়ে দেয়। প্রতিরক্ষার জন্য দুটি শিক্ষা। প্রথমত, “এই program কি নিজের কপি বানিয়ে ছড়াবে?” প্রশ্নটি program-এর আচরণ নিয়ে, তাই সব program-এ নিখুঁত উত্তর দেওয়া যায় না: Fred Cohen ১৯৮০-এর দশকে দেখান যে সাধারণ virus শনাক্তকরণ undecidable, আর পর্ব ৫৩-এর Rice-এর theorem এর সাধারণ রূপ দেয়। দ্বিতীয়ত, তাই বাস্তব প্রতিরক্ষা একক “নিখুঁত detector”-এর ওপর নির্ভর করে না; signature, আচরণ পর্যবেক্ষণ, sandbox, code signing আর ন্যূনতম অনুমতি একসঙ্গে কাজ করে (Cybersecurity কোর্সের পর্ব ৩৩)। এই পর্বের সব উদাহরণ শুধু নিজের কপি ছাপে; কোনো ফাইল লেখে না, কোথাও ছড়ায় না।

৫ · Kolmogorov complexity — সবচেয়ে ছোট বর্ণনা

এবার বর্ণনার দৈর্ঘ্য নিয়ে প্রশ্ন। বাজারঘরের দুটি ১৬ অক্ষরের binary string ভাবুন: 0101010101010101 আর 0110100110010110. প্রথমটি ফোনে এক বাক্যে বলা যায়: “01 আটবার”। দ্বিতীয়টির জন্য প্রায় পুরোটা পড়ে শোনাতে হয়। বাজারের ফর্দের মতো: “ডিম ১২টা” লেখা যায়, কিন্তু বারোটি আলাদা জিনিসের তালিকা ছোট করা যায় না। একটি string-এ কতটা “তথ্য” আছে, তা মাপার একটি উপায় হলো তার সবচেয়ে ছোট বর্ণনার দৈর্ঘ্য।

সংজ্ঞা ৫.১ (Kolmogorov complexity)

একটি নির্দিষ্ট universal Turing machine U ধরুন, যা binary program p পেয়ে চালায়। একটি string x-এর Kolmogorov complexity হলো

KU(x) = min { |p| : U(p) থামে আর আউটপুট x }

অর্থাৎ x ছেপে থামে এমন সবচেয়ে ছোট program-এর bit-দৈর্ঘ্য। U নির্দিষ্ট থাকলে সংক্ষেপে K(x) লেখা হয়।

কয়েকটি সরল সীমা সংজ্ঞা থেকেই আসে; প্রতিটিতে c এমন একটি ধ্রুবক, যা x-এর ওপর নির্ভর করে না।

  • K(x) ≤ |x| + c. “এই লেখাটি ছাপুন: x” ধরনের program-এ নির্দেশ অংশের দৈর্ঘ্য স্থির, বাকিটা x নিজে।
  • K(xx) ≤ K(x) + c. x-এর ছোট program চালিয়ে আউটপুট দুবার ছাপলেই হয়।
  • K(0n) ≤ log2 n + c. “n বার 0 ছাপুন” program-এ শুধু n-কে binary-তে লিখতে হয়, যা ⌊log2 n⌋ + 1 bit. এক লাখ শূন্যের string-এর বর্ণনা মাত্র কয়েক ডজন bit.

সংজ্ঞাটি একটি নির্দিষ্ট U-এর ওপর নির্ভর করে। তাহলে K কি শুধু একটি programming language-এর খেয়াল? না, আর তার কারণ নিচের theorem.

Theorem ৫.২ (Invariance theorem)

U একটি universal machine আর V যেকোনো বর্ণনা-পদ্ধতি (যেকোনো Turing machine, যা program থেকে string বানায়) হলে এমন একটি ধ্রুবক cV আছে যে সব x-এর জন্য KU(x) ≤ KV(x) + cV. ফলে দুটি universal machine U আর U′-এর জন্য একটি ধ্রুবক c আছে, যাতে সব x-এ |KU(x) − KU′(x)| ≤ c.

প্রমাণের রূপরেখা। U universal, তাই V-কে নকল করার একটি নির্দিষ্ট program অংশ iV আছে: U-কে iV আর তারপর p দিলে U ঠিক V(p)-এর আউটপুট দেয়। iV-কে এমনভাবে লেখা হয় (যেমন প্রতিটি bit দুবার লিখে শেষে 01 চিহ্ন দিয়ে) যাতে U বোঝে কোথায় iV শেষ আর p শুরু। তাহলে x-এর সবচেয়ে ছোট V-program p থেকে x-এর একটি U-program পাওয়া যায়, যার দৈর্ঘ্য |p| + cV, যেখানে cV শুধু iV-এর ওপর নির্ভর করে। U আর U′ দুটিই universal হলে দুই দিকে এটি খাটিয়ে পার্থক্য একটি ধ্রুবকে বাঁধা যায়। ∎

ধ্রুবকটি বড় হতে পারে, এক programming language-এ অন্যটির interpreter-এর মাপ। তাই ছোট string-এর K নিয়ে কথা প্রায় অর্থহীন; theorem-টির জোর বড় string-এ, যেখানে ধ্রুবকটি নগণ্য। ব্যাপারটি হাতে-কলমে দেখতে নিচের ব্লকে একটি খুব ছোট বর্ণনা-যন্ত্র U আছে। এর বর্ণনা binary string, দুই ধরনের: 0 + x মানে “x ছাপুন”; আর 1 + k + m + p মানে “m দৈর্ঘ্যের টুকরো p-কে k বার ছাপুন”, যেখানে সংখ্যাগুলো Elias gamma code-এ লেখা (z-টি শূন্য, তারপর z + 1 bit-এর সংখ্যা), যাতে কোথায় সংখ্যা শেষ তা বোঝা যায়। এই U universal নয়: এর প্রতিটি “program” থামে। তাই সব বর্ণনা shortlex ক্রমে চালিয়ে প্রতিটি string-এর সবচেয়ে ছোট বর্ণনা নিখুঁতভাবে বের করা যায়।

from itertools import product
def num(d, i):                      # Elias gamma: z zeros, then z+1 bits
    z = 0
    while i < len(d) and d[i] == "0": z, i = z + 1, i + 1
    if i + z + 1 > len(d): return None, i
    return int(d[i:i + z + 1], 2), i + z + 1
def U(d):                           # tiny machine: description -> string
    if d[:1] == "0": return d[1:]                # 0 + x   : print x
    if d[:1] != "1": return None
    k, i = num(d, 1)                             # 1 + k + |p| + p : print p k times
    m, j = num(d, i) if k else (None, i)
    if not k or not m or k < 2 or len(d) - j != m: return None
    return d[j:] * k
K = {}                              # brute force over ALL descriptions
for L in range(0, 17):              # shortlex: first hit = shortest
    for t in product("01", repeat=L):
        x = U("".join(t))
        if x is not None and x not in K: K[x] = L
for x in ["01" * 8, "0" * 16, "011" * 5, "011010011001011"]:
    print(f"{x:17} length {len(x):2}  K_U = {K[x]}")
print(" n  strings  K<n  K<=n-3  descriptions<=n-3")
for n in range(6, 15, 2):
    ks = [K["".join(t)] for t in product("01", repeat=n)]
    print(f"{n:2} {2**n:8} {sum(k < n for k in ks):4} {sum(k <= n - 3 for k in ks):7}"
          f" {2**(n - 2) - 1:19}")
for n in (8, 10, 12):                            # Berry-style search, only for U
    x = next("".join(t) for L in range(1, 20) for t in product("01", repeat=L)
             if K["".join(t)] >= n)
    print(f"first x with K_U(x) >= {n}: {x}")

আসল আউটপুট (ব্রাউজারের Python):

0101010101010101  length 16  K_U = 13
0000000000000000  length 16  K_U = 12
011011011011011   length 15  K_U = 12
011010011001011   length 15  K_U = 16
 n  strings  K<n  K<=n-3  descriptions<=n-3
 6       64    0       0                  15
 8      256    0       0                  63
10     1024    0       0                 255
12     4096    4       0                1023
14    16384    4       4                4095
first x with K_U(x) >= 8: 0000000
first x with K_U(x) >= 10: 000000000
first x with K_U(x) >= 12: 00000000001

পুনরাবৃত্ত string ছোট হয়: “01 আটবার” ১৬ bit-এর জায়গায় ১৩ bit (১ + gamma(8)-এর ৭ + gamma(2)-এর ৩ + টুকরো 01-এর ২)। অনিয়মিত ১৫ অক্ষরের string-এর জন্য এই U-এর সবচেয়ে ভালো বর্ণনা “0 + পুরো string”, ১৬ bit: একটুও ছোট হয় না। টেবিলে দেখুন, ১৪ দৈর্ঘ্যের ১৬,৩৮৪টি string-এর মধ্যে মাত্র ৪টি নিজের দৈর্ঘ্যের চেয়ে ছোট বর্ণনা পায় (দুটি একরঙা, দুটি 01/10-এর পুনরাবৃত্তি)। শেষ কলামটি যেকোনো বর্ণনা-পদ্ধতির সীমা: n − 3 বা তার কম দৈর্ঘ্যের binary বর্ণনা মোট 2n−2 − 1টি, তাই কোনো যন্ত্রই এর বেশি string-কে ৩ bit ছোট করতে পারে না। পরের অংশ এই সীমাটিই প্রমাণ করে। শেষ তিন লাইন অংশ ৭-এর জন্য: এই U-তে “KU(x) ≥ n এমন প্রথম x” খুঁজে পাওয়া যায় (0000000-এর দুই রকম বর্ণনাই ৮ bit), কারণ এখানে প্রতিটি বর্ণনা থামে।

৬ · সংকোচন-অযোগ্য string — গোনার যুক্তি

সব string কি ছোট বর্ণনা পায়? না, আর প্রমাণটি pigeonhole-এর এক লাইনের হিসাব। একটি বর্ণনা ঠিক একটি আউটপুট দেয় (U deterministic), তাই বর্ণনার সংখ্যা যত, ছোট বর্ণনা পাওয়া string-ও বড়জোর তত।

সংজ্ঞা ৬.১ আর Theorem ৬.২

x-কে c-সংকোচনযোগ্য বলা হয়, যদি K(x) ≤ |x| − c; নইলে x c-সংকোচন-অযোগ্য। 1-সংকোচন-অযোগ্য, অর্থাৎ K(x) ≥ |x|, string-কে শুধু সংকোচন-অযোগ্য বলা হয়।

Theorem: প্রতিটি n ≥ 0-এর জন্য n দৈর্ঘ্যের অন্তত একটি সংকোচন-অযোগ্য binary string আছে। আরও সাধারণভাবে, n দৈর্ঘ্যের string-এর মধ্যে c-সংকোচনযোগ্যের ভগ্নাংশ 2−c+1-এর কম।

প্রমাণ।

  1. n দৈর্ঘ্যের binary string 2nটি। — গোনা
  2. n-এর চেয়ে ছোট দৈর্ঘ্যের binary program: 1 + 2 + 4 + … + 2n−1 = 2n − 1টি। — জ্যামিতিক ধারার যোগফল
  3. প্রতিটি program বড়জোর একটি string-এর বর্ণনা। তাই K(x) < n এমন string বড়জোর 2n − 1টি, অর্থাৎ অন্তত একটি x-এর K(x) ≥ n. — pigeonhole
  4. একইভাবে, K(x) ≤ n − c মানে program-এর দৈর্ঘ্য ≤ n − c; এমন program 2n−c+1 − 1টি, তাই c-সংকোচনযোগ্য string-এর ভগ্নাংশ (2n−c+1 − 1)/2n < 2−c+1. ∎
1string: 000 001 010 0112        100 101 110 1113বর্ণনা: ε  0  14        00 01 10 115৮টি string, ৭টি বর্ণনা
হিসাব
string
ছোট বর্ণনা
সিদ্ধান্ত
  1. String গোনা। {0, 1}-এর ওপর ৩ দৈর্ঘ্যের string আটটি: 000 থেকে 111. প্রত্যেকের একটি সবচেয়ে ছোট বর্ণনা আছে; প্রশ্ন হলো সেটি ৩ bit-এর চেয়ে ছোট হতে পারে কি না।
  2. বর্ণনা গোনা। ৩-এর চেয়ে ছোট binary program: দৈর্ঘ্য ০-এর একটি (ε), দৈর্ঘ্য ১-এর দুটি, দৈর্ঘ্য ২-এর চারটি, মোট সাতটি। কোন U, তা এখানে গুরুত্বহীন।
  3. Pigeonhole. প্রতিটি বর্ণনা চালালে ঠিক একটি আউটপুট আসে (বা কিছুই আসে না)। সাতটি বর্ণনা আটটি string ঢাকতে পারে না, তাই অন্তত একটি string-এর K ≥ 3. কোনটি, যুক্তিটি বলে না।
  4. যেকোনো n. একই হিসাবে 2nটি string আর 2n − 1টি ছোট বর্ণনা। তাই প্রতিটি দৈর্ঘ্যে অন্তত একটি সংকোচন-অযোগ্য string আছে। এটি যেকোনো lossless compressor-এর জন্যও সত্য: সব ফাইল ছোট করা অসম্ভব।
  5. শক্ত রূপ। n − c বা কম দৈর্ঘ্যের বর্ণনা 2n−c+1 − 1টি। c = 10 হলে n দৈর্ঘ্যের string-এর ৫১২ ভাগের এক ভাগের কম ১০ bit ছোট হতে পারে। অর্থাৎ প্রায় সব string সংকোচন-অযোগ্যের কাছাকাছি।

এখান থেকে lossless compression-এর একটি চিরন্তন সত্য আসে, যা ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৩২-এ pigeonhole-এর দিক থেকে দেখেছেন: কোনো compressor সব ফাইল ছোট করতে পারে না, আর যে ফাইলগুলো ছোট হয় সেগুলো সব সম্ভাব্য ফাইলের মধ্যে নগণ্য অংশ। Compressor কাজ করে কারণ মানুষের বানানো ফাইল, যেমন লেখা, log আর ছবি, সেই নগণ্য, নিয়মিত অংশেই পড়ে।

এখান থেকে “এলোমেলো” শব্দের একটি নিখুঁত অর্থও আসে: একটি একক string এলোমেলো, যদি সেটি সংকোচন-অযোগ্য হয় (ভাবনার প্রশ্ন ৫ দেখুন)।

৭ · K গণনা করা যায় না — Berry-র হেঁয়ালি থেকে প্রমাণ

একটি পুরোনো হেঁয়ালি দিয়ে শুরু করা যাক: “বিশটির কম শব্দে বর্ণনা করা যায় না এমন সবচেয়ে ছোট ধনাত্মক পূর্ণসংখ্যা”। এমন সংখ্যা থাকতেই হবে, কারণ বিশটির কম শব্দের বাক্য সসীম সংখ্যক। কিন্তু উদ্ধৃত বাক্যটি নিজেই বিশটির কম শব্দে সংখ্যাটির বর্ণনা দিচ্ছে! এটি Berry-র হেঁয়ালি; Bertrand Russell ১৯০৬ সালের দিকে Oxford-এর গ্রন্থাগারিক G. G. Berry-কে এর কৃতিত্ব দেন বলে প্রচলিত। হেঁয়ালিতে সমস্যা হলো “বর্ণনা করা যায়” কথাটির অস্পষ্টতা। Kolmogorov complexity সেই কথাটিকে নিখুঁত করে, আর তখন হেঁয়ালি একটি প্রমাণে বদলে যায়।

Theorem ৭.১

Function x ↦ K(x) computable নয়: এমন কোনো Turing machine নেই, যা প্রতিটি x-এ থেমে K(x) আউটপুট দেয়।

  1. ধরি K computableprogram Cসবসময় থামে
  2. Pn বানানোপ্রথম x: K(x) ≥ nshortlex খোঁজ
  3. Pn থামেx_n ছাপেঅংশ ৬ থেকে
  4. |Pn| মাপাc + ⌊log₂ n⌋ + 1n শুধু binary-তে
  5. স্ববিরোধ1024 ≤ K ≤ 1011n = 1024, c = 1000
  6. C থাকতে পারে নাK uncomputableঅনুমান মিথ্যা
  1. অনুমান। ধরি C একটি program, যা যেকোনো x পেলে থেমে K(x) বলে দেয়। এই একটি অনুমান থেকেই স্ববিরোধ আসবে।
  2. খোঁজার program. Pn = “ε, 0, 1, 00, … shortlex ক্রমে প্রতিটি x-এ C চালান; প্রথম যে x-এ K(x) ≥ n, সেটি ছেপে থামুন।” এটি Berry-র “বর্ণনা করা যায় না এমন সবচেয়ে ছোট সংখ্যা”-র নিখুঁত রূপ।
  3. থামে। অংশ ৬ অনুযায়ী n দৈর্ঘ্যের একটি সংকোচন-অযোগ্য string আছে, তাই এমন x আছে, আর C সবসময় থামে বলে খোঁজ সসীম সময়ে শেষ হয়। ধরি আউটপুট xn, যার K(xn) ≥ n.
  4. দৈর্ঘ্য। Pn-এর কোড (C আর খোঁজার loop) n-এর ওপর নির্ভর করে না, ধরি c bit. শুধু n-কে program-এর শেষে binary-তে লিখতে হয়: ⌊log2 n⌋ + 1 bit. তাই K(xn) ≤ |Pn| = c + ⌊log2 n⌋ + 1.
  5. সংখ্যায়। c = 1000 ধরি আর n = 1024 নিই: 1024 লিখতে লাগে ১১ bit, তাই |Pn| = 1011. তাহলে 1024 ≤ K(xn) ≤ 1011, যা অসম্ভব। c যত বড়ই হোক, log n-এর চেয়ে n দ্রুত বাড়ে বলে এমন n থাকবেই (c = 1000-এ ক্ষুদ্রতম n = 1011, scratch-এ হিসাব করা)।
  6. সিদ্ধান্ত। সব ধাপ ঠিক, তাই অনুমানটিই ভুল: C নেই, K computable নয়। লক্ষ করুন, Pn নিজেই xn-এর একটি ছোট বর্ণনা: Berry-র বাক্যের মতো।

অংশ ৫-এর ছোট যন্ত্রে একই খোঁজ কেন কাজ করল? কারণ সেখানে প্রতিটি বর্ণনা থামে, তাই KU সরাসরি গোনা যায়; আর খোঁজার Python program ওই U-এর ভাষায় লেখা যায় না, তাই কোনো স্ববিরোধ নেই। Universal U-তে দুটি জিনিস একসঙ্গে ঘটে: খোঁজার program নিজেও একটি U-program, আর কিছু program কখনো থামে না।

একটি প্রলোভন, যা কাজ করে না: “|x| + c পর্যন্ত দৈর্ঘ্যের সব program চালাই; যে সবচেয়ে ছোটটি x ছাপে, তার দৈর্ঘ্যই K(x).” সমস্যা হলো কিছু program কখনো থামে না, আর কোন program এখনো চলছে কিন্তু পরে x ছাপবে, তা জানতে হলে halting problem মেটাতে হয়। সব program পালা করে চালালে (dovetailing) আমরা শুধু ওপর থেকে নামতে থাকা অনুমান পাই: “এখন পর্যন্ত পাওয়া সবচেয়ে ছোট program-এর দৈর্ঘ্য”। এই অনুমান একসময় সঠিক মানে পৌঁছায়, কিন্তু কখন পৌঁছাল, তা কখনো নিশ্চিত জানা যায় না। একে বলা হয়, K ওপর থেকে আনুমানিকভাবে গণনাযোগ্য (upper semi-computable), কিন্তু computable নয়। পর্ব ৫৫-এর Busy Beaver function-ও একই কারণে গণনার বাইরে।

৮ · সংকোচন দিয়ে ওপরের সীমা — zlib, lzma আর বাজারঘরের log

K গণনা করা না গেলেও ওপরের সীমা সহজ। একটি lossless compressor-এর decompressor D একটি নির্দিষ্ট program, তাই “D, তারপর সংকুচিত ফাইল z” মিলে x-এর একটি বর্ণনা:

K(x) ≤ 8 · |z| + cD

এখানে |z| সংকুচিত byte-সংখ্যা আর cD decompressor-এর মাপ। zlib (যা LZ77 ধাঁচে পুনরাবৃত্তি খুঁজে তারপর Huffman code ব্যবহার করে) বা lzma যত ছোট করবে, K-এর ওপরের সীমা তত শক্ত হবে। কিন্তু উল্টো দিকে কিছু পাওয়া যায় না: ফাইল ছোট না হওয়া মানে এই নয় যে K বড়।

সত্যিকারের run. চার রকম ১,০০,০০০ byte-এর ডেটা: seed 56 দিয়ে বানানো এলোমেলো byte; বাজারঘরের কাল্পনিক অর্ডার log (প্রতি লাইনে অর্ডার কোড, এলাকা, অবস্থা আর টাকার অঙ্ক); সেই log-এর byte-গুলোই এলোমেলো ক্রমে সাজানো; আর একটিমাত্র লাইন বারবার। Python-এর standard library-র তিনটি compressor দিয়ে মাপা হয়েছে।

rng = random.Random(56)                       # fixed seed: same data every run
rand = rng.randbytes(N)                       # random bytes
...                                           # order log: BG-0001,Sylhet,packed,4600 ...
shuf = bytearray(log); rng.shuffle(shuf)      # same bytes, order destroyed
for name, d in [("random", rand), ("order log", log),
                ("shuffled log", bytes(shuf)), ("one line x", same)]:
    z = len(zlib.compress(d, 9)); x = len(lzma.compress(d)); b = len(bz2.compress(d))

সত্যিকারের run (ডেস্কটপ, Python 3.14.4, uv দিয়ে বানানো প্রকল্প, শুধু standard library):

~/bazarghar-toc$ uv run python compress_sizes.py
python 3.14.4 | zlib 1.3.1.zlib-ng
data             bytes   zlib-9    lzma     bz2
random          100000   100041  100064  100830
order log       100000    17405   15044   12960
shuffled log    100000    67013   61960   63959
one line x      100000      296     176     125
first log line: BG-0001,Sylhet,packed,4600

চারটি সারি চারটি শিক্ষা দেয়। এলোমেলো byte কোনো compressor ছোট করতে পারেনি, উল্টো ৪১ থেকে ৮৩০ byte বেড়েছে: ফরম্যাটের নিজস্ব খরচ, আর অংশ ৬-এর গোনার যুক্তির বাস্তব রূপ। অর্ডার log ১৩–১৭% আকারে নেমেছে, কারণ “BG-”, এলাকার নাম আর অবস্থার শব্দ বারবার আসে। এলোমেলো করা log-এ একই byte আছে, কিন্তু ক্রম নষ্ট; তাই পুনরাবৃত্তি নেই, শুধু অক্ষরের অসম বণ্টন (কমা আর অঙ্ক বেশি) থেকে প্রায় ৬২–৬৭% পর্যন্ত নামে, যা entropy-র সীমার কাছাকাছি (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৬৮)। একই লাইন বারবার কয়েকশো byte-এ নামে।

সবচেয়ে বড় শিক্ষা প্রথম সারিতে লুকানো। “এলোমেলো” byte আসলে seed 56 আর Python-এর random generator থেকে এসেছে; পুরো script এক কিলোবাইটের কাছাকাছি। তাই এই ১,০০,০০০ byte-এর K সর্বোচ্চ কয়েক হাজার bit, অথচ কোনো compressor সেটি ধরতে পারেনি। Compressor শুধু নির্দিষ্ট কিছু নিয়মিততা খোঁজে; “এটি একটি নির্দিষ্ট seed-এর generator আউটপুট” ধরার কোনো সাধারণ পদ্ধতি থাকলে K computable হয়ে যেত। Compression তাই ওপরের সীমা দেয়, কখনো নিচের সীমা নয়।

LZ77-এর মূল ধারণা নিজে চালিয়ে দেখুন। নিচের JavaScript ব্লকে একটি খুব ছোট compressor আছে: প্রতিটি অবস্থানে আগের ২৫৫ অক্ষরে সবচেয়ে লম্বা মিল খোঁজে; চার বা বেশি অক্ষরের মিল পেলে (কত পেছনে, কত লম্বা) জোড়া লেখে, যার খরচ ধরা হয়েছে ৩ byte, নইলে অক্ষরটি নিজেই (১ byte). Decoder আবার মূল লেখা বানিয়ে মিলিয়ে দেখে।

// Tiny LZ77-style compressor: a literal costs 1 byte, a (back, len) copy 3 bytes
function compress(s, win = 255) {
  const out = [];
  for (let i = 0; i < s.length; ) {
    let len = 0, back = 0;
    for (let j = Math.max(0, i - win); j < i; j++) {
      let k = 0;
      while (k < 255 && s[j + k] === s[i + k]) k++;
      if (k > len) { len = k; back = i - j; }
    }
    if (len >= 4) { out.push([back, len]); i += len; } else out.push(s[i++]);
  }
  return out;
}
function expand(t) {                             // decoder: rebuild the text
  let s = "";
  for (const x of t) if (typeof x === "string") s += x;
    else for (let k = 0; k < x[1]; k++) s += s[s.length - x[0]];
  return s;
}
const size = t => t.reduce((n, x) => n + (typeof x === "string" ? 1 : 3), 0);
let seed = 56; const rnd = n => (seed = (seed * 48271) % 2147483647) % n;  // fixed seed
const pick = a => a[rnd(a.length)];
let log = "";
for (let i = 1; log.length < 3000; i++)
  log += `BG-${String(i).padStart(4, "0")},${pick(["Dhaka", "Khulna", "Sylhet"])},` +
         `${pick(["paid", "packed", "shipped"])}\n`;
log = log.slice(0, 3000);
const sh = log.split("");                        // same letters, order destroyed
for (let i = sh.length - 1; i > 0; i--) { const j = rnd(i + 1); [sh[i], sh[j]] = [sh[j], sh[i]]; }
const noise = Array.from({ length: 3000 }, () => String.fromCharCode(33 + rnd(94))).join("");
for (const [name, s] of [["order log", log], ["shuffled log", sh.join("")], ["random text", noise]]) {
  const t = compress(s), n = size(t);
  console.log(`${name.padEnd(13)} ${s.length} -> ${n} bytes (${(100 * n / s.length).toFixed(1)}%), round trip ok: ${expand(t) === s}`);
}

আসল আউটপুট (ব্রাউজারের JavaScript):

order log     3000 -> 825 bytes (27.5%), round trip ok: true
shuffled log  3000 -> 2998 bytes (99.9%), round trip ok: true
random text   3000 -> 3000 bytes (100.0%), round trip ok: true

অর্ডার log চার ভাগের এক ভাগের একটু বেশিতে নামে, আর decoder হুবহু আগের লেখা ফেরত দেয় (lossless). এলোমেলো করা log-এ এই compressor প্রায় কিছুই পায় না, কারণ এখানে শুধু পুনরাবৃত্তি খোঁজা হয়, অক্ষরের অসম বণ্টন কাজে লাগানো হয় না; zlib সেই কাজটি Huffman ধাপে করে বলে ওপরের সত্যিকারের run-এ এলোমেলো log-ও ৬৭%-এ নেমেছিল। এলোমেলো লেখা একটুও নামে না। ব্লকটি বদলে দেখুন: এলাকার তালিকায় আরও নাম যোগ করলে বা win ছোট করলে অনুপাত কীভাবে বদলায়।

এই ওপরের সীমা বাস্তবেও কাজে লাগে। Minimum description length (MDL) নীতি, যা সাধারণত Jorma Rissanen-এর ১৯৭৮ সালের কাজের সঙ্গে যুক্ত, বলে: যে model আর তার সাহায্যে লেখা ডেটা মিলিয়ে সবচেয়ে ছোট বর্ণনা দেয়, সেটিই ভালো model. এখানেও আসল K-এর বদলে একটি computable বর্ণনা-পদ্ধতি বসানো হয় (ভাবনার প্রশ্ন ৪)।

প্রায় একই সময়ে তিনজন স্বাধীনভাবে এই ধারণায় পৌঁছান বলে সাধারণত বলা হয়: Ray Solomonoff (১৯৬০ সালের একটি প্রতিবেদন আর ১৯৬৪ সালের প্রবন্ধ, আরোহী অনুমানের প্রশ্ন থেকে), Andrey Kolmogorov (১৯৬৫, তথ্যের পরিমাণের সংজ্ঞা থেকে), আর Gregory Chaitin (১৯৬০-এর দশকের মাঝামাঝি থেকে)। তাই কেউ কেউ একে Kolmogorov–Chaitin complexity বা algorithmic information-ও বলেন। বিষয়টির প্রচলিত পাঠ্যবই Ming Li আর Paul Vitányi-এর An Introduction to Kolmogorov Complexity and Its Applications. প্রথম প্রকাশের সাল আর অগ্রাধিকার নিয়ে উৎসভেদে বর্ণনা একটু আলাদা।

আরও গভীরে: এই পর্বের K “plain” complexity; গবেষণায় বেশি ব্যবহৃত হয় prefix-free রূপ, যেখানে কোনো বৈধ program অন্য program-এর শুরুর অংশ নয়, আর তখন সব program-এর থামার সম্ভাবনা যোগ করে Chaitin-এর Ω সংখ্যা পাওয়া যায়, যা এলোমেলো আর অগণনীয়। Chaitin-এর incompleteness theorem অনুযায়ী, সামঞ্জস্যপূর্ণ আর যান্ত্রিকভাবে যাচাইযোগ্য যেকোনো গাণিতিক তত্ত্বের জন্য একটি সংখ্যা L আছে, যার পরে সেই তত্ত্ব কোনো নির্দিষ্ট x-এর জন্য “K(x) > L” প্রমাণ করতে পারে না, যদিও প্রায় সব x-এর জন্য তা সত্য। অসীম ক্রমের এলোমেলোতার নিখুঁত সংজ্ঞা Per Martin-Löf ১৯৬৬ সালে দেন, আর পরে দেখা যায় এটি সংকোচন-অযোগ্যতার ভাষায় সমতুল্যভাবে বলা যায়।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • Recursion theorem-এর বক্তব্য লিখুন। যেকোনো computable t(·, ·)-এর জন্য একটি যন্ত্র R আছে, যাতে সব w-এ r(w) = t(⟨R⟩, w).
  • Quine কীভাবে কাজ করে? তথ্য অংশে বাকি program-এর লেখা; কাজ অংশ সেই লেখা একবার ছাঁচ, একবার উপাদান হিসেবে ব্যবহার করে।
  • Recursion theorem দিয়ে ATM undecidable দেখান। B নিজের ⟨B⟩ জোগাড় করে H(⟨B, w⟩)-এর উল্টো করে; যেকোনো w-এ স্ববিরোধ।
  • প্রতিটি n-এ সংকোচন-অযোগ্য string আছে কেন? 2nটি string, কিন্তু n-এর চেয়ে ছোট program 2n − 1টি।
  • K(x) কি computable? zlib-এর আউটপুট কী বলে? না, Berry-ধাঁচের প্রমাণ; zlib শুধু ওপরের সীমা দেয়।

৯ · AI-এর যুগে recursion theorem আর Kolmogorov complexity

এই বিষয়ে AI assistant-এর কিছু ভুল বারবার দেখা যায়: open(__file__) দিয়ে নিজের ফাইল পড়া “quine”, বৃত্তাকার recursion theorem প্রমাণ, “zlib দিয়ে K মাপা যায়” ধরনের দাবি, আর বানানো ইতিহাস। নিচের টেবিলে প্রতিটি ধরার উপায়।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
Quine-এ নিজের ফাইল পড়া বা input থেকে source নেওয়াProgram-কে string হিসেবে exec দিয়ে চালান (অংশ ২-এর ব্লক); কোনো ফাইল না থাকলেও আউটপুট == source হতে হবে
Recursion theorem-এর প্রমাণে “B নিজেকে ডেকে ⟨B⟩ পায়”দেখুন A-তে ঠিক ⟨B⟩ (বা ⟨BT⟩) লেখা আছে কি না, আর ⟨A⟩ q দিয়ে বানানো হচ্ছে কি না
“zlib-এর আকারই K(x)” বা “এই ফাইল সংকুচিত হয় না, তাই এলোমেলো”Seed দিয়ে বানানো এলোমেলো byte-এর উদাহরণ মনে করুন: compression শুধু ওপরের সীমা
“|x| + c পর্যন্ত সব program চালিয়ে K(x) বের করা যায়”জিজ্ঞেস করুন, না-থামা program-এর কী হবে; উত্তরে halting problem আসতেই হবে
Shannon entropy আর K একই বলাEntropy একটি উৎসের গড়, K একটি একক string-এর; seed-ভিত্তিক ডেটায় দুটি অনেক আলাদা
বানানো ইতিহাস (“Kolmogorov ১৯৫০ সালে K আবিষ্কার করেন”)Sipser বা Li–Vitányi-এর বইয়ে মিলিয়ে নিন

AI-কে কাজে লাগানোর ভালো উপায়: নির্মাণের প্রতিটি অংশ আলাদা করে চাওয়া, প্রতিটি দাবির জন্য একটি যাচাই-কোড চাওয়া যা আপনি নিজে চালাবেন, আর সীমার দিক (ওপরের না নিচের) স্পষ্ট করে জিজ্ঞেস করা।

আমি গণনার তত্ত্ব শিখছি। চারটি কাজ করো। ১. Python-এ এমন একটি quine দাও যা কোনো ফাইল পড়ে না, input নেয় না। সঙ্গে একটি যাচাই-script দাও, যা program-টিকে string হিসেবে exec দিয়ে চালিয়ে আউটপুট আর source মেলায়। ২. Sipser-এর রীতিতে recursion theorem-এর প্রমাণ সংখ্যাযুক্ত ধাপে লেখো: A, B আর T কী, q(w) কী, আর কেন কোনো বৃত্তাকার যুক্তি নেই। ৩. K(x) কেন computable নয়, Berry-ধাঁচের প্রমাণে লেখো; প্রতিটি ধাপে দৈর্ঘ্যের হিসাব দাও। ৪. zlib-এর আকার K(x)-এর ওপরের না নিচের সীমা, এক লাইনে বলো। কোনো সাল বা নাম নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১von Neumann-এর স্বতঃপুনরুৎপাদনশীল যন্ত্র, জীবকোষের DNA আর SELF-এর A/B নির্মাণের মধ্যে মিল কোথায়? একই বর্ণনা কেন দুভাবে ব্যবহার করতে হয়?

১৯৪০-এর দশকে John von Neumann জিজ্ঞেস করেন: একটি যন্ত্র কি নিজের মতো আরেকটি যন্ত্র বানাতে পারে, আর বানানো যন্ত্রটিও আবার পারবে? সরল উত্তর মনে হয় “না”, কারণ নির্মাতাকে নিজের চেয়ে জটিল কিছুর বর্ণনা রাখতে হবে বলে মনে হয়। তাঁর সমাধান ছিল তিন অংশের: একটি সার্বজনীন নির্মাতা, যা যেকোনো বর্ণনা পড়ে সেই যন্ত্র বানায়; একটি নকলকারী, যা বর্ণনাটি না বুঝে শুধু হুবহু কপি করে; আর একটি নিয়ন্ত্রক, যা দুটিকে পালা করে চালায়। বর্ণনায় থাকে নির্মাতা, নকলকারী আর নিয়ন্ত্রকের নকশা, কিন্তু বর্ণনার নিজের কপি নয়। নির্মাতা নতুন দেহ বানায়, নকলকারী বর্ণনাটি কপি করে নতুন দেহে বসিয়ে দেয়।

SELF-এ ঠিক এই ভাগ। A-তে আছে ⟨B⟩, অর্থাৎ বর্ণনা। B সেটিকে দুভাবে ব্যবহার করে: q দিয়ে “অনুবাদ” করে ⟨A⟩ বানায় (বর্ণনাকে নির্দেশ হিসেবে পড়া), আর ⟨B⟩-কে হুবহু রেখে দেয় (বর্ণনাকে শুধু তথ্য হিসেবে কপি করা)। Python quine-এ s একবার ছাঁচ, একবার ঘরে বসানোর উপাদান। অসীম সিঁড়ি এড়ানোর চাবি এই দ্বৈত ব্যবহার; শুধু অনুবাদ করলে বর্ণনা হারায়, শুধু কপি করলে দেহ তৈরি হয় না।

জীবকোষে DNA-ও দুভাবে ব্যবহৃত হয়: transcription আর translation-এর মাধ্যমে তা protein তৈরির নির্দেশ হিসেবে পড়া হয়, আর replication-এর সময় তা অর্থ না বুঝেই হুবহু কপি হয়। von Neumann-এর এই কাজ DNA-র গঠন আবিষ্কারের (১৯৫৩) আগের, যদিও জীববিজ্ঞানের আসল প্রক্রিয়া এই সরল ছবির চেয়ে অনেক জটিল। Recursion theorem এই ধারণার বিমূর্ত, গাণিতিক রূপ: যেকোনো যথেষ্ট শক্তিশালী গণনা-ব্যবস্থায় নিজের বর্ণনা পাওয়া একটি সাধারণ, যান্ত্রিক কাজ।

মূল উপলব্ধি: নিজের কপি বানাতে বর্ণনাকে দুভাবে লাগে, একবার পড়ে মানার নির্দেশ হিসেবে আর একবার না বুঝে নকলের তথ্য হিসেবে; SELF, quine আর von Neumann-এর যন্ত্র একই নকশা।

প্র ০২Ken Thompson-এর “Reflections on Trusting Trust”-এ self-reference কীভাবে একটি compiler-এর লুকানো ঝুঁকি দেখায়? রক্ষকেরা এর বিরুদ্ধে কী করেন?

Ken Thompson তাঁর Turing Award বক্তৃতায় (প্রবন্ধ আকারে ১৯৮৪ সালে প্রকাশিত) একটি চিন্তা-পরীক্ষা দেন, যার শুরুই quine দিয়ে। একটি compiler নিজের source থেকে নিজেকে compile করতে পারে। এখন কল্পনা করুন, compiler-এর binary-তে এমন একটি পরিবর্তন আছে, যা দুটি জিনিস চেনে: কোনো নির্দিষ্ট program compile হলে তাতে একটি গোপন দুর্বলতা ঢোকায়, আর compiler নিজে compile হলে এই পরিবর্তনটিই আবার নতুন binary-তে ঢুকিয়ে দেয়। দ্বিতীয় কাজটির জন্য পরিবর্তনটিকে নিজের কোড জানতে হয়, আর সেটিই quine বা recursion theorem-এর কৌশল। ফল: compiler-এর source পুরো পরিষ্কার, তবু প্রতিটি নতুন binary-তে পরিবর্তনটি বেঁচে থাকে।

Thompson-এর শিক্ষা ছিল, যে code আপনি নিজে পুরোপুরি বানাননি, শুধু তার source পড়ে তাকে পুরো বিশ্বাস করা যায় না; বিশ্বাস পুরো tool-শৃঙ্খলের ওপর নির্ভর করে। এটি তাত্ত্বিক বিষয়টির একটি বাস্তব মুখ: “এই binary-তে কি লুকানো আচরণ আছে?” সাধারণভাবে একটি semantic প্রশ্ন, আর পর্ব ৫৩-এর Rice-এর theorem অনুযায়ী সব ক্ষেত্রে যান্ত্রিকভাবে নিখুঁত উত্তর দেওয়া যায় না।

রক্ষকেরা তাই নিখুঁত detector-এর বদলে স্বাধীন যাচাইয়ের পথ নেন। Reproducible build-এ একই source থেকে স্বাধীন মানুষ আলাদা যন্ত্রে build করে byte-ধরে একই binary পান কি না দেখেন। David A. Wheeler ২০০০-এর দশকে “diverse double-compiling” নামে একটি পদ্ধতি প্রস্তাব করেন: সন্দেহভাজন compiler-এর source একটি স্বাধীনভাবে তৈরি, ভিন্ন compiler দিয়ে compile করে তারপর ফল মেলানো। এর সঙ্গে code signing, নির্ভরযোগ্য উৎসের হিসাব রাখা আর ছোট, যাচাইযোগ্য bootstrap compiler থেকে শুরু করার উদ্যোগও আছে। এই সব পদ্ধতি সাধারণ সমস্যাটি সমাধান করে না; তারা প্রশ্নটি এমনভাবে বদলায় যাতে তুলনা দিয়ে উত্তর মেলে।

মূল উপলব্ধি: Self-reference দিয়ে একটি পরিবর্তন নিজেকে tool-শৃঙ্খলে টিকিয়ে রাখতে পারে; প্রতিরক্ষা নিখুঁত বিশ্লেষণের বদলে স্বাধীন, পুনরুৎপাদনযোগ্য তুলনার ওপর দাঁড়ায়।

প্র ০৩Invariance theorem বলে K একটি ধ্রুবক পর্যন্ত নির্দিষ্ট। তাহলে কেউ যদি বলেন “এই ২০ bit-এর string এলোমেলো”, সেই দাবির অর্থ কী? ধ্রুবকটি বাস্তবে কতটা গুরুত্বপূর্ণ?

Invariance theorem-এর ধ্রুবক হলো এক universal machine-এ অন্যটির interpreter-এর মাপ। Python থেকে একটি ছোট Lisp-এর interpreter কয়েক হাজার bit হতে পারে, আর অদ্ভুত ভাষার ক্ষেত্রে আরও বেশি। এখন কল্পনা করুন একটি বিচিত্র universal machine U′, যার নিয়ম: “program 0 মানে নির্দিষ্ট ২০ bit-এর string s ছাপুন; অন্য program 1p মানে U-তে p চালান।” U′ universal, আর KU′(s) = 1. অর্থাৎ যেকোনো একক string-কে একটি বিশেষ যন্ত্রে খুব সরল দেখানো যায়। ধ্রুবকটি এখানে প্রায় ২০ bit, ঠিক s-এর মাপ।

তাই “এই ২০ bit-এর string এলোমেলো” কথাটির কোনো যন্ত্র-নিরপেক্ষ অর্থ নেই। Kolmogorov complexity-র বক্তব্য অসীম পরিবার নিয়ে: n বড় হতে থাকলে কোনো ক্রমের K কীভাবে বাড়ে, বা একটি বড় string-এর K তার দৈর্ঘ্যের কতটা কাছে। এক লাখ bit-এর string-এর জন্য কয়েক হাজার bit-এর ধ্রুবক নগণ্য; ২০ bit-এর জন্য সেটিই সব। পরিসংখ্যানে যেমন একটি মুদ্রা তিনবার হেড পড়লে কিছু বলা যায় না, কিন্তু দশ হাজারবারের পরে বলা যায়, এখানেও তেমন।

বাস্তবে এর দুটি প্রভাব। প্রথমত, compression-ভিত্তিক মাপ (যেমন অংশ ৮-এর zlib সংখ্যা) শুধু বড় ফাইলে অর্থবহ; কয়েক byte-এর ফাইলে ফরম্যাটের খরচই ফল ঠিক করে দেয়, যেমন এলোমেলো byte-এ ৪১ byte বাড়তি। দ্বিতীয়ত, তাত্ত্বিক ফলগুলো সাধারণত “+ O(1)” বা “+ O(log n)” দিয়ে লেখা হয়, আর সেটিকে গুরুত্বের সঙ্গে পড়তে হয়। “K(x) = 37” ধরনের নির্দিষ্ট সংখ্যা লিখলে একটি নির্দিষ্ট যন্ত্র উল্লেখ করতে হয়, যেমন অংশ ৫-এর ছোট যন্ত্র।

মূল উপলব্ধি: K একটি ধ্রুবক পর্যন্ত যন্ত্র-নিরপেক্ষ, তাই এর অর্থ বড় string আর অসীম পরিবারে; ছোট একক string-এর এলোমেলোতা নিয়ে যন্ত্র-নিরপেক্ষ দাবি করা যায় না।

প্র ০৪K গণনা করা না গেলে MDL বা compression দিয়ে মিল মাপার মতো পদ্ধতি কাজ করে কীভাবে? কী হারায়, আর কোথায় এগুলো ভুল পথে নিতে পারে?

এই পদ্ধতিগুলো K-এর জায়গায় একটি নির্দিষ্ট, computable বর্ণনা-পদ্ধতি বসায়: একটি compressor, বা model-এর একটি শ্রেণি আর তার encoding. সেই পদ্ধতির ভেতরে “সবচেয়ে ছোট বর্ণনা” হিসাব করা যায়, কারণ পদ্ধতিটি universal নয়, ঠিক অংশ ৫-এর ছোট যন্ত্রের মতো। MDL-এ প্রশ্নটি হয়: কোন model-এর বর্ণনা আর সেই model দিয়ে লেখা ডেটার বর্ণনা মিলিয়ে মোট দৈর্ঘ্য সবচেয়ে কম? জটিল model নিজের বর্ণনায় বেশি bit খরচ করে, তাই শুধু ডেটায় মানানোর জন্য অপ্রয়োজনীয় জটিলতা শাস্তি পায়। এটি overfitting-এর বিরুদ্ধে একটি নীতিগত যুক্তি দেয় (Machine learning-এ এর আরেক রূপ regularization).

Compression দিয়ে মিল মাপার ধারণায় দুটি ফাইল x আর y-কে একসঙ্গে সংকুচিত করা হয়। দুটির মিল থাকলে একসঙ্গে সংকুচিত আকার আলাদা আকারের যোগফলের চেয়ে অনেক কম হয়, কারণ compressor একটির নিয়মিততা দিয়ে অন্যটি লেখে। এভাবে ভাষা শনাক্তকরণ বা নথির গুচ্ছ বানানোর পরীক্ষা করা হয়েছে, কোনো বিশেষ feature না বানিয়েই।

যা হারায়: আসল K সব computable নিয়মিততা ধরে, compressor শুধু নিজের চেনা ধাঁচগুলো। অংশ ৮-এর seed-ভিত্তিক byte-এ zlib কিছুই পায়নি, অথচ নিয়মিততা ছিল চরম। তাই দুটি ফাইল ভিন্ন নিয়মে একই উৎস থেকে এলে compressor তাদের মিল ধরতে না-ও পারে। আরও আছে window-এর সীমা: zlib শুধু শেষ ৩২ কিলোবাইটের মধ্যে মিল খোঁজে, তাই বড় ফাইলে দূরের মিল হারায়। আর ফরম্যাটের নিজস্ব খরচ ছোট ফাইলে ফল বিকৃত করে। ভুল পথ এড়াতে তাই compressor বেছে নেওয়া, যথেষ্ট বড় ডেটা নেওয়া আর একটি সরল baseline-এর সঙ্গে তুলনা করা দরকার।

মূল উপলব্ধি: বাস্তব পদ্ধতি K-এর বদলে একটি computable, অ-universal বর্ণনা-পদ্ধতি ব্যবহার করে; তারা ঠিক ততটুকুই দেখে, যতটুকু নিয়মিততা সেই পদ্ধতি চেনে।

প্র ০৫π-এর অঙ্ক, একটি seed-ভিত্তিক random generator-এর আউটপুট আর মুদ্রা ছুড়ে পাওয়া ক্রম: Kolmogorov-এর অর্থে কোনটি এলোমেলো? Cryptography-র “এলোমেলো দেখানো” কেন আলাদা ধারণা?

π-এর প্রথম দশ লাখ অঙ্ক অনেক পরিসংখ্যানিক পরীক্ষায় এলোমেলো দেখায়: প্রতিটি অঙ্ক প্রায় সমান হারে আসে, আর সহজ কোনো ধাঁচ চোখে পড়ে না। কিন্তু Kolmogorov-এর অর্থে এরা মোটেও এলোমেলো নয়। “π-এর প্রথম n অঙ্ক ছাপুন” একটি ছোট program, যার দৈর্ঘ্য একটি ধ্রুবক আর n লেখার log n bit. তাই K প্রায় log n, অথচ দৈর্ঘ্য n. একই কথা একটি seed-ভিত্তিক random generator-এর জন্য: অংশ ৮-এর এক লাখ byte আসলে “seed 56, এই generator, এত byte”-এর বর্ণনা।

মুদ্রা ছুড়ে পাওয়া ক্রমের ক্ষেত্রে অংশ ৬-এর গোনার যুক্তি বলে, n বার ছুড়লে ক্রমটি সংকোচন-অযোগ্যের কাছাকাছি হওয়ার সম্ভাবনা প্রায় নিশ্চিত: c-সংকোচনযোগ্য হওয়ার সম্ভাবনা 2−c+1-এর কম। কিন্তু কোনো একটি নির্দিষ্ট ফলাফল সত্যিই সংকোচন-অযোগ্য কি না, তা প্রমাণ করা যায় না, কারণ K computable নয়।

Cryptography-র প্রয়োজন অন্য। একটি key-generator-এর আউটপুট Kolmogorov-অর্থে এলোমেলো নয় (ছোট seed থেকে আসে), কিন্তু তাতে সমস্যা নেই, যদি কোনো দক্ষ (polynomial সময়ের) পদ্ধতি সেটিকে সত্যিকারের এলোমেলো ক্রম থেকে আলাদা করতে না পারে। অর্থাৎ cryptography গণনার খরচের ভিত্তিতে এলোমেলোতা সংজ্ঞায়িত করে, আর Kolmogorov সংজ্ঞায়িত করে বর্ণনার দৈর্ঘ্য দিয়ে, সময়ের হিসাব ছাড়া। এমন generator আদৌ থাকে কি না, তা complexity theory-র খোলা প্রশ্নের সঙ্গে জড়িত (পর্ব ৭৬-এ one-way function). Lottery বা পরীক্ষার আসন বণ্টনের মতো কাজে তাই দুটির কোনোটিই একা যথেষ্ট নয়; ভালো entropy-র উৎস আর পরীক্ষিত cryptographic generator দুটোই লাগে।

মূল উপলব্ধি: এলোমেলো “দেখানো” আর সংকোচন-অযোগ্য হওয়া আলাদা; π বা seed-ভিত্তিক ক্রমের K ছোট, আর cryptography গণনার খরচ দিয়ে এলোমেলোতা মাপে, বর্ণনার দৈর্ঘ্য দিয়ে নয়।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। quine_check.py আর tiny_machine_k.py ব্লক বদলে নিজের ধারণাও চালিয়ে দেখতে পারেন।

  1. নকশা: Recursion theorem ব্যবহার করে এমন একটি Turing machine M-এর উচ্চস্তরের বর্ণনা দিন, যার language ঠিক {⟨M⟩}, অর্থাৎ M শুধু নিজের বর্ণনা গ্রহণ করে আর বাকি সব input reject করে। M কি decider? Python-এ একই ধারণার একটি ছোট program-এর রূপরেখা দিন।

    M = “input w পেলে: (১) recursion theorem দিয়ে নিজের বর্ণনা ⟨M⟩ জোগাড় করুন; (২) w আর ⟨M⟩ অক্ষরে অক্ষরে মেলান; (৩) মিললে accept, না মিললে reject করুন।” Theorem ৩.২-এ t(⟨R⟩, w) = “w = ⟨R⟩ হলে accept, নইলে reject” নিলে R-ই এই M. দুটি সসীম string মেলানো সবসময় শেষ হয়, তাই M একটি decider, আর L(M) = {⟨M⟩}. Python-এ: t = '...' ছাঁচে def main(w): me = t % t; return w == me রাখুন। Scratch-এ এমন একটি program বানিয়ে যাচাই করা হয়েছে: নিজের source দিলে True, আর source-এর শেষ অক্ষর বাদ দিলে বা একটি অক্ষর বদলালে False.

  2. প্রমাণ: (ক) একটি ধ্রুবক c আছে যাতে সব binary x-এর জন্য K(xx) ≤ K(x) + c, প্রমাণ করুন। (খ) x আর y-এর সবচেয়ে ছোট program দুটি পাশাপাশি রেখে K(xy) ≤ K(x) + K(y) + d প্রমাণ করতে চাইলে কোথায় আটকায়, আর কী যোগ করলে প্রমাণ চলে?

    (ক) ধরি p হলো x-এর সবচেয়ে ছোট program, |p| = K(x). একটি নির্দিষ্ট program অংশ D লিখুন: “আমার পরে যে program আছে তাকে U-তে চালাও, আউটপুট দুবার ছাপো।” D-এর দৈর্ঘ্য c, x-এর ওপর নির্ভর করে না। D-এর পরে p রাখলে program-টি xx ছাপে, তাই K(xx) ≤ |p| + c = K(x) + c. ∎ (খ) সমস্যা হলো সীমানা: x-এর program p আর y-এর program q পাশাপাশি রাখলে U জানে না কোথায় p শেষ। সীমানা চিহ্নিত করতে |p| লিখতে হয়, যাতে প্রায় 2 log K(x) bit লাগে (যেমন প্রতিটি bit দুবার লিখে)। তাই জোড়া দিয়ে পাওয়া যায় K(xy) ≤ K(x) + K(y) + 2 log2 K(x) + d. জানা আছে যে plain K-তে এই ধরনের log-পদ সাধারণভাবে পুরো বাদ দেওয়া যায় না। Prefix-free রূপে program নিজেই নিজের শেষ জানায়, তাই সেখানে এই সমস্যা অনেকটা কমে।

  3. হিসাব: (ক) ১০ দৈর্ঘ্যের binary string-এর মধ্যে সর্বোচ্চ কতটির K < 7 হতে পারে, যেকোনো U-এর জন্য? মোটের কত শতাংশ? (খ) বাজারঘরের একটি ফাইলের zlib-সংকুচিত আকার ২,০০০ byte, আর decompressor-এর মাপ ধরুন ৪০,০০০ bit. K(ফাইল) সম্পর্কে নিশ্চিতভাবে কী বলা যায়, আর কী বলা যায় না?

    (ক) K < 7 মানে program-এর দৈর্ঘ্য ০ থেকে ৬: 1 + 2 + 4 + 8 + 16 + 32 + 64 = 27 − 1 = 127টি program. প্রতিটি বড়জোর একটি string দেয়, তাই সর্বোচ্চ ১২৭টি string, মোট ১,০২৪টির প্রায় ১২.৪%. বাকি অন্তত ৮৯৭টির K ≥ 7. (খ) K(ফাইল) ≤ 8 × 2000 + 40000 = 56,000 bit (ধ্রুবকের ভেতরে decompressor আর জোড়ার খরচ)। এটি শুধু ওপরের সীমা: আসল K এর চেয়ে অনেক কম হতে পারে (যেমন ফাইলটি কোনো ছোট program-এর আউটপুট হলে), আর কোনো নিচের সীমা এখান থেকে আসে না।

  4. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “K computable. Algorithm: x দেওয়া আছে। দৈর্ঘ্য ০, ১, ২, … ক্রমে প্রতিটি program p চালান। প্রথম যে p x ছাপে, তার দৈর্ঘ্যই K(x). যেহেতু ‘x ছাপুন’ program-এর দৈর্ঘ্য |x| + c, খোঁজ সসীম সময়ে শেষ হয়। ∎” কোথায় ভুল?

    “প্রতিটি program p চালান” ধাপে। কিছু ছোট program কখনো থামে না। Algorithm যদি সেগুলোর একটির শেষের জন্য অপেক্ষা করে, সে চিরকাল আটকে থাকে; আর সময়সীমা দিয়ে থামালে এমন একটি ছোট program বাদ পড়তে পারে, যা সীমার পরে x ছেপে থামত। কোনটি অপেক্ষার যোগ্য, তা জানতে halting problem মেটাতে হতো। |x| + c-এর সীমা খোঁজের প্রার্থী সসীম রাখে, কিন্তু প্রতিটি প্রার্থী চালানোর সময় সসীম রাখে না। সব program পালা করে চালালে শুধু ওপর থেকে নামতে থাকা অনুমান পাওয়া যায়, কখন সেটি চূড়ান্ত তা জানা যায় না। Theorem ৭.১ নিশ্চিত করে, কোনো সংশোধনেই এই algorithm ঠিক করা যায় না।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমK(x) computable নয়, এই প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. ধরে নেওয়া: একটি program C সব x-এ থেমে K(x) বলে
  2. Pn বানানো: shortlex ক্রমে প্রথম x খোঁজা, যার K(x) ≥ n
  3. সংকোচন-অযোগ্য string আছে বলে Pn থামে আর একটি xn ছাপে
  4. |Pn| = c + ⌊log2 n⌋ + 1, তাই K(xn) ≤ c + ⌊log2 n⌋ + 1
  5. বড় n-এ n ≤ K(xn) ≤ c + ⌊log2 n⌋ + 1 অসম্ভব
  6. সিদ্ধান্ত: C থাকতে পারে না

Recursion theorem কী বলে?

  • প্রতিটি recursive function-কে loop দিয়ে লেখা যায়
  • যেকোনো computable কাজ t-এর জন্য এমন একটি যন্ত্র R আছে, যা input w পেলে t(⟨R⟩, w) হিসাব করে
  • প্রতিটি recognizable language decidable
  • একটি যন্ত্র শুধু নিজের source ফাইল পড়ে নিজের বর্ণনা জানতে পারে

SELF = A · B নির্মাণে A = P⟨B⟩ আর B tape-এর ⟨M⟩ থেকে q(⟨M⟩) বানিয়ে ⟨M⟩-এর সঙ্গে জোড়ে। B কীভাবে ⟨A⟩ পায়?

  • B-এর ভেতরে ⟨A⟩ আগে থেকে লেখা থাকে
  • A tape-এ ⟨A⟩ লিখে দেয়
  • ব্যবহারকারী input হিসেবে ⟨A⟩ দেন
  • Tape-এর ⟨B⟩-তে q প্রয়োগ করে, কারণ q(⟨B⟩) = ⟨A⟩

U আর U′ দুটি universal Turing machine. Invariance theorem অনুযায়ী কোনটি সত্য?

  • একটি ধ্রুবক c আছে, যাতে সব x-এ |KU(x) − KU′(x)| ≤ c
  • সব x-এ KU(x) = KU′(x)
  • পার্থক্য সর্বোচ্চ |x|-এর সমানুপাতিক
  • ছোট string-এ দুটি মান সবসময় খুব কাছাকাছি

যেকোনো universal machine-এর জন্য, ১২ দৈর্ঘ্যের binary string-এর মধ্যে K(x) ≤ 8 এমন string সর্বোচ্চ কতটি হতে পারে?

  • 256
  • 4096
  • 511
  • 4095

একটি ১,০০,০০০ byte-এর ফাইল zlib দিয়ে একটুও ছোট হলো না। এর থেকে কোন সিদ্ধান্ত বৈধ?

  • ফাইলটির K প্রায় ৮,০০,০০০ bit
  • শুধু এটুকু: K(ফাইল) প্রায় ৮,০০,০০০ bit যোগ একটি ধ্রুবকের বেশি নয়
  • ফাইলটি নষ্ট হয়ে গেছে
  • ফাইলটি নিশ্চিতভাবে Kolmogorov-অর্থে এলোমেলো

Recursion theorem দিয়ে ATM undecidable-এর প্রমাণে যন্ত্র B কী করে?

  • Input হিসেবে নিজের বর্ণনা ⟨B⟩ নেয় আর H-কে জিজ্ঞেস করে
  • নিজের বর্ণনা জোগাড় করে H(⟨B, w⟩)-এর উত্তর হুবহু মেনে চলে
  • H থামে না বলে B চিরকাল loop করে
  • যেকোনো input w-এ নিজের ⟨B⟩ জোগাড় করে, H(⟨B, w⟩) চালায় আর উল্টো উত্তর দেয়

“|x| + c পর্যন্ত দৈর্ঘ্যের সব program চালিয়ে সবচেয়ে ছোটটি খুঁজলেই K(x) পাওয়া যায়।” এই দাবির মূল ত্রুটি কী?

  • কিছু program কখনো থামে না, আর কোনগুলো থামবে তা আগে জানা যায় না
  • সসীম সংখ্যক program নেই
  • K(x) কখনো কখনো |x| + c-এর চেয়ে বড়
  • একই program বিভিন্ন run-এ বিভিন্ন আউটপুট দেয়

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Quine সম্ভব: তথ্য অংশে বাকি program-এর লেখা, আর কাজ অংশ সেই লেখা একবার ছাঁচ, একবার উপাদান হিসেবে ব্যবহার করে।
  2. Recursion theorem: যেকোনো computable t-এর জন্য এমন R আছে, যাতে r(w) = t(⟨R⟩, w); প্রমাণে R = A · B · T, A = P⟨BT⟩, আর B q দিয়ে ⟨A⟩ বানায়।
  3. প্রয়োগ: ATM undecidable (B নিজের ⟨B⟩ নিয়ে H-এর উল্টো করে), MINTM recognizable নয়, fixed-point theorem, আর নিখুঁত virus শনাক্তকরণের অসম্ভবতা।
  4. K(x) = x ছাপে এমন সবচেয়ে ছোট program-এর দৈর্ঘ্য; একটি ধ্রুবক পর্যন্ত যন্ত্র-নিরপেক্ষ, আর প্রতিটি দৈর্ঘ্যে সংকোচন-অযোগ্য string আছে (2n বনাম 2n − 1).
  5. K computable নয় (Berry-ধাঁচের প্রমাণ); compression শুধু ওপরের সীমা দেয়, যেমন বাজারঘরের log ছোট হয় কিন্তু seed-ভিত্তিক এলোমেলো byte হয় না, যদিও তার K ছোট।

পরের পর্বে: মডিউল ১০ শুরু: পর্ব ৫৭ Time complexity আর class P. “গণনা করা যায় কি?” থেকে প্রশ্ন বদলে “কত দ্রুত?”: Turing machine-এর সময় মাপা, polynomial সময় কেন “দক্ষ”-এর মাপকাঠি, আর বাজারঘরের কোন সমস্যা P-তে পড়ে।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান