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

Church–Turing thesis — algorithm-এর সংজ্ঞা

The Church–Turing Thesis — What an Algorithm Is, Equivalent Models of Computation, Status of the Thesis, the Extended Thesis and Turing Completeness

Taught in Bangla, this lesson explains why proving that no algorithm exists needs a mathematical definition of algorithm. It traces Hilbert's questions to the 1936 proposals and their proven equivalence, computes gcd(12, 18) in three models with in-page Python (Pyodide), and discusses why the thesis is not a theorem and the evidence for it. It separates the extended thesis and quantum computers, and covers Turing completeness, including languages kept deliberately non-Turing-complete.

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

  • “Algorithm”-এর অনানুষ্ঠানিক বৈশিষ্ট্য, আর কেন negative ফলাফলের জন্য একটি নিখুঁত সংজ্ঞা লাগে
  • Hilbert থেকে Church, Turing আর Post: কে কোন সংজ্ঞা দিলেন, আর Turing-এর “মানুষ-গণক” বিশ্লেষণ
  • গণনার মডেলগুলোর সমতার theorem আর simulation দিয়ে তার প্রমাণের রূপরেখা; Python-এ একই gcd তিন মডেলে চালিয়ে মেলানো
  • Thesis-এর সঠিক বক্তব্য, কেন এটি প্রমাণযোগ্য theorem নয়, আর extended ও physical রূপের পার্থক্য
  • Turing completeness কী, কীভাবে দেখানো হয়, আর একটি ছোট tape language-এর interpreter step cap-সহ চালানো

১ · “Algorithm” মানে কী — সংজ্ঞা ছাড়া “অসম্ভব” প্রমাণ করা যায় না

প্রায় ২,৩০০ বছর ধরে মানুষ Euclid-এর algorithm দিয়ে দুটি সংখ্যার gcd (গসাগু) বের করছে। কেউ জিজ্ঞেস করেনি, “algorithm ঠিক কী?” দরকার পড়েনি, কারণ একটি পদ্ধতি দেখালেই সবাই মেনে নিত যে এটি একটি পদ্ধতি। গসাগুর গণিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ২১-এ আছে; এখানে আমাদের আগ্রহ পদ্ধতিটির ধরন নিয়ে।

রেলস্টেশনের টিকিট কাউন্টারের একজন নতুন কর্মীর কথা ভাবুন। তাঁর হাতে একটি মোটা নিয়মের খাতা: “যাত্রী শিশু হলে অর্ধেক ভাড়া লিখুন, তারপর ৭ নম্বর নিয়মে যান।” তিনি রেলের নীতি বোঝেন কি না, তাতে কিছু আসে যায় না। খাতা মেনে চললেই ঠিক টিকিট বের হয়। খাতাটি সসীম, প্রতিটি নিয়ম স্পষ্ট, কোনো ধাপে নিজের বুদ্ধি খাটাতে হয় না, আর হিসাবের জন্য যত খুশি কাগজ নেওয়া যায়। এটিই algorithm-এর অনুভূতি: বুদ্ধি ছাড়া, শুধু নিয়ম মেনে করা যায় এমন কাজ।

এই অনুভূতি থেকে algorithm-এর অনানুষ্ঠানিক বৈশিষ্ট্যগুলো লেখা যায়, যাকে ১৯৩০-এর দশকে বলা হতো effective calculability (কার্যকর গণনাযোগ্যতা):

  • সসীম বর্ণনা: নির্দেশের তালিকা সসীম, আর আগে থেকে লেখা।
  • বিচ্ছিন্ন ধাপ: কাজ এগোয় একটি একটি ধাপে; প্রতিটি ধাপ সরল আর যান্ত্রিক।
  • বুদ্ধি বা অনুমান নেই: পরের ধাপ কী, তা বর্তমান অবস্থা থেকেই নির্দিষ্ট।
  • সীমাহীন কিন্তু সসীম সম্পদ: কাগজ যত লাগে পাওয়া যায়, তবে যেকোনো মুহূর্তে ব্যবহৃত কাগজ সসীম।
  • উত্তর থাকলে সসীম ধাপে আসে: থামলে ফল পড়া যায়; আবার কিছু input-এ পদ্ধতি চিরকাল চলতেও পারে।

শেষ বৈশিষ্ট্যটি গুরুত্বপূর্ণ। বাজারঘরের ওয়েবসাইটে একটি “coupon checker” লিখলে সেটি যেকোনো coupon-এ থামবে, এটি আমরা চাই। কিন্তু algorithm-এর সাধারণ ধারণায় এমন পদ্ধতিও পড়ে যা কিছু input-এ শেষ হয় না। তাই গণনা করা ফাংশন হয় partial: কিছু input-এ মান নেই। পর্ব ০৫-এ recognizer আর decider-এর যে পার্থক্য দেখেছেন, তার মূল এখানেই।

এখন আসল সমস্যা। “এই সমস্যার algorithm আছে” দেখাতে শুধু একটি algorithm দেখালেই চলে। কিন্তু “কোনো algorithm নেই” দেখাতে হলে সব সম্ভাব্য algorithm বাদ দিতে হয়। সব কিছু বাদ দিতে হলে জানতে হয় “সব” বলতে কী বোঝায়: algorithm-এর একটি গাণিতিক সংজ্ঞা, যার ওপর quantifier বসানো যায়। এই কারণে ১৯৩০-এর দশকের গণিতবিদদের একটি সংজ্ঞা দরকার হয়েছিল, আর সেই প্রয়োজন এসেছিল Hilbert-এর প্রশ্ন থেকে।

২ · Hilbert-এর প্রশ্ন থেকে ১৯৩৬ — কে কোন সংজ্ঞা দিলেন

কোর্সের এক নজরের সময়রেখা পর্ব ০১-এ আছে। এখানে শুধু algorithm-এর সংজ্ঞার গল্পটি, আরও কাছ থেকে। সালগুলো সাধারণভাবে স্বীকৃত প্রকাশের সাল; অনেক ধারণা আগে বক্তৃতা বা চিঠিতে এসেছিল।

  1. দশম সমস্যা১৯০০Hilbert
  2. Entscheidungsproblem১৯২৮Hilbert, Ackermann
  3. Incompleteness১৯৩১Gödel
  4. Recursive function১৯৩৪Gödel, Herbrand
  5. Church-এর প্রস্তাব১৯৩৬Church, Kleene
  6. যন্ত্রের মডেল১৯৩৬Turing; Post
  7. সমতা আর নাম১৯৩৭–৫২Turing, Kleene
  8. দশম সমস্যার উত্তর১৯৭০Matiyasevich
  1. ১৯০০, প্যারিস। David Hilbert আন্তর্জাতিক গণিত সম্মেলনে ২৩টি সমস্যা দেন। দশম সমস্যা: পূর্ণসংখ্যা-সহগের যেকোনো বহুপদী সমীকরণ (Diophantine equation) দিলে তার পূর্ণসংখ্যা সমাধান আছে কি না, সসীম ধাপে বলার একটি “প্রক্রিয়া” বের করুন। তিনি ধরে নিয়েছিলেন এমন প্রক্রিয়া আছে, শুধু খুঁজে পাওয়া বাকি।
  2. ১৯২৮। Hilbert আর Wilhelm Ackermann-এর logic-এর বইয়ে Entscheidungsproblem স্পষ্ট রূপ পায়: প্রথম-ক্রম logic-এর একটি সূত্র সর্বত্র সত্য কি না, যান্ত্রিকভাবে নির্ণয় করুন। একই বছর Hilbert-এর বক্তৃতায় প্রশ্নটি তাঁর বৃহত্তর কর্মসূচির অংশ হিসেবে আসে। “হ্যাঁ” উত্তর দিতে একটি পদ্ধতি দেখালেই চলত; “না” বলতে সংজ্ঞা লাগত।
  3. ১৯৩১। Kurt Gödel-এর incompleteness theorem: যথেষ্ট শক্তিশালী সামঞ্জস্যপূর্ণ তত্ত্বে এমন সত্য বক্তব্য থাকে যা তত্ত্বের ভেতরে প্রমাণ হয় না। এটি সরাসরি Entscheidungsproblem-এর উত্তর নয়, কিন্তু “সব কিছু যান্ত্রিক করা যায়” আশায় প্রথম বড় ফাটল। প্রমাণে Gödel আজকের ভাষায় primitive recursive ফাংশন ব্যবহার করেন।
  4. ১৯৩৪। Princeton-এর বক্তৃতায় Gödel, Jacques Herbrand-এর একটি প্রস্তাব নিয়ে, general recursive function-এর সংজ্ঞা দেন: সমীকরণের একটি পদ্ধতি থেকে মান হিসাব করা যায় এমন ফাংশন। Gödel নিজে তখন নিশ্চিত ছিলেন না যে এটি “সব কার্যকর গণনা” ধরে।
  5. ১৯৩৬, Church. Alonzo Church প্রস্তাব করেন: effectively calculable = λ-definable = general recursive. Stephen Kleene-এর সঙ্গে কাজে আগেই দেখা গিয়েছিল λ-definable আর general recursive ফাংশন একই। এই সংজ্ঞায় Church দেখান Entscheidungsproblem সমাধানযোগ্য নয়। জানা যায়, Gödel প্রথমে এই প্রস্তাবে সন্তুষ্ট হননি।
  6. ১৯৩৬, Turing আর Post. Alan Turing-এর “On Computable Numbers” (জমা ১৯৩৬, ছাপা ১৯৩৬–৩৭) একটি যন্ত্র-মডেল দেয় আর, আরও গুরুত্বপূর্ণ, কেন এই মডেল কাগজ-কলমের মানুষের সব হিসাব ধরে, তার যুক্তি দেয় (অংশ ৩)। প্রায় একই সময়ে Emil Post আলাদাভাবে খুব কাছাকাছি একটি “কর্মী আর ঘর” মডেল ছাপেন। Gödel পরে Turing-এর বিশ্লেষণকে বিশ্বাসযোগ্য বলে মেনে নেন।
  7. সমতা আর নাম। Turing তাঁর প্রবন্ধের পরিশিষ্টে আর ১৯৩৭ সালের একটি প্রবন্ধে দেখান তাঁর computable ফাংশন আর λ-definable ফাংশন একই। Kleene ১৯৪৩ সালে দাবিটিকে “Thesis I” বলেন, আর ১৯৫২ সালের বইয়ে “Church’s thesis” ও “Turing’s thesis” নাম ব্যবহার করেন; “Church–Turing thesis” নামটি পরে চালু হয়।
  8. ১৯৭০। Martin Davis, Hilary Putnam আর Julia Robinson-এর কয়েক দশকের কাজের ওপর Yuri Matiyasevich শেষ ধাপটি প্রমাণ করেন (MRDP theorem): Hilbert-এর দশম সমস্যার কোনো algorithm নেই। “কোনো algorithm নেই” কথাটির মানেই এখানে Turing machine-এর সংজ্ঞায়; সংজ্ঞা ছাড়া প্রশ্নটির উত্তর দেওয়াই যেত না।

