এই পর্বে যা শিখবেন
- Lambda term লিখে free আর bound variable চেনা, capture এড়িয়ে substitution আর β-reduction করা
- Church numeral দিয়ে যোগ-গুণ, normal order বনাম applicative order, আর Y combinator দিয়ে নামহীন recursion বোঝা
- Primitive recursive আর μ-recursive function-এর সংজ্ঞা দেওয়া, আর Ackermann কেন primitive recursive নয় তার রূপরেখা বলা
- Counter machine-এর program লিখে trace করা, আর দুই counter কেন যথেষ্ট তার প্রমাণের ধাপ সাজানো
- Rule 110-এর একটি প্রজন্ম হাতে হিসাব করা, আর Turing-completeness-এর দাবির শর্তগুলো সাবধানে বলা
১ · এক প্রশ্নের অনেক উত্তর — কেন অন্য মডেল
পর্ব ৪৩ থেকে ৪৮ জুড়ে একটিমাত্র মডেল দেখেছেন: tape, head আর সসীম নিয়মের Turing machine, তার নকশা (পর্ব ৪৪) আর রূপভেদ। কিন্তু ১৯৩০-এর দশকে “যান্ত্রিকভাবে গণনা করা যায়” কথাটির গাণিতিক সংজ্ঞা খুঁজতে গিয়ে কয়েকজন গবেষক প্রায় একসঙ্গে সম্পূর্ণ আলাদা উত্তর দেন। Alonzo Church দেন function-ভিত্তিক lambda calculus; Gödel আর Herbrand-এর কাজ থেকে Kleene দাঁড় করান recursive function; Turing দেন যন্ত্র; Emil Post দেন string-পুনর্লিখনের নিয়ম। পরে এল register machine, cellular automaton আর আরও অনেক কিছু। আশ্চর্যের বিষয়: যতবার কেউ নতুন একটি যুক্তিসংগত মডেল এনেছেন, ততবার প্রমাণ হয়েছে যে সেটি ঠিক একই function-গুলো গণনা করে।
ঢাকা থেকে চট্টগ্রামে একটি পার্সেল পাঠানোর কথা ভাবুন। ট্রেনে, বাসে, ট্রাকে বা জাহাজে পাঠানো যায়। ভাড়া, সময় আর ঝামেলা আলাদা, কিন্তু “কোন কোন জায়গায় পৌঁছানো যায়”, এই প্রশ্নের উত্তর সবার জন্য একই। গণনার মডেলগুলোও তেমন: কোনটি দিয়ে কত দ্রুত বা কত সহজে লেখা যায়, তা আলাদা, কিন্তু কোন কোন function আদৌ গণনা করা যায়, সেই তালিকা একই। এই পর্বে প্রতিটি “যানবাহন” চালিয়ে দেখবেন, আর কেন তারা একই গন্তব্যে পৌঁছায়, তার প্রমাণের রূপরেখা পাবেন।
এই মিল থেকেই Church–Turing thesis-এর জোর আসে; thesis-টির সঠিক বক্তব্য, ইতিহাস আর কেন এটি প্রমাণযোগ্য theorem নয়, তা পর্ব ৪৭-এ আছে; সেখানে মডেলগুলোর সমতার theorem-এর রূপরেখাও দেওয়া আছে। এখানে কাজ ভিন্ন: মডেলগুলো নিজের হাতে চালানো আর প্রতিটি সমতার পেছনের কৌশল দেখা। “সমান” কথাটির অর্থ আগে স্থির করা যাক।
দুটি মডেল X আর Y-কে সমান শক্তিশালী বলা হয়, যদি X-এর প্রতিটি program-এর জন্য এমন একটি Y-program থাকে যা একই (আংশিক) function গণনা করে, আর উল্টোটাও। এখানে function মানে ℕ থেকে ℕ (বা Σ∗ থেকে Σ∗), আর input-output-কে প্রতিটি মডেলের নিজস্ব রূপে লেখা হয়: tape-এ string, Church numeral, counter-এ সংখ্যা ইত্যাদি। রূপান্তরগুলো নিজেরা সহজ ও যান্ত্রিক হতে হয়, নইলে আসল কাজ encoding-ই করে ফেলতে পারে।
প্রতিটি সমতার প্রমাণ একটি simulation argument: একটি মডেলের প্রতিটি configuration অন্য মডেলে কীভাবে লেখা হবে, আর এক ধাপ কয়টি ধাপে অনুকরণ হবে। নিচের মানচিত্রে মাঝখানে Turing machine; প্রতিটি দুই-মাথা তীর মানে “দুই দিকেই অনুকরণ প্রমাণিত”। নিচের ড্যাশ-দেওয়া বাক্সে এমন মডেল, যারা কম শক্তিশালী।
গণনার মডেলের মানচিত্র
মাঝে Turing machine. দুই-মাথা তীর: সমান শক্তি প্রমাণিত। নিচে: যারা সবসময় থামে বা যাদের স্মৃতি সীমিত, তারা কম শক্তিশালী।
২ · Lambda calculus — শুধু function দিয়ে গণনা
Church ১৯৩০-এর দশকের শুরুতে lambda calculus তৈরি করেন, প্রথমে logic-এর ভিত্তি হিসেবে। সেই বড় পরিকল্পনাটি ১৯৩৫ সালে Kleene আর Rosser-এর খুঁজে পাওয়া একটি স্ববিরোধে আটকে যায়, কিন্তু function-এর অংশটুকু, যাকে আজ “বিশুদ্ধ” বা untyped lambda calculus বলা হয়, গণনার মডেল হিসেবে টিকে যায়। এর ব্যাকরণ মাত্র তিন লাইনের।
Variable-এর একটি অসীম set V ধরে, lambda term-এর set Λ সবচেয়ে ছোট set যাতে: (১) প্রতিটি variable x ∈ V একটি term; (২) M term আর x variable হলে λx.M একটি term (abstraction: “x নিয়ে M ফেরত দেয় এমন function”); (৩) M, N term হলে M N একটি term (application: M-কে N-এর ওপর প্রয়োগ)। রীতি: application বাঁ দিক থেকে জোড়ে, M N P = (M N) P; আর λ-এর body যতদূর সম্ভব ডানে যায়, λx.M N = λx.(M N).
Python-এ lambda x: x + 1 লিখলে আপনি এই abstraction-ই ব্যবহার করছেন, নামটিও এখান থেকে এসেছে (Python কোর্সের পর্ব ৪১)। পার্থক্য হলো, lambda calculus-এ সংখ্যা, যোগ, if, loop কিছুই আগে থেকে নেই; সব বানাতে হয় শুধু function দিয়ে।
Free আর bound. λx.M-এ M-এর ভেতরের x-গুলো এই λ দিয়ে বাঁধা (bound). যে variable কোনো λ দিয়ে বাঁধা নয়, সেটি free variable. λx.λy.x y z-এ x আর y bound, z free. বাঁধা variable-এর নাম বদলালে অর্থ বদলায় না: λx.x আর λy.y একই identity function. এই নাম বদলকে বলে α-conversion.
M[x := N] মানে M-এর প্রতিটি free x-এর জায়গায় N বসানো, এমনভাবে যাতে N-এর কোনো free variable ভেতরের কোনো λ-এ “ধরা না পড়ে” (capture). ধরা পড়ার সম্ভাবনা থাকলে আগে সেই λ-এর variable-এর নাম বদলে নিতে হয়। β-rule: (λx.M) N → M[x := N]. (λx.M) N আকারের অংশকে বলে redex. যে term-এ কোনো redex নেই, সেটি β-normal form-এ আছে: হিসাবের “উত্তর”।
Capture-এর একটি উদাহরণ: (λx.λy.x) y. সরল প্রতিস্থাপনে পাওয়া যেত λy.y, অর্থাৎ identity, অথচ আসল অর্থ “যেকোনো input-এ বাইরের y ফেরত দেওয়া”। সঠিক ফল λy′.y, যেখানে ভেতরের y-এর নাম বদলে y′. বহু AI-লেখা ও ছাত্র-লেখা interpreter ঠিক এখানেই ভুল করে।
সংখ্যা: Church numeral. সংখ্যা n হলো “কোনো function f-কে n বার প্রয়োগ করা”: 0 = λf.λx.x, 1 = λf.λx.f x, 2 = λf.λx.f (f x), 3 = λf.λx.f (f (f x)). তাহলে SUCC = λn.λf.λx.f (n f x): n বার f, তারপর আরও একবার। যোগ PLUS = λm.λn.λf.λx.m f (n f x): আগে n বার, তার ওপর m বার। গুণ MULT = λm.λn.λf.m (n f): “n বার f” কাজটিকেই m বার। একটি unary সংখ্যাপদ্ধতি, শুধু চিহ্নের বদলে function-প্রয়োগ দিয়ে গোনা।
নিচের stepper PLUS 1 2-কে normal order-এ কমায়: প্রতিবার সবচেয়ে বাঁয়ের, সবচেয়ে বাইরের redex. পড়ার সুবিধার জন্য যতক্ষণ খোলা হয়নি, ততক্ষণ 1 আর 2 নামেই লেখা।
1PLUS = λm.λn.λf.λx.m f (n f x)2β: m := 13β: n := 241 = λf.λx.f x52 = λf.λx.f (f x)
| term | |
| β-ধাপ | |
| পরের redex |
- শুরু। PLUS-এর সংজ্ঞা বসানো হলো। সবচেয়ে বাইরের redex হলো PLUS আর তার প্রথম argument 1.
- m := 1. Body-তে m-এর জায়গায় 1. বাকি λn এখন 2-এর অপেক্ষায়। 1-এ কোনো free variable নেই, তাই capture-এর ভয় নেই।
- n := 2. এখন term-টি “f আর x নিয়ে, 1 f (2 f x) ফেরত দেওয়া”। বাইরে আর redex নেই; normal order তাই λf.λx-এর ভেতরে ঢোকে, বাঁ দিক থেকে।
- 1 f. 1 = λf.λx.f x-কে f-এর ওপর প্রয়োগ: ফল λx.f x, অর্থাৎ “একবার f”. বাইরের f আর 1-এর ভেতরের f আলাদা variable, কিন্তু এখানে নাম বদলের দরকার পড়েনি।
- একবার f. (λx.f x) প্রয়োগ হলো (2 f x)-এর ওপর: ফল f (2 f x). বাইরের f-টি m = 1-এর অবদান।
- 2 f. এবার ভেতরের redex: 2 f = λx.f (f x), অর্থাৎ “দুবার f”. Normal order সবসময় বাঁয়ের redex আগে নেয়, তাই এটি শেষে এল।
- Normal form. (λx.f (f x)) x → f (f x). মোট f (f (f x)): তিনবার f, অর্থাৎ Church numeral 3. ছয়টি β-ধাপ; নিচের Python reducer হুবহু একই ক্রম ছাপে।
৩ · Reduction-এর কৌশল, Church–Rosser আর Y combinator
একটি term-এ একাধিক redex থাকলে কোনটি আগে? দুটি প্রধান নীতি। Normal order: সবচেয়ে বাঁয়ের-বাইরের redex আগে; argument হিসাব না করেই function-এ বসিয়ে দেওয়া। Applicative order: আগে argument-কে normal form-এ আনা, তারপর প্রয়োগ; Python, C, Java-র call-by-value এই রকম। পছন্দ কি ফল বদলাতে পারে? নিচের Church–Rosser theorem বলে, উত্তর পেলে উত্তর একটিই।
M থেকে দুই ভিন্ন reduction-ক্রমে N1 আর N2 পাওয়া গেলে এমন P আছে, যাতে N1 আর N2 দুটি থেকেই P-তে পৌঁছানো যায়। ফলে কোনো term-এর normal form থাকলে তা একটিই (α-conversion বাদে)। সঙ্গে আরেকটি ফল (standardization): normal form থাকলে normal order সেখানে পৌঁছাবেই। প্রমাণ এখানে বাদ; Barendregt-এর The Lambda Calculus (১৯৮৪) বা যেকোনো lambda calculus পাঠ্যবইয়ে আছে।
“পৌঁছাবেই” কথাটির পরীক্ষা: Ω = (λx.x x)(λx.x x). একবার β করলে ঠিক একই term ফেরত আসে, তাই Ω-এর কোনো normal form নেই; এটি lambda calculus-এর অসীম loop. এখন K = λa.λb.a নিন, যা দ্বিতীয় argument ফেলে দেয়। K z Ω-এর normal form z, আর normal order দুই ধাপে সেখানে যায়। কিন্তু applicative order আগে argument Ω-কে কমাতে চায় এবং চিরকাল আটকে থাকে। কৌশলের পছন্দ উত্তর বদলায় না, কিন্তু উত্তর পাওয়া যাবে কি না, তা বদলাতে পারে।
নিচের দুটি ব্লক একসঙ্গে একটি ছোট lambda reducer: প্রথমটি parser, printer আর capture-এড়ানো substitution; দ্বিতীয়টি normal-order ধাপ আর একটি step cap, যাতে Ω-এর মতো term ব্রাউজার আটকে না দেয়।
import re
def parse(s): # λx.body; application = juxtaposition
tk = re.findall(r"[λ.()]|[a-z0-9]+", s)[::-1]
def term(): # a λ-body runs to ")" or to the end
t = None
while tk and tk[-1] != ")":
x = tk.pop()
if x == "λ": v = tk.pop(); tk.pop(); a = ("lam", v, term())
elif x == "(": a = term(); tk.pop()
else: a = ("var", x)
t = a if t is None else ("app", t, a)
return t
return term()
def show(t):
if t[0] == "var": return t[1]
if t[0] == "lam": return f"λ{t[1]}.{show(t[2])}"
f, a = show(t[1]), show(t[2])
return (f"({f})" if t[1][0] == "lam" else f) + " " + (a if t[2][0] == "var" else f"({a})")
def free(t):
return ({t[1]} if t[0] == "var" else free(t[2]) - {t[1]} if t[0] == "lam"
else free(t[1]) | free(t[2]))
def subst(t, x, s): # t[x := s] without variable capture
if t[0] == "var": return s if t[1] == x else t
if t[0] == "app": return ("app", subst(t[1], x, s), subst(t[2], x, s))
y, b = t[1], t[2]
if y == x: return t
if y in free(s): # rename the bound y to a fresh name first
z = y + "'"
while z in free(s) | free(b): z += "'"
b, y = subst(b, y, ("var", z)), z
return ("lam", y, subst(b, x, s))
t = parse("λx.λy.x y z")
print(show(t), " free:", sorted(free(t)))
print("(λy.x)[x := z] =", show(subst(parse("λy.x"), "x", parse("z"))))
print("(λy.x)[x := y] =", show(subst(parse("λy.x"), "x", parse("y"))))আসল আউটপুট (ব্রাউজারের Python):
λx.λy.x y z free: ['z']
(λy.x)[x := z] = λy.z
(λy.x)[x := y] = λy'.y
Term-কে tuple হিসেবে রাখা হয়েছে: ("var", x), ("lam", x, body), ("app", M, N). প্রথম লাইনে printer রীতি মেনে বন্ধনী বাদ দিয়েছে, আর free variable শুধু z. দ্বিতীয় লাইনে capture-এর ভয় নেই, তাই সরাসরি প্রতিস্থাপন। তৃতীয় লাইনেই ফাঁদ: বসানো হচ্ছে y, আর ভেতরের λ-ও y বাঁধে। Code আগে ভেতরের y-কে y′ নাম দেয়, তারপর বসায়: λy′.y, যা “সবসময় বাইরের y” এই অর্থ রাখে।
def step(t): # normal order: leftmost-outermost redex
if t[0] == "app" and t[1][0] == "lam": return subst(t[1][2], t[1][1], t[2])
for i in ((1, 2) if t[0] == "app" else (2,) if t[0] == "lam" else ()):
if r := step(t[i]): return t[:i] + (r,) + t[i + 1:]
def run(src, cap=1000, trace=False): # returns (normal form or None, steps)
t = parse(src)
for n in range(cap + 1):
if trace: print(f" {n}: {show(t)}")
if (r := step(t)) is None: return t, n
t = r
return None, cap # the step cap: never hang
def N(k): return "(λf.λx." + "f (" * k + "x" + ")" * k + ")" # Church numeral
def value(t): # λf.λx.f (f (... x)) -> number of f
if not (t and t[0] == "lam" and t[2][0] == "lam"): return None
f, x, b, k = t[1], t[2][1], t[2][2], 0
while b[0] == "app" and b[1] == ("var", f): b, k = b[2], k + 1
return k if b == ("var", x) else None
run("(λx.x x) (λy.y)", trace=True)
run(f"(λn.λf.λx.f (n f x)) {N(2)}", trace=True) # SUCC 2
print("Omega:", run("(λx.x x) (λx.x x)", cap=500))
PLUS, MULT = "(λm.λn.λf.λx.m f (n f x))", "(λm.λn.λf.m (n f))"
for name, op in [("PLUS", PLUS), ("MULT", MULT)]:
t, n = run(f"{op} {N(2)} {N(3)}")
print(f"{name} 2 3 = {value(t)} after {n} beta-steps")
claimed_exp = "(λm.λn.m n)" # an AI's claim: "EXP m n = m^n"
print("claimed EXP 2 3 =", value(run(f"{claimed_exp} {N(2)} {N(3)}")[0]))আসল আউটপুট (ব্রাউজারের Python):
0: (λx.x x) (λy.y)
1: (λy.y) (λy.y)
2: λy.y
0: (λn.λf.λx.f (n f x)) (λf.λx.f (f x))
1: λf.λx.f ((λf.λx.f (f x)) f x)
2: λf.λx.f ((λx.f (f x)) x)
3: λf.λx.f (f (f x))
Omega: (None, 500)
PLUS 2 3 = 5 after 6 beta-steps
MULT 2 3 = 6 after 7 beta-steps
claimed EXP 2 3 = 9
(λx.x x)(λy.y): identity-কে নিজের ওপর প্রয়োগ, দুই ধাপে আবার identity. SUCC 2 তিন ধাপে 3. Ω ৫০০ ধাপের cap-এ থেমেছে, normal form পাওয়া যায়নি (None). শেষ লাইনটি একটি সাধারণ ভুল ধরে: “EXP = λm.λn.m n দেয় mn” দাবিটি 2 আর 3-এ 9 দেয়, অর্থাৎ 32. Church numeral m-কে n-এর ওপর প্রয়োগ করলে “n দিয়ে গুণ” m বার হয়, তাই ফল nm. সঠিক EXP = λm.λn.n m. প্রথম দুই সংখ্যা ভুলভাবে বেছে নিলে, যেমন 2 আর 2, এই ভুল ধরা পড়ে না; তাই অসম সংখ্যায় পরীক্ষা করুন।
নাম ছাড়া recursion: Y combinator. Lambda calculus-এ কোনো function-এর নাম নেই, তাহলে factorial নিজেকে ডাকবে কীভাবে? উত্তর একটি fixed-point combinator: Y = λf.(λx.f (x x)) (λx.f (x x)). একবার β করলেই দেখা যায় Y g → (λx.g (x x)) (λx.g (x x)) → g ((λx.g (x x)) (λx.g (x x))), আর বন্ধনীর ভেতরেরটি ঠিক আগের ধাপের term. অর্থাৎ Y g আর g (Y g) একই term-এ পৌঁছায়: Y g হলো g-এর fixed point. তাই FACT = Y (λr.λn.ISZERO n 1 (MULT n (r (PRED n)))) লিখলে r-এর জায়গায় FACT নিজেই বসে। এই কৌশল সাধারণত Haskell Curry-র নামে উল্লেখ করা হয়। একই ধারণার computability-রূপ, Kleene-এর recursion theorem, আসবে পর্ব ৫৬-এ।
একটি সত্যিকারের run. বড় হিসাবের জন্য একই নীতিতে একটু বড় একটি interpreter লেখা হয়েছে (নিজস্ব Python code, কোনো বাইরের library নেই), যাতে normal আর applicative দুই order, নাম দিয়ে সংজ্ঞা আর Church numeral পড়ে সংখ্যা বের করার ব্যবস্থা আছে। Boolean আর predecessor-এর সংজ্ঞা (PRED-এর এই কৌশলটি Kleene ১৯৩০-এর দশকের শুরুতে খুঁজে পান বলে প্রচলিত):
("TRUE", "λa.λb.a"), ("FALSE", "λa.λb.b"),
("ISZERO", "λn.n (λz.FALSE) TRUE"),
("PRED", "λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)"),
("Y", "λf.(λx.f (x x)) (λx.f (x x))"),
D["FACT"] = parse("Y (λr.λn.ISZERO n 1 (MULT n (r (PRED n))))", D)সত্যিকারের run (ডেস্কটপ, Python 3.14.4, uv দিয়ে বানানো প্রকল্প; আউটপুটের মাঝের অংশ বাদ):
~/bazarghar-toc$ uv run python lambda_run.py
Python 3.14.4
…
== arithmetic on Church numerals (normal order)
PLUS 2 3 -> 5 (6 beta-steps)
MULT 2 3 -> 6 (7 beta-steps)
MULT 3 3 -> 9 (9 beta-steps)
EXP 2 3 -> 8 (16 beta-steps)
EXP 3 2 -> 9 (10 beta-steps)
PRED 5 -> 4 (15 beta-steps)
== Omega = (λx.x x)(λx.x x)
normal order: stopped by the step cap (1000 steps)
== (λa.λb.a) z Omega: K throws its second argument away
normal order: z (2 steps)
applicative order: stopped by the step cap (1000 steps)
== FACT 3 with the Y combinator
FACT 3 -> 6 (646 beta-steps)
FACT 4 -> 24 (3873 beta-steps)
আউটপুটের বাদ দেওয়া অংশে PLUS 1 2-এর পূর্ণ trace আছে, যা অংশ ২-এর stepper-এর সাতটি term-এর সঙ্গে হুবহু মেলে। তিনটি শিক্ষা। প্রথমত, K z Ω-এ normal order ২ ধাপে z দেয়, applicative order ১০০০ ধাপেও শেষ করে না: উপপাদ্য ৩.১-এর পরের অংশ চোখের সামনে। দ্বিতীয়ত, Y combinator সত্যিই কাজ করে: FACT 3 = 6, FACT 4 = 24. তৃতীয়ত, দাম: 4! হিসাব করতে ৩৮৭৩টি β-ধাপ, কারণ সংখ্যাগুলো unary আর PRED প্রতিবার পুরো সংখ্যা নতুন করে গড়ে। Lambda calculus ক্ষমতায় Turing machine-এর সমান (Kleene ১৯৩৬ আর Turing ১৯৩৭ এই সমতা প্রমাণ করেন), কিন্তু দক্ষতায় নয়; Haskell বা OCaml-এর মতো functional ভাষা তাই আসল integer আর অনেক কৌশল ব্যবহার করে।
৪ · Recursive function — for-loop আর while-loop-এর গণিত
দ্বিতীয় ঐতিহ্যটি সংখ্যা থেকে শুরু। ১৯৩০-এর দশকে Gödel, Herbrand আর Kleene ℕ-এর ওপর function-এর একটি শ্রেণি দাঁড় করান, যা কয়েকটি সরল function থেকে কয়েকটি নিয়মে গড়ে ওঠে। প্রোগ্রামারের ভাষায়: প্রথম ধাপ for-loop-এর ক্ষমতা, দ্বিতীয় ধাপে while-loop যোগ।
মৌলিক function: শূন্য Z(x) = 0, successor S(x) = x + 1, আর projection Pik(x1, …, xk) = xi. Composition: f আর g1, …, gm থেকে h(x̄) = f(g1(x̄), …, gm(x̄)). Primitive recursion: f আর g থেকে h(x̄, 0) = f(x̄) আর h(x̄, y + 1) = g(x̄, y, h(x̄, y)). মৌলিক function থেকে এই দুই নিয়ম সসীম বার প্রয়োগে যা পাওয়া যায়, সেগুলোই primitive recursive (PR).
যোগ: add(x, 0) = x, add(x, y + 1) = S(add(x, y)). গুণ: mult(x, 0) = 0, mult(x, y + 1) = add(mult(x, y), x). একইভাবে ঘাত, factorial, “x মৌলিক কি না”, n-তম মৌলিক সংখ্যা, এমনকি একটি Turing machine-এর k ধাপের configuration: সবই PR. Primitive recursion ঠিক একটি for-loop: y থেকে 0 পর্যন্ত ঠিক y বার ঘোরা, আর ঘোরার সংখ্যা loop শুরুর আগেই জানা। ১৯৬৭ সালে Meyer আর Ritchie দেখান, শুধু এমন loop-এর একটি খেলনা ভাষা (LOOP) ঠিক PR function-গুলোই গণনা করে।
প্রতিটি primitive recursive function একটি total function: প্রতিটি input-এ সংজ্ঞায়িত।
প্রমাণ (PR-এর সংজ্ঞার ওপর structural induction):
- Z, S আর প্রতিটি Pik সব input-এ সংজ্ঞায়িত। — সরাসরি সংজ্ঞা
- f, g1, …, gm total হলে প্রতিটি x̄-এ gj(x̄) সংজ্ঞায়িত, তাই f(g1(x̄), …) সংজ্ঞায়িত। — composition
- f আর g total হলে প্রতিটি x̄-এর জন্য y-এর ওপর induction: h(x̄, 0) = f(x̄) সংজ্ঞায়িত; h(x̄, y) সংজ্ঞায়িত হলে h(x̄, y + 1) = g(x̄, y, h(x̄, y))-ও। — mathematical induction
- প্রতিটি PR function সসীম বার এই নিয়মে গড়া, তাই প্রতিটি total. ∎ — structural induction
সবসময় থামা ভালো খবর, কিন্তু দাম আছে। Turing machine-এর গণনা করা function সাধারণত partial: যেখানে যন্ত্র থামে না, সেখানে মান নেই। PR দিয়ে এমন function পাওয়া অসম্ভব। আরও গভীর কথা: সব total computable function-ও PR নয়।
এমন একটি total computable function d: ℕ → ℕ আছে, যা primitive recursive নয়।
প্রমাণ (diagonalization, পর্ব ০৪-এর কৌশল):
- প্রতিটি PR function একটি সসীম “সংজ্ঞা” দিয়ে লেখা যায় (কোন মৌলিক function, কোন নিয়ম, কোন ক্রমে)। এই সংজ্ঞাগুলো একটি সসীম alphabet-এর string, তাই shortlex ক্রমে সাজিয়ে p0, p1, p2, … তালিকা বানানো যায়, যাতে প্রতিটি এক-চলকের PR function অন্তত একবার আছে। — Σ∗ গণনাযোগ্য, পর্ব ০২
- একটি program n থেকে pn-এর সংজ্ঞা বের করে, সেটি অনুযায়ী n-এ হিসাব চালাতে পারে। উপপাদ্য ৪.২ অনুযায়ী হিসাব থামবেই। — PR-এর মূল্যায়নকারী একটি algorithm
- সংজ্ঞা দিন d(n) = pn(n) + 1. ধাপ ২ অনুযায়ী d total আর computable. — নির্মাণ
- ধরুন d primitive recursive. তাহলে কোনো k-তে d = pk, তাই d(k) = pk(k). কিন্তু সংজ্ঞা অনুযায়ী d(k) = pk(k) + 1. স্ববিরোধ। ∎ — কর্ণ বরাবর পার্থক্য
একই যুক্তি একটি বড় শিক্ষা দেয়: যে শ্রেণির সব function সবসময় থামে আর যার program-গুলো যান্ত্রিকভাবে তালিকাভুক্ত ও চালানো যায়, সেই শ্রেণি সব total computable function ধরতে পারে না। অংশ ৮-এ এটিই “total ভাষা” নিয়ে প্রোগ্রামারের উপপাদ্য হবে। পুরো ক্ষমতার জন্য দরকার unbounded খোঁজা।
f(x̄, y) থেকে h(x̄) = μy[f(x̄, y) = 0]: সবচেয়ে ছোট y, যাতে f(x̄, y) = 0 আর প্রতিটি z < y-তে f(x̄, z) সংজ্ঞায়িত ও ≠ 0. এমন y না থাকলে h(x̄) অসংজ্ঞায়িত। মৌলিক function থেকে composition, primitive recursion আর μ দিয়ে যা পাওয়া যায়, সেগুলো μ-recursive (partial recursive) function. μ হলো y = 0; while f(x, y) != 0: y += 1, যা না-ও থামতে পারে।
একটি partial function f: ℕk → ℕ μ-recursive ⇔ f কোনো Turing machine দিয়ে গণনাযোগ্য। আরও, Kleene normal form: এমন PR function T আর U আছে যে প্রতিটি μ-recursive f-এর জন্য একটি সংখ্যা e পাওয়া যায়, যাতে f(x) = U(μy T(e, x, y)).
দুই দিকের প্রমাণের রূপরেখা (μ-গঠনগুলো TM-এর subroutine হিসেবে; উল্টো দিকে configuration-এর Gödel numbering) পর্ব ৪৭-এর অংশ ৪-এ আছে, তাই এখানে শুধু normal form-এর অর্থটি: T(e, x, y) = “y হলো যন্ত্র e-এর x-এ একটি সম্পূর্ণ, থেমে যাওয়া গণনার code”, যা যাচাই করতে শুধু bounded loop লাগে, তাই PR. μy T(e, x, y) সেই গণনাটি খোঁজে, আর U তার শেষ configuration থেকে উত্তর পড়ে। অর্থাৎ যেকোনো program-কে একটিমাত্র while-loop আর বাকি সব for-loop দিয়ে লেখা যায়।
৫ · Ackermann function — থামে, কিন্তু for-loop-এ ধরা যায় না
উপপাদ্য ৪.৩-এর d তালিকা-নির্ভর আর কৃত্রিম। একটি “স্বাভাবিক” উদাহরণ অনেক আগেই ছিল: Wilhelm Ackermann ১৯২৮ সালে একটি total কিন্তু PR নয় এমন function প্রকাশ করেন (প্রায় একই সময়ে Gabriel Sudan-ও একটি দেন)। আজ যে দুই-চলকের রূপ চলে, সেটি Rózsa Péter (১৯৩৫) আর Raphael Robinson (১৯৪৮)-এর সরলীকরণ, তাই একে Ackermann–Péter function-ও বলে:
A(0, n) = n + 1 · A(m, 0) = A(m − 1, 1) · A(m, n) = A(m − 1, A(m, n − 1))
প্রতিটি call-এ হয় m কমে, নয়তো m একই থেকে n কমে; (m, n) জোড়ার lexicographic ক্রমে এমন কমা অসীম কাল চলতে পারে না, তাই A সবসময় থামে। এই induction-এর বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১২-এ আছে। নিচের stepper ছোট্ট A(1, 2)-কে নিয়ম ধরে খোলে।
1A(0, n) = n + 12A(m, 0) = A(m − 1, 1)3A(m, n) = A(m − 1, A(m, n − 1))
| রাশি | |
| অপেক্ষমাণ A | |
| মোট call |
- শুরু। A(1, 2): m = 1, n = 2, দুটিই শূন্য নয়, তাই নিয়ম ৩ খাটবে।
- নিয়ম ৩. A(1, 2) = A(0, A(1, 1)). বাইরের A(0, ·) অপেক্ষা করছে ভেতরের মানের জন্য; এটি একটি অসমাপ্ত call, stack-এ জমা।
- আবার নিয়ম ৩. A(1, 1) = A(0, A(1, 0)). অপেক্ষমাণ A এখন তিনটি।
- নিয়ম ২. A(1, 0) = A(0, 1): n শূন্য, তাই m এক কমে, n হয় 1. মোট চতুর্থ call.
- নিয়ম ১. A(0, 1) = 2. প্রথমবার একটি সংখ্যা পাওয়া গেল, আর একটি অপেক্ষমাণ call মিটল।
- নিয়ম ১. A(0, 2) = 3.
- উত্তর। A(0, 3) = 4. মোট ছয়টি call, সর্বোচ্চ তিনটি একসঙ্গে অপেক্ষমাণ। A(1, n) = n + 2; পরের সারিগুলোতে বৃদ্ধি বিস্ফোরক।
সত্যিকারের run-এ একটি explicit stack দিয়ে (Python-এর recursion সীমা এড়াতে) মান, call-সংখ্যা আর সর্বোচ্চ stack-গভীরতা মাপা হয়েছে; একটি call cap-ও আছে।
def ackermann(m, n, cap=10_000_000):
stack, calls, depth = [m], 0, 1
while stack:
m = stack.pop(); calls += 1
if calls > cap: return None, calls, depth
if m == 0: n = n + 1 # A(0, n) = n + 1
elif n == 0: stack.append(m - 1); n = 1 # A(m, 0) = A(m-1, 1)
else: # A(m, n) = A(m-1, A(m, n-1))
stack.append(m - 1); stack.append(m); n -= 1
depth = max(depth, len(stack) + 1)
return n, calls, depthসত্যিকারের run (ডেস্কটপ, Python 3.14.4):
~/bazarghar-toc$ uv run python ackermann.py
Python 3.14.4
m\n 0 1 2 3 4
0 1 2 3 4 5
1 2 3 4 5 6
2 3 5 7 9 11
3 5 13 29 61 125
(m, n) value calls max depth
(1, 2) 4 6 4
(2, 3) 9 44 9
(3, 3) 61 2432 61
(3, 5) 253 42438 253
(3, 8) 2045 2785999 2045
(4, 1) stopped by the call cap after 5000000 calls
A(3, n) = 2^(n+3) - 3 for n <= 8: True
A(4, 1) = 2^16 - 3 = 65533
A(4, 2) = 2^65536 - 3 has 19729 decimal digits
সারিগুলো পড়ুন: A(1, n) = n + 2 (যোগ), A(2, n) = 2n + 3 (গুণ), A(3, n) = 2n+3 − 3 (ঘাত; n ≤ 8-এ যাচাই হয়েছে)। প্রতিটি সারি আগের সারির কাজকে বারবার করে। A(4, n) তাই ঘাতের ওপর ঘাতের মিনার: A(4, 1) = 65533 মাত্র, কিন্তু সেখানে পৌঁছাতে ৫০ লক্ষ call-ও যথেষ্ট নয়; আর A(4, 2)-এ ১৯৭২৯ অঙ্ক। Stepper-এর “ছয়টি call” এখানে (1, 2) সারিতে মিলে গেল (max depth 4 গোনে বাইরের call-সহ)। A(3, 3) = 61-এর জন্য ২৪৩২টি call: মান আর খরচ, দুটিই দেখায় কেন সাধারণ for-loop এর সঙ্গে তাল রাখতে পারে না।
A total আর computable, কিন্তু primitive recursive নয়।
প্রমাণের রূপরেখা। মূল lemma: প্রতিটি PR function f-এর জন্য এমন k আছে যে সব x̄-এ f(x̄) < A(k, max x̄). এর প্রমাণ PR-এর সংজ্ঞার ওপর structural induction, প্রতিটি নিয়মে k কতটা বাড়ে তা হিসাব করে (A-এর কয়েকটি একঘেয়েমি-ধর্ম লাগে; বিস্তারিত বাদ, যেকোনো computability পাঠ্যবইয়ে আছে)। এখন ধরুন A PR. তাহলে g(n) = A(n, n)-ও PR, তাই কোনো k-তে সব n-এ g(n) < A(k, n). n = k বসালে A(k, k) < A(k, k), স্ববিরোধ। ∎ লক্ষ করুন, এটিও আসলে diagonal যুক্তি: A-এর k-তম সারি “k স্তরের loop”-এর সর্বোচ্চ ক্ষমতা, আর কর্ণ A(n, n) প্রতিটি সারিকে ছাড়িয়ে যায়।
৬ · Register আর counter machine — দুটি সংখ্যাই যথেষ্ট
তৃতীয় ঐতিহ্যটি আধুনিক processor-এর সবচেয়ে কাছের। ১৯৬০-এর দশকের শুরুতে Minsky, Lambek, আর Shepherdson ও Sturgis প্রায় একসঙ্গে register machine-এর মডেল দেন: কয়েকটি register, প্রতিটিতে যত বড় ইচ্ছা একটি অঋণাত্মক পূর্ণসংখ্যা, আর একটি সংখ্যাযুক্ত নির্দেশের তালিকা। এর সবচেয়ে সরল রূপ counter machine; বাস্তব processor-এর register-এর সঙ্গে তুলনা কম্পিউটার আর্কিটেকচার কোর্সের পর্ব ২৫-এ পাবেন।
Counter R0, …, Rk−1 ∈ ℕ আর লাইন-নম্বরযুক্ত একটি সসীম program; প্রতিটি লাইন দুই ধরনের একটি: INC r, j (Rr এক বাড়ানো, লাইন j-তে যাওয়া) বা DEC r, j, z (Rr > 0 হলে এক কমানো আর লাইন j-তে যাওয়া; Rr = 0 হলে লাইন z-তে যাওয়া)। H-এ পৌঁছালে যন্ত্র থামে। Configuration হলো (লাইন, R0, …, Rk−1).
এর বেশি কিছু নেই: যোগ, গুণ, তুলনা, সবই এই দুই নির্দেশে বানাতে হয়। সবচেয়ে ছোট উদাহরণ ADD, যা R0 := R0 + R1 করে: লাইন 0 “DEC 1, 1, H”, লাইন 1 “INC 0, 0”. R1 থেকে একটি একটি করে তুলে R0-তে রাখা, বাজারঘরের গুদামে এক তাক থেকে আরেক তাকে বাক্স সরানোর মতো।
0DEC R1 → 1, শূন্য হলে H1INC R0 → 0
| লাইন | |
| R0 | |
| R1 | |
| ধাপ |
- শুরু। লাইন 0, R0 = 2, R1 = 3. উত্তর হওয়া উচিত R0 = 5.
- DEC. R1 > 0, তাই এক কমিয়ে লাইন 1-এ। “শূন্য কি না” পরীক্ষা আর কমানো একই নির্দেশে; এটিই যন্ত্রের একমাত্র সিদ্ধান্ত নেওয়ার উপায়।
- INC. R0 এক বাড়ল, লাইন 0-তে ফেরা। R0 + R1 যোগফল ৫ এখনো অপরিবর্তিত: এটিই loop-এর invariant.
- DEC. R1 = 1.
- INC. R0 = 4.
- DEC. R1 = 0.
- INC. R0 = 5. লাইন 0-তে ফেরা।
- থামা। এবার R1 = 0, তাই DEC কমায় না, লাইন H-এ পাঠায়। মোট ৭ ধাপ; সাধারণভাবে 2·R1 + 1, input-এর মান অনুযায়ী, দৈর্ঘ্য অনুযায়ী নয়।
নিচের ব্লকে একটি counter-machine simulator. প্রথমে ADD-এর trace আর ২০ × ২০টি জোড়ায় brute-force যাচাই। তারপর প্রমাণের মূল কৌশলটি: দুই counter দিয়ে “একটি counter-কে 3 দিয়ে গুণ”, শেষে একটি loop step cap-এ থামানো।
# Counter (Minsky) machine. Instructions, by line number:
# ("INC", r, next) r += 1, go to next
# ("DEC", r, next, ifzero) if r > 0: r -= 1, go to next; else go to ifzero
def run(prog, regs, cap=10_000, trace=False):
pc, regs = 0, list(regs)
for steps in range(cap + 1):
if trace: print(f" {steps}: line {pc} R = {regs}")
if pc == "H": return regs, steps
ins = prog[pc]
if ins[0] == "INC": regs[ins[1]] += 1; pc = ins[2]
elif regs[ins[1]] > 0: regs[ins[1]] -= 1; pc = ins[2]
else: pc = ins[3]
return "step cap", cap # never hang
ADD = {0: ("DEC", 1, 1, "H"), 1: ("INC", 0, 0)} # R0 := R0 + R1
run(ADD, [2, 3], trace=True)
print("ADD on all pairs below 20 correct:",
all(run(ADD, [a, b])[0] == [a + b, 0] for a in range(20) for b in range(20)))
def times(k): # R0 := k * R0 using R1 as scratch (two counters only)
p = {0: ("DEC", 0, 1, k + 1)}
for j in range(1, k + 1): p[j] = ("INC", 1, j + 1 if j < k else 0)
p[k + 1] = ("DEC", 1, k + 2, "H"); p[k + 2] = ("INC", 0, k + 1)
return p
a, b = 2, 1 # three registers a, b, c ...
c0 = 2 ** a * 3 ** b # ... packed as 2^a 3^b 5^c
regs, n = run(times(3), [c0, 0]) # "b += 1" = multiply by 3
print(f"2^{a}*3^{b} = {c0} -> {regs[0]} = 2^2*3^2 in {n} steps")
print("LOOP:", run({0: ("INC", 0, 0)}, [0, 0], cap=1000))আসল আউটপুট (ব্রাউজারের Python):
0: line 0 R = [2, 3]
1: line 1 R = [2, 2]
2: line 0 R = [3, 2]
3: line 1 R = [3, 1]
4: line 0 R = [4, 1]
5: line 1 R = [4, 0]
6: line 0 R = [5, 0]
7: line H R = [5, 0]
ADD on all pairs below 20 correct: True
2^2*3^1 = 12 -> 36 = 2^2*3^2 in 122 steps
LOOP: ('step cap', 1000)
প্রথম আট লাইন stepper-এর আটটি configuration-এর সঙ্গে হুবহু মেলে, আর ৪০০টি জোড়ায় ADD নির্ভুল। তারপর মূল চাল: তিনটি সংখ্যা a = 2, b = 1, c = 0-কে একটি counter-এ রাখা হয়েছে 2a3b5c = 12 হিসেবে। “b এক বাড়ানো” মানে “3 দিয়ে গুণ করা”, আর times(3) সেটি শুধু দুটি counter দিয়ে করে: R0 থেকে একটি তুললে R1-এ তিনটি রাখে, তারপর সব ফেরত আনে। ফল 36 = 2232, অর্থাৎ a অপরিবর্তিত, b = 2. খরচ 10·R0 + 2 = ১২২ ধাপ: একটি নির্দেশ অনুকরণে counter-এর মান-এর সমানুপাতিক ধাপ, যা exponential ধীরতা আনে। শেষ লাইনে চিরকাল INC করা যন্ত্রটি ১০০০ ধাপের cap-এ থেমেছে।
প্রতিটি Turing machine M-এর জন্য একটি 2-counter machine আছে, যা M-কে অনুকরণ করে: M input w-এ থামে ⇔ যন্ত্রটি একটি নির্দিষ্টভাবে encode করা শুরুর মানে থামে, আর থামলে উত্তরও encode করা রূপে পাওয়া যায়।
প্রমাণের রূপরেখা (চার ধাপ, প্রতিটি একটি simulation):
- Tape = দুটি stack. Head-এর বাঁয়ের অংশ এক stack-এ, head-এর নিচের ঘর থেকে ডানের অংশ আরেকটিতে; head সরানো মানে এক stack থেকে pop করে অন্যটিতে push. এটি পর্ব ৩২-এর two-stack পর্যবেক্ষণ (pda-basics). — TM ≤ 2 stack
- Stack = একটি সংখ্যা. |Γ| = b হলে stack-এর বিষয়বস্তুকে base-b সংখ্যা হিসেবে পড়ুন, ওপরের চিহ্ন সবচেয়ে কম গুরুত্বপূর্ণ অঙ্ক। Push s = “b দিয়ে গুণ করে s যোগ”, pop = “b দিয়ে ভাগ, ভাগশেষই ওপরের চিহ্ন”। গুণ আর ভাগ একটি সহায়ক counter দিয়ে করা যায়, আর ভাগশেষ সসীম, তাই state-এ রাখা যায়। — 2 stack ≤ 3 counter
- অনেক counter = একটি সংখ্যা. Counter a, b, c-কে একটিতে রাখুন 2a3b5c হিসেবে (prime-power encoding). b বাড়ানো = 3 দিয়ে গুণ, b কমানো = 3 দিয়ে ভাগ, “b = 0?” = “3 দিয়ে বিভাজ্য নয়?”। প্রতিটি দ্বিতীয় counter-কে scratch হিসেবে নিয়ে করা যায়, ঠিক উপরের times(3)-এর মতো। — 3 counter ≤ 2 counter
- তিনটি অনুকরণ জোড়া দিলে TM ≤ 2-counter machine, আর উল্টো দিক সহজ: একটি TM দুটি সংখ্যা tape-এ রেখে INC আর DEC করতে পারে। ∎
দুটি সতর্কতা। প্রথমত, input-কে বিশেষ রূপে, যেমন n-এর বদলে 2n হিসেবে, দিতে হয়; Rich Schroeppel-এর ১৯৭২ সালের একটি ফল অনুযায়ী দুই-counter যন্ত্র সরাসরি n থেকে 2n বানাতে পারে না। তাই “দুই counter Turing-complete” কথাটি encoding-সহ সত্য। দ্বিতীয়ত, এক counter যথেষ্ট নয়: একটি counter মানে পর্ব ৩২-এর counter automaton-এর ক্ষমতা, যা এমনকি একটি PDA-রও কম। সিঁড়িটি তাই: সসীম স্মৃতি < এক counter < এক stack < দুই stack = দুই counter = Turing machine.
৭ · Cellular automaton আর tag system — নিয়ম যত সরল, তবু সার্বজনীন
একটি cellular automaton-এ কোনো আলাদা “যন্ত্র” বা “head” নেই। আছে শুধু ঘরের একটি সারি, প্রতিটি 0 বা 1, আর একটি স্থানীয় নিয়ম: প্রতিটি প্রজন্মে সব ঘর একসঙ্গে নিজের আর দুই প্রতিবেশীর মান দেখে নতুন মান নেয়। স্টেডিয়ামের দর্শকদের “মেক্সিকান ওয়েভ” ভাবুন: কেউ পুরো ঢেউ দেখে না, প্রত্যেকে শুধু পাশের দুজনকে দেখে দাঁড়ায় বা বসে, তবু ঢেউ পুরো গ্যালারি ঘোরে।
তিন ঘরের প্রতিবেশ 23 = ৮ রকম, আর প্রতিটির জন্য নতুন মান 0 বা 1, তাই এমন নিয়ম 28 = ২৫৬টি। Stephen Wolfram ১৯৮৩ সালে এদের নম্বর দেন: প্রতিবেশ 111, 110, …, 000-এর নতুন মানগুলো পরপর লিখে binary সংখ্যা হিসেবে পড়া। Rule 110-এর ক্ষেত্রে 01101110 = ১১০.
| প্রতিবেশ | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| নতুন মান | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
নিচের stepper আট ঘরের সারি 01110100-এর পরের প্রজন্ম হিসাব করে। সারির বাইরের ঘরগুলো সবসময় 0 ধরা হয়েছে।
1111 → 02110 → 13101 → 14100 → 05011 → 16010 → 17001 → 18000 → 0
| পুরোনো সারি | |
| ঘর | |
| প্রতিবেশ | |
| নতুন সারি |
- শুরু। পুরোনো সারি 01110100. প্রতিটি নতুন ঘর নির্ভর করে পুরোনো সারির তিনটি ঘরের ওপর; নতুন মান পুরোনো সারিতে লেখা হয় না, তাই সব ঘর “একসঙ্গে” বদলায়।
- ঘর 0. বাঁয়ে সারির বাইরের 0, নিজে 0, ডানে 1: প্রতিবেশ 001, নিয়মে 1.
- ঘর 1. প্রতিবেশ 011 → 1.
- ঘর 2. 111 → 0: তিনটিই 1 হলে মাঝেরটি মরে। ভিড় বেশি হলে মরা, এই নিয়মই Rule 110-কে আকর্ষণীয় করে।
- ঘর 3. 110 → 1.
- ঘর 4. 101 → 1: মাঝের ফাঁকা ঘর ভরে যায়।
- ঘর 5. 010 → 1: একা 1 টিকে থাকে।
- ঘর 6. 100 → 0: শুধু বাঁয়ে 1 থাকলে মাঝের ঘর 0 থাকে। এজন্য Rule 110-এর নকশা শুধু বাঁ দিকে বাড়ে।
- শেষ। ঘর 7: 000 → 0. নতুন সারি 11011100; নিচের JavaScript ব্লকের দ্বিতীয় অংশ ঠিক এই সারি ছাপে।
// Elementary cellular automaton on a fixed-width row; cells outside are 0.
// New cell = bit number (4*left + 2*self + right) of the rule number.
function show(rule, start, gens = 16) {
gens = Math.min(gens, 40); // cap the generations
const bit = (n) => (rule >> n) & 1;
let row = [...start].map(Number);
const nb = [7, 6, 5, 4, 3, 2, 1, 0].map((n) => n.toString(2).padStart(3, "0") + ">" + bit(n));
console.log(`Rule ${rule}: ${nb.slice(0, 4).join(" ")}`);
console.log(` ${nb.slice(4).join(" ")}`);
for (let g = 0; g < gens; g++) {
const live = row.filter((c) => c).length;
console.log(String(g).padStart(2) + " " + row.map((c) => (c ? "#" : ".")).join("") + " " + live);
row = row.map((c, i) => bit(4 * (row[i - 1] ?? 0) + 2 * c + (row[i + 1] ?? 0)));
}
}
show(110, "0".repeat(31) + "1"); // one live cell at the right end
show(110, "01110100", 1 + 1); // the cell-by-cell example
show(30, "0".repeat(12) + "1" + "0".repeat(12), 8); // Rule 30 for contrastআসল আউটপুট (ব্রাউজারের JavaScript):
Rule 110: 111>0 110>1 101>1 100>0
011>1 010>1 001>1 000>0
0 ...............................# 1
1 ..............................## 2
2 .............................### 3
3 ............................##.# 3
4 ...........................##### 5
5 ..........................##...# 3
6 .........................###..## 5
7 ........................##.#.### 6
8 .......................#######.# 8
9 ......................##.....### 5
10 .....................###....##.# 6
11 ....................##.#...##### 8
12 ...................#####..##...# 8
13 ..................##...#.###..## 8
14 .................###..####.#.### 11
15 ................##.#.##..#####.# 11
Rule 110: 111>0 110>1 101>1 100>0
011>1 010>1 001>1 000>0
0 .###.#.. 4
1 ##.###.. 5
Rule 30: 111>0 110>0 101>0 100>1
011>1 010>1 001>1 000>0
0 ............#............ 1
1 ...........###........... 3
2 ..........##..#.......... 3
3 .........##.####......... 6
4 ........##..#...#........ 4
5 .......##.####.###....... 9
6 ......##..#....#..#...... 5
7 .....##.####..######..... 12
# মানে 1, . মানে 0, শেষের সংখ্যা জীবিত ঘর। একটিমাত্র 1 থেকে Rule 110 বাঁ দিকে বাড়ে আর ত্রিভুজ-আকৃতির কাঠামো তৈরি করে, যা নিয়মিতও নয়, পুরো এলোমেলোও নয়। দ্বিতীয় অংশ stepper-এর 01110100 → 11011100 নিশ্চিত করে। Rule 30 তুলনার জন্য: এর মাঝের কলাম এতটাই এলোমেলো দেখায় যে Wolfram একে random সংখ্যা তৈরিতে ব্যবহারের প্রস্তাব দেন। প্রজন্ম ৪০-এ আর সারি নির্দিষ্ট প্রস্থে বাঁধা, তাই ব্লকটি তাৎক্ষণিক শেষ হয়। ডেস্কটপে স্বাধীনভাবে লেখা একটি Python script (Python 3.14.4, সত্যিকারের run) একই শুরু থেকে ২৪ প্রজন্ম ছাপে; প্রথম ১৬টি এই আউটপুটের সঙ্গে হুবহু মেলে, আর শেষ সারি ........##.#.######..##......###, জীবিত ঘর ১৪টি।
Rule 110 Turing-complete, এই অর্থে: যেকোনো Turing machine-এর গণনা একটি cyclic tag system-এর মাধ্যমে Rule 110-এর একটি শুরুর সারিতে encode করা যায়, যেখানে সারির দুই পাশে অসীম পর্যন্ত একটি নির্দিষ্ট নকশা পর্যাবৃত্তভাবে (বারবার) চলতে থাকে।
এই দাবির শর্তগুলো গুরুত্বপূর্ণ। (১) শুরুর সারি সসীম নয়: দুই দিকে পর্যাবৃত্ত পটভূমি লাগে। সসীম সারি আর চারপাশে শুধু 0 হলে, যেমন উপরের ব্লকে, এই ফল সরাসরি খাটে না। (২) “থামা” মানে সারিতে একটি নির্দিষ্ট নকশা দেখা দেওয়া; cellular automaton নিজে কখনো থামে না। (৩) Wolfram ১৯৮০-এর দশকে এমন অনুমান করেন, আর Matthew Cook ১৯৯০-এর দশকে Wolfram-এর গবেষণা দলে কাজ করার সময় প্রমাণটি দেন; একটি আইনি বিরোধের কারণে প্রকাশ পিছিয়ে যায় বলে বর্ণিত, শেষে Complex Systems জার্নালে ২০০৪ সালে প্রকাশিত হয়।
Game of Life. John Conway-র ১৯৭০ সালের Game of Life দুই-মাত্রার: মৃত ঘরে ঠিক ৩টি জীবিত প্রতিবেশী থাকলে জন্ম, জীবিত ঘরে ২ বা ৩টি থাকলে টিকে থাকা, নইলে মৃত্যু। Martin Gardner-এর একটি জনপ্রিয় কলামে (অক্টোবর ১৯৭০) এটি ব্যাপক পরিচিতি পায়। Berlekamp, Conway আর Guy-এর Winning Ways (১৯৮২) বইয়ে glider-এর স্রোত দিয়ে logic gate গড়ে এর সার্বজনীনতার রূপরেখা দেওয়া হয়, আর ২০০০ সালে Paul Rendell Life-এর ভেতরে একটি সত্যিকারের Turing machine-এর নকশা চালিয়ে দেখান বলে উল্লেখ পাওয়া যায়।
Tag system. Emil Post ১৯২০-এর দশকের শুরুতে আরও সরল একটি ব্যবস্থা নিয়ে কাজ করেন: একটি string, প্রতিটি চিহ্নের জন্য একটি “জোড়ার শব্দ” আর একটি সংখ্যা m. প্রতি ধাপে প্রথম চিহ্ন দেখে তার শব্দটি শেষে জোড়া হয়, তারপর সামনে থেকে m টি চিহ্ন মুছে ফেলা হয়। রেলস্টেশনের টিকিট-লাইনের মতো: সামনের জন সরে যায়, আর তাঁর টিকিটের ধরন অনুযায়ী কয়েকজন নতুন লোক পেছনে দাঁড়ায়। Cocke আর Minsky ১৯৬৪ সালে দেখান যে m = 2-এর tag system-ই Turing-complete. মূলত এর একটি রূপ (cyclic tag system) দিয়েই Cook Rule 110-এর প্রমাণ গাঁথেন। অন্যদিকে Post-এর নিজের একটি ছোট 3-tag system (0 → 00, 1 → 1101) প্রতিটি শুরুর string-এ শেষ পর্যন্ত থামে বা পুনরাবৃত্তিতে ঢোকে কি না, সেটি আজও অজানা বলে উল্লেখ পাওয়া যায়।
৮ · সব মডেল সমান — প্রোগ্রামারের জন্য এর অর্থ
নিচের সারণি মডেলগুলোকে পাশাপাশি রাখে। “এক ধাপ” কতটা ছোট আর অনুকরণের খরচ কত, তা আলাদা; কিন্তু শেষ কলাম সবার জন্য একই।
| মডেল | স্মৃতি | এক ধাপ | সমতার কৌশল | ক্ষমতা |
|---|---|---|---|---|
| Turing machine | অসীম tape | এক ঘর পড়া-লেখা-সরা | — | পূর্ণ |
| Lambda calculus | term নিজেই | একটি β-reduction | TM-এর configuration term-এ; term-কে tape-এ | পূর্ণ |
| μ-recursive | সংখ্যা | একটি নিয়মের প্রয়োগ | Kleene normal form | পূর্ণ |
| Primitive recursive | সংখ্যা | একটি নিয়মের প্রয়োগ | — | সবসময় থামে; Ackermann বাদ |
| 2-counter machine | দুটি সংখ্যা | INC বা DEC | stack → সংখ্যা → 2a3b5c | পূর্ণ (encoding-সহ) |
| Rule 110 | অসীম সারি | একটি প্রজন্ম | TM → cyclic tag → Rule 110 | পূর্ণ (পর্যাবৃত্ত পটভূমি) |
| Python, C | সীমাহীন ধরে নিলে | একটি নির্দেশ | interpreter/compiler | পূর্ণ |
Turing-complete মানে কী, কী নয়। একটি ভাষা বা ব্যবস্থা Turing-complete, যদি (অসীম স্মৃতি ধরে নিলে) সেটি যেকোনো Turing machine অনুকরণ করতে পারে। এর জন্য সাধারণত দুটি জিনিসই যথেষ্ট: সীমাহীন স্মৃতি (বড় হতে থাকা list বা সংখ্যা) আর এমন loop বা recursion, যার ঘোরার সংখ্যা আগে থেকে বাঁধা নয়। বাস্তব কম্পিউটারের স্মৃতি সসীম, তাই কঠোর অর্থে সেটি বিশাল একটি finite-state যন্ত্র; তবু “Turing-complete” বলা হয়, কারণ স্মৃতি বাড়ালেই program-টি আরও বড় input-এ চলে। আরেকটি অর্থ সবচেয়ে গুরুত্বপূর্ণ: Turing-complete ভাষায় halting problem-এর সমস্যাও উত্তরাধিকারে আসে। কোনো program থামবে কি না, তা সাধারণভাবে নির্ণয় করা যায় না (পর্ব ৫১)।
তাহলে উল্টো পথ: এমন ভাষা কি বানানো যায়, যার প্রতিটি program থামবেই? যায়। Agda, Coq (সম্প্রতি Rocq নামে পরিচিত) বা Idris-এর মতো প্রমাণ-সহায়ক ভাষা প্রতিটি recursive function-এর থামা যাচাই করে (structural recursion, termination checker), কারণ সেখানে একটি program একটি গাণিতিক প্রমাণও, আর না-থামা “প্রমাণ” অর্থহীন। David Turner ২০০৪ সালে “total functional programming” নামে এই ধারণাকে সাধারণ প্রোগ্রামিংয়ের জন্যও প্রস্তাব করেন। কিন্তু উপপাদ্য ৪.৩-এর যুক্তি এখানে একটি কঠিন সীমা টানে।
ধরুন L একটি total programming language: প্রতিটি L-program ℕ → ℕ-এর একটি total function গণনা করে, program-গুলো সংখ্যা দিয়ে চিহ্নিত করা যায়, আর L-এ সংখ্যার ওপর +1 লেখা যায়। তাহলে eval(p, x) = “program p-কে x-এ চালানোর ফল” function-টি L-এ লেখা যায় না, যদিও এটি total আর computable.
প্রমাণ।
- ধরুন eval L-এ লেখা যায়। তাহলে d(x) = eval(x, x) + 1-ও L-এ লেখা যায়। — L-এ composition আর +1 আছে
- d একটি L-program, তাই তার একটি নম্বর আছে, ধরুন e: সব x-এ eval(e, x) = d(x). — program-এর নম্বর
- x = e বসালে d(e) = eval(e, e) + 1 = d(e) + 1. — ধাপ ১ আর ২
- L total, তাই d(e) একটি সংখ্যা, আর কোনো সংখ্যা নিজের চেয়ে এক বড় হতে পারে না। স্ববিরোধ। ∎ — totality
Turing-complete ভাষায় ধাপ ৪ ভাঙে: d(e) থামতে নাও পারে, তাই স্ববিরোধ হয় না, আর interpreter লেখা যায় (পর্ব ৪৮-এর universal machine). ফলে প্রতিটি ভাষার নকশায় একটি বেছে নেওয়া আছে: সব থামার নিশ্চয়তা, নয়তো সার্বজনীনতা; দুটি একসঙ্গে নয়। বাজারঘরের discount-নিয়মের জন্য একটি ছোট ভাষা বানালে, যেখানে প্রতিটি নিয়ম দ্রুত শেষ হওয়া জরুরি, ইচ্ছা করেই loop বাদ রাখা বা সীমিত রাখা তাই একটি যুক্তিসংগত নকশা।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- (λx.λy.x) a b-এর normal form কী? a; দুই ধাপের β-reduction.
- Church numeral 2 লিখুন, আর SUCC দিন। 2 = λf.λx.f (f x); SUCC = λn.λf.λx.f (n f x).
- Primitive recursive আর μ-recursive-এর পার্থক্য? প্রথমটি শুধু bounded loop, সবসময় total; μ unbounded খোঁজা যোগ করে আর ঠিক Turing-computable partial function দেয়।
- Ackermann function কেন বিখ্যাত? Total আর computable, কিন্তু primitive recursive নয়; প্রতিটি PR function-কে ছাড়িয়ে বাড়ে।
- Turing-complete হতে কয়টি counter লাগে? দুটি (input বিশেষভাবে encode করা হলে); একটিতে হয় না।
আরও গভীরে: সমান ক্ষমতা মানে সমান দক্ষতা নয়, আর এখানেই এখনকার গবেষণা। Cook-এর মূল Rule 110 নির্মাণ exponential ধীর ছিল; Turlough Neary আর Damien Woods ২০০৬ সালে দেখান যে Rule 110 Turing machine-কে polynomial সময়ে অনুকরণ করতে পারে, তাই “Rule 110-এর ভবিষ্যৎ সারি বলা” একটি P-complete সমস্যা। উল্টো দিকে, lambda calculus-এ type যোগ করলে (simply typed lambda calculus) প্রতিটি term-এর normal form থাকে, ফলে ক্ষমতা কমে যায়; type আর প্রমাণের এই সম্পর্ক (Curry–Howard) পর্ব ৭৮-এ program analysis-এর সীমার সঙ্গে ফিরে আসবে।
৯ · AI-এর যুগে গণনার মডেল
AI assistant এই বিষয়ে আত্মবিশ্বাসী কিন্তু প্রায়ই অর্ধেক-ঠিক উত্তর দেয়, কারণ উৎসগুলোতেই সংক্ষিপ্ত, শর্তহীন বক্তব্য বেশি। অংশ ৩-এর ব্লকে দেখেছেন, “EXP = λm.λn.m n” দাবি ঠিক উল্টো ঘাত দেয়, আর ২ ও ২-এর মতো সমান সংখ্যায় পরীক্ষা করলে ভুলটি লুকিয়ে থাকে। নিচের সারণিতে সাধারণ ভুল আর ধরার উপায়।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| Substitution-এ capture: (λx.λy.x) y থেকে λy.y | Reducer-এ চালান; capture পরীক্ষার জন্য এমন উদাহরণই বেছে নিন |
| Church numeral-এ ক্রম উল্টো (EXP, MULT), বা ভুল PRED | ০ থেকে ৫ পর্যন্ত সব অসম জোড়ায় Python-এর উত্তরের সঙ্গে মেলান |
| “Primitive recursive = সব total computable function” | উপপাদ্য ৪.৩ আর Ackermann; “কেন সব থামা function PR?” প্রশ্ন করুন |
| “এক counter-ই যথেষ্ট, সব সংখ্যা 2a3b-এ রাখলেই হয়” | গুণ বা ভাগের জন্য scratch counter কোথায়, তা জিজ্ঞাসা করুন |
| “Rule 110 যেকোনো সসীম শুরুর সারি থেকে TM অনুকরণ করে”, বা Cook-এর প্রমাণের ভুল সাল | শর্ত (পর্যাবৃত্ত পটভূমি) আর প্রকাশনা (Complex Systems, ২০০৪) নিজে মিলিয়ে নিন |
| Church–Turing thesis-কে প্রমাণিত theorem বলা, বা বানানো রেফারেন্স | Sipser বা Hopcroft–Motwani–Ullman-এ মিলিয়ে নিন; thesis-এর মর্যাদা পর্ব ৪৭-এ |
AI-কে কাজে লাগানোর ভালো উপায়: শুধু উত্তর নয়, প্রতিটি β-ধাপ, শর্তসহ theorem-এর বক্তব্য আর এমন একটি যাচাই-কোড চাওয়া, যা আপনি নিজে চালাবেন।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Simply typed lambda calculus-এ প্রতিটি term থামে, অথচ Haskell বা OCaml-এ type থাকার পরও program চিরকাল চলতে পারে। পার্থক্যটা কোথায়?
Untyped lambda calculus-এ যেকোনো term যেকোনো term-এর ওপর প্রয়োগ করা যায়, এমনকি নিজের ওপরও: x x. Ω আর Y combinator দুটিই এই self-application-এর ওপর দাঁড়িয়ে। Church নিজেই ১৯৪০ সালে একটি typed রূপ দেন, যেখানে প্রতিটি variable-এর একটি type থাকে, যেমন “সংখ্যা থেকে সংখ্যা”। সেখানে x x লেখা যায় না, কারণ x-এর type একই সঙ্গে A আর A → B হতে পারে না। ফল নাটকীয়: simply typed lambda calculus-এ প্রতিটি term-এর normal form আছে, আর যেকোনো ক্রমে reduce করলেও শেষ হয় (strong normalization; William Tait-এর ১৯৬৭ সালের প্রমাণ সুপরিচিত)। অর্থাৎ type যোগ করামাত্র ভাষাটি total হয়ে যায়, আর উপপাদ্য ৮.১ অনুযায়ী Turing-complete থাকে না।
তাহলে Haskell বা OCaml কীভাবে while-loop-এর সমান কিছু লেখে? তারা type ব্যবস্থার পাশে সাধারণ recursion আলাদাভাবে যোগ করে: OCaml-এর let rec, বা Haskell-এ যেকোনো function নিজের নামে নিজেকে ডাকতে পারে। এটি কার্যত একটি built-in fixed-point combinator, যা type-এর বাধা পেরিয়ে আসে। তাই এসব ভাষা Turing-complete, আর তাদের type checker শুধু বলে “উত্তর এলে সঠিক type-এর আসবে”, “উত্তর আসবে” বলে না।
মাঝখানে একটি আকর্ষণীয় এলাকা আছে। Gödel-এর System T বা Girard-এর System F-এর মতো আরও শক্তিশালী typed ব্যবস্থাও সব term থামায়, অথচ এরা primitive recursive-এর চেয়ে অনেক বেশি পারে: Ackermann function System T-তেই লেখা যায়, কারণ সেখানে function-এর ওপর recursion চলে। তবু উপপাদ্য ৮.১-এর diagonal যুক্তি এদেরও সীমা টানে: কোনোটিই নিজের evaluator লিখতে পারে না। Agda আর Coq এই ধারার উত্তরসূরি। Type আর প্রমাণের এই সম্পর্ক পর্ব ৭৮-এ আবার আসবে।
মূল উপলব্ধি: type ব্যবস্থা নিজে থামার নিশ্চয়তা দিতে পারে, আর বাস্তব ভাষাগুলো জেনেশুনে সাধারণ recursion যোগ করে সেই নিশ্চয়তা ছেড়ে সার্বজনীনতা কেনে।
প্র ০২Rule 110 Turing-complete, তাহলে কি একটি Rule 110 কম্পিউটার বানানো বাস্তবসম্মত? “Turing-complete” দাবি থেকে কী সিদ্ধান্ত টানা যায় না?
Turing-completeness শুধু বলে “নীতিগতভাবে পারে”, আর সেই নীতির মধ্যে তিনটি বড় শর্ত লুকিয়ে থাকে। প্রথমটি দক্ষতা। Cook-এর মূল নির্মাণে একটি Turing machine-এর ধাপ অনুকরণে Rule 110-এর বিপুল সংখ্যক প্রজন্ম লাগত, আর tag system-এর মধ্য দিয়ে যাওয়ায় খরচ exponential হতো বলে বিশ্লেষণ করা হয়েছে। Neary আর Woods ২০০৬ সালে দেখান যে খরচ polynomial-এ নামানো যায়, কিন্তু polynomial মানেই দ্রুত নয়; বাস্তব কাজে এমন যন্ত্র আধুনিক processor-এর তুলনায় অকল্পনীয় ধীর।
দ্বিতীয়টি শুরুর অবস্থা। Rule 110-এর প্রমাণে সারির দুই পাশে অসীম পর্যন্ত একটি পর্যাবৃত্ত নকশা লাগে। গণিতে এটি গ্রহণযোগ্য, কারণ পর্যাবৃত্ত নকশাকে সসীমভাবে বর্ণনা করা যায়। কিন্তু এতে একটি সূক্ষ্ম প্রশ্ন ওঠে: encoding কতটা কাজ নিজেই করছে? যদি শুরুর সারি বানাতেই কোনো জটিল হিসাব লাগত, তাহলে “Rule 110 গণনা করছে” বলা প্রতারণা হতো। তাই গবেষকরা encoding-এর ওপর শর্ত রাখেন: সেটি নিজে সরল আর যান্ত্রিক হতে হবে। দুই-counter যন্ত্রের ক্ষেত্রেও একই কথা, n-এর বদলে 2n দেওয়া কি encoding-এ অনেক কাজ লুকানো? Schroeppel-এর ফল দেখায়, এই পার্থক্যটি বাস্তব।
তৃতীয়টি পর্যবেক্ষণ। Cellular automaton থামে না; “উত্তর” পড়তে হলে বাইরের কাউকে নির্দিষ্ট নকশা খুঁজতে হয়। তাহলে কতটুকু গণনা automaton করছে, আর কতটুকু পর্যবেক্ষক? এগুলো দর্শনের প্রশ্ন নয়, সংজ্ঞার প্রশ্ন, আর প্রতিটি সার্বজনীনতার দাবিতে উত্তরটি স্পষ্ট করে লিখতে হয়।
তবু এই ফলগুলো মূল্যবান। এগুলো দেখায় যে সার্বজনীন গণনার জন্য জটিল নকশা লাগে না; খুব সরল স্থানীয় নিয়মেও তা লুকিয়ে থাকতে পারে। এর একটি কঠিন পরিণাম: এমন সরল ব্যবস্থার দীর্ঘমেয়াদি আচরণ নিয়ে অনেক প্রশ্ন undecidable, কারণ halting problem তাদের ভেতরে বসানো যায়।
মূল উপলব্ধি: “Turing-complete” একটি সর্বোচ্চ-সীমার দাবি, ব্যবহারযোগ্যতার নয়; প্রতিটি দাবির সঙ্গে encoding, শুরুর অবস্থা আর খরচ জিজ্ঞাসা করুন।
প্র ০৩প্রায় সব কাজের function primitive recursive, তবু প্রোগ্রামিং ভাষায় while-loop কেন রাখা হয়, যেখানে এর দাম halting problem?
এটা সত্য যে দৈনন্দিন program-এর প্রায় প্রতিটি function, sorting, খোঁজা, matrix গুণ, এমনকি exponential সময়ের brute force, একটি bounded loop দিয়ে লেখা যায়, যদি আগে থেকে বলে দেওয়া যায় loop সর্বোচ্চ কতবার ঘুরবে। Meyer আর Ritchie-র LOOP ভাষা ঠিক সেটাই করে। তাহলে while-loop বাদ দিয়ে সব program-কে থামার নিশ্চয়তা দেওয়া যেত না?
তিনটি কারণে বাস্তবে তা হয় না। প্রথমত, সীমা আগে থেকে জানা কঠিন হতে পারে। একটি server অনির্দিষ্টকাল অনুরোধ নিতে থাকে; একটি interpreter অজানা program চালায়; একটি সংখ্যাতত্ত্বের খোঁজ কখন শেষ হবে কেউ জানে না। সীমা জোর করে লিখতে গেলে program কৃত্রিম হয়ে যায়। দ্বিতীয়ত, উপপাদ্য ৮.১: যে ভাষায় সব program থামে, সে নিজের interpreter লিখতে পারে না, অথচ interpreter, virtual machine, compiler-এর মতো জিনিস লেখাই প্রোগ্রামিংয়ের একটি বড় অংশ। তৃতীয়ত, Ackermann দেখায় যে কিছু থামা function-এর জন্যও “কতবার” প্রশ্নের উত্তর এত বড় যে কোনো নির্দিষ্ট গভীরতার for-loop তা লিখতে পারে না।
তবে প্রবণতা উল্টো দিকেও চলছে। নিরাপত্তা-গুরুত্বপূর্ণ কাজে, যেমন smart contract, কিছু configuration ভাষা বা database query-তে, নকশাকারীরা জেনেশুনে ক্ষমতা কমান, যাতে প্রতিটি অনুরোধ নির্দিষ্ট সময়ে শেষ হয়; অনেক ব্যবস্থায় এর বদলে প্রতিটি হিসাবে একটি খরচের সীমা বসানো থাকে, যা আসলে একটি step cap. Agda বা Coq-এর মতো ভাষা আরেক পথ নেয়: সাধারণত থামা নিশ্চিত করে, আর অসীম চলা আচরণ, যেমন server, বর্ণনা করতে আলাদা গঠন (coinduction) দেয়। প্রত্যেকে একই দ্বন্দ্বের মধ্যে একটি বিন্দু বেছে নিচ্ছে।
মূল উপলব্ধি: while-loop রাখা মানে সার্বজনীনতা কেনা, আর তার দাম থামার প্রশ্নের অনির্ণেয়তা; কোন দাম দেবেন, তা ভাষার উদ্দেশ্যের ওপর নির্ভর করে।
প্র ০৪Church numeral-এ 4! হিসাবে প্রায় চার হাজার β-ধাপ লাগে। তাহলে “lambda calculus Turing machine-এর সমান” কথাটির অর্থ কী, আর কী নয়?
সমতার দাবি শুধু এটুকু: যে function একটি মডেলে গণনা করা যায়, সেটি অন্যটিতেও করা যায়। কত ধাপে, কত স্মৃতিতে, সে বিষয়ে এটি কিছু বলে না। Church numeral মূলত unary সংখ্যা, তাই n-এর আকার n-এর সমানুপাতিক, আর গুণের মতো কাজে term-এর আকার দ্রুত বাড়ে। PRED আরও খারাপ: প্রতিবার পুরো সংখ্যা জোড়ায় জোড়ায় আবার গড়ে, তাই n থেকে এক কমাতে প্রায় n ধাপ। এজন্য FACT 4-এ ৩৮৭৩টি ধাপ দেখেছেন।
একটি প্রচলিত গল্প আছে যে Church প্রথমে সন্দেহ করেছিলেন, lambda calculus-এ predecessor আদৌ লেখা যায় কি না, আর তরুণ Kleene দাঁতের চিকিৎসকের চেয়ারে বসে কৌশলটি খুঁজে পান। গল্পটি কতটা আক্ষরিক, তা নিশ্চিত নয়, কিন্তু এটি দেখায় যে “লেখা যায়” প্রমাণ করাই একসময় অজানা ছিল, দক্ষতা তো দূরের কথা।
দক্ষতার প্রশ্ন আলাদাভাবে তোলে extended Church–Turing thesis: যুক্তিসংগত মডেলগুলো একে অপরকে polynomial খরচে অনুকরণ করে। Turing machine, RAM আর lambda calculus-এর ক্ষেত্রে এটি সাধারণত সত্য ধরা হয়, তবে lambda calculus-এ “এক β-ধাপ”-কে এক একক খরচ ধরা যায় কি না, তা নিয়ে গবেষকদের দীর্ঘ আলোচনা হয়েছে, কারণ একটি ধাপেই term বিশাল হয়ে যেতে পারে। Counter machine-এর ক্ষেত্রে আমরা দেখেছি, prime-power encoding-এ অনুকরণ exponential ধীর। আর quantum computer নিয়ে প্রশ্ন হলো ঠিক এই extended thesis টেকে কি না (পর্ব ৪৭-এর অংশ ৭, বিস্তারিত পর্ব ৭৫)।
বাস্তব functional ভাষা তাই lambda calculus-কে তত্ত্বের কেন্দ্র রাখে কিন্তু বাস্তবায়নে binary integer, environment আর closure ব্যবহার করে, প্রতিটি β-ধাপে পুরো term নতুন করে লেখে না।
মূল উপলব্ধি: computability-র সমতা আর complexity-র সমতা দুটি আলাদা দাবি; প্রথমটি প্রমাণিত ও দৃঢ়, দ্বিতীয়টি মডেল আর খরচের সংজ্ঞার ওপর নির্ভর করে।
প্র ০৫Undecidability-র প্রমাণে counter machine, tag system-এর মতো ছোট মডেল এত জনপ্রিয় কেন?
একটি নতুন সমস্যা X undecidable দেখাতে সাধারণ পদ্ধতি reduction: একটি জানা undecidable সমস্যাকে X-এ রূপান্তর করা (পর্ব ৫২)। ধরুন রূপান্তরটি শুরু হয় Turing machine থেকে। তাহলে X-এর ভাষায় একটি tape, একটি head, যেকোনো আকারের alphabet আর যেকোনো সংখ্যক state-এর নিয়ম বসাতে হয়, যা প্রায়ই কষ্টসাধ্য। কিন্তু যদি শুরু হয় একটি দুই-counter যন্ত্র থেকে, তাহলে বসাতে হয় মাত্র দুটি সংখ্যা আর দুই ধরনের নির্দেশ। মডেল যত ছোট, reduction তত সহজ।
ইতিহাসে এর উদাহরণ অনেক। Minsky-র ১৯৬১ সালের প্রবন্ধের শিরোনামই ছিল Post-এর “tag” সমস্যার অনির্ণেয়তা নিয়ে, আর দুই-counter ফলটি এসেছিল সেই কাজের পথে। Post correspondence problem (পর্ব ৫৪)-এর প্রমাণে Turing machine-এর গণনাকে domino-র সারিতে সাজানো হয়। Hilbert-এর দশম সমস্যা, অর্থাৎ পূর্ণসংখ্যার বহুপদী সমীকরণের সমাধান আছে কি না, ১৯৭০ সালে Matiyasevich-এর কাজে Davis, Putnam আর Robinson-এর আগের ফলের ওপর ভিত্তি করে অনির্ণেয় প্রমাণিত হয়; পরে Jones আর Matiyasevich register machine থেকে সরাসরি সমীকরণ বানানোর একটি সরল পথ দেখান বলে উল্লেখ পাওয়া যায়। Tile দিয়ে মেঝে ঢাকার প্রশ্ন, কিছু matrix-গুণের প্রশ্ন, এমনকি কিছু খেলার নিয়মও এভাবে অনির্ণেয় প্রমাণিত।
উল্টো দিকে, ছোট মডেলের সার্বজনীনতা দেখায় অনির্ণেয়তা কতটা কাছে। Post-এর ছোট্ট 3-tag system বা Collatz-ধরনের সরল নিয়মের দীর্ঘমেয়াদি আচরণ আজও অজানা; এগুলো সার্বজনীন কি না জানা না থাকলেও, প্রায় এমন সরল নিয়মে সার্বজনীনতা আছে বলে আমরা জানি। এজন্য busy beaver-এর মতো প্রশ্নে (পর্ব ৫৫) খুব ছোট যন্ত্রেই উত্তর পাওয়া অবিশ্বাস্য কঠিন হয়ে ওঠে।
মূল উপলব্ধি: ছোট সার্বজনীন মডেল হলো reduction-এর হাতিয়ার; শুরুর মডেল যত সরল, নতুন সমস্যায় তাকে বসানো তত সহজ।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। অংশ ৩ আর ৬-এর ব্লকে নিজের term বা program বসিয়ে যাচাইও করতে পারেন।
-
নকশা (counter machine-এ গুণ): চারটি counter-এর একটি যন্ত্র দিন, যা R2 := R0 × R1 করে (শুরুতে R2 = R3 = 0); শেষে R1-এর মান যেন অক্ষত থাকে। (2, 3)-এ মোট কয়টি ধাপ লাগে?
ধারণা: R0 থেকে একটি করে তুলে প্রতিবার R1-কে R2-তে যোগ করা; যোগের সময় R1 খালি হয়ে যায়, তাই একই সঙ্গে R3-এ একটি copy রেখে পরে R1 ফিরিয়ে আনা।
Program: 0: DEC 0, 1, H · 1: DEC 1, 2, 4 · 2: INC 2, 3 · 3: INC 3, 1 · 4: DEC 3, 5, 0 · 5: INC 1, 4.
প্রতি বাইরের ঘূর্ণনে 1 (DEC R0) + 3·R1 (সরানো) + 1 (R1 শূন্য) + 2·R1 (ফেরানো) + 1 (R3 শূন্য) = 5·R1 + 3 ধাপ; সব মিলিয়ে R0·(5·R1 + 3) + 1. (2, 3)-এ 2 · 18 + 1 = ৩৭ ধাপে R = [0, 3, 6, 0]. Scratch-এ 0 থেকে 11 পর্যন্ত সব ১৪৪টি জোড়ায় R2 = R0 × R1 আর R1 অক্ষত মিলেছে; (3, 4)-এ ৭০ ধাপ।
-
প্রমাণের ভুল খুঁজুন: একজন লিখেছেন, “এক counter-এর যন্ত্রই Turing-complete. কারণ: দুই-counter যন্ত্রের মান a, b-কে একটি counter-এ 2a3b হিসেবে রাখুন। a বাড়ানো মানে 2 দিয়ে গুণ, b কমানো মানে 3 দিয়ে ভাগ, আর শূন্য-পরীক্ষা মানে বিভাজ্যতা। তাই প্রতিটি দুই-counter যন্ত্র এক counter-এ অনুকরণ করা যায়। ∎” ভুলটি কোথায়?
ভুল “2 দিয়ে গুণ” ধাপে। Counter machine-এর নির্দেশ শুধু INC আর DEC; গুণ বা ভাগ কোনো মৌলিক নির্দেশ নয়। দুই counter থাকলে গুণ করা যায়: প্রথমটি থেকে একটি তুলে দ্বিতীয়টিতে দুটি রাখা, তারপর ফেরত (অংশ ৬-এর times(k)). একটিমাত্র counter-এ তোলা মানটি কোথাও রাখার জায়গা নেই; finite control-এ রাখা যায় শুধু সসীম তথ্য, অথচ মানটি যত বড় ইচ্ছা হতে পারে।
সঠিক বক্তব্য: prime-power কৌশল k counter থেকে দুই counter-এ নামায়, এক-এ নয়। এক counter-এর যন্ত্রের ক্ষমতা পর্ব ৩২-এর counter automaton-এর সমান, যা PDA-র চেয়েও দুর্বল, আর এর থামার প্রশ্ন decidable বলে জানা। প্রমাণে “এই কাজটি কোন নির্দেশ দিয়ে হবে” প্রশ্নটি না করলে এমন লুকানো অনুমান ঢুকে পড়ে।
-
Trace আর অনুমান: (ক) A(2, 1)-এর মান আর মোট call-সংখ্যা অনুমান করুন, তারপর নিয়ম ধরে খুলে মেলান। (খ) Rule 110-এ আট ঘরের সারি 00010110 (বাইরের ঘর 0) থেকে পরের দুটি প্রজন্ম লিখুন।
(ক) A(2, 1) = A(1, A(2, 0)) = A(1, A(1, 1)), আর A(1, 1) = 3 (A(1, n) = n + 2), তাই A(1, 3) = 5. মান ৫, A(2, n) = 2n + 3-এর সঙ্গে মেলে। Call গুনলে: A(2, 1), A(2, 0), A(1, 1)-এর জন্য ৪টি (A(1, 1), A(1, 0), A(0, 1), A(0, 2)), আর A(1, 3)-এর জন্য ৮টি; মোট 1 + 1 + 4 + 8 = ১৪. Scratch-এর ackermann.py-ও (5, 14) দেয়।
(খ) 00010110 → 00111110 → 01100010. দ্বিতীয় ধাপে মাঝের 1-গুলো মরে যায় (111 → 0), শুধু দুই প্রান্ত টেকে, আর বাঁয়ের প্রান্ত এক ঘর বাঁয়ে বাড়ে (001 → 1). দুটি সারি scratch script আর JS ব্লকের নিয়মে মিলেছে।
-
প্রমাণ: PLUS′ = λm.λn.m SUCC n. প্রমাণ করুন যে সব m, n ∈ ℕ-এ PLUS′ m n-এর normal form ঠিক Church numeral m + n.
প্রমাণ। (১) দুই β-ধাপে PLUS′ m n → m SUCC n, যেখানে m, n Church numeral. — β-rule, m আর n closed বলে capture নেই (২) m = λf.λx.fm x, তাই আরও দুই ধাপে m SUCC n → SUCC (SUCC (⋯ (SUCC n))), m বার SUCC. — Church numeral-এর সংজ্ঞা (৩) m-এর ওপর induction-এ দাবি: SUCCm n-এর normal form m + n. ভিত্তি m = 0: শুধু n. ধাপ: SUCCm+1 n = SUCC (SUCCm n); Church–Rosser অনুযায়ী ভেতরটি আগে normal form m + n-এ আনলে ফল একই, আর SUCC k → k + 1 (অংশ ৩-এর ব্লকে k = 2-এ তিন ধাপে)। (৪) normal form অনন্য (উপপাদ্য ৩.১), তাই PLUS′ m n-এর normal form m + n. ∎
যাচাই: বড় interpreter-এ 0 থেকে 4 পর্যন্ত সব ২৫টি জোড়ায় ফল m + n মিলেছে; PLUS′ 2 3 লাগে ১০টি β-ধাপ, যেখানে PLUS 2 3 লাগে ৬টি। একই function, ভিন্ন term, ভিন্ন খরচ।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি Turing machine-কে দুই-counter যন্ত্রে অনুকরণের প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Tape-কে head-এর বাঁ আর ডান অংশে ভাগ করে দুটি stack হিসেবে দেখা
- প্রতিটি stack-কে base-b সংখ্যা হিসেবে পড়া: push = গুণ ও যোগ, pop = ভাগ ও ভাগশেষ
- গুণ-ভাগের জন্য একটি সহায়ক counter নিয়ে তিন counter-এ অনুকরণ
- সব counter-কে 2a3b5c আকারে একটি সংখ্যায় রাখা
- বাড়ানো-কমানো = মৌলিক দিয়ে গুণ-ভাগ, শূন্য-পরীক্ষা = বিভাজ্যতা, দ্বিতীয় counter scratch হিসেবে
Lambda term (λx.λy.x) a b-এর β-normal form কী?
- a
- b
- a b
- কোনো normal form নেই
Ackermann function A(0, n) = n + 1, A(m, 0) = A(m − 1, 1), A(m, n) = A(m − 1, A(m, n − 1)) সম্পর্কে কোনটি সঠিক?
- কিছু input-এ এটি থামে না, তাই partial
- এটি primitive recursive, শুধু খুব দ্রুত বাড়ে
- এটি total আর computable, কিন্তু primitive recursive নয়
- এটি কোনো Turing machine দিয়ে গণনা করা যায় না
Rule 110 cellular automaton-এ নতুন মান: 111 → 0, 110 → 1, 101 → 1, 100 → 0, 011 → 1, 010 → 1, 001 → 1, 000 → 0. সারির বাইরের ঘর 0 ধরলে 0110-এর পরের প্রজন্ম কী?
- 1111
- 1110
- 0110
- 1001
শুধু INC আর DEC (শূন্য হলে লাফ) নির্দেশের counter machine-এ, input-কে উপযুক্তভাবে encode করলে, যেকোনো Turing machine অনুকরণে সর্বনিম্ন কয়টি counter যথেষ্ট?
- ১টি
- ২টি
- ৩টি
- tape-এর দৈর্ঘ্যের সমান সংখ্যক
K = λa.λb.a আর Ω = (λx.x x)(λx.x x). Term K z Ω-এর ক্ষেত্রে কোনটি সঠিক?
- কোনো normal form নেই, কারণ Ω-এর normal form নেই
- Normal আর applicative দুই order-ই z-এ পৌঁছায়
- Normal form হলো Ω
- Normal form z; normal order পৌঁছায়, applicative order চিরকাল চলে
একটি প্রোগ্রামিং ভাষার প্রতিটি program প্রতিটি সংখ্যা-input-এ থামে, program-গুলোকে সংখ্যা দিয়ে চিহ্নিত করা যায়, আর ভাষায় +1 লেখা যায়। এমন ভাষা সম্পর্কে কোনটি প্রমাণিত?
- ভাষাটি Turing-complete হতে পারে
- ভাষাটি প্রতিটি total computable function লিখতে পারে
- ভাষাটি নিজের interpreter (eval) লিখতে পারে না
- ভাষার প্রতিটি program polynomial সময়ে চলে
Church numeral-এ m = λf.λx.fm x. একজন দাবি করেন EXP = λm.λn.m n হিসাব করে mn. EXP 2 3-এর normal form কোন সংখ্যা?
- 9
- 8
- 6
- কোনো normal form নেই
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Lambda calculus: variable, λx.M আর M N; হিসাব মানে β-reduction, capture এড়াতে α-conversion; Church–Rosser অনুযায়ী normal form একটিই, আর থাকলে normal order সেখানে পৌঁছায়।
- Church numeral n = “f-কে n বার”; SUCC, PLUS, MULT সরল, EXP-এ ক্রম n m; Y combinator নাম ছাড়া recursion দেয়।
- Primitive recursive = bounded loop, সবসময় total, কিন্তু সব total computable function নয় (diagonal যুক্তি, Ackermann); μ যোগ করলে ঠিক Turing-computable partial function.
- দুই counter-ই যথেষ্ট (tape → দুই stack → সংখ্যা → 2a3b5c), এক counter নয়; Rule 110 আর 2-tag system-ও সার্বজনীন, তবে encoding ও শুরুর শর্তসহ।
- সমান ক্ষমতা ≠ সমান দক্ষতা; আর কোনো ভাষা একসঙ্গে “সব program থামে” আর “নিজের interpreter লেখা যায়” হতে পারে না।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৪৩ · Turing machine — formal definition আর configurationফিরে দেখুনযে মডেলের সঙ্গে এই পর্বের সব মডেলের তুলনা।
- পর্ব ৪৪ · Turing machine নকশা — ধাপে ধাপে উদাহরণফিরে দেখুনSubroutine আর ধাপ গোনা, যা μ-recursive থেকে TM-এ রূপান্তরের ভিত্তি।
- পর্ব ৪৭ · Church–Turing thesis — algorithm-এর সংজ্ঞাফিরে দেখুনমডেলগুলোর সমতার theorem, thesis-এর মর্যাদা আর ইতিহাস।
- পর্ব ৩২ · Pushdown automaton — stack-সহ automatonপটভূমিএক counter, এক stack আর দুই stack-এর ক্ষমতার সিঁড়ি।
- পর্ব ০৪ · Theory of Computation-এর প্রমাণপটভূমিDiagonalization, যা এখানে PR-এর সীমা আর total ভাষার সীমা প্রমাণ করল।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৫০ Decidable আর Turing-recognizable language.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ১২ — Recursive সংজ্ঞা আর structural inductionপাশের ট্র্যাকAckermann function-এর থামার প্রমাণ, ℕ × ℕ-এর ওপর induction দিয়ে।
- JavaScript · পর্ব ২৩ — functional programmingপাশের ট্র্যাকPure function, currying আর composition: lambda calculus-এর ধারণা বাস্তব code-এ।