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

বাস্তবে undecidability — static analysis, tiling আর Busy Beaver

Undecidability in Practice — Static Analysis, Type Checking, Compiler Limits, the Busy Beaver Function, Wang Tiles and Hilbert's Tenth Problem

Taught in Bangla, this lesson brings undecidability into engineering: no static analysis tool can always halt and never err, so real tools give false positives, false negatives or both. A real mypy 2.4.1 run flags a line that never executes and misses one that crashes. It covers decidability limits in type checking, the uncomputable Busy Beaver function with its known values up to S(5), why timeouts do not decide halting, Wang tiles and Hilbert's tenth problem, with in-page Python (Pyodide) demos.

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

  • Sound আর complete analysis-এর নিখুঁত অর্থ, আর কেন একটি সবসময়-থামা tool দুটি একসঙ্গে হতে পারে না (প্রমাণসহ)
  • সত্যিকারের type checker-এর ভুল সতর্কতা আর মিস করা bug চেনা, আর type checking ও compiler optimisation-এর সীমা
  • Busy Beaver function-এর সংজ্ঞা, কেন এটি গণনাযোগ্য নয় তার প্রমাণ, আর ছোট n-এ নিজে হাতে মান খুঁজে পাওয়া
  • Timeout, ধাপের সীমা আর bounded check কী বলে আর কী বলে না
  • Wang tiling, Hilbert-এর দশম সমস্যা আর Gödel-এর অসম্পূর্ণতার সঙ্গে halting problem-এর যোগ

১ · তত্ত্ব থেকে অফিসে — বাজারঘরের “সব ধরা” যাচাইকারী

এই মডিউলে এ পর্যন্ত চারটি বড় ফল এসেছে। পর্ব ৫১-এ diagonalization দিয়ে দেখেছেন, ATM আর halting problem HALTTM decidable নয়। পর্ব ৫২-এ mapping reduction দিয়ে এই দেয়াল অন্য সমস্যায় ছড়িয়েছে। পর্ব ৫৩-এ Rice-এর theorem বলেছে, Turing machine-এর language নিয়ে প্রতিটি non-trivial প্রশ্ন undecidable. পর্ব ৫৪-এ grammar-এর প্রশ্নেও একই দেয়াল দেখা গেছে। এই পর্বের প্রশ্ন ব্যবহারিক: যে প্রকৌশলী প্রতিদিন linter, type checker আর compiler ব্যবহার করেন, তাঁর কাছে এর মানে কী?

বাজারঘরের CTO একটি স্বপ্নের tool চান: প্রতিটি নতুন code merge হওয়ার আগে সেটি পড়ে নিশ্চিত বলবে, “এই checkout code কোনো input-এ crash করবে না” বা “করবে”। কখনো ভুল সতর্কতা নয়, কখনো কোনো bug মিস নয়, আর প্রতিটি code-এ কিছু সময় পরে উত্তর। এটি ঢাকার ট্রাফিক পুলিশের কাছে এমন একটি যন্ত্র চাওয়ার মতো, যা প্রতিটি গাড়ির দিকে একবার তাকিয়ে নিশ্চিত বলবে সে আজ কোনো দুর্ঘটনা ঘটাবে কি না। নিখুঁত যন্ত্রটি নেই; বাস্তবে আছে চেকপোস্ট, যা কিছু নির্দোষ গাড়ি থামায় আর কিছু দোষী গাড়ি ছেড়ে দেয়। এই পর্ব দেখায় কেন, আর এই দুই ধরনের ভুলের মধ্যে প্রকৌশলীরা কীভাবে বেছে নেন।

শুরুতেই একটি কথা স্পষ্ট করা দরকার, কারণ এটি নিয়ে ভুল বোঝাবুঝি সবচেয়ে বেশি। Undecidability বলে: এমন কোনো একক algorithm নেই, যা সব input-এ থেমে সঠিক উত্তর দেয়। এটি বলে না যে কোনো নির্দিষ্ট program নিয়ে কিছু প্রমাণ করা যায় না, বা বেশিরভাগ বাস্তব program কঠিন। Static analysis tool লক্ষ লক্ষ program-এ চমৎকার কাজ করে; theorem শুধু নিশ্চিত করে যে প্রতিটি tool-এর জন্য অন্তত কিছু program আছে, যেখানে সে ভুল করবে, “জানি না” বলবে, বা থামবে না।

২ · Static analysis — sound, complete আর অসম্ভব তৃতীয়টি

Static analysis মানে program না চালিয়ে source code পড়ে তার আচরণ নিয়ে কিছু বলা। এর একটি প্রশ্ন ধরুন: “এই program কি কোনো input-এ crash করতে পারে?” Tool-এর উত্তর হয় “সতর্কতা” (warn), নয় “ঠিক আছে” (ok). দুই ধরনের ভুল সম্ভব, আর তাদের নাম গুরুত্বপূর্ণ।

সংজ্ঞা ২.১ (Sound আর complete analyzer)

ধরুন P একটি “খারাপ” আচরণ (যেমন crash), আর A একটি analyzer যা প্রতিটি program p-তে warn বা ok বলে।

  • A sound, যদি p-তে P সত্যিই ঘটলে A অবশ্যই warn বলে। অর্থাৎ false negative নেই; “ok” বললে সেটি নিশ্চিত।
  • A complete, যদি A warn বললে p-তে P সত্যিই ঘটে। অর্থাৎ false positive নেই; প্রতিটি সতর্কতা একটি আসল bug.

(কিছু বই আর tool শব্দ দুটি উল্টো অর্থে ব্যবহার করে, “bug খোঁজা” না “নিরাপত্তা প্রমাণ” কোন দৃষ্টিকোণ থেকে বলা হচ্ছে তার ওপর নির্ভর করে। তাই সবসময় দেখুন: কোন ভুলটি বাদ দেওয়া হলো?)

দুই ধরনের আপস

লাল: যে program-গুলোতে bug সত্যিই আছে। হলুদ: যেগুলোতে analyzer সতর্ক করে।

Sound analyzer over-approximates bugs, complete analyzer under-approximates them Sound: কোনো bug মিস নয় আসল bug সতর্কতা (warn) বাড়তি হলুদ = false positive “ok” বললে নিশ্চিত নিরাপদ Complete: কোনো ভুল সতর্কতা নয় সতর্কতা আসল bug বাইরের লাল = false negative “warn” বললে নিশ্চিত bug
ছবি ৫৫.১ — Sound analyzer bug-এর অঞ্চলকে বাইরে থেকে ঢাকে (over-approximation), complete analyzer ভেতর থেকে (under-approximation). দুটি রেখা হুবহু মেলাতে চাইলে tool-কে কিছু program-এ চিরকাল চলতে হবে।

দুটি চরম উদাহরণ দেখলে সংজ্ঞা পরিষ্কার হয়। “সব program-এ warn” একটি sound analyzer (কিছু মিস করে না), কিন্তু অকেজো। “কোনো program-এ warn নয়” একটি complete analyzer (কখনো ভুল সতর্কতা নয়), সমান অকেজো। Testing আর fuzzing স্বভাবে complete: একটি test যদি crash দেখায়, crash-টি আসল; কিন্তু যে input কেউ চেষ্টা করেনি, সেখানের bug মিস হয়। একটি typed language-এর type checker সাধারণত sound হওয়ার লক্ষ্য রাখে নির্দিষ্ট এক শ্রেণির ভুলের জন্য: পাস করলে সেই ধরনের type error runtime-এ হবে না, কিন্তু কিছু নির্দোষ program-ও বাতিল হয়।

উপপাদ্য ২.২ (নিখুঁত crash-detector নেই)

CRASH = {⟨p⟩ : p কোনো input-এ crash করে} undecidable. ফলে এমন কোনো analyzer নেই, যা সব program-এ থামে এবং একই সঙ্গে sound ও complete.

প্রমাণ: HALTTM ≤m CRASH দেখাব। দিকটি লক্ষ করুন: জানা undecidable সমস্যা থেকে নতুন সমস্যায়, তাই নতুন সমস্যাটি undecidable হয়।

  1. Input ⟨M, w⟩ থেকে একটি program pM,w বানান: “নিজের input উপেক্ষা করুন; M-কে w-এর ওপর অনুকরণ করুন; অনুকরণ থামলে ইচ্ছে করে crash করুন (যেমন শূন্য দিয়ে ভাগ)।” অনুকরণের কোডে নিজে কোনো crash নেই। — নির্মাণ
  2. রূপান্তর f(⟨M, w⟩) = ⟨pM,w⟩ শুধু একটি নির্দিষ্ট কাঠামোয় M আর w বসায়, তাই f একটি computable function; M চালানোর দরকার হয় না। — f-কে নিজে থামতে হবে
  3. M w-এ থামলে pM,w প্রতিটি input-এ crash করে; M w-এ না থামলে pM,w কখনো crash লাইনে পৌঁছায় না। তাই ⟨M, w⟩ ∈ HALTTM ⇔ f(⟨M, w⟩) ∈ CRASH. — “⇔” দুই দিকেই
  4. CRASH decidable হলে HALTTM decidable হতো, যা পর্ব ৫১-এ মিথ্যা প্রমাণিত। তাই CRASH undecidable. — reduction-এর নিয়ম
  5. একটি সবসময়-থামা analyzer sound আর complete দুটিই হলে সে ঠিক CRASH-এর সদস্যে warn দিত, অর্থাৎ CRASH-এর decider হতো। তা নেই। ∎

এটি Rice-এর theorem-এর একটি বিশেষ রূপ, program-এর ভাষায়: “crash করে কি না” program-এর আচরণের প্রশ্ন (semantic), কোডের চেহারার নয়। পর্ব ৫৩-এ সাধারণ রূপ আর অনেক উদাহরণ দেখেছেন; এখানে তার দাম কে দেয়, সেটিই দেখার বিষয়। Sound tool-গুলো সাধারণত abstract interpretation-এর মতো কৌশলে মানের একটি “মোটা” ছবি রাখে (যেমন “x ধনাত্মক কোনো পূর্ণসংখ্যা”, নির্দিষ্ট মান নয়), আর সেই ছবিতে যা অসম্ভব প্রমাণ করা যায় না, তাতেই সতর্ক করে। এর গাণিতিক কাঠামো পর্ব ৭৮ (program analysis-এর সীমা)-এর বিষয়।

৩ · সত্যিকারের run — mypy-এর একটি ভুল সতর্কতা আর একটি মিস

তত্ত্বটি একটি সত্যিকারের tool-এ দেখা যাক। mypy হলো Python-এর একটি স্বাধীন type checker (MIT licence), যা type hint পড়ে চালানোর আগেই type-এর অসংগতি খোঁজে; এর ব্যবহার Python কোর্সের পর্ব ৪০-এ আছে, এখানে শুধু এর সীমা। নিচের ফাইলে বাজারঘরের দুটি function. প্রথমটির একটি লাইনে type error আছে, কিন্তু সেই লাইন কখনো চলে না। দ্বিতীয়টিতে mypy-এর চোখে কোনো সমস্যা নেই, অথচ সেটি সত্যিই crash করে।

import json


def settle(n: int) -> int:
    # bazarghar batch checksum: halve if even, else 3n + 1, until 1
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
    return n