একটি সূক্ষ্ম কথা: Church আর Turing দুজনেই Entscheidungsproblem-এর উত্তর “না” দেন, কিন্তু তাঁদের অবদান আলাদা। Church-এর সংজ্ঞা গাণিতিকভাবে নিখুঁত ছিল, কিন্তু কেন “সব কার্যকর গণনা” এর মধ্যে পড়ে, তার পক্ষে যুক্তি ছিল মূলত সংজ্ঞাগুলোর মিল। Turing সরাসরি প্রশ্নটি বিশ্লেষণ করেন: একজন মানুষ নিয়ম মেনে হিসাব করলে ঠিক কী কী করেন। এই কারণে অনেক লেখক thesis-এর মূল যুক্তির কৃতিত্ব Turing-কে দেন। ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৫-এ thesis-এর প্রথম পরিচয় আছে; এই পর্ব তার অনেক গভীরে যায়।

৩ · Turing-এর বিশ্লেষণ — কাগজ-কলমের মানুষ থেকে যন্ত্র

১৯৩৬ সালে “computer” শব্দের মানে ছিল একজন মানুষ, যিনি পেশাগতভাবে হিসাব করেন। Turing-এর প্রবন্ধের নবম অংশে তিনি এমন একজন মানুষের কাজকে ধাপে ধাপে সরল করেন, আর দেখান যে প্রতিটি সরলীকরণে হিসাব করার ক্ষমতা কমে না। শেষে যা থাকে, তা-ই Turing machine. নিচের stepper সেই যুক্তির পাঁচটি ধাপ দেখায়।

  1. কাগজ → ফিতাএক মাত্রাঘরে ভাগ করা
  2. সসীম চিহ্নΓপ্রতি ঘরে একটি
  3. সসীম মনের অবস্থাQstate
  4. সীমিত দৃষ্টিheadএকবারে এক ঘর
  5. স্থানীয় পরিবর্তনδলেখা, এক ঘর সরা
  1. কাগজ থেকে ফিতা। স্কুলের খাতায় হিসাব হয় দুই মাত্রায়, ঘরকাটা পাতায়। Turing বলেন, দুই মাত্রা জরুরি নয়: সারিগুলো পাশাপাশি জুড়ে দিলে একটি লম্বা ফিতা পাওয়া যায়, শুধু এক সারি থেকে আরেক সারিতে যেতে বেশি হাঁটতে হয়। হিসাবের ক্ষমতা কমে না, শুধু সময় বাড়ে।
  2. সসীম চিহ্ন। মানুষ সসীম রকমের চিহ্ন লেখেন। অসীম রকম হলে কিছু চিহ্ন একে অপরের এত কাছাকাছি হতো যে চোখে আলাদা করা যেত না। বড় সংখ্যা বা লম্বা শব্দ কয়েকটি ঘরে ভেঙে লেখা যায়। তাই প্রতি ঘরে একটি চিহ্ন, চিহ্নের set Γ সসীম।
  3. সসীম মনের অবস্থা। হিসাবের মাঝখানে মানুষের মাথায় থাকে “এখন কোন ধাপে আছি”। Turing যুক্তি দেন, এমন আলাদা আলাদা অবস্থার সংখ্যাও সসীম; বেশি কিছু মনে রাখতে হলে সেটি কাগজে লিখে রাখা যায়। এই অবস্থাগুলোই যন্ত্রের state, set Q.
  4. সীমিত দৃষ্টি। একবারে মানুষ সীমিত কয়েকটি ঘর দেখেন। k ঘর একসঙ্গে দেখার কাজ একটি ঘর দেখে k বার সরে আর state-এ মনে রেখে করা যায়। তাই একটি head, একবারে এক ঘর।
  5. স্থানীয় পরিবর্তন। প্রতিটি সরল ধাপে মানুষ একটি দেখা ঘর বদলান, অথবা কাছের ঘরে নজর সরান, আর মনের অবস্থা বদলান। এটিই transition δ(q, a) = (r, b, L/R). ফল: মানুষ-গণকের প্রতিটি নিয়ম-মানা হিসাব এমন যন্ত্রে নকল করা যায়। এটি গাণিতিক প্রমাণ নয়, কারণ শুরুর বিন্দু “মানুষ কী করতে পারেন” একটি অনানুষ্ঠানিক বর্ণনা; কিন্তু প্রতিটি ধাপ আলাদাভাবে যাচাই করা যায়।

যন্ত্রটির formal সংজ্ঞা, M = (Q, Σ, Γ, δ, q0, qaccept, qreject), configuration u q v আর তিন রকম পরিণতি (accept, reject, loop) পর্ব ৪৩-এ বিস্তারিত এসেছে; multi-tape আর nondeterministic রূপ যে একই ক্ষমতার, তা পর্ব ৪৫ আর ৪৬-এ। এই robustness, অর্থাৎ মডেল বদলালেও ক্ষমতা না বদলানো, thesis-এর পক্ষে একটি বড় সাক্ষ্য: সংজ্ঞাটি কোনো খেয়ালি বাছাইয়ের ফল নয়।

৪ · এক শ্রেণি, অনেক মডেল — সমতার theorem

১৯৩০-এর দশকের সংজ্ঞাগুলো দেখতে একেবারে আলাদা। একটি ফাংশন বানানো আর প্রয়োগের নিয়ম, একটি সমীকরণের পদ্ধতি, একটি ফিতা-ওয়ালা যন্ত্র, একটি string-বদলের নিয়মের পদ্ধতি। পরে আরও মডেল এসেছে। নিচের সারণিতে প্রধানগুলো:

মডেলমূল ধারণাকে, কবে
λ-calculusশুধু ফাংশন বানানো (λx.…) আর প্রয়োগ; সংখ্যাও ফাংশন দিয়ে লেখাChurch, ১৯৩০-এর দশক
μ-recursive functionশূন্য, পরের সংখ্যা আর projection থেকে শুরু; composition, primitive recursion আর “সবচেয়ে ছোট y খোঁজা” (μ) দিয়ে নতুন ফাংশনGödel, Herbrand, Kleene; ১৯৩৪–৩৬
Turing machineফিতা, head, সসীম state; প্রতি ধাপে পড়া, লেখা, এক ঘর সরাTuring, ১৯৩৬
Post systemString-এর ওপর rewriting নিয়ম; Post-এর ১৯৩৬ সালের কর্মী-মডেল আর পরের canonical systemPost, ১৯৩৬ ও ১৯৪৩
Register machineকয়েকটি register, প্রতিটিতে একটি অঋণাত্মক পূর্ণসংখ্যা; নির্দেশ শুধু “বাড়াও” আর “কমাও, শূন্য হলে লাফ”Minsky, Shepherdson–Sturgis; ১৯৬০-এর দশক
Python, C, Java…সাধারণ programming language, অসীম মেমরি ধরে নিলেআধুনিক

বিস্ময়কর ঘটনা হলো, এরা সবাই ঠিক একই ফাংশনগুলো গণনা করে। এটি thesis নয়, এটি প্রমাণিত theorem. Thesis-এর অংশটুকু হলো এই সাধারণ শ্রেণিকে “algorithm দিয়ে যা গণনা করা যায়”-এর সঙ্গে মেলানো। নিচের ছবিতে দুটি অংশ আলাদা করে দেখানো হয়েছে।

কোনটি প্রমাণিত, কোনটি thesis

ভরাট তীর মানে গাণিতিক প্রমাণ আছে; ভাঙা তীর মানে দাবিটি একটি thesis, প্রমাণ নয়।

Proven equivalences versus the Church–Turing thesis “কার্যকরভাবে গণনাযোগ্য” (অনানুষ্ঠানিক ধারণা) thesis: প্রমাণ নয় Turing-computable ফাংশন প্রমাণিত সমতা Turing machineλ-calculus μ-recursive ফাংশনPost system Register machinePython, C, Java Turing ১৯৩৬Church ১৯৩৬ Gödel, KleenePost ১৯৩৬, ১৯৪৩ ১৯৬০-এর দশকঅসীম মেমরি ধরে
ছবি ৪৭.১ — নিচের ফ্রেমের ছয়টি মডেল একে অপরকে নকল করতে পারে, তা প্রমাণিত। ওপরের ভাঙা তীরটিই Church–Turing thesis.
সংজ্ঞা ৪.১ (Turing-computable partial function)

একটি partial function f: ℕk ⇀ ℕ (কিছু input-এ মান না-ও থাকতে পারে) Turing-computable, যদি এমন একটি Turing machine M থাকে যাকে (x1, …, xk)-এর একটি নির্দিষ্ট encoding দিলে: f(x1, …, xk) সংজ্ঞায়িত হলে M থামে আর tape-এ f-এর মানের encoding রেখে যায়; সংজ্ঞায়িত না হলে M কখনো থামে না। Encoding unary (1n) বা binary, যেকোনো যুক্তিসংগত রীতি চলে (পর্ব ০৫).

Theorem ৪.২ (মডেলগুলোর সমতা)

ℕk ⇀ ℕ ধরনের একটি partial function f-এর জন্য নিচের শর্তগুলো সমতুল্য: (ক) f Turing-computable; (খ) f λ-definable; (গ) f μ-recursive (partial recursive); (ঘ) f কোনো register machine-এ গণনাযোগ্য।

প্রমাণের রূপরেখা। সমতা দেখানো হয় simulation-এর একটি চক্র দিয়ে: প্রতিটি মডেল পরেরটিকে নকল করে, শেষটি প্রথমটিকে। প্রতিটি তীর একটি simulation argument: একটি মডেলের প্রতিটি configuration-কে অন্যটির একটি configuration-এ অনুবাদ, আর প্রতিটি ধাপকে কয়েকটি ধাপে।

  1. μ-recursive ⇒ register machine. মৌলিক ফাংশন (শূন্য, পরের সংখ্যা, projection) এক-দুই নির্দেশের program. Composition মানে program জোড়া লাগানো, ফল এক register থেকে আরেকটিতে সরিয়ে। Primitive recursion একটি গোনা loop. μ-operator, অর্থাৎ “সবচেয়ে ছোট y যেখানে g(x, y) = 0”, একটি সীমাহীন loop: y = 0, 1, 2, …; এমন y না থাকলে loop চিরকাল চলে, যা partial function-এর ঠিক আচরণ।
  2. Register machine ⇒ Turing machine. Register r1, …, rm-এর মান tape-এ লেখা হয় 1r1#1r2#…; program-এর নির্দেশ নম্বর থাকে TM-এর state-এ। “বাড়াও” মানে সঠিক block-এ একটি 1 ঢোকানো (ডানের অংশ এক ঘর সরিয়ে), “কমাও” মানে একটি 1 সরানো, “শূন্য কি না” মানে block-টি ফাঁকা কি না দেখা। প্রতিটির জন্য একটি সসীম TM subroutine.
  3. Turing machine ⇒ μ-recursive. TM-এর configuration u q v-কে একটি সংখ্যা দিয়ে encode করুন (Gödel numbering). এক ধাপ ⊢ সংখ্যার ওপর একটি primitive recursive ফাংশন, কারণ এটি শুধু head-এর আশেপাশের কয়েকটি অঙ্ক বদলায়; t ধাপ পরের configuration primitive recursion দিয়ে। তারপর μ দিয়ে খুঁজুন সবচেয়ে ছোট t, যেখানে configuration থেমে যাওয়া state-এ; সেখান থেকে ফল পড়ুন।
  4. λ-definable ⇔ μ-recursive. Church numeral দিয়ে সংখ্যা লিখে প্রতিটি μ-recursive গঠন λ-তে লেখা যায় (μ-এর জন্য fixed-point combinator), আর উল্টো দিকে λ-term-কে সংখ্যা দিয়ে encode করে β-reduction নকল করা যায়। এই অংশের বিস্তারিত এখানে বাদ রাখা হলো; Kleene-এর Introduction to Metamathematics (১৯৫২)-এ আছে, আর λ-calculus নিজে আসবে পর্ব ৪৯-এ।

