Church-Turing Thesis — যে দাবিটা প্রমাণ করা যায় না, তবু বিশ্বাস করি
Church-Turing Thesis
একটা দাবি যা কোনো গণিতবিদ কখনো প্রমাণ করতে পারবেন না — 'algorithm' শব্দের স্বজ্ঞাত অর্থে যা গণনাযোগ্য, তা Turing machine দিয়েও গণনাযোগ্য। প্রমাণ নেই, কিন্তু প্রমাণের চেয়ে শক্তিশালী একটা যুক্তি আছে: তিনটা স্বাধীন পথ, একই গন্তব্যে।
আগে এটা বুঝি
আগের লেসনের শেষে আমরা একটা দাবি করেছিলাম যা প্রমাণ ছাড়াই রেখে দিয়েছিলাম: Turing machine “সবকিছু” গণনা করতে পারে। এই লেসনে আমরা সেই দাবিটা মুখোমুখি হব — আর একটা অস্বস্তিকর সত্য আবিষ্কার করব: এই দাবিটা প্রমাণ করা সম্ভবই না।
এটা শুনতে অদ্ভুত লাগতে পারে। গণিতে আমরা তো প্রমাণ করেই দাবি করি। কিন্তু সমস্যাটা গভীরে — “algorithm” বা “effectively computable” শব্দটার কোনো স্বাধীন, পূর্ব-আনুষ্ঠানিক (pre-formal) সংজ্ঞা নেই যার বিরুদ্ধে Turing machine-কে তুলনা করে “সমান” প্রমাণ করা যায়। আমাদের কাছে শুধু একটা স্বজ্ঞা (intuition) আছে — “যা একজন মানুষ কাগজ-কলম দিয়ে, চিন্তাশক্তি ছাড়া, নিয়ম মেনে করতে পারে” — আর একটা আনুষ্ঠানিক মডেল (Turing machine)। এই দুইটার মধ্যে সমতা প্রমাণ করতে হলে দুইটাকেই একই ভাষায় লিখতে হবে — কিন্তু স্বজ্ঞাটা কখনোই সম্পূর্ণ আনুষ্ঠানিক ভাষায় বাঁধা যায় না, কারণ বাঁধলেই সেটা আর স্বজ্ঞা থাকে না, নিজেই একটা মডেল হয়ে যায়।
এটা অনেকটা “সময়ের” সংজ্ঞা প্রমাণ করার চেষ্টার মতো — পদার্থবিজ্ঞানের কোনো সূত্র “সময়” প্রমাণ করে না, বরং সময় সম্পর্কে একটা স্বজ্ঞাত ধারণা নিয়ে সূত্র লেখা হয়, আর সেই সূত্র বারবার experiment-এ সফল হলে আমরা তাতে আস্থা রাখি। ঠিক একইভাবে:
Church-Turing thesis: “effectively computable” (স্বজ্ঞাত অর্থে algorithm দিয়ে গণনাযোগ্য) প্রতিটা function ঠিক ততগুলোই যতগুলো কোনো Turing machine দিয়ে গণনাযোগ্য।
এটা একটা thesis — “theorem” না। নামের এই পার্থক্যটা ইচ্ছাকৃত, আর এই লেসনের কেন্দ্রীয় বিষয়।
মূল ধারণা
থিসিসটা ঠিক কী বলে — আর কী বলে না
সতর্কতার সাথে পড়ুন — প্রতিটা শব্দ গুরুত্বপূর্ণ।
প্রতিটা function যা “effectively computable” (একটা সসীম, যান্ত্রিক পদ্ধতিতে গণনাযোগ্য, স্বজ্ঞাত অর্থে) তা একটা Turing machine দিয়েও গণনাযোগ্য — এবং বিপরীতভাবে।
যা এটা বলে না:
- এটা বলে না TM efficiently গণনা করে — শুধু বলে গণনা সম্ভব, সসীম সময়ে (যতই দীর্ঘ হোক)
- এটা বলে না প্রতিটা প্রশ্নের উত্তর আছে — বরং এটা বলে “কোন প্রশ্নের উত্তর নীতিগতভাবে কোনো algorithm দিয়েই বের করা অসম্ভব” এই দাবিগুলো অর্থপূর্ণ, কারণ এখন “algorithm” শব্দটার একটা দৃঢ় সংজ্ঞা (TM) আছে
- এটা একটা গাণিতিক উপপাদ্য না — এটা প্রমাণ করা যায় না, শুধু সমর্থনে প্রমাণ জমা করা যায় (নিচে দেখুন)
- এটা মিথ্যাও প্রমাণ করা কঠিন — কিন্তু অসম্ভব না (নিচে hypercomputation অংশে)
কেন প্রমাণযোগ্য নয় — যুক্তির কাঠামো
ধরা যাক আপনি প্রমাণ করতে চান “effectively computable = Turing machine দিয়ে গণনাযোগ্য”। প্রমাণের জন্য দুইটা জিনিস দরকার — দুইটা
জিনিসের আনুষ্ঠানিক সংজ্ঞা, তারপর দেখানো তারা একই সেট বর্ণনা
করে।
কিন্তু “effectively computable”-এর কোনো আনুষ্ঠানিক সংজ্ঞা নেই — এটা শুধু একটা স্বজ্ঞা:
“একজন মানুষ (বা যেকোনো যান্ত্রিক প্রক্রিয়া) সসীম, স্পষ্ট নিয়ম অনুসরণ করে, সসীম সময়ে, সৃজনশীলতা বা অনুপ্রেরণা ছাড়া গণনা করতে পারে এমন যেকোনো কিছু।”
এই বাক্যটা ইংরেজিতে (বা বাংলায়) লেখা — এটা কোনো গাণিতিক বস্তু না।
আপনি একে TM-এর সাথে “সমান” প্রমাণ করতে পারবেন না, কারণ প্রমাণের
জন্য উভয় পক্ষকেই একই আনুষ্ঠানিক ভাষায় থাকতে হয়। এটা অনেকটা এরকম
প্রশ্নের মতো — “প্রমাণ করুন + চিহ্নটা ‘যোগ করা’ ধারণাটাকে ঠিকভাবে
প্রকাশ করে” — উত্তরটা প্রমাণ না, বরং একটা সিদ্ধান্ত (convention)
যা সবাই মেনে নেয় কারণ এটা প্রত্যাশা অনুযায়ী আচরণ করে।
অনানুষ্ঠানিক জগৎ আনুষ্ঠানিক জগৎ
───────────────── ────────────────
"effectively computable" ≈?≈ Turing machine
(স্বজ্ঞা, ভাষায় বর্ণিত, (আনুষ্ঠানিক সংজ্ঞা,
গাণিতিক বস্তু না) গাণিতিক বস্তু)
↑ ↑
কোনো প্রমাণ এখানে এখানে প্রমাণ সম্ভব
পৌঁছাতে পারে না, (এবং হয়েছে — নিচে দেখুন)
কারণ বাম পক্ষ
আনুষ্ঠানিক নাতাহলে আমরা কীভাবে এতে আস্থা রাখি? প্রমাণ না, বরং একত্রীকরণ (convergence) — যেটা এই লেসনের পরের অংশের বিষয়।
ভেতরে কী ঘটছে
তিনটা স্বাধীন পথ, একই গন্তব্য
১৯৩০-এর দশকে, স্বাধীনভাবে, একাধিক গণিতবিদ “effectively computable” ধারণাটাকে আনুষ্ঠানিক করার চেষ্টা করলেন — সম্পূর্ণ ভিন্ন দৃষ্টিভঙ্গি থেকে।
| মডেল | উদ্ভাবক | বছর | ভিত্তি ধারণা |
|---|---|---|---|
| General recursive functions | Gödel, Herbrand | ১৯৩৪ | সংখ্যার উপর ফাংশন — base function + composition + recursion + minimization |
| Lambda calculus | Church | ১৯৩৬ | Function-ই একমাত্র বস্তু — সবকিছু function-এর application দিয়ে প্রকাশ |
| Turing machine | Turing | ১৯৩৬ | Tape, state, mechanical step-by-step প্রক্রিয়া |
| Post systems | Post | ১৯৩৬ | String rewriting নিয়মের সেট |
| μ-recursive functions | Kleene | ১৯৩৬ | recursive function-এর একটা পরিশীলিত রূপ |
এই মডেলগুলো দেখতে সম্পূর্ণ আলাদা। Lambda calculus-এ কোনো “state” নেই, শুধু function আর application:
(λx. x + 1) 5 → 5 + 1 → 6Turing machine-এ কোনো “function application” নেই, শুধু tape আর state transition। এই দুইটা মডেল একে অপরের থেকে এতটাই ভিন্ন যে কেউ প্রথমে আশা করেনি তারা একই ক্ষমতার হবে।
অথচ ১৯৩৭ সালে Turing নিজেই প্রমাণ করলেন — lambda calculus আর Turing machine ঠিক একই function-এর সেট গণনা করে। পরে দেখানো হলো general recursive functions, Post systems, μ-recursive functions — সবগুলোও ঠিক একই সেটে গিয়ে মেলে।
যুক্তির তিনটা স্তম্ভ
Church-Turing thesis-এর পক্ষে যুক্তি সাধারণত তিন ধরনের প্রমাণের সমষ্টি:
১. একত্রীকরণ (convergence) — উপরে আলোচিত। বহু স্বাধীন পথ, একই গন্তব্য।
২. কোনো পাল্টা উদাহরণ নেই। ১৯৩৬ থেকে আজ পর্যন্ত — প্রায় ৯০ বছরে — কেউ এমন একটা function দেখাতে পারেননি যেটা “স্বজ্ঞাতভাবে algorithm দিয়ে গণনাযোগ্য” মনে হয়, অথচ কোনো Turing machine সেটা গণনা করতে পারে না। প্রতিটা নতুন প্রোগ্রামিং ভাষা (Python, Rust, Prolog, Haskell) — সবগুলোই প্রমাণিতভাবে TM-এর সমতুল্য শক্তির (কোনো একটা বেশি বা কম নয়)।
৩. Turing-এর মূল যুক্তি — মানুষের গণনা প্রক্রিয়ার বিশ্লেষণ। ১৯৩৬-এর paper-এ Turing শুধু একটা মডেল প্রস্তাব করেননি — যুক্তি দিয়ে দেখিয়েছেন কেন এই মডেল যথেষ্ট। তিনি একজন মানুষের “computation” করার প্রক্রিয়াকে বিশ্লেষণ করলেন এবং যুক্তি দিলেন:
- মানুষ একবারে সসীম সংখ্যক symbol দেখতে পারে (দৃষ্টির সীমাবদ্ধতা)
- মানুষের মানসিক অবস্থা যেকোনো মুহূর্তে সসীম সংখ্যক সম্ভাব্য “মোডের” একটা (অসীম distinct মানসিক অবস্থা থাকলে, দুইটা যথেষ্ট কাছাকাছি অবস্থা গুলিয়ে ফেলার ঝুঁকি থাকত)
- প্রতিটা “পরবর্তী পদক্ষেপ” শুধু বর্তমানে দেখা প্রতীক আর বর্তমান মানসিক অবস্থার উপর নির্ভর করে
এই তিনটা যুক্তিসঙ্গত সীমাবদ্ধতা মিলিয়ে ঠিক TM-এর সংজ্ঞাতেই পৌঁছায় — এটা একটা দার্শনিক যুক্তি, গাণিতিক প্রমাণ না, কিন্তু এটাই কারণ কেন TM-এর সংজ্ঞাটা “স্বেচ্ছাচারী” মনে হয় না।
উদাহরণ
Lambda calculus বনাম Turing machine — একই ফাংশন, দুই ভাষায়
একটা কংক্রিট উদাহরণ দিয়ে দেখা যাক দুইটা মডেল কতটা ভিন্ন দেখতে, তবু সমতুল্য।
Factorial, lambda calculus-এ (Church encoding-এর ধারণাগত রূপ, সরলীকৃত):
FACT = λn. IF (ISZERO n) 1 (MULT n (FACT (PRED n)))এখানে কোনো “state” নেই, কোনো “tape” নেই — শুধু function definition
আর recursive application। n একটা “Church numeral” (সংখ্যা নিজেই
একটা function হিসেবে এনকোড করা — n মানে “একটা function-কে n
বার apply করো”)।
একই factorial, Turing machine-এ: আগের লেসনে দেখা transition table-এর ধাঁচে — states যা “এখন কোন digit-এ আছি”, “কী carry করছি” ইত্যাদি track করে, আর tape-এ unary বা binary encoded সংখ্যা।
এই দুইটা বর্ণনা কল্পনাযোগ্যভাবে ভিন্ন — একটায় কোনো memory/tape নেই, একটায় কোনো function/application নেই। তবু ১৯৩৭-এর Turing-এর প্রমাণ অনুযায়ী, যেকোনো lambda calculus expression-এর জন্য একটা TM বানানো যায় যা সেটা simulate করে, আর বিপরীতভাবে।
কী দিয়ে থিসিসটা মিথ্যা প্রমাণ হতো
একটা থিসিস অর্থপূর্ণ হতে হলে, নীতিগতভাবে falsifiable হতে হবে — এমন কিছু কল্পনা করা যায় যা মিথ্যা প্রমাণ করত। Church-Turing thesis-এর ক্ষেত্রে:
Hypercomputation — যদি কেউ এমন একটা যন্ত্র বা প্রক্রিয়া দেখাতে পারতেন যা “স্বজ্ঞাতভাবে effectively computable” মনে হয়, অথচ কোনো TM সেটা গণনা করতে পারে না — থিসিসটা মিথ্যা প্রমাণিত হতো। কিছু তাত্ত্বিক প্রস্তাব:
- Zeno machine — একটা কাল্পনিক মেশিন যা প্রথম step-এ
1সেকেন্ড নেয়, দ্বিতীয়টায়0.5সেকেন্ড, তৃতীয়টায়0.25… মোট2সেকেন্ডে অসীম সংখ্যক step সম্পন্ন করে। এমন মেশিন halting problem-ও “সমাধান” করতে পারত (সসীম সময়ে অসীম চেক করে)। - Oracle machine — Turing নিজেই ১৯৩৯-এ প্রস্তাব করেছিলেন একটা TM যার একটা বিশেষ “oracle” tape আছে যা তাৎক্ষণিকভাবে (এক step-এ) একটা undecidable প্রশ্নের (যেমন halting problem) উত্তর দেয়। এটা থিসিসকে খণ্ডন করে না (কারণ এটা একটা thought experiment, বাস্তব বাস্তবায়ন প্রস্তাবিত না) — বরং এটা complexity hierarchy-র একটা তাত্ত্বিক টুল, যেখানে “যদি ধরে নিই X সমাধানযোগ্য, তাহলে আর কী কী সমাধানযোগ্য হয়” প্রশ্ন করা যায়।
গুরুত্বপূর্ণ: এই দুইটাই কল্পনার জগতে — কোনো বাস্তব যন্ত্র আজ পর্যন্ত hypercomputation দেখায়নি। এগুলো থিসিসটাকে খণ্ডন করেনি, বরং দেখিয়েছে থিসিসটা অর্থহীন না — এমন কিছু কল্পনা করা যায় যা সত্য হলে থিসিসটা মিথ্যা হতো, কিন্তু বাস্তবে এমন কিছু পাওয়া যায়নি।
নিজে চালিয়ে দেখুন
দুইটা সম্পূর্ণ ভিন্ন গণনার মডেল, একই ফলাফল
# ── ধরন ১: lambda calculus-ধাঁচ — কোনো state নেই, শুধু function composition ──
# (Python-এ lambda calculus-এর 'বিশুদ্ধ' রূপ লেখা কঠিন, কিন্তু চেতনাটা ধরা যায়)
Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))) # Y-combinator, recursion ছাড়াই recursion
fact_lambda = Y(lambda self: lambda n: 1 if n == 0 else n * self(n - 1))
print("lambda-ধাঁচ factorial(5) =", fact_lambda(5))
# ── ধরন ২: tape-driven state machine ধাঁচ — TM-এর চেতনায়, কোনো function call নেই ──
def fact_tm_style(n):
"""কোনো recursion না, কোনো higher-order function না — শুধু
tape-এর মতো একটা list, আর state হিসেবে দুইটা counter।"""
tape = [1, n] # tape[0] = running product (accumulator), tape[1] = countdown
state = "loop"
steps = 0
while state != "halt":
steps += 1
if tape[1] == 0:
state = "halt"
else:
tape[0] = tape[0] * tape[1] # 'write' — tape-এর ঘর বদলানো
tape[1] = tape[1] - 1 # 'move/write' — countdown কমানো
return tape[0], steps
result, steps = fact_tm_style(5)
print("TM-ধাঁচ factorial(5) =", result, f"({steps} steps-এ)")
assert fact_lambda(5) == result == 120
print("\nদুইটা সম্পূর্ণ ভিন্ন 'চিন্তাভঙ্গি' — একই ফলাফল। এটাই একত্রীকরণের সারমর্ম।")এবার নিজে চেষ্টা করুন — Fibonacci একই দুই স্টাইলে লিখুন:
fib_lambda = Y(lambda self: lambda n: n if n \< 2 else self(n-1) + self(n-2))
def fib_tm_style(n):
tape = [0, 1, n] # tape = [a, b, countdown]
while tape[2] > 0:
tape[0], tape[1] = tape[1], tape[0] + tape[1]
tape[2] -= 1
return tape[0]
for i in range(10):
assert fib_lambda(i) == fib_tm_style(i), f"মিলল না n={i}"
print("Fibonacci-ও দুই স্টাইলে মিলে গেল, n=0..9")Lambda calculus-ধাঁচের (শুধু function, কোনো loop/state নেই) আর একটা tape-driven state-machine ধাঁচের — দুইটা সম্পূর্ণ ভিন্ন প্রোগ্রামিং স্টাইল দিয়ে একই গণনা করা সম্ভব, যা Church-Turing thesis-এর একত্রীকরণ (convergence) যুক্তির একটা ছোট, হাতে-ছোঁয়া উদাহরণ।
বাস্তব সিস্টেমে
Physical Church-Turing thesis — একটা গভীরতর প্রশ্ন
মূল থিসিসটা “গাণিতিক” computability নিয়ে — কী function গণনাযোগ্য, পদার্থবিজ্ঞানের কোনো সীমাবদ্ধতা বিবেচনা না করে। একটা শক্তিশালী সংস্করণ আছে যা পদার্থবিজ্ঞান যোগ করে:
Physical Church-Turing thesis: মহাবিশ্বে যেকোনো ভৌত প্রক্রিয়া (physical process) একটা Turing machine দিয়ে simulate করা যায় (efficiency উপেক্ষা করে)।
এটা মূল থিসিসের চেয়ে শক্তিশালী দাবি — শুধু “গণিতে কী গণনাযোগ্য” না, বরং “প্রকৃতি নিজে কী গণনা করতে পারে”। এই সংস্করণটাই quantum computing নিয়ে বিতর্কের কেন্দ্রে।
Quantum computer কি থিসিসটা লঙ্ঘন করে? না — এবং এটা একটা সাধারণ ভুল বোঝাবুঝি।
গণনার তত্ত্বের বাইরে, এই ধারণার প্রভাব
Programming language ডিজাইন। একবার Church-Turing thesis মেনে নিলে, একটা গভীর ফলাফল আসে: প্রতিটা Turing-complete ভাষা (Python, Java, C, Haskell, Prolog) একই class-এর সমস্যা সমাধান করতে সক্ষম — কোনো ভাষা মৌলিকভাবে “বেশি শক্তিশালী” না। ভাষাগুলো ভিন্ন হয় expressiveness (কত সংক্ষেপে লেখা যায়), performance, নিরাপত্তা, এসব দিক থেকে — কম্পিউটেবিলিটি দিক থেকে না। এই কারণেই “কোন ভাষা সবচেয়ে শক্তিশালী” প্রশ্নটা (computability অর্থে) অর্থহীন — সবগুলোই সমান শক্তির, যদি Turing-complete হয়।
AI ও চিন্তার তত্ত্ব। Church-Turing thesis-এর একটা বিতর্কিত সম্প্রসারণ — “মানুষের মস্তিষ্কও একটা Turing machine দিয়ে simulate করা যায়” (strong AI-এর একটা ভিত্তি ধারণা)। এই সম্প্রসারণটা মূল থিসিসের চেয়ে অনেক বেশি বিতর্কিত — Roger Penrose-এর মতো পদার্থবিজ্ঞানী যুক্তি দিয়েছেন মস্তিষ্কের কিছু প্রক্রিয়া quantum-gravitational এবং non-computable হতে পারে। এটা মূল Church-Turing thesis-এর প্রশ্ন না (যেটা প্রায় সর্বজনস্বীকৃত), বরং তার একটা অনেক বেশি সাহসী সম্প্রসারণ (যেটা বিতর্কিত)।
Compiler ও type theory। Compilers module-এ পরে দেখবেন — একটা type checker-এর মূল কাজ প্রোগ্রামের আচরণ সম্পর্কে কিছু প্রশ্নের উত্তর দেওয়া (যেমন “এই ভ্যারিয়েবল কি সবসময় integer থাকবে”)। কেন type checker সবসময় রক্ষণশীল (conservative) — কিছু নিরাপদ প্রোগ্রামকেও প্রত্যাখ্যান করে — তার মূল কারণ Church-Turing thesis-এর একটা সরাসরি পরিণতি (undecidability), যা কয়েক লেসন পরে আনুষ্ঠানিকভাবে আসবে।
যে ভুলগুলো সবাই করে
“Church-Turing thesis একটা প্রমাণিত উপপাদ্য (theorem), যেহেতু এটা ৯০ বছর ধরে টিকে আছে।”
না — “৯০ বছর কোনো পাল্টা উদাহরণ পাওয়া যায়নি” মানে শক্তিশালী পরোক্ষ প্রমাণ, প্রমাণ না। এটা বিজ্ঞানের সেই অর্থে “প্রতিষ্ঠিত” যে অর্থে নিউটনের গতিসূত্র বা তাপগতিবিদ্যার দ্বিতীয় সূত্র প্রতিষ্ঠিত — বহুবার পরীক্ষিত, কখনো ব্যর্থ হয়নি, তাই বিশ্বাসযোগ্য — কিন্তু গাণিতিক অর্থে “প্রমাণিত” না, কারণ প্রমাণ করার কোনো উপায়ই নেই (আগে আলোচিত — “algorithm”-এর কোনো স্বাধীন আনুষ্ঠানিক সংজ্ঞা নেই যার বিরুদ্ধে TM-কে মেলানো যায়)।
এই পার্থক্যটা গুরুত্বপূর্ণ কারণ এটা মনে করিয়ে দেয় — গণনার তত্ত্ব বিশুদ্ধ গণিত হলেও, তার ভিত্তি (কোন মডেলটা “computation” ধারণাটা ধরে) একটা empirical/philosophical সিদ্ধান্তের উপর দাঁড়িয়ে, পুরোপুরি a priori প্রমাণের উপর না।
“Lambda calculus, Turing machine, আর general recursive functions 'একই জিনিস' — শুধু নাম আলাদা।”
আনুষ্ঠানিকভাবে সমতুল্য (একই function-এর সেট গণনা করে), কিন্তু গঠনে সম্পূর্ণ ভিন্ন — এই পার্থক্যটাই তাদের একত্রীকরণকে অর্থবহ করে তোলে।
যদি তিনজন গণিতবিদ শুধু একে অপরের মডেল সামান্য পরিবর্তন করে “নতুন” মডেল বানাতেন, একত্রীকরণে কোনো বিস্ময় থাকত না — তারা তো আসলে একই জিনিস বিভিন্ন notation-এ লিখতেন। কিন্তু lambda calculus (function, কোনো state নেই) আর Turing machine (state, tape, কোনো higher-order function নেই) — এরা ধারণাগতভাবে এতটাই দূরবর্তী যে স্বাধীনভাবে আবিষ্কৃত হওয়াটা বিশ্বাসযোগ্য। ঠিক এই স্বাধীনতা আর গঠনগত দূরত্বই একত্রীকরণকে প্রমাণসদৃশ শক্তি দেয় — আগের “hood” অংশের মূল যুক্তি।
“Quantum computer Church-Turing thesis ভঙ্গ করে, কারণ এটা 'classical কম্পিউটার যা পারে না তা করতে পারে'।”
Quantum computer classical TM-এর চেয়ে দ্রুত কিছু সমস্যা সমাধান করতে পারে (বিশ্বাস করা হয়) — কিন্তু কোনো নতুন function computable করে না। Shor’s algorithm একটা সংখ্যাকে factor করে; একটা classical TM-ও ঠিক একই factor বের করতে পারে (brute force দিয়ে, সূচকীয় বেশি সময় নিয়ে)। উত্তর একই, শুধু সময় ভিন্ন।
এই বিভ্রান্তিটা “কী গণনাযোগ্য” (Church-Turing thesis-এর প্রশ্ন)
আর “কত দ্রুত গণনাযোগ্য” (complexity theory-র প্রশ্ন, P বনাম NP
বনাম BQP) গুলিয়ে ফেলার একটা নির্দিষ্ট রূপ — এই module জুড়ে বারবার
ফিরে আসা একটা সতর্কতা।
বুঝেছেন কি না দেখুন
1Church-Turing thesis-কে কেন “theorem” না বলে “thesis” বলা হয়? এক
বাক্যে বলুন।
স্মরণ
কারণ এটা প্রমাণ করা যায় না — এতে একটা পক্ষ (“effectively computable”, একটা অনানুষ্ঠানিক স্বজ্ঞা) আরেকটা পক্ষের (Turing machine, একটা আনুষ্ঠানিক সংজ্ঞা) সাথে গাণিতিকভাবে তুলনা করার কোনো উপায় নেই, যেহেতু প্রথম পক্ষের কোনো স্বাধীন আনুষ্ঠানিক সংজ্ঞাই নেই।
2একজন বন্ধু বলছে: “যেহেতু Church-Turing thesis প্রমাণ করা যায় না,
তাহলে এটাতে বিশ্বাস করার কোনো ভিত্তিই নেই — এটা নিছক অনুমান।” এই
যুক্তির কোথায় ত্রুটি?
যুক্তি
“প্রমাণযোগ্য নয়” আর “কোনো ভিত্তি নেই” — এই দুইটা সমার্থক না। থিসিসের পক্ষে শক্তিশালী পরোক্ষ প্রমাণ আছে:
- একাধিক স্বাধীনভাবে আবিষ্কৃত মডেল (TM, lambda calculus, general recursive functions, Post systems) সবাই সমতুল্য প্রমাণিত
- ৯০ বছরে কোনো পাল্টা উদাহরণ পাওয়া যায়নি — কোনো “স্বজ্ঞাতভাবে computable” function যা TM গণনা করতে পারে না
- Turing-এর নিজের বিশ্লেষণী যুক্তি — মানুষের গণনা প্রক্রিয়ার যুক্তিসঙ্গত সীমাবদ্ধতা থেকে সরাসরি TM-এর সংজ্ঞায় পৌঁছানো
এটা ঠিক পদার্থবিজ্ঞানের সূত্রের মতো — নিউটনের গতিসূত্রও “প্রমাণ” করা যায় না (physics-এর কোনো সূত্রই আনুষ্ঠানিক প্রমাণ পায় না, শুধু experiment-এর সমর্থন), তবু এটাতে বিশ্বাস করার শক্তিশালী ভিত্তি আছে। “প্রমাণযোগ্য নয়” মানে “যুক্তিহীন” না — গণিত আর পদার্থবিজ্ঞানের সীমানায় এই ধরনের থিসিস স্বাভাবিক।
3কল্পনা করুন কেউ আবিষ্কার করলেন একটা নতুন ভৌত প্রক্রিয়া (যেমন একটা
বিশেষ ধরনের ব্ল্যাক হোল-based ডিভাইস) যা সসীম সময়ে halting
problem সমাধান করে (যেকোনো TM আর ইনপুট দিলে, বলে দেয় এটা থামবে
কি না, সবসময় সঠিক উত্তর, সসীম সময়ে)। এটা কোন থিসিসকে চ্যালেঞ্জ
করবে — মূল Church-Turing thesis, নাকি physical Church-Turing
thesis, নাকি দুইটাই? ব্যাখ্যা করুন।
প্রয়োগ
এটা physical Church-Turing thesis-কে চ্যালেঞ্জ করবে, মূল (গাণিতিক) থিসিসকে নয় — যদিও পরোক্ষভাবে এটা মূল থিসিসের উপরও প্রশ্ন তুলবে।
কেন physical: physical Church-Turing thesis দাবি করে “মহাবিশ্বে যেকোনো ভৌত প্রক্রিয়া TM দিয়ে simulate করা যায়”। যদি এই ব্ল্যাক হোল ডিভাইসটা সত্যিই কাজ করে, তাহলে এটা এমন একটা “ভৌত প্রক্রিয়া” যা কোনো TM দিয়ে simulate করা যায় না (কারণ পরের লেসনে আমরা প্রমাণ করব — halting problem কোনো TM-ই সমাধান করতে পারে না, প্রমাণটা diagonalization-ভিত্তিক এবং TM-এর সংজ্ঞার একটা মৌলিক ফলাফল, কোনো নির্দিষ্ট TM-এর সীমাবদ্ধতা না)। তাই এই ডিভাইসটা সরাসরি physical থিসিসের বিরুদ্ধে একটা পাল্টা উদাহরণ।
কেন মূল থিসিসও পরোক্ষভাবে প্রশ্নবিদ্ধ হবে: মূল থিসিস শুধু গাণিতিক computability নিয়ে, তাই কঠোরভাবে বললে এই আবিষ্কার সেটাকে সরাসরি খণ্ডন করে না (TM-এর গাণিতিক সংজ্ঞা আর undecidability proof অপরিবর্তিত থাকবে)। কিন্তু বাস্তবে এটা একটা গভীর দার্শনিক প্রশ্ন তুলবে — “effectively computable”-এর স্বজ্ঞাটাই কি ভুল ছিল, যদি প্রকৃতি নিজে TM-এর চেয়ে বেশি “গণনা” করতে পারে? এই কারণেই দুইটা থিসিস (গাণিতিক ও physical) সম্পর্কযুক্ত হলেও আলাদা রাখা গুরুত্বপূর্ণ — একটা প্রশ্ন গণিত সম্পর্কে, আরেকটা প্রকৃতি সম্পর্কে।
4“Oracle machine” চিন্তা-পরীক্ষাটা কি Church-Turing thesis-কে খণ্ডন
করে? কেন বা কেন না?
যুক্তি
না, খণ্ডন করে না। Oracle machine একটা কাল্পনিক নির্মাণ — একটা TM যাকে একটা বিশেষ tape দেওয়া হয়েছে যা (ধরে নেওয়া হয়) কোনো নির্দিষ্ট undecidable প্রশ্নের উত্তর তাৎক্ষণিকভাবে দেয়। কিন্তু এটা বাস্তবায়নযোগ্য বলে দাবি করা হয় না — এটা একটা গাণিতিক টুল, “যদি ধরে নিই X সমাধানযোগ্য, তখন কী হয়” প্রশ্ন অন্বেষণ করার জন্য।
Church-Turing thesis একটা দাবি ভৌত বা গাণিতিকভাবে বাস্তব কম্পিউটেশন প্রক্রিয়া নিয়ে (“effectively computable” মানে সত্যিকার একটা যান্ত্রিক পদ্ধতি প্রয়োগ করা যায়)। Oracle machine স্বীকারই করে যে oracle-টা “জাদু” — এটা কোনো বাস্তব যান্ত্রিক প্রক্রিয়ার দাবি করে না। তাই এটা থিসিসের পরিধির বাইরে, এবং থিসিসকে খণ্ডন করে না — বরং এটা দেখায় থিসিসটা falsifiable (নীতিগতভাবে খণ্ডনযোগ্য), যা একটা অর্থপূর্ণ বৈজ্ঞানিক দাবির প্রয়োজনীয় বৈশিষ্ট্য।
Oracle machine-এর আসল ব্যবহারিক গুরুত্ব complexity theory-তে — “relative computability” আর complexity hierarchy বিশ্লেষণে, যেটা এই module-এর পরের অংশে (complexity classes) ফিরে আসবে।
এরপর কী
Church-Turing thesis আমাদের একটা শক্ত ভিত্তি দিল — Turing machine দিয়ে “algorithm”-এর সীমা প্রশ্ন করা এখন অর্থপূর্ণ, শুধু একটা খেলনা মডেলের সীমাবদ্ধতা না। এবার আমরা সেই সীমাটা খুঁজে বের করব।
পরের লেসনে আমরা প্রথম কংক্রিট উদাহরণ দেখব একটা প্রশ্নের যা কোনো algorithm দিয়েই সমাধানযোগ্য না — halting problem। এই লেসনে আমরা প্রথম দেখেছিলাম (TM simulator experiment-এ) একটা মেশিন loop করতে পারে, reject না করেই। পরের লেসনে আমরা প্রমাণ করব — “এই মেশিন loop করবে কি না” প্রশ্নের একটা সাধারণ, সবসময়-কাজ-করা algorithm নীতিগতভাবেই অসম্ভব। প্রমাণটা diagonalization নামের একটা কৌশল ব্যবহার করবে — গণনার তত্ত্বের সবচেয়ে গুরুত্বপূর্ণ একক প্রমাণ।
আরও পড়ুন
- An Unsolvable Problem of Elementary Number Theory — Alonzo Church · American Journal of Mathematics, 1936 — lambda calculus দিয়ে Entscheidungsproblem-এর সমাধান
- Computability and Complexity from a Programming Perspective — Neil D. Jones · কেন thesis-টা 'প্রমাণযোগ্য নয়' তার সবচেয়ে পরিষ্কার দার্শনিক আলোচনা
- Is Quantum Mechanics Compatible with a Deterministic Universe? — David Deutsch · Physical Church-Turing thesis ও quantum computation নিয়ে মূল আলোচনার সূত্রপাত