def label(order: int) -> str:
    if settle(order) != 1:          # never true when settle() returns
        return order + "-late"      # a type error on a line that never runs
    return f"BG-{order:04d}"


def discount(raw: str) -> int:
    data = json.loads(raw)          # mypy sees: Any
    return data["pct"] + 5          # crashes if pct arrives as a string


print(label(42))
print(discount('{"pct": 10}'))
print(discount('{"pct": "10"}'))

সত্যিকারের run (ডেস্কটপ, uv-এর একটি project-এ mypy 2.4.1, Python 3.14.4; mypy-তে কোনো usage-reporting বা telemetry নেই, installed package-এর code খুঁজে নিশ্চিত হয়েছি):

~/bazarghar-toc$ uv run python -m mypy orders.py
orders.py:13: error: Incompatible return value type (got "int", expected "str")  [return-value]
orders.py:13: error: Unsupported operand types for + ("int" and "str")  [operator]
Found 2 errors in 1 file (checked 1 source file)

~/bazarghar-toc$ uv run python -m mypy --strict orders.py
orders.py:13: error: Incompatible return value type (got "int", expected "str")  [return-value]
orders.py:13: error: Unsupported operand types for + ("int" and "str")  [operator]
orders.py:19: error: Returning Any from function declared to return "int"  [no-any-return]
Found 3 errors in 1 file (checked 1 source file)

~/bazarghar-toc$ uv run python orders.py
BG-0042
15
Traceback (most recent call last):
  File "~/bazarghar-toc/orders.py", line 24, in <module>
    print(discount('{"pct": "10"}'))
  File "~/bazarghar-toc/orders.py", line 19, in discount
    return data["pct"] + 5          # crashes if pct arrives as a string
TypeError: can only concatenate str (not "int") to str

তিনটি ঘটনা। লাইন ১৩ একটি false positive: mypy দুটি error দেখায়, কিন্তু program চালালে লাইনটি কখনো চলে না; label(42) শান্তভাবে BG-0042 ছাপে। লাইন ১৯ একটি false negative: সাধারণ mode-এ mypy চুপ, অথচ শেষ লাইনে সত্যিকারের TypeError. json.loads-এর ফল mypy-এর কাছে Any, অর্থাৎ “যেকোনো কিছু”, আর Any-এর ওপর mypy নকশা করেই কোনো দাবি যাচাই করে না। --strict লাইন ১৯-এর দিকে আঙুল তোলে, তবে bug হিসেবে নয়, “Any ফেরত দিচ্ছেন” এই সতর্কতা হিসেবে; বাড়তি কড়াকড়ি মিস কমায়, বিনিময়ে বেশি সতর্কতা দেয়। (Traceback-এর কিছু নির্দেশক লাইন বাদ আর path ছোট করে দেখানো।)

এখানে একটি সততার কথা। লাইন ১৩-এর ক্ষেত্রে একটি চতুর tool কাজটি পারত: settle()-এর loop শুধু n == 1 হলেই শেষ হয়, তাই settle() ফিরলে তার ফল সবসময় 1; এটি একটি সহজ loop invariant. mypy মানের হিসাব রাখে না, শুধু type-এর, তাই এটি দেখে না। Undecidability বলে না যে এই নির্দিষ্ট লাইনটি কোনো tool কখনো বুঝবে না; বলে যে প্রতিটি tool-এর জন্য এমন কোনো না কোনো program আছে, যেখানে সে আটকাবে। আর settle() আরেকটি গভীর প্রশ্নও লুকিয়ে রাখে: প্রতিটি ধনাত্মক order-এ settle() কি আদৌ থামে? এটিই Collatz conjecture, যা আজও অপ্রমাণিত (n ≤ 0 হলে settle() নিশ্চিত চিরকাল চলে, যেমন 0 → 0 → 0 …)। নিচের stepper mypy আর runtime-কে পাশাপাশি দেখায়।

11def label(order: int) -> str:12    if settle(order) != 1:13        return order + "-late"14    return f"BG-{order:04d}"
দুই দৃষ্টিকোণ
mypy জানে
runtime-এ
রায়
  1. Signature. mypy জানে order একটি int আর ফেরত মান str হতে হবে। Runtime-এ order = 42.
  2. settle(order). mypy settle()-এর signature থেকে জানে ফল একটি int, কিন্তু কোন int, তা হিসাব করে না। Runtime-এ ৮টি ধাপে 42 থেকে 1-এ পৌঁছায়।
  3. শর্ত. mypy-এর কাছে “int != 1” সত্যও হতে পারে, তাই দুটি শাখাই সম্ভব ধরে। Runtime-এ শর্তটি মিথ্যা।
  4. লাইন ১৩. mypy শাখাটি পরীক্ষা করে int + str পায়: error. Runtime কখনো এখানে আসে না। এটি একটি false positive.
  5. লাইন ১৪. Runtime BG-0042 ফেরত দেয়। কোন শাখা আসলে চলে, তা program-এর আচরণের প্রশ্ন; সব program-এ এর নিখুঁত উত্তর দেওয়া undecidable, তাই mypy সাবধানে দুটিই ধরে নেয়।

৪ · Type checking আর compiler — কোথায় decidable, কোথায় নয়