চক্রটি বন্ধ হলো: (গ) ⇒ (ঘ) ⇒ (ক) ⇒ (গ), আর (খ) ⇔ (গ). ∎ (রূপরেখা; register machine-এর অংশের পূর্ণ রূপ Minsky-র Computation: Finite and Infinite Machines (১৯৬৭)-এ পাবেন।)

Programming language কেন একই শ্রেণিতে? এক দিকে, Python-এ একটি TM simulator লেখা যায় (এই পর্বেই লিখবেন), তাই TM যা পারে Python-ও পারে। অন্য দিকে, Python interpreter নিজে একটি algorithm, যা নীতিগতভাবে একটি TM-এ নকল করা যায় (পর্ব ৪৮-এর universal machine-এর ধারণা)। একটিই শর্ত: মেমরি যত দরকার তত। এমন ব্যবস্থাকে বলে Turing-complete. পর্ব ৩২-এ দেখেছেন, দুটি stack-ই যথেষ্ট; এক stack-এ নয়।

৫ · তিন মডেল, এক উত্তর — gcd(12, 18)

Theorem-টি এবার হাতে-কলমে দেখা যাক। একটি ফাংশন নিন, gcd(x, y), যেখানে x, y ≥ 1, আর বিয়োগের রূপের Euclid: যতক্ষণ x ≠ y, বড়টি থেকে ছোটটি বিয়োগ করুন। একই পদ্ধতি লেখা হবে তিন মডেলে। প্রথম ব্লকে একটি Turing machine simulator (প্রতিটি run-এ ধাপের সীমা, অর্থাৎ step cap, ১,০০,০০০) আর gcd-এর একটি TM. Tape-এর রূপ $1x#1y; $ বাঁ প্রান্তের চিহ্ন, যাতে যন্ত্র শুরুতে ফিরতে পারে। কৌশল: zig-zag করে বাঁয়ের একটি 1-কে A আর ডানের একটি 1-কে B বানান; যে দিক আগে ফুরায় সেটি ছোট সংখ্যা। তারপর বড় দিকের চিহ্নিত ঘরগুলো X (ফাঁকা হিসেবে গণ্য) আর ছোট দিকের চিহ্ন আবার 1. এক রাউন্ডে (x, y) থেকে (x, y − x) বা (x − y, y). দুই দিক একসঙ্গে ফুরালে x = y: উত্তর বাঁয়ের 1-গুলোর সংখ্যা।

B = "_"                                        # blank cell
def run_tm(d, tape, q="s", cap=100_000):
    t, h, n = list(tape), 0, 0
    while q != "acc":
        if n == cap: return None, n             # step cap: stop, no answer
        a = t[h] if h < len(t) else B
        if (q, a) not in d: return None, n      # no rule: reject
        q, w, m = d[(q, a)]
        if h == len(t): t.append(B)
        t[h] = w; n += 1
        h = h + 1 if m == "R" else max(h - 1, 0)  # cell 0: L stays put
    return "".join(t), n
def rules(spec):             # "q syms>r write move";  "=" keeps the symbol
    d = {}
    for rule in spec.split(";"):
        lhs, rhs = rule.split(">"); q, syms = lhs.split(); r, w, m = rhs.split()
        for a in syms: d[(q, a)] = (r, a if w == "=" else w, m)
    return d
GCD = rules("""s $>hash = R; hash 1AX>hash = R; hash #>findL = L;
 findL AX>findL = L; findL 1>goR A R; findL $>leftDone = R;
 goR 1AX>goR = R; goR #>findR = R; findR BX>findR = R;
 findR 1>back B L; findR _>rDone = L; back 1BX>back = L; back #>findL = L;
 leftDone AX>leftDone = R; leftDone #>checkR = R; checkR BX>checkR = R;
 checkR 1>cleanR = L; checkR _>finR = L; cleanR B>cleanR X L;
 cleanR X>cleanR = L; cleanR #>restL = L; restL A>restL 1 L;
 restL 1X>restL = L; restL $>hash = R; finR B>finR X L; finR X>finR = L;
 finR #>finL = L; finL A>finL 1 L; finL 1X>finL = L; finL $>acc = R;
 rDone B>rDone 1 L; rDone X>rDone = L; rDone #>un1 = L; un1 X>un1 = L;
 un1 A>rdL 1 L; rdL A>rdL X L; rdL 1X>rdL = L; rdL $>hash = R""")
def tm_gcd(a, b):            # input $1^a#1^b, answer = number of 1s left
    out, n = run_tm(GCD, "$" + "1" * a + "#" + "1" * b)
    return (out.count("1") if out else None), n
for a, b in [(12, 18), (20, 8), (5, 5), (3, 0)]:
    print(f"gcd({a}, {b}) -> {tm_gcd(a, b)}   (answer, steps)")
print(len(GCD), "rules;", run_tm(GCD, "$" + "1" * 12 + "#" + "1" * 18)[0])

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

gcd(12, 18) -> (6, 1075)   (answer, steps)
gcd(20, 8) -> (4, 1073)   (answer, steps)
gcd(5, 5) -> (5, 97)   (answer, steps)
gcd(3, 0) -> (None, 100000)   (answer, steps)
51 rules; $11111XXXXXX1#XXXXXXXXXXXXXXXXXX_

৫১টি নিয়মের (state, চিহ্ন) জোড়ার যন্ত্রটি gcd(12, 18) = 6 দিতে ১,০৭৫টি ধাপ নেয়। শেষের tape-এ বাঁ দিকে ঠিক ছয়টি 1, মাঝে মাঝে X; ডান দিকে সব X. gcd(3, 0) যন্ত্রের পূর্বশর্ত (x, y ≥ 1) ভাঙে: ডান দিক প্রথম থেকেই ফাঁকা, তাই প্রতি রাউন্ডে একই অবস্থায় ফিরে আসে আর যন্ত্র চিরকাল চলে। Simulator ১,০০,০০০ ধাপে থেমে None দেয়। মনে রাখুন, step cap শুধু আমাদের simulator-এর নিরাপত্তা; TM-এর সংজ্ঞায় এমন কোনো সীমা নেই, আর “চিরকাল চলবে কি না” আগে থেকে বলার সাধারণ পদ্ধতি নেই (halting problem, পর্ব ৫১)।

এবার একই কাজ একটি register machine-এ। নির্দেশ দুই রকম: ("inc", r, পরের নির্দেশ) আর ("dec", r, শূন্য-না-হলে পরের, শূন্য-হলে পরের)। Program-এর বাইরে লাফ মানে থামা। পরের ব্লক আগের ব্লকের namespace ব্যবহার করে আর তিন মডেলকে x, y ∈ {1, …, 10}-এর ১০০টি জোড়ায় Python-এর math.gcd-এর সঙ্গে মেলায়।

from math import gcd
# Register machine: ("inc", r, next) or ("dec", r, next_if_positive, next_if_zero)
RM = [("dec", "a", 1, 3), ("dec", "b", 2, 9), ("inc", "t", 0),    # 0-2 lockstep
      ("dec", "b", 4, 7), ("inc", "b", 5),                          # 3-4 a ran out
      ("dec", "t", 6, 0), ("inc", "a", 5),                          # 5-6 a := t
      ("dec", "t", 8, 12), ("inc", "a", 7),                         # 7-8 equal: done
      ("inc", "a", 10), ("dec", "t", 11, 0), ("inc", "b", 10)]      # 9-11 b := t
def rm_run(prog, regs, cap=100_000):
    r, pc, n = dict(regs), 0, 0
    while pc < len(prog):                       # jumping past the end = halt
        if n == cap: return None, n
        op = prog[pc]; n += 1
        if op[0] == "inc": r[op[1]] += 1; pc = op[2]
        elif r[op[1]] > 0: r[op[1]] -= 1; pc = op[2]
        else: pc = op[3]
    return r, n
def rm_gcd(a, b):
    r, n = rm_run(RM, {"a": a, "b": b, "t": 0})
    return r["a"], n
def py_gcd(x, y):                               # the same idea, in Python
    while x != y:
        if x > y: x -= y
        else: y -= x
    return x
print("gcd(12, 18):", tm_gcd(12, 18), rm_gcd(12, 18), py_gcd(12, 18))
pairs = [(a, b) for a in range(1, 11) for b in range(1, 11)]
agree = sum(tm_gcd(a, b)[0] == rm_gcd(a, b)[0] == py_gcd(a, b) == gcd(a, b)
            for a, b in pairs)
print(f"{agree} of {len(pairs)} pairs agree (TM, register machine, Python, math.gcd)")
print("max steps: TM", max(tm_gcd(a, b)[1] for a, b in pairs),
      " RM", max(rm_gcd(a, b)[1] for a, b in pairs))

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

gcd(12, 18): (6, 1075) (6, 131) 6
100 of 100 pairs agree (TM, register machine, Python, math.gcd)
max steps: TM 925  RM 129

তিনটি মডেল, চারটি হিসাব, ১০০টি জোড়ার প্রতিটিতে একই উত্তর। ধাপের সংখ্যা কিন্তু খুব আলাদা: gcd(12, 18)-এ TM ১,০৭৫ ধাপ, register machine ১৩১ ধাপ, আর Python loop মাত্র দুটি পুনরাবৃত্তি। কী গণনা করা যায়, তাতে মডেলগুলো সমান; কত দ্রুত, তাতে নয়। এই পার্থক্যই অংশ ৭-এর extended thesis-এর বিষয়। আর এটি একটি পরীক্ষা, প্রমাণ নয়: ১০০টি জোড়ায় মিল দেখায় যে আমাদের তিনটি program সম্ভবত ঠিক, কিন্তু theorem ৪.২-এর প্রমাণ আসে simulation-এর সাধারণ যুক্তি থেকে।

একটি Python loop কীভাবে নিচের স্তরের ধাপে ভাঙে, পরের stepper তা দেখায়। বাঁয়ে Python-এর লাইন, ডানে register machine আর TM-এ সেই লাইনের কাজ।