Rice-এর theorem দেখে মনে হতে পারে, type checking-ও undecidable হওয়া উচিত। আসলে উল্টো: বেশিরভাগ type system ইচ্ছে করে নকশা করা হয় যাতে type checking decidable থাকে। কৌশলটি হলো প্রশ্ন বদলানো। “এই program runtime-এ কোনো type error করবে কি?” একটি semantic প্রশ্ন, undecidable. “এই program কি type system-এর নিয়ম মেনে লেখা?” একটি syntactic প্রশ্ন, কোডের গঠন দেখে উত্তর দেওয়া যায়। এরপর একটি আলাদা theorem (type soundness, যার প্রচলিত স্লোগান “well-typed programs can't go wrong”) প্রমাণ করে, নিয়ম মানলে নির্দিষ্ট ধরনের runtime error হবে না। দাম: নিয়ম না-মানা কিন্তু নির্দোষ কিছু program বাতিল হয়, ঠিক লাইন ১৩-এর মতো।

Type system বা প্রশ্নChecking/inferenceমন্তব্য
Simply typed λ-calculus, C-ধাঁচের সরল typedecidable, দ্রুতশুধু গঠন দেখে সিদ্ধান্ত
Hindley–Milner (ML-ধাঁচের type inference)decidableসবচেয়ে খারাপ ক্ষেত্রে সূচকীয় হতে পারে বলে জানা, বাস্তবে দ্রুত
System F-এ annotation ছাড়া type inferenceundecidableJ. B. Wells ১৯৯০-এর দশকে প্রমাণ করেন বলে পরিচিত
Java generics-এর subtypingundecidableRadu Grigore ২০১৭ সালে দেখান বলে জানা যায়
C++ template, কিছু ভাষার type-level programmingTuring-completecompiler তাই গভীরতা বা ধাপের সীমা রাখে

শেষ সারিটি এই পর্বের পরিচিত ছবি: যখন type system নিজেই Turing-complete, তখন type checking-এর মধ্যেই একটি halting problem লুকিয়ে থাকে। Compiler তখন যা করে, তা অংশ ৬-এর timeout: একটি সীমা (যেমন template instantiation-এর গভীরতা) পেরোলে error দিয়ে থামে, যদিও program-টি হয়তো আরও কিছু ধাপে ঠিক হতো।

Compiler optimisation. Dead code elimination এমন কোড মুছে দেয় যা কখনো চলবে না বা যার ফল কেউ ব্যবহার করে না। “এই লাইন কখনো চলবে কি?” উপপাদ্য ২.২-এর প্রশ্নই, শুধু crash-এর জায়গায় “এই লাইনে পৌঁছানো”। তাই compiler শুধু সেই কোড মোছে যা নিশ্চিতভাবে মৃত, যেমন if (0)-এর ভেতর বা return-এর পরে; বাকি সন্দেহজনক কোড রেখে দেয়। এটি একটি sound নীতি: ভুল করে জীবিত কোড মোছা চলবে না, মৃত কোড রেখে দেওয়া চলবে।

একই যুক্তি আরও বড় দাবিতে খাটে: “সবচেয়ে ভালো optimising compiler” অসম্ভব। ধরুন একটি compiler প্রতিটি program-কে তার সবচেয়ে ছোট সমতুল্য রূপে বদলাতে পারে। যে program কিছু ছাপে না আর কখনো থামে না, তার সবচেয়ে ছোট রূপ একটি এক-লাইনের অসীম loop. তাহলে সেই compiler-এর output দেখে বলা যেত কোন program থামে না, যা halting problem-এর সমাধান হতো। Andrew Appel-এর compiler পাঠ্যবইয়ে এটিকে রসিকতা করে “compiler লেখকদের পূর্ণ কর্মসংস্থানের উপপাদ্য” বলা হয়েছে বলে পরিচিত: প্রতিটি compiler-এর চেয়ে ভালো আরেকটি compiler সবসময় বানানো যায়, তাই কাজ কখনো ফুরায় না।

৫ · Busy Beaver — একটি function, যা কোনো যন্ত্র গুনতে পারে না

Undecidability-র সবচেয়ে নাটকীয় চেহারা একটি সংখ্যার ক্রম। Tibor Radó ১৯৬২ সালে একটি খেলা প্রস্তাব করেন বলে পরিচিত: n-টি state আর দুটি চিহ্ন {0, 1}-এর একটি Turing machine বানান, যা ফাঁকা tape (সব 0) থেকে শুরু করে একসময় থামে, আর থামার আগে যত সম্ভব বেশি ধাপ চলে। ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৫-এ brute force দিয়ে S(2) = 6 পেয়েছিলেন; এখানে প্রমাণ, n = 3, আর সত্যিকারের BB(5).

সংজ্ঞা ৫.১ (Busy Beaver function)

যন্ত্রগুলো n-টি সাধারণ state আর একটি আলাদা halt state Z নিয়ে, tape alphabet {0, 1} (0 হলো blank), tape দুই দিকে অসীম, আর প্রতিটি ধাপে একটি চিহ্ন লেখা, বাঁয়ে (L) বা ডানে (R) সরা, আর state বদলানো; halt-এ যাওয়ার transition-ও একটি ধাপ।

  • S(n) = এমন সব n-state যন্ত্রের মধ্যে, যারা ফাঁকা tape থেকে শুরু করে থামে, সবচেয়ে বেশি ধাপের সংখ্যা।
  • Σ(n) = তাদের মধ্যে থামার সময় tape-এ সবচেয়ে বেশি 1-এর সংখ্যা।

আজকাল BB(n) বলতে প্রায়ই S(n) বোঝানো হয়। n-state যন্ত্র সসীম সংখ্যক ((4n + 4)2n-টি), তাই S(n) একটি সুসংজ্ঞায়িত সংখ্যা। Busy Beaver নামটি সেই চরিত্রের যে সবচেয়ে বেশি খেটে তবে থামে।

এই কোর্সের রীতিতে tape শুধু ডানে অসীম (পর্ব ৪৩); Busy Beaver-এর প্রচলিত সংজ্ঞায় দুই দিকে, আর পর্ব ৪৫-এ দেখেছেন এতে গণনার ক্ষমতা বদলায় না। যন্ত্র লেখার একটি প্রচলিত সংক্ষিপ্ত রূপ আছে: প্রতিটি state-এর জন্য দুটি তিন-অক্ষরের নিয়ম (0 পড়লে, 1 পড়লে), যেমন 1RB মানে “1 লিখুন, ডানে সরুন, state B”. 2-state চ্যাম্পিয়ন 1RB1LB_1LA1RZ: A0 → 1RB, A1 → 1LB, B0 → 1LA, B1 → 1RZ. নিচের stepper এটি ফাঁকা tape-এ চালায়, পর্ব ৪৩-এর u q v configuration রীতিতে।

A01 লিখুন, R, BA11 লিখুন, L, BB01 লিখুন, L, AB11 লিখুন, R, থামুন
যন্ত্রের অবস্থা
ধাপ
configuration
নিয়ম
1-এর সংখ্যা
  1. শুরু. সব ঘরে 0, head-এর নিচে 0, state A.
  2. ধাপ ১. A 0 পড়ে: নিয়ম A0 → 1RB. ঘরে 1, head ডানে, state B.
  3. ধাপ ২. B 0 পড়ে: B0 → 1LA. আরেকটি 1, head বাঁয়ে প্রথম ঘরে, state A. Tape এখন 11.
  4. ধাপ ৩. A এবার 1 পড়ে: A1 → 1LB. Head শুরুর ঘরের বাঁয়ে একটি নতুন ফাঁকা ঘরে যায়; দুই দিকে অসীম tape এখানে কাজে লাগে।
  5. ধাপ ৪. B 0 পড়ে: B0 → 1LA. তৃতীয় 1, head আরও বাঁয়ে।
  6. ধাপ ৫. A 0 পড়ে: A0 → 1RB. চতুর্থ 1, head ডানে।
  7. ধাপ ৬. B 1 পড়ে: B1 → 1RZ, যন্ত্র থামে। মোট ৬ ধাপ আর tape-এ চারটি 1: S(2) = 6, Σ(2) = 4. দুটিই যে সর্বোচ্চ, তার প্রমাণ সব 2-state যন্ত্র পরীক্ষা করে, যা নিচের code করে।

সব যন্ত্র একটি একটি করে না বানিয়ে একটি চতুর খোঁজ: সব transition প্রথমে “ফাঁকা” রাখুন, ফাঁকা tape-এ চালান, আর যখনই run এমন একটি transition চায় যা এখনো নেই, সেখানে শাখা করুন: হয় এটি “1 লিখে থামা” (একটি থামা যন্ত্র পাওয়া গেল), নয় সম্ভাব্য সব নিয়ম বসিয়ে আবার চালানো। নতুন state-এর নাম সবসময় ক্রমে (A, B, C) দেওয়া হয়, যাতে শুধু নাম বদলানো একই যন্ত্র বারবার না আসে। যে run ধাপের সীমা (step cap) ছোঁয়, তাকে আলাদা গোনা হয়।

def run(T, cap):                  # T: {(state, read): (write, move, next)}
    tape, pos, q = {}, 0, "A"     # blank tape, start state A
    for steps in range(cap):
        key = (q, tape.get(pos, 0))
        if key not in T:          # first transition the run needs but T lacks
            return steps, key, sum(tape.values()) - key[1]
        w, m, q = T[key]; tape[pos] = w; pos += m
    return cap, None, None

def search(n, cap):               # tree search: add a transition only when needed
    best = {"steps": 0, "ones": 0}; count = {"halt": 0, "cap": 0}
    def grow(T):
        steps, key, ones = run(T, cap)
        if key is None:
            count["cap"] += 1; return            # still running at the cap
        count["halt"] += 1                       # choice 1: here "write 1, halt"
        best["steps"] = max(best["steps"], steps + 1)
        best["ones"] = max(best["ones"], ones + 1)
        used = {"A"} | {q for q, _ in T} | {t[2] for t in T.values()}
        states = sorted(used) + ([chr(65 + len(used))] if len(used) < n else [])
        for w in (0, 1):                         # choice 2: define it, run again
            for m in (-1, 1):
                for nq in states:
                    grow({**T, key: (w, m, nq)})
    grow({})
    return best, count

for n in (1, 2, 3):
    best, count = search(n, 50)
    print(f"n={n}: longest halting run {best['steps']} steps, most 1s {best['ones']},"
          f" halted {count['halt']}, still running at cap 50: {count['cap']}")
champ = {("A", 0): (1, 1, "B"), ("A", 1): (1, -1, "B"), ("B", 0): (1, -1, "A")}
print("1RB1LB_1LA1RZ:", run(champ, 50)[0] + 1, "steps")

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

n=1: longest halting run 1 steps, most 1s 1, halted 1, still running at cap 50: 4
n=2: longest halting run 6 steps, most 1s 4, halted 37, still running at cap 50: 260
n=3: longest halting run 21 steps, most 1s 6, halted 3543, still running at cap 50: 38970
1RB1LB_1LA1RZ: 6 steps

n = 2-এ সবচেয়ে দীর্ঘ থামা run ৬ ধাপ আর সর্বোচ্চ চারটি 1, stepper-এর সঙ্গে মেলে। n = 3-এ ২১ ধাপ আর ছয়টি 1, যা প্রকাশিত S(3) = 21 আর Σ(3) = 6-এর সঙ্গে মেলে (দুটি সর্বোচ্চ আলাদা যন্ত্রে আসে)। কিন্তু সাবধান: এই code নিজে প্রমাণ করেনি যে S(3) = 21. ৩৮,৯৭০টি শাখা ৫০ ধাপ পরেও চলছিল, আর code জানে না তাদের কেউ ৫১তম বা দশ লাখতম ধাপে থামবে কি না। S(3) = 21 প্রতিষ্ঠা করতে প্রতিটি না-থামা যন্ত্রের জন্য আলাদা প্রমাণ লাগে, যেমন “একই configuration ফিরে আসে” বা “tape-এর একটি নকশা চিরকাল বাড়ে”; ১৯৬০-এর দশকে মানুষ আর কম্পিউটার মিলে এই কাজ করেছিল বলে পরিচিত। এই ফাঁকটিই সংখ্যাটিকে গণনার অযোগ্য করে।

উপপাদ্য ৫.২ (S গণনাযোগ্য নয়)

এমন কোনো Turing machine নেই, যা প্রতিটি n-এর জন্য থেমে S(n) লেখে।

প্রমাণ: প্রথমে একটি সহায়ক ফল। HALTε = {⟨M⟩ : M ফাঁকা tape-এ থামে}, অর্থাৎ blank-tape halting problem, undecidable: ⟨M, w⟩ থেকে Mw বানান, যে tape মুছে w লেখে আর তারপর M চালায়। এই রূপান্তর computable, আর Mw ফাঁকা tape-এ থামে ⇔ M w-এ থামে; তাই HALTTM ≤m HALTε, আর HALTε undecidable.

  1. ধরুন যন্ত্র B প্রতিটি n-এ থেমে S(n) গণনা করে। — বিপরীত অনুমান
  2. D = “input ⟨M⟩ পেলে: M-এর state গুনে n বের করুন (দুই-চিহ্নের যন্ত্রে রূপান্তর আগে করে নিন); B দিয়ে S(n) হিসাব করুন; M-কে ফাঁকা tape-এ বড়জোর S(n) ধাপ চালান; ততক্ষণে থামলে গ্রহণ, নইলে বর্জন।” — নির্মাণ
  3. D সবসময় থামে: n গোনা সসীম, B থামে, আর অনুকরণ বড়জোর S(n) ধাপ। — decider
  4. M ফাঁকা tape-এ থামলে সে n-state যন্ত্র হিসেবে বড়জোর S(n) ধাপে থামে (S(n)-এর সংজ্ঞা), তাই D গ্রহণ করে; না থামলে কোনো ধাপেই থামে না, D বর্জন করে। তাই D HALTε-কে decide করে। — সঠিকতা
  5. এটি সহায়ক ফলের বিরোধী। তাই B নেই। ∎

প্রমাণটি আরও শক্তিশালী একটি কথা বলে। যদি কোনো computable f-এর জন্য সব যথেষ্ট বড় n-এ f(n) ≥ S(n) হতো, তবে D-তে S(n)-এর জায়গায় f(n) বসিয়ে একই প্রমাণ চলত। তাই S যেকোনো computable function-এর চেয়ে শেষ পর্যন্ত দ্রুত বাড়ে: 2n, n!, Ackermann (পর্ব ৪৯), সবাইকে একসময় ছাড়িয়ে যায়। ছোট n-এ জানা মানগুলো সেই বিস্ফোরণের শুরু দেখায়। নিচের সত্যিকারের run প্রকাশিত চ্যাম্পিয়ন যন্ত্রগুলো চালায়, ৫-state যন্ত্রটির সাড়ে চার কোটির বেশি ধাপসহ।

সত্যিকারের run (একই project, Python 3.14.4, সাধারণ bytearray tape-এ নিজের লেখা ২৫ লাইনের simulator; যন্ত্রগুলোর বর্ণনা প্রকাশিত চ্যাম্পিয়ন তালিকা থেকে):

~/bazarghar-toc$ uv run python bb_champions.py 2 3 4 5
2 states  1RB1LB_1LA1RZ                        halted=True  steps=6  ones=4  (0.0 s)
3 states  1RB1RZ_1LB0RC_1LC1LA                 halted=True  steps=21  ones=5  (0.0 s)
4 states  1RB1LB_1LA0LC_1RZ1LD_1RD0RA          halted=True  steps=107  ones=13  (0.0 s)
5 states  1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA   halted=True  steps=47,176,870  ones=4,098  (4.7 s)

৪-state যন্ত্রটি ১০৭ ধাপে ১৩টি 1 রেখে থামে; Allen Brady ১৯৮০-এর দশকে S(4) = 107 প্রমাণ করেন বলে পরিচিত। ৫-state যন্ত্রটি Heiner Marxen আর Jürgen Buntrock ১৯৮৯ সালে খুঁজে পান বলে জানা যায়: ৪৭,১৭৬,৮৭০ ধাপ আর ৪,০৯৮টি 1. এটি শুধু দেখায় S(5) ≥ 47,176,870. সমতা, অর্থাৎ এর চেয়ে বেশি চলে থামে এমন কোনো ৫-state যন্ত্র নেই, প্রমাণ করতে প্রায় ১৮ কোটির মতো যন্ত্রের প্রতিটির থামা বা না-থামা নিশ্চিত করতে হয়েছিল। bbchallenge নামের একটি অনলাইন সহযোগী দল ২০২৪ সালে ঘোষণা করে যে Coq (এখন Rocq) proof assistant-এ যাচাই করা একটি প্রমাণে S(5) = 47,176,870 প্রতিষ্ঠিত হয়েছে; বিস্তারিত লেখা পরে গবেষণাপত্র আকারে প্রকাশিত হয়েছে বলে জানা যায়। (৩-state যন্ত্রটি ২১ ধাপের চ্যাম্পিয়ন; ছয়টি 1-এর চ্যাম্পিয়ন আলাদা যন্ত্র।)

কতদূর জানা: S(6)-এর জন্য জানা নিম্নসীমা এত বিশাল যে সাধারণ সূচক দিয়েও লেখা যায় না, আর S(6) কোনোদিন নির্ণয় হবে কি না কেউ জানে না। আরও অদ্ভুত একটি ফল: Adam Yedidia আর Scott Aaronson ২০১৬ সালে কয়েক হাজার state-এর একটি যন্ত্র বানান, যার থামা বা না-থামা প্রচলিত গণিতের ভিত্তি ZFC-তে প্রমাণ করা যায় না (ZFC নিজে consistent ধরে নিলে); পরে অন্যরা সংখ্যাটি কয়েকশোতে নামিয়েছেন বলে জানা যায়। অর্থাৎ কোনো এক সসীম n-এর পরে S(n)-এর মান নির্দিষ্ট একটি সংখ্যা হলেও আমাদের প্রচলিত গণিত দিয়ে তা প্রমাণ করা অসম্ভব।

৬ · Timeout কেন halting decide করে না

প্রকৌশলীর স্বাভাবিক উত্তর: “T ধাপ চালাই; থামলে থামে, না থামলে ধরে নিই loop করছে।” এই “timeout বিচারক” একটি decider, কিন্তু অন্য একটি প্রশ্নের: “M কি T ধাপের মধ্যে থামে?” পর্ব ৫১-এ এই পার্থক্য দেখেছেন; এবার Busy Beaver দিয়ে তার চরম রূপ।

// Two-symbol machines: state -> [rule on 0, rule on 1]; rule = [write, move, next]
const CHAMP4 = { A: [[1, 1, "B"], [1, -1, "B"]], B: [[1, -1, "A"], [0, -1, "C"]],
                 C: [[1, 1, "Z"], [1, -1, "D"]], D: [[1, 1, "D"], [0, 1, "A"]] };
const LOOPER = { A: [[1, 1, "B"], [1, 1, "B"]], B: [[0, -1, "A"], [0, -1, "A"]] };

function steps(M, cap) {            // steps until halt (Z), or null if cap reached
  const tape = new Map(); let pos = 0, q = "A";
  for (let t = 1; t <= cap; t++) {
    const [w, m, next] = M[q][tape.get(pos) || 0];
    tape.set(pos, w); pos += m; q = next;
    if (q === "Z") return t;
  }
  return null;
}
function judge(M, T) {              // the "timeout judge": silence means LOOPS
  return steps(M, T) === null ? "LOOPS" : "HALTS";
}

const truth = steps(CHAMP4, 1e6);
console.log("4-state champion really halts after", truth, "steps");
for (const T of [50, 100, 106, 107, 1000]) {
  const v = judge(CHAMP4, T);
  console.log(`T=${String(T).padStart(4)}: champion ${v}${v === "LOOPS" ? "  <- WRONG" : ""},`,
              `looper ${judge(LOOPER, T)}`);
}

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

4-state champion really halts after 107 steps
T=  50: champion LOOPS  <- WRONG, looper LOOPS
T= 100: champion LOOPS  <- WRONG, looper LOOPS
T= 106: champion LOOPS  <- WRONG, looper LOOPS
T= 107: champion HALTS, looper LOOPS
T=1000: champion HALTS, looper LOOPS

LOOPER দুই ঘরের মধ্যে চিরকাল আসা-যাওয়া করে (একই configuration ফিরে আসে), তাই তার জন্য বিচারক সবসময় ঠিক। চ্যাম্পিয়নের জন্য T ≤ 106 হলে বিচারক ভুল “LOOPS” বলে, যদিও যন্ত্রটি ১০৭তম ধাপে থামে। এখানে T বাড়িয়ে ঠিক করা গেল, কারণ আমরা আগে থেকে উত্তর জানতাম। ৫-state যন্ত্রের জন্য T ≥ 47,176,870 লাগবে, আর বড় n-এর জন্য এমন কোনো T আগে থেকে হিসাব করার উপায় নেই।

1বিচারক J_T: T ধাপ, তারপর “LOOPS”2প্রতিপক্ষ: T + 1 ধাপে থামা যন্ত্র3T বড় করা: নতুন প্রতিপক্ষ4n-অনুযায়ী T(n), computable5T(n) < S(n) কোনো n-এ
বিচারক বনাম প্রতিপক্ষ
বিচারক
পরীক্ষার যন্ত্র
রায়
  1. বিচারক. J100 যেকোনো যন্ত্র ১০০ ধাপ চালায়; না থামলে “LOOPS”. সত্যিকারের loop-এ, যেমন LOOPER, সে ঠিক।
  2. প্রথম প্রতিপক্ষ. CHAMP4 ১০৭তম ধাপে থামে। J100 ভুল করে “LOOPS” বলে।
  3. সীমা বাড়ানো. J1000 নিলেও প্রতিপক্ষ আছে: একটি যন্ত্র যে ১০০০ পর্যন্ত গোনে আর তারপর থামে (একটি সরল counter, এর বর্ণনা T থেকে গণনাযোগ্য)। প্রতিটি নির্দিষ্ট T-এর জন্য এমন একটি যন্ত্র আছে।
  4. চতুর বিচারক. সীমাটি যন্ত্রের আকার অনুযায়ী হোক: n-state যন্ত্রের জন্য T(n) ধাপ, যেখানে T কোনো computable function. এই বিচারক সব যন্ত্রে ঠিক হবে কি?
  5. না. সব n-এ T(n) ≥ S(n) হলে বিচারকটি HALTε-এর decider হতো (উপপাদ্য ৫.২-এর প্রমাণ)। তাই কোনো n-এ T(n) < S(n), আর সেই n-এর চ্যাম্পিয়ন বিচারককে ভুল প্রমাণ করে। কোনো computable timeout নিয়মই সব ক্ষেত্রে যথেষ্ট নয়।

তাহলে timeout কি অকেজো? একেবারেই না; এটি একটি সৎ প্রশ্নের সঠিক উত্তর দেয়: “এই কাজ আমার বাজেটের মধ্যে শেষ হয় কি?” বাজারঘরের checkout service ২ সেকেন্ডে উত্তর না দিলে ব্যবহারকারীকে “আবার চেষ্টা করুন” দেখানো সম্পূর্ণ যুক্তিসংগত। ভুল শুধু timeout-এর ফলকে “এই program কখনো থামে না” হিসেবে পড়া। পর্ব ২১-এর regex match timeout-ও ঠিক এই অর্থে একটি বাজেট, প্রমাণ নয়।

৭ · গণিতের দেয়াল — Wang tile আর Hilbert-এর দশম সমস্যা

Undecidability শুধু program নিয়ে নয়। এমন প্রশ্নেও দেখা দেয় যেখানে কোনো যন্ত্রের নাম নেই, যা শুনলে নিছক জ্যামিতি বা সংখ্যাতত্ত্ব মনে হয়।

Wang tile. একটি Wang tile একটি বর্গ, যার চার কিনারায় চারটি রং (উত্তর, পূর্ব, দক্ষিণ, পশ্চিম)। Tile ঘোরানো যায় না, আর পাশাপাশি দুটি tile-এর মিলিত কিনারার রং এক হতে হবে। প্রতিটি নকশার যত খুশি কপি পাওয়া যায়। প্রশ্ন (tiling problem, বা domino problem): একটি সসীম tile-set দিয়ে কি পুরো অসীম সমতল ঢাকা যায়? বাজারঘরের নতুন গুদামের মেঝের কথা ভাবুন, যার কোনো শেষ নেই।

Hao Wang ১৯৬১ সালের দিকে একটি যুক্তি দেন: যদি প্রতিটি tile-set যা সমতল ঢাকে, তা একটি পর্যায়ক্রমিক (periodic, একটি নকশা বারবার) ভাবে-ও ঢাকে, তবে প্রশ্নটি decidable. কারণ দুটি খোঁজ পালা করে চালানো যায় (পর্ব ৫০-এর dovetailing): একটি খোঁজে পর্যায়ক্রমিক নকশা; অন্যটি k = 1, 2, 3, …-এর জন্য দেখে k × k বর্গ ঢাকা যায় কি না। দ্বিতীয় খোঁজের যুক্তি: যদি সমতল ঢাকা না যায়, তবে কোনো সসীম k-তে k × k বর্গও ঢাকা যায় না (এটি König-এর lemma-র একটি প্রয়োগ, প্রমাণ এখানে বাদ)। নিচের code সেই দ্বিতীয় খোঁজটি করে।

# A Wang tile = (north, east, south, west) edge colours; no rotation allowed.
def tile_square(T, k, cap=300_000):      # backtracking, row by row, with a cap
    grid, tries = [None] * (k * k), 0
    def place(i):
        nonlocal tries
        if i == k * k: return True
        r, c = divmod(i, k)
        for j, (n, e, s, w) in enumerate(T):
            tries += 1
            if tries > cap: raise TimeoutError
            if c and T[grid[i - 1]][1] != w: continue   # left neighbour's east
            if r and T[grid[i - k]][2] != n: continue   # upper neighbour's south
            grid[i] = j
            if place(i + 1): return True
        return False
    try: ok = place(0)
    except TimeoutError: return "NO ANSWER (cap)", tries
    return (grid if ok else None), tries

CHECKER = [(0, 0, 1, 1), (1, 1, 0, 0)]
FLOOR = [(0, 2, 2, 1), (2, 0, 1, 0), (1, 0, 0, 0), (0, 1, 1, 2), (1, 1, 0, 2)]
for name, T in [("CHECKER", CHECKER), ("FLOOR", FLOOR)]:
    for k in range(1, 9):
        g, tries = tile_square(T, k)
        if g is None or isinstance(g, str):
            print(f"{name}: {k}x{k} {'impossible' if g is None else g}"
                  f" after {tries} tries -> no tiling of the whole floor"); break
    else:
        print(f"{name}: every square up to 8x8 tiles; rows:",
              [g[r * 8:r * 8 + 4] for r in range(2)], "...")
g, _ = tile_square(FLOOR, 5)
print("FLOOR 5x5:", *[" ".join(map(str, g[r * 5:r * 5 + 5])) for r in range(5)], sep="\n  ")

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

CHECKER: every square up to 8x8 tiles; rows: [[0, 1, 0, 1], [1, 0, 1, 0]] ...
FLOOR: 6x6 impossible after 3445 tries -> no tiling of the whole floor
FLOOR 5x5:
  1 1 1 1 1
  2 2 2 2 2
  0 3 0 3 0
  1 2 1 2 1
  4 0 4 0 4

CHECKER-এর দুটি tile দাবার ছকের মতো পালা করে বসে; দুই সারির নকশা বারবার ব্যবহার করলে পুরো সমতল ঢাকা যায়, তাই উত্তর নিশ্চিত “হ্যাঁ”। FLOOR-এর পাঁচটি tile ৫ × ৫ বর্গ ঢাকে (শেষ পাঁচ লাইন, প্রতিটি সংখ্যা একটি tile-এর ক্রমিক নম্বর), কিন্তু ৬ × ৬ পারে না, তাই পুরো মেঝে ঢাকা অসম্ভব, এটিও নিশ্চিত। লক্ষ করুন, প্রথম কয়েকটি বর্গ দেখে FLOOR-কে “ভালো” মনে হচ্ছিল। আর এমন কোনো k নেই যার পরে খোঁজা বন্ধ করা নিরাপদ: সাধারণ tile-set-এ হয়তো k = 1000-এ গিয়ে প্রথম ব্যর্থতা আসে।

Wang-এর অনুমান মিথ্যা প্রমাণিত হয়। Robert Berger ১৯৬৬ সালে প্রকাশিত কাজে এমন একটি tile-set দেখান যা সমতল ঢাকে, কিন্তু কখনো পর্যায়ক্রমিকভাবে নয় (aperiodic tile-set; তাঁর প্রথম set-এ বিশ হাজারের বেশি tile ছিল বলে পরিচিত), আর প্রমাণ করেন tiling problem undecidable. প্রমাণের ধারণা: যেকোনো Turing machine M থেকে একটি tile-set বানানো, যার প্রতিটি সারি M-এর একটি configuration, আর পরের সারি পরের configuration; সমতল ঢাকা যায় ঠিক তখন, যখন M ফাঁকা tape-এ কখনো থামে না। এটি পর্ব ৫৪-এর computation history-র কৌশলেরই দুই-মাত্রিক রূপ। পরে tile-এর সংখ্যা অনেক কমেছে; Emmanuel Jeandel আর Michael Rao ২০১৫ সালে ১১টি tile-এর একটি aperiodic set দেখান আর প্রমাণ করেন এর চেয়ে কমে হয় না বলে জানা যায়।

Hilbert-এর দশম সমস্যা. David Hilbert ১৯০০ সালে গণিতের ২৩টি সমস্যার তালিকা দেন; দশমটি চায় এমন একটি পদ্ধতি, যা যেকোনো পূর্ণসংখ্যা-সহগের বহুপদী সমীকরণ (Diophantine equation) দেখে বলবে তার পূর্ণসংখ্যা সমাধান আছে কি না। Martin Davis, Hilary Putnam আর Julia Robinson কয়েক দশকের কাজে পথ তৈরি করেন, আর Yuri Matiyasevich ১৯৭০ সালে শেষ ধাপটি প্রমাণ করেন; ফলটি তাই MRDP theorem নামে পরিচিত: প্রতিটি recognizable set একটি Diophantine set. এর ফল: Hilbert-এর দশম সমস্যা undecidable. সমাধান থাকলে খুঁজে পাওয়া যায় (সব পূর্ণসংখ্যার tuple পালা করে চেষ্টা করুন), তাই প্রশ্নটি recognizable; কিন্তু “সমাধান নেই” বলার কোনো সাধারণ পদ্ধতি নেই।

from math import isqrt
# Search for positive integers x, y with x*x - d*y*y == c, trying y = 1, 2, 3, ...
def search(d, c, cap):
    for y in range(1, cap + 1):
        x2 = c + d * y * y
        if isqrt(x2) ** 2 == x2:
            return f"FOUND x={isqrt(x2)}, y={y}"
    return f"NO ANSWER after y={cap:,} (cap)"

for d, c in [(2, 1), (7, 1), (61, 1), (3, 2)]:
    print(f"x^2 - {d}y^2 = {c}:", search(d, c, 100_000))

x, y = 1766319049, 226153980          # smallest solution, known for centuries
print("check: x^2 - 61y^2 =", x * x - 61 * y * y)
print("x^2 mod 3 is always one of", sorted({a * a % 3 for a in range(3)}),
      "-> x^2 = 3y^2 + 2 would need x^2 mod 3 = 2: never")

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

x^2 - 2y^2 = 1: FOUND x=3, y=2
x^2 - 7y^2 = 1: FOUND x=8, y=3
x^2 - 61y^2 = 1: NO ANSWER after y=100,000 (cap)
x^2 - 3y^2 = 2: NO ANSWER after y=100,000 (cap)
check: x^2 - 61y^2 = 1
x^2 mod 3 is always one of [0, 1] -> x^2 = 3y^2 + 2 would need x^2 mod 3 = 2: never

শেষ দুটি সমীকরণে খোঁজ একই কথা বলে, “NO ANSWER”, অথচ সত্য সম্পূর্ণ আলাদা। x2 − 61y2 = 1-এর সমাধান আছে, কিন্তু সবচেয়ে ছোটটিতেই y = 226,153,980, যা আমাদের সীমার অনেক বাইরে (ভারতীয় গণিতবিদ দ্বিতীয় ভাস্কর দ্বাদশ শতকেই এটি জানতেন বলে পরিচিত)। x2 − 3y2 = 2-এর কোনো সমাধান নেই, কিন্তু সেটি জানা গেল একটি আলাদা চতুর যুক্তিতে: পূর্ণবর্গকে 3 দিয়ে ভাগ করলে ভাগশেষ 0 বা 1, কখনো 2 নয়। প্রতিটি সমীকরণের জন্য এমন একটি চতুর যুক্তি খুঁজে দেওয়ার যান্ত্রিক নিয়মই নেই; MRDP theorem ঠিক এটিই বলে।

Gödel-এর সঙ্গে যোগ. Kurt Gödel ১৯৩১ সালে দেখান, পূর্ণসংখ্যার পাটিগণিতের জন্য যুক্তিসংগত (consistent) আর যান্ত্রিকভাবে যাচাইযোগ্য যেকোনো স্বতঃসিদ্ধ-ব্যবস্থায় এমন সত্য বাক্য থাকে যা সেখানে প্রমাণ করা যায় না (অসম্পূর্ণতার উপপাদ্য)। Halting problem এর একটি দুর্বলতর রূপ সহজে দেয়: ধরুন একটি sound ব্যবস্থা “M ফাঁকা tape-এ থামে না” ধরনের প্রতিটি সত্য বাক্য প্রমাণ করতে পারে। প্রমাণ যান্ত্রিকভাবে তালিকা করা যায়, তাই M চালানো আর “M থামে না”-র প্রমাণ খোঁজা পালা করে করলে HALTε decidable হতো। তা নয়; তাই কিছু সত্য “থামে না” বাক্য অপ্রমাণযোগ্য থেকে যায়। Yedidia–Aaronson-এর যন্ত্র ঠিক এমন একটি বাক্যের নির্দিষ্ট উদাহরণ। (Gödel-এর আসল প্রমাণ আলাদা আর আরও শক্তিশালী; এখানে শুধু যোগসূত্রটি।)

৮ · প্রকৌশলীরা কীভাবে undecidability-র সঙ্গে বাঁচেন

প্রতিটি undecidable প্রশ্নের সামনে প্রকৌশলীর হাতে চারটি দরজা। প্রতিটি theorem-এর একটি করে শর্ত ছেড়ে দেয়: সব input, সঠিক উত্তর, সবসময় থামা, বা পুরো ভাষা।

কৌশলকী ছেড়ে দেয়উদাহরণ
Conservative approximation (sound analysis)নিখুঁততা: কিছু ভুল সতর্কতাtype checker, compiler-এর dead code elimination, abstract interpretation
Bounded check আর timeoutসম্পূর্ণতা: সীমার বাইরে কিছু বলে নাbounded model checking, test timeout, regex timeout
Testing, fuzzing, property-based testsound-ness: যা চেষ্টা হয়নি তা মিসunit test, coverage-guided fuzzer
“জানি না” উত্তর রাখাসবসময় হ্যাঁ/না: তৃতীয় উত্তরtermination prover, SMT solver-এর “unknown”
দুর্বল ভাষা বেছে নেওয়াপ্রকাশক্ষমতা: Turing-complete নয়regular expression, SQL-এর কিছু অংশ, total functional language, config ভাষা

শেষ সারিটি এই কোর্সের পুরো কাঠামোর ব্যবহারিক রূপ। বাজারঘরের order code “BG-” আর চারটি অঙ্ক কি না, তা একটি DFA দিয়ে যাচাই করা হয়, Turing machine দিয়ে নয়; ফলে প্রতিটি প্রশ্ন, এমনকি দুটি validator সমান কি না, decidable (পর্ব ২০)। যত কম শক্তিশালী মডেল, তত বেশি প্রশ্ন decidable; Chomsky hierarchy-তে নিচে নামা মানে নিশ্চয়তা কেনা। Software testing কোর্সের পর্ব ০৬ (static analysis), পর্ব ৫৮ (property-based testing) আর পর্ব ৬০ (fuzz testing) এই কৌশলগুলোর ব্যবহারিক দিক দেখায়।

সাধারণ ভুল ধারণা: “undecidable, তাই চেষ্টা করে লাভ নেই।” উল্টোটাই সত্য। Undecidability বলে নিখুঁত tool অসম্ভব, তাই ভালো tool-এর জন্য সবসময় জায়গা আছে; আর বাস্তব code-এর বেশিরভাগ অংশ সরল, যেখানে আনুমানিক tool প্রায় সবসময় ঠিক। দ্বিতীয় ভুল: “এই tool সব bug ধরে।” কোনো tool যদি দাবি করে যে Turing-complete ভাষার সব program-এ আচরণের একটি non-trivial ধর্ম নিখুঁতভাবে যাচাই করে আর সবসময় থামে, দাবিটি গাণিতিকভাবে মিথ্যা।

আরও গভীরে: Abstract interpretation (Patrick আর Radhia Cousot, ১৯৭৭) sound analysis-কে একটি গাণিতিক কাঠামো দেয়: মানের একটি “abstract domain” (যেমন শুধু চিহ্ন: ঋণাত্মক, শূন্য, ধনাত্মক) আর loop-এর জন্য “widening” নামের একটি কৌশল, যা নিশ্চিত করে analysis সবসময় থামে, বিনিময়ে নিখুঁততা হারিয়ে। Undecidability-র মাত্রাও আছে: HALTTM “শুধু” recognizable, কিন্তু “M সব input-এ থামে” (TOTAL) আরও এক তলা কঠিন, recognizable বা co-recognizable কোনোটিই নয়; এই তলাগুলো arithmetical hierarchy. Busy Beaver গবেষণা আজও সক্রিয়: ছোট n-এর অনেক যন্ত্রের আচরণ Collatz-ধাঁচের খোলা প্রশ্নের সঙ্গে যুক্ত বলে জানা যায়।

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

  • Sound আর complete analysis-এর পার্থক্য কী? Sound কোনো আসল bug মিস করে না (false positive থাকতে পারে); complete কোনো ভুল সতর্কতা দেয় না (false negative থাকতে পারে)।
  • নিখুঁত static analyzer কেন অসম্ভব? HALTTM ≤m CRASH: “M-কে w-এ চালান, থামলে crash” program; বা সরাসরি Rice-এর theorem.
  • Busy Beaver function গণনাযোগ্য নয় কেন? S(n) জানা থাকলে n-state যন্ত্র S(n) ধাপ চালিয়ে blank-tape halting decide করা যেত।
  • Timeout দিয়ে halting problem মেটে না কেন? প্রতিটি T-এর পরে থামা যন্ত্র আছে; আর state অনুযায়ী computable সীমা T(n) কোনো n-এ S(n)-এর চেয়ে ছোট।
  • Type checking কি undecidable? সাধারণত না: এটি syntactic নিয়ম যাচাই; তবে কিছু শক্তিশালী type system-এ (System F inference, Java generics subtyping) undecidable.

৯ · AI-এর যুগে undecidability আর code analysis

AI coding assistant আজ নিজেই একটি “analyzer”: code দেখে বলে কোথায় bug, কোন loop থামবে, কোন লাইন অপ্রয়োজনীয়। এই পর্বের theorem তার ক্ষেত্রেও খাটে: কোনো AI, যত বড়ই হোক, সব program-এ এসব প্রশ্নের নিখুঁত উত্তর দিতে পারে না, কারণ সে-ও শেষ পর্যন্ত একটি গণনা। এছাড়া এই বিষয়ে কয়েকটি ভুল AI-এর উত্তরে প্রায়ই দেখা যায়।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“এই tool/AI সব bug ধরতে পারে” বা “এই loop নিশ্চিত থামে” বিনা প্রমাণেএকটি কমতে-থাকা মাপ (যেমন n প্রতি ধাপে কমে, কখনো ঋণাত্মক নয়) চেয়ে নিন; না পেলে দাবিটি অনুমান
Sound আর complete উল্টো অর্থেপ্রশ্ন করুন: কোন ভুলটি বাদ গেল, false positive না false negative?
Reduction-এর দিক উল্টো: CRASH থেকে HALT-এ reduce করে CRASH-কে undecidable বলাজানা undecidable সমস্যা থেকে নতুনটিতে যেতে হবে: HALTTM ≤m CRASH
Busy Beaver-এর ভুল মান বা ভুল সাল (যেমন S(5) “অজানা”, বা S(4) = 13)S আর Σ আলাদা: S(4) = 107, Σ(4) = 13; নিজে simulator চালিয়ে মেলান
“Timeout বাড়ালে সমস্যা মিটবে”দেরিতে থামা একটি যন্ত্র দিয়ে timeout বিচারক পরীক্ষা করুন; অংশ ৬-এর যুক্তি মনে রাখুন
বানানো রেফারেন্স বা প্রমাণের দাবি (“X ২০২১ সালে BB(6) নির্ণয় করেন”)প্রাথমিক উৎস বা Sipser, Hopcroft–Motwani–Ullman-এ খুঁজুন; না পেলে বিশ্বাস করবেন না

AI-কে কাজে লাগানোর ভালো উপায়: তাকে দিয়ে একটি analyzer-এর ভুল খুঁজে বের করানো, আর প্রতিটি দাবি নিজে চালিয়ে যাচাই করা।

আমি গণনার তত্ত্ব শিখছি, এখন static analysis-এর সীমা নিয়ে কাজ করছি। ১. Python-এ ২০ লাইনের মধ্যে দুটি ছোট function লেখো: একটিতে mypy একটি false positive দেবে (এমন লাইনে error, যা কখনো চলে না), অন্যটিতে একটি false negative (mypy চুপ, কিন্তু runtime-এ TypeError). প্রতিটি কেন ঘটে, এক অনুচ্ছেদে ব্যাখ্যা করো। ২. Sound আর complete analysis-এর সংজ্ঞা দাও, আর বলো তোমার উদাহরণে mypy কোনটি ভাঙছে। ৩. HALT_TM থেকে CRASH = {⟨p⟩ : p কোনো input-এ crash করে}-এ একটি mapping reduction লেখো; reduction function-টি কেন computable আর কেন "⇔" দুই দিকে সত্য, ধাপে ধাপে দেখাও। ৪. কোনো সাল, নাম বা Busy Beaver-এর মান নিয়ে নিশ্চিত না হলে স্পষ্ট বলো; বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১Rice-এর theorem থাকা সত্ত্বেও বড় বড় software প্রতিষ্ঠান static analysis-এ এত বিনিয়োগ করে কেন? Sound না হয়ে “কাজের” হওয়া কেন অনেক ক্ষেত্রে ভালো কৌশল?

কারণ theorem একটি সবচেয়ে-খারাপ-ক্ষেত্রের কথা বলে, আর বাস্তব code সবচেয়ে খারাপ ক্ষেত্র থেকে অনেক দূরে। Rice-এর theorem (১৯৫৩ সালে প্রকাশিত) নিশ্চিত করে যে প্রতিটি analyzer-এর জন্য কিছু program আছে, যেখানে সে ভুল করবে; কিন্তু সেই program-গুলো প্রায়ই কৃত্রিম, যেমন “M-কে w-এ চালান, থামলে crash”. প্রতিদিনের code-এ বেশিরভাগ bug সরল ধরনের: null-এর ব্যবহার, বন্ধ না-করা ফাইল, ভুল type, সীমার বাইরে index. এগুলো ধরতে পুরো আচরণ বোঝার দরকার হয় না।

দ্বিতীয় কারণ মানুষের মনোযোগ। একটি পরিচিত শিল্প-অভিজ্ঞতা, যা বিভিন্ন প্রতিষ্ঠানের প্রকৌশলীরা প্রবন্ধে বর্ণনা করেছেন বলে জানা যায়: যদি একটি tool-এর অনেক সতর্কতা ভুল হয়, developer-রা একসময় সব সতর্কতা উপেক্ষা করতে শেখেন, আসলগুলোসহ। তাই অনেক শিল্প-tool ইচ্ছে করে unsound: তারা কিছু bug মিস করে, কিন্তু যা দেখায়, তার বেশিরভাগই আসল। এটি complete দিকের কাছাকাছি থাকা একটি আপস। mypy-ও তাই করে: Any দেখলে চুপ থাকে, যাতে পুরোনো untyped code-এ হাজার হাজার সতর্কতা না আসে।

অন্যদিকে যেখানে একটি bug-এর দাম বিশাল, যেমন বিমান বা চিকিৎসা-যন্ত্রের নিয়ন্ত্রক software, সেখানে sound tool ব্যবহারের প্রচলন বেশি বলে জানা যায়: “এই code-এ কোনো runtime error নেই” প্রমাণ করতে abstract interpretation-ভিত্তিক analyzer, আর ভুল সতর্কতাগুলো মানুষ একে একে যাচাই করেন। দাম বেশি, কিন্তু নিশ্চয়তাও বেশি। আরেকটি কৌশল হলো ভাষা নিজেই সীমিত করা: এমন coding নিয়ম মানা (যেমন অসীম recursion বা ইচ্ছেমতো pointer নিষেধ), যাতে analysis সহজ হয়। এটি অংশ ৮-এর “দুর্বল ভাষা বেছে নেওয়া”।

অর্থাৎ Rice-এর theorem বিনিয়োগ বন্ধ করার কারণ নয়, বরং বিনিয়োগের দিক ঠিক করার: কোন ভুলটি (false positive না false negative) কোন ক্ষেত্রে সহনীয়, সেই সিদ্ধান্ত।

মূল উপলব্ধি: Undecidability বলে নিখুঁত analyzer অসম্ভব, কাজের analyzer নয়; প্রকৌশলের প্রশ্ন হলো কোন ধরনের ভুল কোন ক্ষেত্রে মেনে নেওয়া যায়।

প্র ০২S(5) = 47,176,870 প্রমাণ করতে একটি সহযোগী দলের কয়েক বছর লাগল কেন, যেখানে ৫-state যন্ত্র সসীম সংখ্যক? আর computer-এ যাচাই করা প্রমাণে আস্থা রাখার কারণ কী?

যন্ত্র সসীম, কিন্তু প্রতিটির ভাগ্য জানা কঠিন। অংশ ৫-এর tree search-এর মতো খোঁজে ৫-state-এর ক্ষেত্রে প্রায় ১৮ কোটির মতো যন্ত্র আসে বলে প্রকাশিত হিসাব। প্রতিটির জন্য দুটির একটি দেখাতে হয়: যন্ত্রটি ৪৭,১৭৬,৮৭০ বা তার কম ধাপে থামে, অথবা কখনো থামে না। প্রথমটি সহজ, শুধু চালালেই হয়। দ্বিতীয়টির জন্য কোনো সাধারণ পদ্ধতি নেই, ঠিক উপপাদ্য ৫.২-এর কারণে; প্রতিটি না-থামা যন্ত্রের জন্য একটি প্রমাণ লাগে।

bbchallenge দল তাই একগুচ্ছ “decider” লেখে, প্রতিটি এক ধরনের না-থামা আচরণ চেনে: configuration ফিরে আসা, tape-এর একটি নকশা নিয়মিতভাবে বাড়া, একটি সসীম automaton দিয়ে tape-এর সম্ভাব্য সব চেহারা বর্ণনা করা, যাতে halt অবস্থা কখনো আসে না, ইত্যাদি। বেশিরভাগ যন্ত্র এই সাধারণ decider-গুলোতে ধরা পড়ে; বাকি কয়েক ডজন “কঠিন” যন্ত্রের প্রতিটির জন্য আলাদা যুক্তি লেখা হয়েছিল বলে জানা যায়। এটি এই পর্বের মূল শিক্ষার সরাসরি উদাহরণ: সাধারণ decider নেই, কিন্তু অনেকগুলো আংশিক decider মিলে একটি নির্দিষ্ট সসীম সমস্যা মেটাতে পারে।

আস্থার প্রশ্নে: চূড়ান্ত প্রমাণ Coq (এখন নাম Rocq) নামের একটি proof assistant-এ লেখা। Proof assistant-এ প্রতিটি যুক্তির ধাপ একটি ছোট, বহু-পরীক্ষিত “kernel” যাচাই করে; ফলে বিশ্বাস করতে হয় শুধু সেই kernel আর সংজ্ঞাগুলো (যেমন Turing machine আর S(n)-এর সংজ্ঞা ঠিকভাবে লেখা হয়েছে কি না), হাজার হাজার লাইনের প্রতিটি যুক্তি আলাদা করে নয়। ১৯৭৬ সালের চার-রঙের উপপাদ্যের computer-সাহায্যপ্রাপ্ত প্রমাণ নিয়ে যে বিতর্ক হয়েছিল, পরে Georges Gonthier-এর দল Coq-এ সেটি যাচাই করে সেই সংশয় অনেকটা মেটান বলে পরিচিত; BB(5)-এর ক্ষেত্রে শুরু থেকেই এই পথ নেওয়া হয়।

দলটি খোলা অনলাইন সহযোগিতায় কাজ করেছে, যেখানে অনেক অপেশাদার গবেষকও অবদান রেখেছেন বলে জানা যায়; এটি নিজেই আধুনিক গণিতের একটি নতুন ধরন।

মূল উপলব্ধি: S(5)-এর মতো একটি নির্দিষ্ট মান জানা মানে অনেক আংশিক decider আর হাতে লেখা যুক্তি দিয়ে প্রতিটি যন্ত্রের ভাগ্য নিষ্পত্তি করা; কোনো এক algorithm সব n-এ এটি পারে না।

প্র ০৩বাস্তব কম্পিউটারের memory সসীম, তাই প্রতিটি বাস্তব program আসলে একটি বিশাল finite automaton. তাহলে বাস্তবে halting problem কি decidable নয়?

নীতিগতভাবে হ্যাঁ, ব্যবহারিকভাবে না, আর পার্থক্যটি শেখার মতো। একটি যন্ত্রের memory যদি ঠিক b bit হয়, তার মোট অবস্থা বড়জোর 2b. Pigeonhole নীতি অনুযায়ী 2b ধাপের পরেও না থামলে কোনো অবস্থা পুনরাবৃত্ত হয়েছে, আর deterministic যন্ত্র তখন চিরকাল একই চক্রে ঘুরবে। তাই “2b + 1 ধাপ চালান” একটি সঠিক decider (পর্ব ৫১-এও এটি এসেছে)।

কিন্তু সংখ্যাটি দেখুন। মাত্র এক কিলোবাইট memory মানে b = 8192, আর 28192 একটি প্রায় আড়াই হাজার অঙ্কের সংখ্যা; মহাবিশ্বের আনুমানিক কণার সংখ্যা এর তুলনায় নগণ্য। আধুনিক কম্পিউটারের গিগাবাইট memory-র কথা বাদই দিন। অর্থাৎ decidability আর practicality আলাদা প্রশ্ন, ঠিক যেমন পর্ব ৫০-এ দেখেছেন decidable সমস্যাও দ্বিগুণ সূচকীয় সময় নিতে পারে।

দ্বিতীয় সমস্যা মডেলিংয়ের। একটি program চলার সময় ফাইল লেখে, network থেকে তথ্য আনে, প্রয়োজনে আরও memory চায়। Program-টি কোন যন্ত্রে চলবে, কতটা memory পাবে, তা code-এ লেখা থাকে না। তাই program নিয়ে চিন্তা করার সবচেয়ে সৎ মডেল হলো সীমাহীন memory-র যন্ত্র, অর্থাৎ Turing machine. এই কারণেই theorem-গুলো Turing machine নিয়ে বলা হয়।

তবু সসীমতার ধারণা ব্যবহারিক tool-এ সত্যিই কাজে লাগে। Model checking (পর্ব ৭৭) সসীম অবস্থার ব্যবস্থায় সব reachable অবস্থা খোঁজে, আর bounded model checking k ধাপ পর্যন্ত সব পথ একটি SAT সূত্রে বেঁধে খোঁজে। এগুলো সফল হয় কারণ তারা পুরো কম্পিউটার নয়, একটি ছোট বিমূর্ত মডেল বিশ্লেষণ করে, যেমন একটি protocol-এর ২০টি অবস্থা।

মূল উপলব্ধি: সসীম memory-র যন্ত্রে halting নীতিগতভাবে decidable, কিন্তু অবস্থার সংখ্যা এত বিশাল যে তা অর্থহীন; তাই theorem-এর জন্য সীমাহীন memory-র মডেলই সঠিক, আর ব্যবহারিক tool ছোট বিমূর্ত মডেল বেছে নেয়।

প্র ০৪Wang tiling-এর মতো নিছক জ্যামিতিক প্রশ্ন কীভাবে Turing machine-এর সমান কঠিন হয়? Aperiodic tiling-এর আবিষ্কার গণিত আর বিজ্ঞানে কী প্রভাব ফেলেছে?

মূল ধারণা হলো tile-কে “স্থানীয় নিয়ম” হিসেবে দেখা। একটি Turing machine-এর প্রতিটি ধাপও স্থানীয়: পরের configuration-এর একটি ঘর শুধু আগের configuration-এর কাছাকাছি কয়েকটি ঘরের ওপর নির্ভর করে। তাই একটি tile-এর উত্তর কিনারায় “আগের সারির এই ঘরে কী ছিল” আর দক্ষিণ কিনারায় “এই সারিতে কী আছে” লেখা যায়, আর পূর্ব-পশ্চিম কিনারা দিয়ে head-এর অবস্থান আর state পাশের ঘরে পাঠানো যায়। রং মেলানোর নিয়ম তখন ঠিক transition function-এর কাজ করে। পর্ব ৫৪-এ PCP-এর ডমিনো দিয়ে একই কাজ এক মাত্রায় হয়েছিল; এখানে দুই মাত্রা।

কঠিন অংশটি Berger-এর: সমতলের কোথা থেকে যন্ত্র শুরু হবে, তা কেউ বলে দেয় না; tile-set-কে নিজেই সমতলকে বড় থেকে আরও বড় “বর্গাকার কাঠামোয়” ভাগ করতে বাধ্য করতে হয়, প্রতিটির ভেতরে যন্ত্রের একটি সসীম অংশ চলে। এই স্ব-সদৃশ কাঠামো স্বভাবতই পর্যায়ক্রমিক নয়, আর এভাবেই প্রথম aperiodic tile-set আসে। ১৯৬৬ সালে Berger-এর set-এ বিশ হাজারের বেশি tile ছিল বলে পরিচিত; Raphael Robinson ১৯৭১ সালে মাত্র ছয়টি প্রান্তিক-আকারের tile দিয়ে কাজটি সরল করেন বলে জানা যায়।

এরপর Roger Penrose ১৯৭০-এর দশকে দুটি আকারের aperiodic tiling দেখান, যা জনপ্রিয় গণিতের প্রতীক হয়ে ওঠে। ১৯৮২ সালে Dan Shechtman এমন একটি ধাতব সংকর আবিষ্কার করেন, যার পরমাণুর বিন্যাস নিয়মিত কিন্তু পর্যায়ক্রমিক নয় (quasicrystal); প্রথমে অনেক বিজ্ঞানী বিশ্বাস করেননি, পরে ২০১১ সালে এর জন্য তিনি রসায়নে Nobel পুরস্কার পান। Aperiodic tiling-এর গণিত এই কাঠামো বোঝার একটি ভাষা দিয়েছিল। আর ২০২৩ সালে একটি দল একটিমাত্র আকারের aperiodic tile (“hat” নামে পরিচিত) খুঁজে পায় বলে ঘোষণা করে, যা দীর্ঘদিনের একটি প্রশ্নের উত্তর।

Computability-র দিক থেকে শিক্ষাটি হলো: যেখানেই স্থানীয় নিয়ম অসীম জায়গায় প্রয়োগ হয়, সেখানে Turing machine লুকিয়ে থাকতে পারে; cellular automaton (পর্ব ৪৯) এর আরেকটি উদাহরণ।

মূল উপলব্ধি: Tile-এর রং মেলানো একটি Turing machine-এর স্থানীয় transition নকল করতে পারে, তাই tiling undecidable; আর এই প্রমাণের উপজাত aperiodic tiling পরে পদার্থবিজ্ঞানের quasicrystal বোঝায় কাজে লেগেছে।

প্র ০৫Hilbert চেয়েছিলেন গণিতের প্রতিটি প্রশ্নের যান্ত্রিক সমাধান। Gödel, Turing আর Matiyasevich-এর ফল কি গণিতের জন্য পরাজয়, নাকি অন্য কিছু?

Hilbert-এর আশা ছিল দুটি: গণিতের একটি সম্পূর্ণ আর সংগত স্বতঃসিদ্ধ-ব্যবস্থা, আর একটি যান্ত্রিক পদ্ধতি যা যেকোনো বাক্যের সত্যতা নির্ণয় করবে (Entscheidungsproblem, ১৯২৮ সালের দিকে স্পষ্টভাবে বলা)। ১৯৩০ সালে এক বক্তৃতায় তাঁর বিখ্যাত উক্তি “আমাদের জানতেই হবে, আমরা জানব” প্রায়ই উদ্ধৃত হয়। ঠিক তার আগের দিনই, একই শহরের এক সম্মেলনে, Gödel তাঁর অসম্পূর্ণতার ফলের প্রথম ঘোষণা দেন বলে গল্পটি পরিচিত।

১৯৩১ সালে Gödel প্রথম আশাটি ভাঙেন; ১৯৩৬ সালে Church আর Turing দ্বিতীয়টি। Hilbert-এর দশম সমস্যা, যা ১৯০০ সালে একটি পদ্ধতি চেয়েছিল, ১৯৭০ সালে Matiyasevich-এর হাতে নেতিবাচক উত্তর পায়; লক্ষ করুন, ১৯০০ সালে “algorithm”-এর কোনো নিখুঁত সংজ্ঞাই ছিল না, তাই নেতিবাচক উত্তর দেওয়াই সম্ভব ছিল না। Turing machine সেই সংজ্ঞা দিয়েছে (পর্ব ৪৭)।

কিন্তু এটিকে পরাজয় বলা কঠিন, তিনটি কারণে। প্রথম, সীমা জানা নিজেই জ্ঞান: পদার্থবিজ্ঞানে আলোর গতির সীমা বা তাপগতিবিদ্যার দ্বিতীয় সূত্রের মতো, এই ফলগুলো বলে কী চেষ্টা করা বৃথা, আর গবেষণাকে সঠিক প্রশ্নে পাঠায়। দ্বিতীয়, এই প্রমাণগুলো থেকেই কম্পিউটার বিজ্ঞানের জন্ম: Turing-এর universal machine (পর্ব ৪৮) stored-program কম্পিউটারের তাত্ত্বিক রূপ, এসেছে ঠিক এই নেতিবাচক উত্তর দেওয়ার প্রয়োজনে। তৃতীয়, গণিতবিদরা থেমে থাকেননি: সীমিত ক্ষেত্রে decidability পাওয়া গেছে (Presburger arithmetic, বাস্তব সংখ্যার বীজগণিতে Tarski-র পদ্ধতি), আর proof assistant আজ মানুষের প্রমাণ যান্ত্রিকভাবে যাচাই করে, যা Hilbert-এর স্বপ্নের একটি দুর্বল কিন্তু বাস্তব রূপ।

বাজারঘরের প্রকৌশলীর জন্যও একই শিক্ষা: “সব ধরা” যাচাইকারী নেই জানলে তিনি ভালো test, স্পষ্ট নিয়মের ভাষা আর সৎ timeout বানান, অসম্ভবের পেছনে সময় নষ্ট করেন না।

মূল উপলব্ধি: Gödel, Turing আর Matiyasevich দেখিয়েছেন যান্ত্রিক পদ্ধতির নিখুঁত সীমা কোথায়; সেই সীমা চেনা থেকেই কম্পিউটার বিজ্ঞান আর আধুনিক যাচাই-পদ্ধতির জন্ম, তাই এটি পরাজয় নয়, একটি মানচিত্র।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। bb_search.py, timeout_judge.js আর diophantine.py-তে নিজের input বসিয়ে উত্তর যাচাইও করতে পারেন।

  1. নির্মাণ: বাজারঘরের একটি নিয়ম: “SMS পাঠানোর function send_sms(number) কখনো ফাঁকা number দিয়ে ডাকা হবে না।” EMPTY_SMS = {⟨p⟩ : p কোনো input-এ send_sms("") ডাকে}. HALTTM থেকে EMPTY_SMS-এ একটি mapping reduction নির্মাণ করুন, আর ব্যাখ্যা করুন কেন এই নিয়মের নিখুঁত যাচাইকারী নেই।

    f(⟨M, w⟩) = ⟨pM,w⟩, যেখানে pM,w = “নিজের input উপেক্ষা করুন; M-কে w-এর ওপর অনুকরণ করুন; থামলে send_sms("") ডাকুন।” অনুকরণের অংশে send_sms কোথাও নেই। f শুধু একটি কাঠামোয় M আর w বসায়, M চালায় না, তাই computable.

    সঠিকতা: M w-এ থামলে pM,w প্রতিটি input-এ ফাঁকা SMS পাঠায়, তাই ⟨pM,w⟩ ∈ EMPTY_SMS; না থামলে কখনো send_sms লাইনে পৌঁছায় না, তাই ∉. অর্থাৎ ⟨M, w⟩ ∈ HALTTM ⇔ f(⟨M, w⟩) ∈ EMPTY_SMS, আর HALTTM ≤m EMPTY_SMS. HALTTM undecidable, তাই EMPTY_SMS-ও। একটি সবসময়-থামা, sound আর complete যাচাইকারী ঠিক EMPTY_SMS-এর decider হতো, তাই তা নেই। বাস্তবে প্রকৌশলীরা একটি sound নিয়ম বেছে নেন, যেমন “send_sms-এর আগে সবসময় একটি স্পষ্ট শূন্য-নয় পরীক্ষা থাকতে হবে”, যা কোড দেখেই যাচাই করা যায়।

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: S(n) computable. প্রমাণ: প্রতিটি n-এর জন্য n-state যন্ত্র সসীম সংখ্যক। সবগুলো ফাঁকা tape-এ চালাই, যারা থামে তাদের ধাপের সংখ্যা লিখি, আর সর্বোচ্চটি নিই। সসীম সংখ্যক সংখ্যার সর্বোচ্চ সবসময় নেওয়া যায়। ∎” ভুলটি কোথায়?

    ভুল ধাপটি “সবগুলো চালাই, যারা থামে তাদের ধাপ লিখি”। না-থামা যন্ত্র চালানো কখনো শেষ হয় না, আর কোন যন্ত্র থামবে না, তা আগে থেকে জানার উপায় নেই (HALTε undecidable). তাই এই “algorithm” কোনো n-এ, যেখানে অন্তত একটি না-থামা যন্ত্র আছে (n ≥ 1-এ সবসময় আছে), নিজেই থামে না। পালা করে চালালেও লাভ নেই: কখন থামবেন? থামার মুহূর্ত বলতে হলে S(n) আগে থেকেই জানা লাগে।

    সূক্ষ্ম আরেকটি বিভ্রান্তি: “প্রতিটি S(n) একটি নির্দিষ্ট সংখ্যা” সত্য, আর প্রতিটি নির্দিষ্ট n-এর জন্য “S(n) লিখে দেয়” এমন একটি তুচ্ছ যন্ত্রও আছে। কিন্তু computable function মানে একটি একক যন্ত্র, যা সব n-এ কাজ করে। উপপাদ্য ৫.২ দেখায় এমন যন্ত্র নেই।

  3. Trace আর আউটপুট অনুমান: 2-state যন্ত্র 1RB1RZ_1LB1LA: A0 → 1RB, A1 → 1RZ, B0 → 1LB, B1 → 1LA. ফাঁকা tape থেকে u q v রূপে প্রতিটি configuration লিখুন। মোট কত ধাপ, কয়টি 1? অংশ ৬-এর timeout বিচারক T = 5 আর T = 6-এ কী বলবে?

    A 0 ⊢ 1 B 0 ⊢ B 11 ⊢ A 011 ⊢ 1 B 11 ⊢ A 111 ⊢ 1 Z 11. ধাপগুলো: (১) A0 → 1RB; (২) B0 → 1LB, head শুরুর ঘরে; (৩) B1 → 1LA, head বাঁয়ে নতুন ঘরে; (৪) A0 → 1RB; (৫) B1 → 1LA; (৬) A1 → 1RZ, থামা। মোট ৬ ধাপ, tape-এ তিনটি 1.

    T = 5: পাঁচ ধাপ পরে যন্ত্র এখনো চলছে (state A), বিচারক ভুল করে “LOOPS” বলবে। T = 6: ষষ্ঠ ধাপে থামে, “HALTS”. এটিও একটি 2-state যন্ত্র যা ঠিক S(2) = 6 ধাপ চলে, কিন্তু Σ(2) = 4-এর চেয়ে কম 1 লেখে: S আর Σ-এর চ্যাম্পিয়ন আলাদা হতে পারে। timeout_judge.js-এ যন্ত্রটি {A: [[1, 1, "B"], [1, 1, "Z"]], B: [[1, -1, "B"], [1, -1, "A"]]} লিখে যাচাই করুন।

  4. হিসাব: (ক) x2 − 5y2 = 1-এর সবচেয়ে ছোট ধনাত্মক পূর্ণসংখ্যা সমাধান কী? (খ) প্রমাণ করুন x2 − 5y2 = 2-এর কোনো পূর্ণসংখ্যা সমাধান নেই। (গ) diophantine.py-এর search() (খ)-এর সমীকরণে কী ছাপবে, আর সেই ছাপা কেন নিজে কোনো প্রমাণ নয়?

    (ক) y = 1: x2 = 6, পূর্ণবর্গ নয়। y = 2: 21, নয়। y = 3: 46, নয়। y = 4: 81 = 92. তাই (x, y) = (9, 4); যাচাই: 81 − 80 = 1. search(5, 1, 100_000) ছাপবে FOUND x=9, y=4.

    (খ) সমীকরণটি 5 দিয়ে ভাগশেষে দেখুন: x2 ≡ 2 (mod 5). x-এর ভাগশেষ 0, 1, 2, 3, 4 হলে x2-এর ভাগশেষ যথাক্রমে 0, 1, 4, 4, 1. এদের মধ্যে 2 নেই, তাই কোনো পূর্ণসংখ্যা x এটি মানে না, আর সমীকরণের সমাধান নেই। ∎

    (গ) ছাপবে NO ANSWER after y=100,000 (cap). এটি শুধু বলে y ≤ 100,000-এ সমাধান নেই; x2 − 61y2 = 1-ও ঠিক একই লাইন ছাপে, অথচ তার সমাধান আছে। “নেই”-এর প্রমাণ এসেছে (খ)-এর mod 5 যুক্তি থেকে, খোঁজ থেকে নয়।

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

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

ক্রম“S(n) গণনাযোগ্য নয়” প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. ধরে নেওয়া: একটি যন্ত্র B প্রতিটি n-এ থেমে S(n) লেখে
  2. Input ⟨M⟩ পেলে M-এর state গুনে n বের করা
  3. B দিয়ে S(n) হিসাব করা
  4. M-কে ফাঁকা tape-এ বড়জোর S(n) ধাপ চালানো, থামলে গ্রহণ, নইলে বর্জন
  5. এভাবে blank-tape halting problem decidable হয়, যা অসম্ভব; তাই B নেই

একটি static analyzer সব program-এ থামে আর “program কোনো input-এ শূন্য দিয়ে ভাগ করতে পারে কি না” প্রশ্নের উত্তর দেয় (Turing-complete ভাষায়)। নিচের কোনটি অবশ্যই সত্য?

  • এটি অবশ্যই কিছু ভুল সতর্কতা (false positive) দেয়
  • কিছু program-এ এটি ভুল করে: false positive বা false negative, অন্তত একটি
  • এটি অবশ্যই কিছু আসল bug মিস করে (false negative)
  • যথেষ্ট ভালো algorithm হলে এটি কখনো ভুল করবে না

একটি bug-খোঁজার analyzer-কে “sound” বলা হয় (যে অর্থে কোনো আসল bug বাদ যায় না)। এর মানে কী?

  • “ok” বললে program-এ সেই ধরনের bug নিশ্চিত নেই, যদিও কিছু সতর্কতা ভুল হতে পারে
  • প্রতিটি সতর্কতা একটি আসল bug
  • এটি কখনো ভুল করে না
  • এটি যত সময়ই লাগুক, শেষে থামে

Busy Beaver function S(n) (n-state, দুই-চিহ্নের যে যন্ত্রগুলো ফাঁকা tape-এ থামে, তাদের সর্বোচ্চ ধাপ) সম্পর্কে কোনটি সঠিক?

  • S(n) কিছু n-এর জন্য সংজ্ঞায়িতই নয়
  • S(n) ≤ 2n সব n-এর জন্য
  • S গণনাযোগ্য হলে blank-tape halting problem decidable হতো
  • S(5) এখনো সম্পূর্ণ অজানা

একটি “timeout বিচারক” যেকোনো যন্ত্র ১০০০ ধাপ চালায়, না থামলে “LOOPS” বলে। একটি যন্ত্রে সে “LOOPS” বলল। নিশ্চিতভাবে কী জানা গেল?

  • যন্ত্রটি কখনো থামবে না
  • যন্ত্রটি একটি configuration-এর চক্রে ঘুরছে
  • যন্ত্রটির ১০০০-এর বেশি state আছে
  • যন্ত্রটি প্রথম ১০০০ ধাপে থামেনি, এর বেশি কিছু নয়

একটি Wang tile-set দিয়ে ৫ × ৫ বর্গ ঢাকা যায়, কিন্তু ৬ × ৬ বর্গ ঢাকা যায় না (tile ঘোরানো নিষেধ, মিলিত কিনারার রং এক হতে হবে)। এই set সম্পর্কে কী বলা যায়?

  • এটি সমতলকে aperiodic ভাবে ঢাকে
  • এটি পুরো সমতল ঢাকতে পারে না
  • এর উত্তর undecidable, তাই জানা যায় না
  • এটি সমতলকে পর্যায়ক্রমিক ভাবে ঢাকে

Hilbert-এর দশম সমস্যা (পূর্ণসংখ্যা-সহগের বহুপদী সমীকরণের পূর্ণসংখ্যা সমাধান আছে কি না) সম্পর্কে MRDP theorem থেকে কোনটি পাওয়া যায়?

  • সমাধান থাকলে খোঁজে তা পাওয়া যায়, কিন্তু “সমাধান নেই” বলার কোনো সাধারণ algorithm নেই
  • কোনো সমীকরণেই “সমাধান নেই” প্রমাণ করা যায় না
  • প্রতিটি সমাধানযোগ্য সমীকরণের একটি সমাধান 100,000-এর মধ্যে থাকে
  • প্রশ্নটি decidable, তবে algorithm খুব ধীর

শব্দকোষ

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

মনে রাখুন

  1. Sound analyzer কোনো আসল bug মিস করে না, complete analyzer কোনো ভুল সতর্কতা দেয় না; non-trivial semantic প্রশ্নে সবসময়-থামা কোনো tool দুটি একসঙ্গে হতে পারে না (HALTTM ≤m CRASH).
  2. mypy-এর মতো বাস্তব tool দুই ধরনের ভুলই করে: কখনো না-চলা লাইনে error, আর Any-এর পেছনে লুকানো সত্যিকারের crash.
  3. Type checking সাধারণত decidable, কারণ সেটি syntactic নিয়ম যাচাই; কিছু শক্তিশালী type system-এ তা undecidable. Compiler শুধু নিশ্চিত মৃত কোড মোছে।
  4. S(n) গণনাযোগ্য নয় আর যেকোনো computable function-এর চেয়ে দ্রুত বাড়ে; S(2) = 6, S(3) = 21, S(4) = 107, S(5) = 47,176,870. কোনো computable timeout নিয়ম halting decide করে না।
  5. Wang tiling আর Hilbert-এর দশম সমস্যা undecidable; দুটিতেই “হ্যাঁ” বা “না”-এর একটি দিক খোঁজে পাওয়া যায়, অন্য দিকের সাধারণ পদ্ধতি নেই।

পরের পর্বে: Recursion theorem আর Kolmogorov complexity: একটি যন্ত্র কীভাবে নিজের বর্ণনা পায়, quine, আর একটি string-এর “তথ্যের পরিমাণ” কেন গণনা করা যায় না।

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

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