1def gcd(x, y):  # x, y ≥ 12    while x != y:3        if x > y:4            x = x - y5        else:6            y = y - x7    return x
একই লাইন, নিচের স্তরে
Register machine
Turing machine
  1. Input. Python-এ দুটি variable. Register machine-এ দুটি register, সঙ্গে একটি সাহায্যকারী t. TM-এ দুটি unary block, মাঝে #, শুরুতে $.
  2. তুলনা। “x != y” আর “x > y” নিচের স্তরে আলাদা কোনো নির্দেশ নয়। দুটি সংখ্যা একসঙ্গে একটি একটি করে কমানো হয়; কোনটি আগে ফুরায়, তা-ই তুলনার ফল। Register machine-এ t গোনে কতগুলো জোড়া গেল; TM-এ গোনার কাজ করে A আর B চিহ্ন।
  3. y = y − x. x আগে ফুরালে বড় দিকে ঠিক y − x বাকি। Register machine-এ b-তে সেটিই আছে; a-কে t থেকে আবার ভরা হয়। TM-এ ডানের চিহ্নিত ঘরগুলো X হয়ে যায় (গোনা থেকে বাদ), বাঁয়ের A আবার 1.
  4. x = x − y. উল্টো ক্ষেত্র। একটি সূক্ষ্মতা: register machine-এ a একবার বেশি কমেছিল, নির্দেশ 9 তা ফেরত দেয়। TM-এ শেষ A-টির কোনো জোড়া ছিল না, তাই একটি A আবার 1 হয়, বাকিগুলো X.
  5. সমান। দুই দিক একসঙ্গে ফুরানো মানে x = y; Python-এর while শর্ত মিথ্যা।
  6. Return. এক লাইনের “return x” নিচের স্তরে কয়েক ডজন বা কয়েকশো ধাপ। একটি উচ্চ-স্তরের লাইন = সসীম সংখ্যক নিচের ধাপ: compiler আর interpreter ঠিক এই অনুবাদ করে, আর এই কারণেই পর্ব ৫০ থেকে আমরা TM-কে উচ্চ স্তরের ভাষায় বর্ণনা করলেও কিছু হারাই না।

এবার সংখ্যাগুলো। নিচের stepper প্রতিটি রাউন্ড শেষে তিন মডেলের অবস্থা দেখায়; সংখ্যাগুলো উপরের দুই ব্লকের simulator থেকে নেওয়া (X12 মানে পরপর ১২টি X).

1শুরু2রাউন্ড ১: y = y − x3রাউন্ড ২: x = x − y4রাউন্ড ৩: x = y, থামা5১০০টি জোড়ায় যাচাই
রাউন্ড শেষে
Python (x, y)
RM (a, b, t)
RM মোট ধাপ
TM tape
TM মোট ধাপ
  1. শুরু। একই input তিন রূপে: দুটি Python variable, দুটি register, আর tape-এ বারোটি আর আঠারোটি 1.
  2. রাউন্ড ১. 12 < 18, তাই y থেকে 12 বিয়োগ: (12, 6). Register machine-এ এ পর্যন্ত ৬৪ ধাপ, TM-এ ৩৯১ ধাপ। TM-এর ডান দিকে ১২টি ঘর এখন X; গোনা হয় শুধু 1.
  3. রাউন্ড ২. 12 > 6, তাই x থেকে 6 বিয়োগ: (6, 6). TM-এর বাঁ দিকে 1⁵ X⁶ 1, অর্থাৎ মোট ছয়টি 1; কোন ঘরে আছে তাতে কিছু আসে যায় না, unary-তে শুধু সংখ্যা গুরুত্বপূর্ণ।
  4. রাউন্ড ৩. দুই দিক একসঙ্গে ফুরায়: x = y = 6. Register machine ১৩১ ধাপে থামে, a = 6 (b আর t শূন্য)। TM ১,০৭৫ ধাপে accept করে, বাঁয়ে ছয়টি 1. Python দুই রাউন্ডেই while থেকে বের হয়েছে।
  5. যাচাই। দ্বিতীয় ব্লক ১০০টি জোড়ায় চারটি হিসাব মিলিয়েছে, সব মিলেছে। ১ থেকে ১০-এর জোড়ায় সবচেয়ে বেশি ধাপ TM-এ ৯২৫, register machine-এ ১২৯।

৬ · Thesis-এর বক্তব্য, মর্যাদা আর সাক্ষ্য

Church–Turing thesis

প্রতিটি effectively calculable (কোনো স্পষ্ট, যান্ত্রিক, বুদ্ধি-নিরপেক্ষ পদ্ধতিতে গণনাযোগ্য) partial function f: ℕk ⇀ ℕ Turing-computable. Language-এর ভাষায়: কোনো algorithm দিয়ে যে language-এর সদস্যতা সব input-এ নির্ণয় করা যায়, সেটি একটি decidable language, অর্থাৎ তার জন্য সব input-এ থামা একটি TM আছে।

উল্টো দিক, “প্রতিটি Turing-computable ফাংশন effectively calculable”, নিয়ে কোনো বিতর্ক নেই: একটি TM-এর নিয়ম মেনে চলা নিজেই একটি যান্ত্রিক পদ্ধতি। তাই Church–Turing thesis আসলে বলে দুটি ধারণা একই: অনানুষ্ঠানিক “algorithm” আর গাণিতিক “Turing machine”.

কেন এটি theorem নয়

একটি theorem প্রমাণ করতে হলে দুই পাশের বস্তু গাণিতিকভাবে সংজ্ঞায়িত হতে হয়। এখানে এক পাশ, “effectively calculable”, মানুষের অভিজ্ঞতা থেকে আসা একটি ধারণা। এর সঙ্গে একটি গাণিতিক সংজ্ঞা মেলানো যায় যুক্তি আর সাক্ষ্য দিয়ে, প্রমাণ দিয়ে নয়। পদার্থবিজ্ঞানের একটি সূত্রের সঙ্গে তুলনা করুন: সূত্রটি গণিতে লেখা, কিন্তু সেটি প্রকৃতির সঙ্গে মেলে কি না, তা প্রমাণ নয়, পর্যবেক্ষণের বিষয়। তেমনি thesis-টিকে মিথ্যা প্রমাণ করা নীতিগতভাবে সম্ভব: কেউ এমন একটি পদ্ধতি দেখালেন যা সবাই “যান্ত্রিক” বলে মানেন, অথচ যা কোনো TM করতে পারে না। ৯০ বছরে এমন কিছু পাওয়া যায়নি।

পক্ষের চারটি সাক্ষ্য

  1. স্বাধীন সংজ্ঞাগুলোর মিল: ভিন্ন দর্শন থেকে আসা অন্তত ছয়টি সংজ্ঞা একই শ্রেণি দেয় (theorem ৪.২)। একটি খেয়ালি সংজ্ঞায় এমন হওয়া খুব অস্বাভাবিক।
  2. Turing-এর বিশ্লেষণ: মানুষ-গণকের প্রতিটি ক্ষমতা ধাপে ধাপে যন্ত্রে নামানো যায় (অংশ ৩)।
  3. Robustness: TM-কে বেশি tape, দুই দিকে অসীম tape, nondeterminism বা random access দিলেও নতুন ফাংশন আসে না (পর্ব ৪৫–৪৬)।
  4. অভিজ্ঞতা: আজ পর্যন্ত লেখা প্রতিটি algorithm আর প্রতিটি programming language-এর program একটি TM-এ নকল করা যায়।

প্রমাণে thesis-এর ব্যবহার, আর ভুল পড়া

Thesis-এর একটি ব্যবহারিক কাজ আছে। পর্ব ৫০ থেকে আমরা TM-কে বর্ণনা করব উচ্চ স্তরের ভাষায়: “M = ‘input ⟨G⟩-এ: G-এর প্রতিটি vertex ঘুরে দেখুন…’”. প্রতিটি নিয়ম লিখে দেখানোর বদলে আমরা ধরে নিই যে যেকোনো স্পষ্ট algorithm একটি TM-এ রূপ দেওয়া যায়। কঠোর অর্থে এটি thesis নয়, theorem ৪.২-এর সাধারণ অভিজ্ঞতা; সন্দেহ হলে সব সময় নিচের স্তরে নামা যায়, যেমন অংশ ৫-এ করলেন।

তিনটি প্রচলিত ভুল পড়া এড়িয়ে চলুন। (১) Thesis দক্ষতা নিয়ে কিছু বলে না: TM-এ ১,০৭৫ ধাপ আর Python-এ ২টি পুনরাবৃত্তি দুটিই “গণনাযোগ্য”। (২) Thesis পদার্থবিজ্ঞানের সব প্রক্রিয়া নিয়ে নয়; সেটি আলাদা “physical” রূপ (অংশ ৭)। (৩) Thesis বলে না যে মস্তিষ্ক একটি Turing machine; এটি নিয়ম-মানা হিসাব নিয়ে, মন নিয়ে নয়। দার্শনিক আলোচনায় এই পার্থক্য প্রায়ই হারিয়ে যায়।

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

  • Church–Turing thesis লিখুন। এটি কি প্রমাণিত? Effectively calculable = Turing-computable; প্রমাণযোগ্য নয়, কারণ এক পাশ অনানুষ্ঠানিক।
  • λ-calculus আর TM-এর সমতা কি thesis? না, এটি প্রমাণিত theorem (Turing ১৯৩৭).
  • Thesis-এর পক্ষে সাক্ষ্য কী? স্বাধীন মডেলগুলোর সমতা, Turing-এর বিশ্লেষণ, variant-এর robustness, কোনো পাল্টা-উদাহরণ নেই।
  • Quantum computer কি thesis ভাঙে? না; নতুন ফাংশন গণনা করে না। শুধু extended (দক্ষতার) রূপকে চ্যালেঞ্জ করতে পারে।
  • Turing-complete মানে কী? অসীম মেমরি ধরে যেকোনো TM নকল করতে পারে; সাধারণত একটি জানা Turing-complete মডেল নকল করে প্রমাণ করা হয়।

৭ · Extended thesis, quantum computer আর পদার্থবিজ্ঞানের সীমা

অংশ ৫-এ দেখলেন, মডেলগুলো একই ফাংশন গণনা করে কিন্তু ভিন্ন গতিতে। গতির পার্থক্য কত বড় হতে পারে? এর উত্তরে একটি শক্ত দাবি আছে:

Extended (strong) Church–Turing thesis

যেকোনো “যুক্তিসংগত”, বাস্তবে গড়া যায় এমন গণনার মডেল একটি probabilistic Turing machine দিয়ে polynomial বাড়তি সময়ে নকল করা যায়: মূল মডেলে t ধাপ লাগলে TM-এ বড়জোর tc-এর মতো ধাপ, কোনো স্থির c-এর জন্য।

Extended thesis-এর পক্ষে সাক্ষ্য: multi-tape TM থেকে single-tape-এ সময় বড়জোর বর্গ হয় (পর্ব ৪৫), random-access মেমরির মডেলও polynomial সময়ে TM-এ নকল হয়। এই কারণেই class P (পর্ব ৫৭) মডেল বদলালে বদলায় না। Nondeterministic TM-এর জানা simulation exponential সময় নেয় (পর্ব ৪৬), কিন্তু nondeterminism বাস্তবে গড়া যায় এমন যন্ত্র নয়, তাই এটি দাবির বিরুদ্ধে যায় না। “Probabilistic” শব্দটি আছে, কারণ random বিট ব্যবহার করা যন্ত্র বাস্তবে গড়া যায়; এতে বাড়তি শক্তি আসে কি না (P বনাম BPP), তা খোলা প্রশ্ন।

এখানে quantum computer আসে। ১৯৯৪ সালে Peter Shor একটি quantum algorithm দেন (Shor-এর algorithm), যা একটি বড় সংখ্যার মৌলিক উৎপাদক polynomial সময়ে বের করে। Classical যন্ত্রে, random বিটসহ, এমন কোনো polynomial algorithm জানা নেই। তাই যদি (ক) বড়, নির্ভুল quantum কম্পিউটার গড়া যায়, আর (খ) factoring সত্যিই কোনো classical polynomial algorithm-এ না হয়, তবে extended thesis মিথ্যা। দুটি শর্তই এখনো অনিশ্চিত: (খ) প্রমাণিত নয়, আর এমন যন্ত্রের প্রকৌশল এখনো চলছে। বিস্তারিত পর্ব ৭৫-এ।

কিন্তু মূল Church–Turing thesis-এর ক্ষেত্রে quantum computer কোনো হুমকি নয়। একটি quantum যন্ত্রের অবস্থা হলো সসীম সংখ্যক complex সংখ্যার একটি তালিকা (amplitude), আর প্রতিটি ধাপ একটি matrix গুণ। একটি classical TM এই সংখ্যাগুলো যথেষ্ট নির্ভুলভাবে হিসাব করে quantum যন্ত্রটিকে নকল করতে পারে, যদিও n qubit-এর জন্য তালিকাটি 2n লম্বা, তাই সময় exponential হতে পারে। ফল: quantum যন্ত্র যা গণনা করে, TM-ও তা গণনা করে; প্রশ্ন শুধু গতির। Halting problem quantum কম্পিউটারেও undecidable.

Physical Church–Turing thesis

আরও বড় দাবি: প্রকৃতির কোনো প্রক্রিয়া এমন ফাংশন গণনা করতে পারে না যা TM পারে না। একে বলে physical Church–Turing thesis. এটি মূল thesis থেকে আলাদা: মূল thesis নিয়ম-মানা মানুষ নিয়ে, physical রূপ পদার্থবিজ্ঞানের নিয়ম নিয়ে। Robin Gandy ১৯৮০ সালে কিছু স্পষ্ট শর্ত (সসীম গতিতে তথ্য চলা, প্রতিটি অংশে সসীম তথ্য) মানা “যন্ত্র” নিয়ে দেখান যে তারা TM-এর বেশি পারে না; David Deutsch ১৯৮৫ সালে quantum পদার্থবিজ্ঞানের দৃষ্টিকোণ থেকে একটি “Church–Turing principle” প্রস্তাব করেন। এর বাইরে কিছু তাত্ত্বিক প্রস্তাব আছে, যাকে বলে hypercomputation: অসীম নির্ভুল বাস্তব সংখ্যা ধরে রাখা analog যন্ত্র, প্রতি ধাপে আগের ধাপের অর্ধেক সময় নেওয়া যন্ত্র, বা সাধারণ আপেক্ষিকতার বিশেষ spacetime ব্যবহার। এদের কোনোটি বাস্তবে গড়া যায় বলে কোনো সাক্ষ্য নেই; পদার্থবিজ্ঞানের কিছু যুক্তি (যেমন Bekenstein bound নামে পরিচিত সীমা) বলে, একটি সীমিত জায়গা আর শক্তিতে শুধু সসীম তথ্য রাখা যায়।

রূপদাবিঅবস্থা
মূল thesisAlgorithm = TM (কী গণনা করা যায়)সর্বজনগ্রাহ্য; প্রমাণযোগ্য নয়
Extendedবাস্তব মডেল ↔ probabilistic TM, polynomial খরচেQuantum computing-এর কারণে সন্দেহে; অমীমাংসিত
Physicalপ্রকৃতির কোনো প্রক্রিয়া TM-এর বাইরে গণনা করে নাপদার্থবিজ্ঞানের প্রশ্ন; বিপক্ষে বাস্তব সাক্ষ্য নেই

আরও গভীরে: কেউ কেউ thesis-কে “প্রমাণ” করার চেষ্টা করেছেন: algorithm-এর জন্য কয়েকটি স্পষ্ট axiom লিখে (যেমন প্রতিটি ধাপ সীমিত অংশ বদলায়, অবস্থা একটি গাণিতিক structure) দেখানো যে এগুলো মানা যেকোনো পদ্ধতি TM-এ নকল হয়; Wilfried Sieg-এর কাজ আর Nachum Dershowitz ও Yuri Gurevich-এর ২০০৮ সালের প্রবন্ধ এর পরিচিত উদাহরণ। এতে প্রশ্নটি সরে যায় “axiom-গুলো কি algorithm-এর সব ধারণা ধরে?”-তে, যা আবার অনানুষ্ঠানিক। জটিলতার দিকে, Cobham ও Edmonds-এর ১৯৬৫ সালের প্রস্তাব (“দক্ষ = polynomial সময়”) একটি দ্বিতীয় thesis, যার ওপর P-এর পুরো তত্ত্ব দাঁড়ায়; DSA কোর্সের পর্ব ৬৪-এ algorithm-এর দিক থেকে এর ছবি আছে।

৮ · Turing completeness — অপ্রত্যাশিত জায়গায়, আর ইচ্ছা করে এড়ানো

একটি ব্যবস্থা (ভাষা, যন্ত্র, নিয়মের খেলা) Turing-complete, যদি অসীম মেমরি ধরে নিলে সেটি যেকোনো Turing machine নকল করতে পারে। প্রমাণের প্রচলিত পথ: সরাসরি TM নয়, একটি জানা Turing-complete মডেল, যেমন দুই-counter register machine বা একটি tag system, নকল করে দেখানো। নিচে একটি খুব ছোট “tiny tape language”: একটি সারি ঘর, প্রতি ঘরে একটি অঋণাত্মক পূর্ণসংখ্যা, একটি pointer, আর মাত্র সাতটি নির্দেশ। + ঘর বাড়ায়, − কমায় (শূন্যের নিচে নয়), > আর < pointer সরায়, [ … ] হলো “ঘর শূন্য না হওয়া পর্যন্ত চালাও”, আর . ঘরের সংখ্যাটি ছাপে। Interpreter-এ step cap ১,০০,০০০।

// tiny tape language: + - < > [ ] .   (each cell holds a whole number >= 0)
function run(prog, cap = 100000) {
  const tape = [0], out = [], jump = {}, open = [];
  for (let i = 0; i < prog.length; i++) {       // pair up the brackets first
    if (prog[i] === "[") open.push(i);
    if (prog[i] === "]") { const j = open.pop(); jump[i] = j; jump[j] = i; }
  }
  let pc = 0, h = 0, steps = 0;
  while (pc < prog.length) {
    if (steps === cap) return `step cap hit (${cap}), output [${out}]`;
    const c = prog[pc]; steps++;
    if (c === "+") tape[h]++;
    else if (c === "-") tape[h] = Math.max(0, tape[h] - 1);
    else if (c === ">") { h++; if (h === tape.length) tape.push(0); }
    else if (c === "<") h = Math.max(0, h - 1);   // never left of cell 0
    else if (c === ".") out.push(tape[h]);        // print the number
    else if (c === "[" && tape[h] === 0) pc = jump[pc];
    else if (c === "]" && tape[h] !== 0) pc = jump[pc];
    pc++;
  }
  return `halted after ${steps} steps, output [${out}]`;
}
console.log("3 + 5     :", run("+++>+++++[-<+>]<."));
console.log("4 x 6     :", run("++++[>++++++<-]>."));
console.log("countdown :", run("+++++[.-]"));
console.log("forever   :", run("+[]"));

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

3 + 5     : halted after 37 steps, output [8]
4 x 6     : halted after 47 steps, output [24]
countdown : halted after 21 steps, output [5,4,3,2,1]
forever   : step cap hit (100000), output []

প্রথম program ঘর ০-তে 3, ঘর ১-এ 5 রাখে, তারপর loop-এ ঘর ১ থেকে একটি করে ঘর ০-তে সরায়: যোগফল 8. দ্বিতীয়টি ঘর ০-এর প্রতিটি এককের জন্য ঘর ১-এ ছয় যোগ করে: 24. তৃতীয়টি 5 থেকে নিচে ছাপে। চতুর্থটি, “+[]”, ঘরে 1 রেখে এমন loop-এ ঢোকে যা ঘরটি কখনো বদলায় না; interpreter ১,০০,০০০ ধাপে নিজেকে থামায়। এই সীমা ছাড়া পাতা আটকে যেত, আর সাধারণভাবে আগে থেকে বলা যায় না কোন program থামবে।

কেন এই ছোট ভাষা Turing-complete (প্রমাণের রূপরেখা): প্রতিটি register একটি ঘর। “inc r” মানে pointer r-এ নিয়ে +, “dec r, শূন্য হলে লাফ” মানে − আর [ ] দিয়ে শূন্য-পরীক্ষা। Register machine-এর যথেচ্ছ লাফ (goto) সরাসরি নেই, কিন্তু একটি ঘরে “এখন কোন নির্দেশ” সংখ্যাটি রেখে একটি বড় loop-এর ভেতরে প্রতিটি নির্দেশের জন্য একটি “এই নম্বর হলে চালাও” অংশ লিখে goto নকল করা যায় (Böhm–Jacopini ধাঁচের structured program-এর যুক্তি)। তিন register-এর machine Turing-complete (Minsky দেখান, দুটি counter-ও যথেষ্ট; পর্ব ৪৯), তাই এই ভাষাও, যদি ঘর আর ঘরের মান সীমাহীন হয়। এমন ছোট ভাষার একটি পূর্বসূরি Corrado Böhm-এর ১৯৬৪ সালের P′′ বলে পরিচিত।

অপ্রত্যাশিত জায়গায়, সতর্কতাসহ

অনেক ব্যবস্থা, যা “গণনার জন্য” বানানো হয়নি, Turing-complete বলে দেখানো হয়েছে বা দাবি করা হয়েছে। প্রতিটি দাবিতে দুটি প্রশ্ন করুন: অসীম মেমরি কোথা থেকে আসে, আর loop কে চালায়?

  • Conway-এর Game of Life (১৯৭০): ঘরের একটি জালি, প্রতিটি ঘর বাঁচে বা মরে প্রতিবেশীর সংখ্যা দেখে। Berlekamp, Conway ও Guy ১৯৮২ সালে universality-র নির্মাণের রূপরেখা দেন; পরে অনেকে জালির ভেতরে পূর্ণ যন্ত্র বানিয়ে দেখিয়েছেন। অসীম জালি ধরে নিতে হয়।
  • Rule 110: এক-মাত্রার একটি cellular automaton; Matthew Cook-এর universality-র প্রমাণ ২০০৪ সালে প্রকাশিত হয় (পর্ব ৪৯)।
  • C++-এর template: compile-এর সময়েই হিসাব চালানো যায়, আর template ব্যবস্থা নীতিগতভাবে Turing-complete বলে দেখানো হয়েছে (Todd Veldhuizen-এর ২০০৩ সালের প্রতিবেদন বহুল উদ্ধৃত); বাস্তবে compiler-গুলো গভীরতার সীমা রাখে।
  • HTML আর CSS: CSS দিয়ে Rule 110-এর ধাপ দেখানোর একটি পরিচিত উদাহরণ আছে, কিন্তু সেখানে প্রতিটি ধাপ চালাতে ব্যবহারকারীকে ক্লিক করতে হয়; loop চালায় মানুষ। তাই অনেকে একে পূর্ণ Turing-complete বলেন না।

ইচ্ছা করে Turing-complete না রাখা

Turing completeness সবসময় গুণ নয়। Turing-complete ভাষার program থামবে কি না, সাধারণভাবে বলা যায় না, আর program-এর আচরণ নিয়ে প্রায় কোনো অ-তুচ্ছ প্রশ্নই সব program-এর জন্য নির্ণয়যোগ্য নয় (Rice-এর theorem, পর্ব ৫৩)। তাই অনেক জায়গায় ভাষা ইচ্ছা করে দুর্বল রাখা হয়: regular expression (পর্ব ১৩) সবসময় থামে; সাধারণ SQL query, recursive অংশ ছাড়া, প্রতিটি সসীম database-এ থামে; অনেক configuration ভাষায় loop নেই; কিছু ব্যবস্থা প্রতিটি program-কে একটি নির্দিষ্ট ধাপের বাজেট দেয়, ঠিক আমাদের step cap-এর মতো। বাজারঘরের coupon-নিয়মের জন্য যদি একটি ছোট ভাষা বানান, তাতে শুধু তুলনা আর সীমিত loop রাখলে প্রতিটি নিয়ম নিশ্চিতভাবে থামবে, আর আপনি নিয়মগুলো স্বয়ংক্রিয়ভাবে পরীক্ষাও করতে পারবেন।

৯ · AI-এর যুগে Church–Turing thesis আর ছোট যন্ত্র

এই বিষয়ে AI assistant-এর ভুল দুই রকম। প্রথমটি ধারণার: thesis-কে “Turing ১৯৩৬ সালে প্রমাণ করেন” বলা, “quantum computer thesis ভেঙেছে” বলা, বা কোনো ব্যবস্থাকে উৎস ছাড়াই Turing-complete বলা। দ্বিতীয়টি নির্মাণের: register machine বা TM-এর program দেখতে ঠিক, কিন্তু একটি register ফেরত ভরতে ভুলে যাওয়া। নিচের ব্লকে “c = a × b”-এর একটি খসড়া (AI-এর উত্তরের ধাঁচে বানানো উদাহরণ) 0 থেকে 6-এর সব জোড়ায় যাচাই করা হয়েছে; ব্লকটি নিজের simulator নিয়ে স্বয়ংসম্পূর্ণ।

def rm_run(prog, regs, cap=10_000):            # ("inc", r, nxt) / ("dec", r, pos, zero)
    r, pc, n = dict(regs), 0, 0
    while pc < len(prog):
        if n == cap: return None                # step cap: treat as "no answer"
        op = prog[pc]; n += 1
        if op[0] == "inc": r[op[1]] += 1; pc = op[2]
        elif r[op[1]] > 0: r[op[1]] -= 1; pc = op[2]
        else: pc = op[3]
    return r
# AI draft: "c = a * b" — inner loop empties b and never refills it
ai = [("dec", "a", 1, 9),                      # 0 outer loop: one round per unit of a
      ("dec", "b", 2, 0),                      # 1 inner loop over b
      ("inc", "c", 1)]                         # 2
# fixed: copy b into t while counting, then pour t back into b
fix = [("dec", "a", 1, 9),
       ("dec", "b", 2, 4), ("inc", "c", 3), ("inc", "t", 1),
       ("dec", "t", 5, 0), ("inc", "b", 4)]
def check(name, prog, n=6):
    bad = []
    for a in range(n + 1):
        for b in range(n + 1):
            r = rm_run(prog, {"a": a, "b": b, "c": 0, "t": 0})
            if r is None or r["c"] != a * b: bad.append((a, b, r and r["c"]))
    print(f"{name}: {len(bad)} wrong of {(n + 1) ** 2}; first: {bad[:3]}")
check("AI draft", ai)
check("fixed   ", fix)

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

AI draft: 30 wrong of 49; first: [(2, 1, 1), (2, 2, 2), (2, 3, 3)]
fixed   : 0 wrong of 49; first: []

খসড়াটি a = 0 বা a = 1 হলে, অথবা b = 0 হলে ঠিক উত্তর দেয়, তাই হাতে দু-একটি উদাহরণে (যেমন 1 × 5) ভুল ধরা পড়ে না। কিন্তু ভেতরের loop প্রথম রাউন্ডেই b খালি করে, পরের রাউন্ডগুলোতে যোগ করার কিছু থাকে না: a ≥ 1 হলে c = b. ভুল ঠিক সেই ৫ × ৬ = ৩০টি জোড়ায়, যেখানে a ≥ 2 আর b ≥ 1. সংশোধিত program b কমানোর সময় t-তে একটি করে জমায়, আর ভেতরের loop শেষে t থেকে b আবার ভরে; ৪৯টি জোড়াতেই ঠিক।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“Church–Turing thesis একটি প্রমাণিত theorem”জিজ্ঞেস করুন: “effectively calculable”-এর গাণিতিক সংজ্ঞা কী? না থাকলে প্রমাণও নেই; প্রমাণিত অংশ শুধু মডেলগুলোর সমতা
“Quantum computer Church–Turing thesis ভেঙে দিয়েছে”Computability আর efficiency আলাদা করুন; quantum শুধু extended রূপকে চ্যালেঞ্জ করে, তাও শর্তসাপেক্ষে
“X Turing-complete” দাবি, উৎস ছাড়াকোন জানা মডেল নকল করা হয়েছে, অসীম মেমরি কোথায়, loop কে চালায়: তিনটি প্রশ্নের উত্তর আর প্রকাশিত উৎস চান
Register বা tape ফেরত না ভরা, পূর্বশর্ত (x, y ≥ 1) ভুলে যাওয়াছোট সব input-এ simulator চালিয়ে গাণিতিক সংজ্ঞার সঙ্গে মেলান; step cap রেখে অসীম loop ধরুন
বানানো সাল বা উক্তি (“Turing ১৯৩৭ সালে thesis নাম দেন”)Sipser, Hopcroft–Motwani–Ullman বা Kleene-এর বইয়ে মিলিয়ে নিন; নিশ্চিত না হলে সাল বাদ দিন

AI-কে কাজে লাগানোর ভালো উপায়: তার কাছ থেকে program-এর সঙ্গে প্রতিটি loop-এর invariant আর একটি পরীক্ষার কোড চাওয়া, যা আপনি নিজে চালাবেন; আর ধারণার প্রশ্নে “কোনটি প্রমাণিত, কোনটি নয়” আলাদা করে চাওয়া।

আমি গণনার তত্ত্ব শিখছি। দুটি কাজ করো। ১. Register machine (নির্দেশ শুধু: inc r; dec r, শূন্য হলে অন্য লাফ) দিয়ে c = a mod b লেখো, যেখানে b ≥ 1; সাহায্যকারী register লাগলে নাম দাও। প্রতিটি loop-এর invariant এক লাইনে বলো, আর শেষে a, b-এর মান কী থাকে বলো। ২. শুধু standard library দিয়ে একটি Python simulator দাও, যা 0 ≤ a ≤ 10, 1 ≤ b ≤ 10-এর সব জোড়ায় program চালিয়ে a % b-এর সঙ্গে মেলায়, ধাপের একটি সীমা রাখে আর অমিলগুলো ছাপে। ৩. তারপর আলাদা করে বলো: Church–Turing thesis-এর কোন অংশ প্রমাণিত theorem, কোন অংশ প্রমাণযোগ্য নয়, আর quantum computing কোন রূপকে চ্যালেঞ্জ করে। ৪. কোনো সাল বা দাবি নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১Church-এর সংজ্ঞা গাণিতিকভাবে নিখুঁত হলেও Gödel প্রথমে রাজি হননি, অথচ Turing-এর বিশ্লেষণ তাঁকে রাজি করায়। দুই ধরনের যুক্তির পার্থক্য কী?

Church-এর প্রস্তাবের মূল যুক্তি ছিল “বিস্তারগত”: λ-definable ফাংশনের শ্রেণি অনেক বড়, পরিচিত সব গণনাযোগ্য ফাংশন এর মধ্যে পড়ে, আর Herbrand–Gödel-এর general recursive শ্রেণির সঙ্গে এটি হুবহু মেলে। এই সাক্ষ্য শক্ত, কিন্তু একটি ফাঁক রেখে যায়। দুটি সংজ্ঞা মিলে গেলে হয়তো দুটিই একই ভুল ধারণা থেকে এসেছে; হয়তো ভবিষ্যতে কেউ এমন পদ্ধতি দেখাবেন যা দুটির বাইরে। পরে প্রকাশিত চিঠিপত্র আর স্মৃতিচারণ অনুযায়ী, Gödel ১৯৩৪–৩৫ সালে Church-এর প্রস্তাবকে সন্তোষজনক মনে করেননি; তিনি চাইছিলেন “কার্যকর পদ্ধতি” ধারণাটির নিজের বিশ্লেষণ, শুধু একটি সুন্দর শ্রেণি নয়।

Turing ঠিক সেটিই দেন। তিনি একটি মানুষ-গণককে নিয়ে শুরু করেন আর প্রশ্ন করেন: হিসাবের সময় এই মানুষের কাজের কোন বৈশিষ্ট্যগুলো আসলে অপরিহার্য? সসীম চিহ্ন, সসীম মনের অবস্থা, একবারে সীমিত দৃষ্টি, স্থানীয় পরিবর্তন। প্রতিটি বৈশিষ্ট্যের পক্ষে আলাদা যুক্তি আছে, যা একজন পাঠক নিজে বিচার করতে পারেন। শেষে যে যন্ত্র দাঁড়ায়, সেটি “আবিষ্কৃত” মনে হয়, “বাছাই করা” নয়। Gödel পরে লেখেন, Turing-এর কাজে যান্ত্রিক পদ্ধতির ধারণার একটি নিখুঁত ও প্রশ্নাতীতভাবে যথাযথ সংজ্ঞা পাওয়া গেছে; উদ্ধৃতির শব্দ উৎসভেদে একটু আলাদা, তবে মূল কথা এটাই।

এই পার্থক্যটি আজও কাজে লাগে। একটি নতুন সংজ্ঞা প্রস্তাব করলে দুই ধরনের সাক্ষ্য লাগে: পুরোনো সংজ্ঞার সঙ্গে মিল (বিস্তারগত), আর ধারণাটির নিজের বিশ্লেষণ (ধারণাগত)। Complexity-তে “দক্ষ = polynomial” প্রস্তাবের পক্ষে প্রথম ধরনের সাক্ষ্য অনেক, দ্বিতীয় ধরনের কম; তাই সেটি নিয়ে বিতর্কও বেশি।

মূল উপলব্ধি: সংজ্ঞাগুলোর মিল দেখায় শ্রেণিটি স্বাভাবিক; কিন্তু “এটিই algorithm” বিশ্বাসযোগ্য হয় তখন, যখন কেউ algorithm-এর ধারণাটি নিজেই খুলে দেখান আর প্রতিটি সরলীকরণের কারণ দেন।

প্র ০২Church–Turing thesis কি কখনো ভুল প্রমাণ হতে পারে? কী ধরনের আবিষ্কার তা করত, আর এখন পর্যন্ত প্রস্তাবিত “hypercomputer”-গুলো কেন বিশ্বাসযোগ্য নয়?

নীতিগতভাবে পারে, আর এখানেই এটি একটি theorem থেকে আলাদা। দুটি ভিন্ন ধরনের “ভুল প্রমাণ” কল্পনা করা যায়। প্রথমটি মূল thesis-এর বিরুদ্ধে: কেউ কাগজ-কলমে মানা যায় এমন একটি পদ্ধতি দেখালেন, যা সবাই যান্ত্রিক বলে মানেন, অথচ যা দিয়ে, ধরুন, halting problem-এর উত্তর পাওয়া যায়। এটি প্রায় অসম্ভব মনে হয়, কারণ যেকোনো লিখিত নিয়মের তালিকা Turing-এর বিশ্লেষণের মধ্যেই পড়ে। দ্বিতীয়টি physical রূপের বিরুদ্ধে: প্রকৃতিতে এমন একটি প্রক্রিয়া পাওয়া গেল, যা নির্ভরযোগ্যভাবে একটি অ-গণনাযোগ্য ফাংশনের মান দেয়।

দ্বিতীয় ধরনের কিছু তাত্ত্বিক প্রস্তাব আছে। একটি হলো “accelerating” যন্ত্র: প্রথম ধাপে এক সেকেন্ড, দ্বিতীয়টিতে আধা সেকেন্ড, তারপর সিকি; দুই সেকেন্ডে অসীম ধাপ শেষ, তাই একটি program থামে কি না দেখা যায়। আরেকটি analog যন্ত্র, যা একটি বাস্তব সংখ্যাকে অসীম নির্ভুলতায় রাখে; সেই সংখ্যার অঙ্কে অ-গণনাযোগ্য তথ্য লুকানো থাকলে যন্ত্রটি তা পড়তে পারে। তৃতীয়টি সাধারণ আপেক্ষিকতার বিশেষ spacetime, যেখানে একজন পর্যবেক্ষক সসীম সময়ে আরেকজনের অসীম দীর্ঘ হিসাবের ফল পান।

প্রতিটিতে অসীম কিছু লুকানো আছে: অসীম গতি, অসীম নির্ভুলতা, বা অসীম শক্তি ও স্থান। বাস্তব পদার্থবিজ্ঞানে প্রতিটি মাপে noise থাকে, আর কিছু যুক্তি বলে সীমিত জায়গায় সীমিত তথ্যই রাখা যায়। তার ওপর, এমন যন্ত্র কোনো উত্তর দিলে আমরা কীভাবে যাচাই করব যে উত্তরটি ঠিক? যাচাইয়ের জন্য আবার একটি অ-গণনাযোগ্য হিসাব লাগবে। তাই বেশিরভাগ গবেষক hypercomputation-কে গাণিতিক কৌতূহল হিসেবে দেখেন, বাস্তব সম্ভাবনা হিসেবে নয়। তবু প্রশ্নটি খোলা রাখাই বিজ্ঞানের রীতি।

মূল উপলব্ধি: Thesis প্রমাণযোগ্য নয় বলেই খণ্ডনযোগ্য; আর প্রতিটি প্রস্তাবিত পাল্টা-উদাহরণ কোনো না কোনো অসীমতা চায়, যা বাস্তবে পাওয়ার কোনো সাক্ষ্য নেই।

প্র ০৩“Quantum computer Church–Turing thesis ভেঙে দিয়েছে” — এই দাবিতে কোথায় সত্য, কোথায় ভুল? Extended thesis নিয়ে আমরা আসলে কী জানি?

দাবিটি দুটি ভিন্ন thesis গুলিয়ে ফেলে। মূল thesis “কী গণনা করা যায়” নিয়ে। একটি quantum circuit-এর আচরণ রৈখিক বীজগণিতে লেখা: amplitude-এর একটি vector, প্রতিটি gate একটি unitary matrix. একটি classical program এই vector হিসাব করে প্রতিটি ফলের সম্ভাবনা যেকোনো কাঙ্ক্ষিত নির্ভুলতায় বের করতে পারে। খরচ বিশাল হতে পারে, কারণ n qubit-এর vector-এ 2nটি সংখ্যা, কিন্তু খরচ সসীম। তাই quantum যন্ত্র কোনো নতুন ফাংশন গণনা করে না; halting problem সেখানেও undecidable.

Extended thesis “কত দ্রুত” নিয়ে। এখানে quantum computing সত্যিকারের চ্যালেঞ্জ। Shor-এর algorithm (১৯৯৪) factoring আর discrete logarithm-কে quantum যন্ত্রে polynomial সময়ে করে; classical যন্ত্রে, random বিটসহ, এমন algorithm জানা নেই। কিন্তু “জানা নেই” মানে “নেই” নয়: factoring কোনো classical polynomial algorithm-এ হয় না, তা প্রমাণিত নয়। আবার complexity-র ভাষায় BPP ⊆ BQP জানা, কিন্তু অন্তর্ভুক্তিটি কঠোর কি না, অজানা। BQP আর NP-এর সম্পর্কও অজানা; quantum কম্পিউটার NP-complete সমস্যা দ্রুত করে, এমন কোনো সাক্ষ্য নেই।

প্রকৌশলের দিকও আছে। বড় সংখ্যার factoring-এর জন্য অনেক qubit আর error correction লাগে। কিছু পরীক্ষায় দাবি করা হয়েছে যে বিশেষ নমুনা-তোলার কাজে quantum যন্ত্র classical যন্ত্রকে ছাড়িয়েছে, কিন্তু এসব দাবির পরে প্রায়ই উন্নত classical simulation এসেছে, আর এগুলো extended thesis-এর কঠোর খণ্ডন নয়। তাই সৎ বক্তব্য: যদি বড় fault-tolerant quantum কম্পিউটার গড়া যায় আর factoring classical ভাবে কঠিন হয়, তবে extended thesis মিথ্যা।

মূল উপলব্ধি: Quantum computing computability-র সীমা সরায় না; সরাতে পারে efficiency-র সীমা, আর সেটিও দুটি অপ্রমাণিত শর্তের ওপর নির্ভর করে।

প্র ০৪প্রতিটি বাস্তব কম্পিউটারের মেমরি সসীম, তাই কঠোর অর্থে সেটি একটি finite automaton. তাহলে “Python Turing-complete” কথাটির অর্থ কী, আর কেন অনেক ভাষা ইচ্ছা করে Turing-complete রাখা হয় না?

কথাটি আক্ষরিকভাবে সত্য। একটি laptop-এর RAM আর disk মিলে সসীম সংখ্যক bit, তাই সম্ভাব্য অবস্থাও সসীম, আর তত্ত্বে এটি একটি DFA, যার state-সংখ্যা 2-এর ঘাত কয়েক লাখ কোটি। কিন্তু এই বর্ণনা কিছু শেখায় না। “Python Turing-complete” মানে: Python-এর নিয়মে কোনো আগাম সীমা নেই; মেমরি ফুরালে আরও মেমরি যোগ করলে একই program বড় input-এ চলবে। Algorithm-এর নকশা মেমরির নির্দিষ্ট পরিমাণের ওপর নির্ভর করে না। TM-এর অসীম tape এই “যত দরকার তত” ধারণার গাণিতিক রূপ। একটি নির্দিষ্ট মেশিনে নির্দিষ্ট input-এর ক্ষেত্রে অবশ্যই সীমা আছে, যেমন Python-এর recursion limit.

উল্টো দিকে, Turing completeness-এর একটি দাম আছে। Turing-complete ভাষার program নিয়ে প্রায় কোনো অ-তুচ্ছ আচরণগত প্রশ্ন, যেমন “এটি কি সবসময় থামে?”, “এটি কি কখনো এই ফাইল লেখে?”, সাধারণভাবে নির্ণয়যোগ্য নয় (পর্ব ৫১, ৫৩)। তাই যেখানে নিশ্চয়তা দরকার, সেখানে ভাষা দুর্বল রাখা হয়। Regular expression সবসময় থামে আর সময়ও অনুমান করা যায় (automaton-ভিত্তিক engine-এ)। কিছু proof assistant-এর ভাষায় প্রতিটি function-কে থামতে বাধ্য করা হয় (total language), যাতে program-কে প্রমাণ হিসেবেও ব্যবহার করা যায়। Operating system-এর kernel-এ ব্যবহারকারীর দেওয়া ছোট program চালানোর কিছু ব্যবস্থায় আগে একটি verifier দেখে নেয় loop সীমিত কি না। কিছু ব্যবস্থা প্রতিটি হিসাবকে একটি ধাপ বা খরচের বাজেট দেয়।

মূল উপলব্ধি: Turing completeness হলো “নিয়মে কোনো সীমা নেই”-এর দাবি; এটি ক্ষমতা দেয়, কিন্তু বিশ্লেষণের ক্ষমতা কেড়ে নেয়, তাই ভালো নকশা প্রয়োজনের চেয়ে বেশি শক্তি দেয় না।

প্র ০৫Hilbert-এর দশম সমস্যার উত্তর পেতে ৭০ বছর লাগল কেন? “কোনো algorithm নেই” প্রমাণে Church–Turing thesis ঠিক কোথায় কাজে লাগে?

১৯০০ সালে Hilbert চেয়েছিলেন একটি “প্রক্রিয়া”, যা যেকোনো Diophantine সমীকরণ, যেমন x2 + y2 = z2 বা x3 + y3 + z3 = 33, দেখে বলবে পূর্ণসংখ্যা সমাধান আছে কি না। “আছে” উত্তরের জন্য অনুসন্ধান চলে: সব পূর্ণসংখ্যার tuple একে একে চেষ্টা করুন, সমাধান থাকলে একসময় পাবেন। তাই যে সমীকরণগুলোর সমাধান আছে, তাদের set একটি recognizable set (পর্ব ৫০-এর ভাষায়)। সমস্যা হলো সমাধান না থাকলে অনুসন্ধান কখনো শেষ হয় না। প্রশ্ন ছিল, এর চেয়ে ভালো কোনো পদ্ধতি আছে কি না।

“নেই” প্রমাণের জন্য প্রথম লাগল algorithm-এর সংজ্ঞা, যা ১৯৩৬-এ এল। তারপর লাগল একটি সেতু: Diophantine সমীকরণ যে প্রতিটি recognizable set বর্ণনা করতে পারে। Martin Davis, Hilary Putnam আর Julia Robinson ১৯৫০ আর ৬০-এর দশকে এই সেতুর প্রায় পুরোটা বানান, শুধু একটি অংশ বাকি ছিল: exponential বৃদ্ধির একটি সম্পর্ক Diophantine ভাবে প্রকাশ করা। ১৯৭০ সালে Yuri Matiyasevich Fibonacci সংখ্যা ব্যবহার করে সেই অংশ প্রমাণ করেন। ফল (MRDP theorem): প্রতিটি recognizable set কোনো Diophantine সমীকরণের সমাধান-set হিসেবে লেখা যায়। Halting problem-এর set-ও তাই। দশম সমস্যার algorithm থাকলে halting problem decidable হতো, যা অসম্ভব (পর্ব ৫১)।

Thesis এখানে কোথায়? প্রমাণটি পুরোপুরি গাণিতিক: “কোনো Turing machine দশম সমস্যা decide করে না”। Thesis লাগে শুধু শেষ অনুবাদে: “তাই কোনো algorithm নেই”, অর্থাৎ Hilbert-এর অনানুষ্ঠানিক “প্রক্রিয়া” শব্দের সঙ্গে মেলানোয়। এটিই thesis-এর আসল ভূমিকা: গাণিতিক theorem-কে মানুষের প্রশ্নের ভাষায় ফিরিয়ে আনা। একটি চমকপ্রদ পরিণতি: এমন একটি নির্দিষ্ট বহুপদী আছে, যার পূর্ণসংখ্যা সমাধান খোঁজা যেকোনো program-এর সমান কঠিন।

মূল উপলব্ধি: “কোনো algorithm নেই” ধরনের প্রতিটি ফলাফল আসলে দুটি অংশ: একটি প্রমাণিত theorem (কোনো TM নেই) আর thesis-এর একটি অনুবাদ (তাই কোনো algorithm নেই)।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। three_models.py ব্লকের rm_run আর tiny_tape.js-এর run দিয়ে নিজের উত্তর চালিয়েও দেখতে পারেন।

  1. নকশা: শুধু ("inc", r, পরের) আর ("dec", r, শূন্য-না-হলে, শূন্য-হলে) নির্দেশ দিয়ে একটি register machine লিখুন, যা থামার সময় register a-তে max(a, b) রাখে। একটি সাহায্যকারী register t (শুরুতে 0) ব্যবহার করতে পারেন। নির্দেশের নম্বর 0 থেকে; program-এর বাইরে লাফ মানে থামা।

    ভাবনা: a আর b একসঙ্গে কমান, t-তে জোড়া গুনুন; যেটি পরে ফুরায় তার বাকি অংশ + t = বড়টি।

    0: dec a → 1, শূন্য হলে → 3
    1: dec b → 2, শূন্য হলে → 5
    2: inc t → 0
    3: dec b → 4, শূন্য হলে → 6   (a আগে ফুরাল: b-এর বাকি a-তে)
    4: inc a → 3
    5: inc a → 6                    (b আগে ফুরাল: a-র বাড়তি কমানো ফেরত)
    6: dec t → 7, শূন্য হলে → 8   (t যোগ করা; 8 = থামা)
    7: inc a → 6

    Invariant: loop 0–2-এ (a + t, b + t) সবসময় শুরুর (a, b). a আগে শূন্য হলে b-তে b − a বাকি, তা a-তে সরিয়ে t = a যোগ করলে b. b আগে শূন্য হলে a একবার বেশি কমেছে; নির্দেশ ৫ তা ফেরত দিয়ে a − b, তারপর t = b যোগে a. Scratch-এ 0 ≤ a, b ≤ 9-এর ১০০টি জোড়ায় max(a, b)-এর সঙ্গে মিলেছে।

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “λ-calculus, μ-recursive function, register machine আর Turing machine সমতুল্য, এটি প্রমাণিত। এর বাইরে কোনো মডেল কেউ আজ পর্যন্ত দেখাতে পারেননি। অতএব প্রতিটি algorithm Turing-computable, আর Church–Turing thesis একটি প্রমাণিত theorem. ∎” যুক্তির কোন ধাপ ভুল, আর সঠিক বক্তব্য কী?

    প্রথম বাক্য সত্য (theorem ৪.২)। দ্বিতীয় বাক্য একটি পর্যবেক্ষণ, প্রমাণ নয়: “আজ পর্যন্ত কেউ দেখাননি” থেকে “কখনো দেখানো যাবে না” আসে না; এটি অসীম সংখ্যক ক্ষেত্র নিয়ে সসীম সাক্ষ্য থেকে সাধারণীকরণ। তৃতীয় বাক্যে আসল লাফ: “প্রতিটি algorithm” একটি অনানুষ্ঠানিক ধারণা নিয়ে কথা বলে, যার কোনো গাণিতিক সংজ্ঞা যুক্তিতে নেই; গাণিতিক প্রমাণ শুধু সংজ্ঞায়িত বস্তুর মধ্যে সম্পর্ক দেখাতে পারে।

    সঠিক বক্তব্য: “চারটি মডেল একই partial function শ্রেণি গণনা করে” একটি theorem; “এই শ্রেণি = effectively calculable ফাংশন” একটি thesis, যার পক্ষে শক্ত সাক্ষ্য (স্বাধীন সংজ্ঞার মিল, Turing-এর বিশ্লেষণ, robustness) আছে কিন্তু প্রমাণ নেই।

  3. Output অনুমান করুন: এই পর্বের tiny tape language-এ (+ বাড়ায়, − কমায় কিন্তু শূন্যের নিচে নয়, > ও < pointer সরায়, [ … ] ঘর শূন্য না হওয়া পর্যন্ত চালায়, . সংখ্যা ছাপে) program ++[>+++<-]>[.-] কী ছাপবে?

    “++” ঘর ০-তে 2. প্রথম loop প্রতিবার ঘর ১-এ 3 যোগ করে আর ঘর ০ থেকে 1 কমায়; দুইবার চলে, তাই ঘর ১ = 6, ঘর ০ = 0. তারপর “>” ঘর ১-এ যায়, আর দ্বিতীয় loop ছাপে আর কমায়: 6, 5, 4, 3, 2, 1, তারপর ঘর শূন্য হয়ে থামে। tiny_tape.js-এ চালালে আসে halted after 37 steps, output [6,5,4,3,2,1].

  4. শ্রেণিবিভাগ: প্রতিটি বক্তব্যকে “প্রমাণিত theorem”, “thesis (প্রমাণযোগ্য নয়)” বা “খোলা প্রশ্ন / অপ্রমাণিত”-এ ভাগ করুন: (ক) প্রতিটি λ-definable ফাংশন Turing-computable. (খ) প্রতিটি algorithm দিয়ে গণনাযোগ্য ফাংশন Turing-computable. (গ) প্রতিটি quantum circuit-এর ফলের সম্ভাবনা একটি TM হিসাব করতে পারে। (ঘ) Factoring-এর কোনো classical polynomial-time algorithm নেই। (ঙ) Multi-tape TM-এর t ধাপ single-tape TM-এ O(t2) ধাপে নকল হয়।

    (ক) প্রমাণিত theorem (Turing ১৯৩৭). (খ) Thesis: “algorithm” অনানুষ্ঠানিক। (গ) প্রমাণিত: amplitude-গুলো হিসাব করে নকল করা যায়, সময় exponential হতে পারে। (ঘ) অপ্রমাণিত, খোলা প্রশ্ন; এটি সত্য হলে আর বড় quantum কম্পিউটার গড়া গেলে extended thesis মিথ্যা হয়। (ঙ) প্রমাণিত theorem (পর্ব ৪৫).

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

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

ক্রমঘটনাগুলো সময়ের ক্রমে সাজান (▲▼ চেপে সরান)

  1. Hilbert-এর ২৩টি সমস্যা, দশমটি Diophantine সমীকরণ নিয়ে
  2. Hilbert ও Ackermann-এর বইয়ে Entscheidungsproblem-এর স্পষ্ট রূপ
  3. Gödel-এর incompleteness theorem
  4. Church আর Turing আলাদাভাবে দেখান Entscheidungsproblem সমাধানযোগ্য নয়
  5. Matiyasevich দেখান Hilbert-এর দশম সমস্যার কোনো algorithm নেই
  6. Shor-এর quantum factoring algorithm

Church–Turing thesis-এর মর্যাদা সম্পর্কে কোন বক্তব্য সঠিক?

  • Turing ১৯৩৬ সালে এটি গাণিতিকভাবে প্রমাণ করেন
  • এটি theorem নয়, কারণ “algorithm” একটি অনানুষ্ঠানিক ধারণা; তবে সর্বজনগ্রাহ্য
  • Quantum computer এটি মিথ্যা প্রমাণ করেছে
  • এটি P বনাম NP-এর মতো একটি খোলা গাণিতিক প্রশ্ন, যার প্রমাণ খোঁজা চলছে

নিচের কোনটি একটি প্রমাণিত theorem?

  • λ-definable ফাংশন আর Turing-computable ফাংশন একই শ্রেণি
  • প্রতিটি algorithm একটি Turing machine দিয়ে বাস্তবায়ন করা যায়
  • Quantum কম্পিউটার factoring-এ যেকোনো classical algorithm-এর চেয়ে exponential দ্রুত
  • যেকোনো বাস্তব মডেল probabilistic TM-এ polynomial খরচে নকল হয়

একটি বড়, নির্ভুল quantum কম্পিউটার গড়া গেলে Church–Turing thesis-এর কোন রূপ ঝুঁকিতে পড়তে পারে?

  • মূল thesis, কারণ quantum যন্ত্র halting problem সমাধান করবে
  • শুধু halting problem-এর undecidability
  • Extended thesis, যদি factoring সত্যিই classical polynomial সময়ে না হয়
  • Multi-tape আর single-tape TM-এর সমতার theorem

“একটি সাধারণ laptop-এর মেমরি সসীম, তবু আমরা বলি Python Turing-complete.” এর সবচেয়ে সঠিক ব্যাখ্যা কোনটি?

  • Laptop-এর মেমরি এত বড় যে সেটি আসলে অসীম
  • Python যেকোনো Turing machine-এর চেয়ে দ্রুত চলে
  • Python program থামবে কি না, Python নিজে বলে দিতে পারে
  • Python-এর নিয়মে মেমরির কোনো আগাম সীমা নেই; যত দরকার মেমরি দিলে যেকোনো TM নকল করা যায়

একটি register machine-এর নির্দেশ: 0: dec a → 1, a শূন্য হলে → 3 (থামা); 1: inc b → 2; 2: inc b → 0. শুরুতে a = 3, b = 0 হলে থামার সময় b কত?

  • 3
  • 6
  • 8
  • 0

নিচের কোনটি Church–Turing thesis-এর পক্ষে সাক্ষ্য নয়?

  • λ-calculus, μ-recursive function আর Turing machine প্রমাণিতভাবে সমতুল্য
  • Turing-এর মানুষ-গণকের বিশ্লেষণ
  • TM-এর variant (multi-tape, nondeterministic) একই ক্ষমতার
  • এটি set theory-র প্রচলিত axiom থেকে প্রমাণিত হয়েছে

শব্দকোষ

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

মনে রাখুন

  1. “কোনো algorithm নেই” প্রমাণ করতে algorithm-এর গাণিতিক সংজ্ঞা লাগে; Hilbert-এর প্রশ্নগুলো এই প্রয়োজন তৈরি করে, ১৯৩৬ সালে Church, Turing আর Post উত্তর দেন।
  2. λ-calculus, μ-recursive function, Turing machine, Post system, register machine আর সাধারণ programming language একই partial function শ্রেণি গণনা করে: এটি প্রমাণিত theorem, simulation-এর চক্র দিয়ে।
  3. Church–Turing thesis: effectively calculable = Turing-computable. এক পাশ অনানুষ্ঠানিক, তাই theorem নয়; সাক্ষ্য: মডেলগুলোর মিল, Turing-এর বিশ্লেষণ, robustness, পাল্টা-উদাহরণ নেই।
  4. Extended thesis দক্ষতা নিয়ে (polynomial খরচে নকল); quantum computing এটিকে চ্যালেঞ্জ করতে পারে, মূল thesis-কে নয়। Physical thesis পদার্থবিজ্ঞানের দাবি।
  5. Turing-complete = অসীম মেমরি ধরে যেকোনো TM নকল করতে পারে; জানা মডেল নকল করে দেখানো হয়। থামার নিশ্চয়তা চাইলে ভাষা ইচ্ছা করে দুর্বল রাখা হয়।

পরের পর্বে: Universal Turing machine: একটি যন্ত্রকে string ⟨M⟩ হিসেবে লেখা, আর এমন একটি যন্ত্র যা ⟨M, w⟩ পেয়ে M-কে w-তে নকল করে; program-ই data, আর আজকের interpreter ও stored-program কম্পিউটারের তাত্ত্বিক মূল।

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

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