Turing Machine — গণনার সবচেয়ে সরল আনুষ্ঠানিক মডেল

আগে এটা বুঝি

১৯২৮ সালে গণিতবিদ David Hilbert একটা প্রশ্ন তুললেন যেটা শুনতে নিরীহ, কিন্তু উত্তর দিতে গিয়ে পুরো কম্পিউটার বিজ্ঞানের জন্ম হলো। প্রশ্নটার নাম Entscheidungsproblem (decision problem):

গণিতের যেকোনো দাবির জন্য, এমন একটা যান্ত্রিক পদ্ধতি কি আছে যা সসীম সময়ে বলে দেবে দাবিটা সত্য না মিথ্যা?

লক্ষ্য করুন শব্দটা — “যান্ত্রিক” (mechanical)। ১৯৩৬ সাল পর্যন্ত এই শব্দটার কোনো গাণিতিক সংজ্ঞা ছিল না। “Algorithm” মানে তখনো একটা স্বজ্ঞাত (intuitive) ধারণা — “যা একজন মানুষ নিয়ম মেনে করতে পারে, চিন্তাশক্তি ছাড়াই, শুধু কাগজ-কলম দিয়ে।”

২২ বছর বয়সী Alan Turing এই প্রশ্নে একটা অদ্ভুত পথ নিলেন। তিনি প্রশ্ন করলেন না “কম্পিউটার কী পারে” — কারণ কম্পিউটার তখনো নেই। তিনি প্রশ্ন করলেন: একজন মানুষ যখন হিসাব করে, ঠিক কী কী করে?

তিনি লক্ষ্য করলেন মানুষ কাগজে হিসাব করার সময়:

কাগজে একবারে একটা জায়গায় নজর রাখে (বাকি কাগজ তখন প্রাসঙ্গিক নয়)
যা দেখে তার ভিত্তিতে একটা সসীম নিয়মের তালিকা থেকে একটা নিয়ম বেছে নেয়
কিছু লেখে বা মুছে, তারপর মনোযোগ বাম বা ডানে সরায়
মাথায় সসীম সংখ্যক “মানসিক অবস্থা” রাখে (যেমন “এখন আমি ধার নিচ্ছি”)

এই চারটা পর্যবেক্ষণ থেকে Turing একটা কাল্পনিক যন্ত্র ডিজাইন করলেন — অসীম দীর্ঘ কাগজের ফালি (tape), একটা মাথা (head) যা একবারে একটা ঘর পড়ে-লেখে, আর সসীম সংখ্যক অবস্থা (state)। এতটাই সরল যে প্রথম দেখায় খেলনা মনে হয়।

অথচ এই যন্ত্রটাই ৯০ বছর পরেও গণনার সীমার একমাত্র সর্বজনস্বীকৃত সংজ্ঞা। এই লেসনে আমরা সেই যন্ত্রটা বানাব, হাতে চালাব, আর দেখব কেন এত সরল কিছু এত শক্তিশালী।

একই সময়ে, স্বাধীনভাবে

Turing যখন Cambridge-এ এই মডেল লিখছেন, ঠিক তখনই Princeton-এ Alonzo Church lambda calculus নামে সম্পূর্ণ ভিন্ন দেখতে একটা মডেল দিয়ে একই প্রশ্নের উত্তর দিচ্ছেন — function-ভিত্তিক, tape-হীন। দুইজন একে অপরের কাজ না জেনেই প্রায় একই সময়ে (Church ১৯৩৬-এর এপ্রিলে, Turing মে-তে) Entscheidungsproblem-এর নেতিবাচক উত্তর প্রকাশ করলেন।

পরে প্রমাণিত হলো — দুইটা মডেল হুবহু একই ভাষার সেট সংজ্ঞায়িত করে। এই আশ্চর্য মিলটাই পরের লেসনের (Church-Turing thesis) কেন্দ্রীয় বিষয়।

মূল ধারণা

আনুষ্ঠানিক সংজ্ঞা

একটা Turing machine একটা 7-tuple:

$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

উপাদান	অর্থ
`Q`	সসীম state-এর সেট
`Σ` (sigma)	input alphabet — blank চিহ্ন ছাড়া
`Γ` (gamma)	tape alphabet — `Σ ⊆ Γ`, আর একটা বিশেষ blank চিহ্ন `⊔ ∈ Γ \ Σ` থাকে
`δ : Q × Γ → Q × Γ × {L, R}`	transition function
`q0 ∈ Q`	start state
`q_accept ∈ Q`	accept state
`q_reject ∈ Q`	reject state (`q_reject ≠ q_accept`)

Tape — দুই দিকে অসীম দীর্ঘ, ঘরে ভাগ করা। শুরুতে input string বাম প্রান্তে লেখা, বাকি সব ঘর ⊔ (blank)।

Head — একটা মুহূর্তে একটামাত্র ঘর পড়ে। প্রতি step-এ:

বর্তমান state আর head-এর নিচের symbol পড়ে
δ(q, a) = (q', a', d) অনুযায়ী: symbol-টা a' দিয়ে replace করে, state q'-এ যায়, head d (বাম বা ডান) দিকে এক ঘর সরে

tape:   ⊔ ⊔ 0 1 1 0 ⊔ ⊔ ⊔ ...
                ↑
head position   3
current state:  q2

একটা TM-এর snapshot — tape, head position, আর current state।

Configuration (বা instantaneous description) — tape-এর content, head position, আর current state — এই তিনটা মিলে যন্ত্রের সম্পূর্ণ “মুহূর্তের ছবি”। সাধারণত লেখা হয় u q v আকারে, যেখানে u head-এর বাম দিকের tape content, v head আর তার ডানের content, আর q current state।

গণনা (computation): যন্ত্র q0 state-এ শুরু হয়ে, প্রতি step-এ δ অনুযায়ী নতুন configuration-এ যায় — যতক্ষণ না q_accept বা q_reject-এ পৌঁছায়। TM-এর সবচেয়ে গুরুত্বপূর্ণ আচরণ যেটা DFA/NFA থেকে একে আলাদা করে: এটা কখনো নাও থামতে পারে — গণনা চিরকাল চলতে পারে, কোনো accept/reject ছাড়াই। এই সম্ভাবনাটাই কয়েক লেসন পরে halting problem-এর ভিত্তি।

তিনটা জিনিস যা TM-কে DFA/PDA-এর চেয়ে শক্তিশালী করে

আগের লেসনগুলোতে আমরা DFA (সসীম memory) আর PDA (একটা stack — শুধু LIFO access) দেখেছি। TM-এর তিনটা নতুন ক্ষমতা:

অসীম memory — tape যতদূর দরকার বাড়ে
যেকোনো দিকে movement — শুধু push/pop নয়, tape-এর যেকোনো জায়গায় ফিরে গিয়ে আগের লেখা পড়া বা বদলানো যায় (random access-এর মতো, যদিও sequential movement দিয়ে)
লেখার ক্ষমতা — tape-এ শুধু পড়া নয়, বদলানো যায়, যেটা PDA-র stack-এও সীমিতভাবে সম্ভব (শুধু top-এ) কিন্তু tape-এ সম্পূর্ণ স্বাধীন

এই তিনটার সমন্বয়েই TM Chomsky hierarchy-র সবচেয়ে উপরের স্তর — recursively enumerable languages — চেনে, যেটা regular আর context-free-এর strict superset।

ভাষা গ্রহণ — accept, reject, আর loop

M একটা string w accept করে যদি q0, w থেকে শুরু করা computation একটা সসীম সংখ্যক step পরে q_accept-এ পৌঁছায়।

M-এর গৃহীত ভাষা: L(M) = {w : M w-কে accept করে}।

তিনটা সম্ভাব্য পরিণতি আছে, দুইটা না:

পরিণতি	অর্থ
Accept	`q_accept`-এ পৌঁছায়
Reject	`q_reject`-এ পৌঁছায়
Loop (থামে না)	কখনো কোনোটাতেই পৌঁছায় না

এই তৃতীয় সম্ভাবনাটাই TM-কে DFA/PDA থেকে গুণগতভাবে আলাদা করে, আর এই মডিউলের বাকি অর্ধেক এই একটা সম্ভাবনার চারপাশেই আবর্তিত হবে।

ভেতরে কী ঘটছে

কেন এত সরল কিছু এত শক্তিশালী

একটা স্বাভাবিক প্রশ্ন — একটা machine যার কাছে শুধু “বাম যাও, ডান যাও, লেখো” আছে, সেটা কীভাবে matrix multiplication, database query, web browser — সব গণনা করতে পারে?

উত্তরটা তিনটা পর্যবেক্ষণে:

১. State সসীম হলেও, তার সংখ্যায় কোনো ঊর্ধ্বসীমা নেই। একটা TM-এর কোটি কোটি state থাকতে পারে — সংজ্ঞা অনুযায়ী তা “সসীম” থাকলেই হলো। জটিল control logic (loop, if-else, function call) সবই বহু state-এর সমন্বয়ে encode করা যায়।

২. Tape data structure-এর চূড়ান্ত রূপ। Array, linked list, tree, hash table — সব কিছুই শেষ পর্যন্ত মেমরির একটা রৈখিক সারি (আজকের RAM-ও ঠিক তাই, ঠিকানার একটা রৈখিক সারি)। TM-এর tape সেই ধারণারই সবচেয়ে খালি (bare-bones) রূপ — আর দেখানো যায় (পরের কয়েক লেসনে না হলেও, algorithms module-এর data structure লেসনগুলোতে) যে যেকোনো data structure একটা tape-এর উপর simulate করা যায়, শুধু সময়ের একটা (polynomial) মূল্যে।

৩. Composition — ছোট TM জোড়া লাগিয়ে বড় TM। একটা TM যা w-এর তৃতীয় bit খুঁজে বের করে, আরেকটা যা দুইটা সংখ্যা যোগ করে — এদের জোড়া লাগিয়ে একটা তৃতীয় TM বানানো যায় যা প্রথমটার output নিয়ে দ্বিতীয়টা চালায়। ঠিক যেমন উচ্চ-স্তরের প্রোগ্রামিং ভাষায় function compose করেন, ঠিক তেমনি TM-ও composable।

এই তিনটা মিলে একটা গভীর দাবির ভিত্তি তৈরি করে, যেটা আমরা পরের লেসনে আনুষ্ঠানিকভাবে দেখব: যেকোনো “algorithm” শব্দের স্বজ্ঞাত অর্থে যা গণনাযোগ্য, তা একটা Turing machine দিয়েও গণনাযোগ্য।

Variant — বেশি ক্ষমতা মনে হয়, কিন্তু নেই

তিনটা স্বাভাবিক সম্প্রসারণ বিবেচনা করা যাক — প্রতিটাই প্রথম দেখায় বেশি শক্তিশালী মনে হয়।

Multi-tape TM

k-টা tape, প্রতিটার নিজস্ব independent মাথা। এক step-এ সবগুলো মাথা একসাথে (নিজ নিজ symbol পড়ে, নিজ নিজ নিয়মে) move করে। এটা প্রোগ্রামিং সহজ করে — একটা tape input রাখতে, একটা scratch space-এর জন্য, একটা output-এর জন্য ব্যবহার করা যায়।

দাবি: প্রতিটা k-tape TM-এর জন্য একটা সমতুল্য single-tape TM আছে যা ঠিক একই ভাষা চেনে।

যুক্তির খসড়া (simulation): single tape-কে kটা “ট্র্যাকে” ভাগ করুন (কল্পনা করুন প্রতিটা ঘরে kটা symbol স্ট্যাক করা আছে, একসাথে একটা যৌগিক symbol হিসেবে)। প্রতিটা মূল tape-এর মাথার অবস্থান একটা বিশেষ চিহ্ন (যেমন ডট) দিয়ে সেই ট্র্যাকে মার্ক করে রাখা হয়। একটা “সিমুলেটেড step”-এ single-tape TM পুরো tape জুড়ে একবার বাম থেকে ডানে, তারপর ডান থেকে বামে স্ক্যান করে সবগুলো মার্কড অবস্থান খুঁজে বের করে, প্রতিটা ট্র্যাকের জন্য k-tape TM-এর নিয়ম প্রয়োগ করে।

খরচ: k-tape TM-এর t step সিমুলেট করতে single-tape TM-এর O(t²) step লাগে (প্রতি সিমুলেটেড step-এ tape-এর দৈর্ঘ্য সমান একটা scan লাগে, আর tape দৈর্ঘ্য O(t) পর্যন্ত বাড়তে পারে)। ধীর, কিন্তু সসীম — কোনো নতুন ভাষা চেনা যায় না যা single-tape TM চিনত না।

Nondeterministic TM (NTM)

δ : Q × Γ → 𝒫(Q × Γ × {L,R}) — একটা (state, symbol) জোড়ার জন্য একাধিক সম্ভাব্য পরবর্তী step থাকতে পারে। NTM একটা string accept করে যদি অন্তত একটা সম্ভাব্য computation path accept-এ পৌঁছায়।

দাবি: প্রতিটা NTM-এর জন্য একটা সমতুল্য deterministic TM আছে।

যুক্তির খসড়া: NTM-এর সব সম্ভাব্য computation path একটা tree তৈরি করে (প্রতিটা node-এ branching factor সর্বোচ্চ b)। একটা DTM এই পুরো tree-কে breadth-first ভাবে explore করতে পারে — প্রতিটা depth-এ সব path একটু একটু করে এগিয়ে নিয়ে। যদি কোনো path accept-এ পৌঁছায়, DTM-ও accept করে।

(BFS জরুরি — DFS করলে একটা অসীম path-এ আটকে গিয়ে অন্য একটা ছোট accepting path কখনো খুঁজে পাওয়া যাবে না।)

খরচ: depth d-তে nondeterministic TM O(d) step নেয়, কিন্তু সিমুলেটিং DTM-কে O(bᵈ) node explore করতে হতে পারে — সূচকীয় (exponential) ধীরগতি।

এই একটা ফলাফল পরের অংশের ভিত্তি

লক্ষ্য করুন প্যাটার্নটা — multi-tape-এ polynomial slowdown, nondeterminism-এ exponential slowdown। দুইটা ক্ষেত্রেই কোনো নতুন ভাষা চেনা যায় না (computability অপরিবর্তিত), কিন্তু সময়ের খরচ নাটকীয়ভাবে বদলায় (complexity বদলায়)।

এই পার্থক্যটাই — “কী গণনাযোগ্য” বনাম “কত দ্রুত গণনাযোগ্য” — এই পুরো module-এর কেন্দ্রীয় বিভাজন রেখা। এই লেসনগুলো (৫-৯) প্রথমটা নিয়ে; পরের লেসনগুলো (complexity classes, P vs NP) দ্বিতীয়টা নিয়ে। আর ঠিক এইখানেই সেই বিভাজনের বীজ বোনা হলো — deterministic বনাম nondeterministic TM-এর সময়ের পার্থক্যটাই পরে P বনাম NP-এর আনুষ্ঠানিক সংজ্ঞা হয়ে দাঁড়াবে।

Two-way infinite tape, বনাম half-infinite

কিছু পাঠ্যবই tape-কে শুধু ডানে অসীম ধরে (বামে একটা প্রান্ত আছে)। এটাও সমতুল্য — দুই-দিকে-অসীম tape-কে একটা ট্র্যাকে “উপরের সারি” আর অন্য ট্র্যাকে “নিচের সারি” ভাঁজ করে একটা half-infinite tape-এ simulate করা যায় (কল্পনা করুন tape-টা মাঝখান থেকে ভাঁজ করা)।

সাধারণ নীতি — একটা গুরুত্বপূর্ণ প্যাটার্ন যা পুরো module জুড়ে ফিরে আসবে: TM-এর সংজ্ঞায় “যুক্তিসঙ্গত” যেকোনো সম্প্রসারণ (multi-tape, nondeterminism, two-dimensional tape, multiple heads একই tape-এ) — এসব computational power বদলায় না, শুধু efficiency বদলাতে পারে। এই স্থিতিস্থাপকতাই (robustness) পরের লেসনে Church-Turing thesis-এর একটা প্রধান প্রমাণ।

উদাহরণ

হাতে একটা TM বানানো — `{0ⁿ1ⁿ : n ≥ 0}`

এই ভাষাটা — সমান সংখ্যক 0 তারপর সমান সংখ্যক 1 — আগের লেসনে দেখেছি এটা context-free (PDA দিয়ে চেনা যায়, stack ব্যবহার করে)। এখানে সেটাকেই TM দিয়ে বানাব — শুধু দেখানোর জন্য যে TM কীভাবে কাজ করে, একটা এমন ভাষায় যেটার আচরণ আমরা ইতিমধ্যে বুঝি।

অ্যালগরিদম (ইংরেজিতে প্রথমে):

বাম প্রান্তের সবচেয়ে বামের 0-কে X দিয়ে চিহ্নিত করুন (already crossed)
ডানে গিয়ে সবচেয়ে বামের uncrossed 1-কে Y দিয়ে চিহ্নিত করুন
বামে ফিরে যান, ধাপ ১-এ ফিরুন
যখন আর কোনো uncrossed 0 নেই: ডানে গিয়ে যাচাই করুন কোনো uncrossed 1 অবশিষ্ট নেই — থাকলে reject, না থাকলে accept

Transition table:

State	পড়া	লেখা	move	পরের state
`q0`	`0`	`X`	R	`q1`
`q0`	`Y`	`Y`	R	`q3`
`q0`	`⊔`	`⊔`	R	`q_accept`
`q0`	`1`	—	—	`q_reject`
`q1`	`0`	`0`	R	`q1`
`q1`	`Y`	`Y`	R	`q1`
`q1`	`1`	`Y`	L	`q2`
`q1`	`⊔`	—	—	`q_reject`
`q2`	`0`	`0`	L	`q2`
`q2`	`Y`	`Y`	L	`q2`
`q2`	`X`	`X`	R	`q0`
`q3`	`Y`	`Y`	R	`q3`
`q3`	`⊔`	`⊔`	R	`q_accept`
`q3`	`0` বা `1`	—	—	`q_reject`

q0 = “একটা নতুন 0 খুঁজছি”; q1 = “matching 1 খুঁজতে ডানে যাচ্ছি”; q2 = “matching শেষ, শুরুতে ফিরে যাচ্ছি”; q3 = “সব crossed, বাকি অংশ পরিষ্কার কি না যাচাই করছি”।

Trace — input `0011`

step	state	tape (head `[..]`-এ চিহ্নিত)
0	`q0`	`[0]011`
1	`q1`	`X[0]11`
2	`q1`	`X0[1]1`
3	`q2`	`X[0]Y1`
4	`q0`	`[X]0Y1`
5	`q1`	`X[0]Y1`
6	`q1`	`XX[Y]1`
7	`q1`	`XXY[1]`
8	`q2`	`XX[Y]Y`
9	`q2`	`X[X]YY`
10	`q0`	`XX[Y]Y`
11	`q3`	`XXY[Y]`
12	`q3`	`XXYY[⊔]`
13	`q_accept`	— accept!

`0011` -এর উপর TM-এর সম্পূর্ণ execution — প্রতিটা ধাপে tape, head, state।

১৩টা step, ৪টা symbol input-এ। লক্ষ্য করুন প্যাটার্নটা — প্রতিটা 0-1 জোড়া matched করতে tape-এ বারবার সামনে-পিছনে যেতে হচ্ছে। n সংখ্যক 0 আর n সংখ্যক 1-এর জন্য এই machine Θ(n²) step নেয় — প্রতিটা matching round tape-এর length-এর সমান দূরত্ব পাড়ি দেয়, আর n রাউন্ড লাগে।

TM ডিজাইন করার সময় যা মনে রাখবেন

প্রতিটা state-কে একটা ইংরেজি বাক্যে নাম দিন আগে (“আমি এখন কী খুঁজছি বা মনে রাখছি”), তারপর transition table লিখুন। উপরের উদাহরণে q1 = “matching 1 খুঁজতে ডানে যাচ্ছি” — এই বাক্যটাই বলে দেয় q1-এ 0 আর Y দেখলে কী করতে হবে (উপেক্ষা করে এগিয়ে যাওয়া) আর 1 দেখলে কী (mark করে ফিরে যাওয়া)।

এটা ঠিক প্রোগ্রামিং-এর সাথে মেলে — একটা while loop-এর ভেতর variable-এর “invariant” কী বোঝায় তা লিখে রাখলে loop body লেখা সহজ হয় (Level 0-এর loop invariant লেসন মনে করুন)। TM state আসলে loop-এর সেই “কোথায় আছি” ধারণারই একটা বিচ্ছিন্ন (discrete) রূপ।

নিজে চালিয়ে দেখুন

EXPERIMENT

TM simulator লিখে হাতে-করা trace যাচাই করুন

Python 3· ২০ মিনিট

BLANK = "_"

# {0^n 1^n} মেশিনের transition table
# key: (state, symbol) -> value: (new_state, write_symbol, move)
delta = {
    ("q0", "0"): ("q1", "X", "R"),
    ("q0", "Y"): ("q3", "Y", "R"),
    ("q0", BLANK): ("qaccept", BLANK, "R"),

    ("q1", "0"): ("q1", "0", "R"),
    ("q1", "Y"): ("q1", "Y", "R"),
    ("q1", "1"): ("q2", "Y", "L"),

    ("q2", "0"): ("q2", "0", "L"),
    ("q2", "Y"): ("q2", "Y", "L"),
    ("q2", "X"): ("q0", "X", "R"),

    ("q3", "Y"): ("q3", "Y", "R"),
    ("q3", BLANK): ("qaccept", BLANK, "R"),
}

def run(input_str, max_steps=10_000, trace=False):
    tape = list(input_str) + [BLANK] * 20      # কার্যত-অসীম tape
    head, state, steps = 0, "q0", 0

    while state not in ("qaccept", "qreject") and steps \< max_steps:
        symbol = tape[head]
        key = (state, symbol)
        if key not in delta:
            state = "qreject"
            break
        new_state, write, move = delta[key]
        tape[head] = write
        state = new_state
        head += 1 if move == "R" else -1
        steps += 1
        if trace:
            shown = "".join(tape).rstrip(BLANK) or BLANK
            print(f"step {steps:>3}  state={state:<8}  head={head:<3}  tape={shown}")

    if steps >= max_steps:
        return "TIMEOUT (সম্ভবত loop করছে)"
    return "ACCEPT" if state == "qaccept" else "REJECT"


for s in ["", "01", "0011", "000111", "0010", "10", "0001111"]:
    print(f"{s!r:>10} -> {run(s)}")

print("\n--- সম্পূর্ণ trace, input='0011' ---")
run("0011", trace=True)

প্রত্যাশিত output:

       '' -> ACCEPT
     '01' -> ACCEPT
   '0011' -> ACCEPT
 '000111' -> ACCEPT
   '0010' -> REJECT
       '10' -> REJECT
'0001111' -> REJECT

শেষ trace-টা হাতে-করা table-এর সাথে হুবহু মিলিয়ে দেখুন — step-সংখ্যা, state, head position প্রতিটা লাইনে।

এখন ইচ্ছে করে একটা transition বাদ দিন:

del delta[("q1", "1")]     # matching 1 খুঁজে পাওয়ার নিয়মটাই মুছে দিলাম
print(run("0011", max_steps=50))

(q1, "1")-এর কোনো নিয়ম নেই, তাই run() সাথে সাথে reject করে — কারণ এই কোডে “নিয়ম নেই” মানেই reject ধরা হয়েছে। কিন্তু বাস্তব সংজ্ঞায় δ total function হতে হয় (প্রতিটা (state, symbol) জোড়ার জন্য কিছু না কিছু বলতেই হয়) — তাই formal TM-এ “নিয়ম নেই” বলে কিছু হয় না, শুধু ছোট করে q_reject-এ পাঠানো একটা explicit entry থাকে। আসল বিপদ আসে যখন ভুল entry থাকে যা একটা infinite loop তৈরি করে — নিচেরটা চেষ্টা করুন:

delta[("q1", "1")] = ("q1", "1", "R")    # bug: L-এর বদলে R, আর state বদলায় না
print(run("0011", max_steps=50))          # TIMEOUT

এটাই halting problem-এর প্রথম আভাস — আপনি একটা TM-এর কোড দেখে বলতে পারবেন না এটা কখনো থামবে কি না, শুধু চালিয়ে দেখা ছাড়া। আর চালিয়ে দেখাও নিশ্চিত উত্তর দেয় না — না থামলে আপনি কখনো জানবেন না সেটা আরেকটু পরে থামত, নাকি চিরকাল চলবে। এই প্রশ্নটাই কয়েক লেসন পরে আনুষ্ঠানিকভাবে প্রমাণ করব — এটা সমাধানের কোনো general পদ্ধতিই নেই।

এটা কী প্রমাণ করে

আগের section-এ হাতে করা ১৩-step trace ঠিক ছিল কি না — আর transition table সামান্য ভুল হলে (যেমন একটা entry missing) মেশিন কীভাবে 'loop' করে, reject করে না, তা প্রত্যক্ষভাবে দেখায়।

নিজে বানান

BUILD IT

Universal Turing Machine simulator — encoded ⟨M, w⟩ থেকে সিমুলেশন

Python · ●●●○○

একটা TM-কে JSON/dict আকারে encode করুন — states, alphabet, transition table
একটা generic simulator লিখুন যা যেকোনো encoded TM আর input নিয়ে চালায়
একই simulator দিয়ে দুইটা ভিন্ন TM চালিয়ে দেখান এটা সত্যিই "universal"
একটা step-limit যোগ করুন আর তার তাৎপর্য নিয়ে মন্তব্য লিখুন

Universal Turing machine-এর মূল ধারণা: একটা মেশিন U যা ইনপুট হিসেবে নেয় অন্য একটা TM-এর বর্ণনা ⟨M⟩ (encoded, tape-এ লেখা string হিসেবে) আর একটা input w, এবং M-কে w-এর উপর যেভাবে চলত ঠিক সেভাবেই সিমুলেট করে।

class TuringMachine:
    def __init__(self, states, alphabet, blank, delta, start, accept, reject):
        self.states = states
        self.alphabet = alphabet
        self.blank = blank
        self.delta = delta          # dict: (state, symbol) -> (state, symbol, move)
        self.start = start
        self.accept = accept
        self.reject = reject


def universal_simulate(M: TuringMachine, w: str, max_steps=100_000, trace=False):
    """U(⟨M⟩, w) — M-এর description আর input w নিয়ে M-কে simulate করে।
    এই একটাই function, কিন্তু M বদলালেই ভিন্ন মেশিনের আচরণ পাওয়া যায় —
    এটাই universality।"""
    tape = list(w) + [M.blank] * 50
    head, state, steps = 0, M.start, 0

    while state not in (M.accept, M.reject) and steps \< max_steps:
        sym = tape[head]
        key = (state, sym)
        if key not in M.delta:
            return "REJECT (no transition)", steps
        new_state, write, move = M.delta[key]
        tape[head] = write
        state = new_state
        head += 1 if move == "R" else -1
        if head \< 0:
            tape.insert(0, M.blank); head = 0
        steps += 1
        if trace:
            print(f"  [{M.states.index(state) if False else state}] "
                  f"{''.join(tape).rstrip(M.blank)}")

    if steps >= max_steps:
        return "TIMEOUT", steps
    return ("ACCEPT" if state == M.accept else "REJECT"), steps


# ── Machine ১: unary increment — একটা '1'-এর ব্লক দৈর্ঘ্যে এক যোগ করে ──
m_incr = TuringMachine(
    states=["q0", "qaccept", "qreject"],
    alphabet=["1"], blank="_",
    delta={
        ("q0", "1"): ("q0", "1", "R"),
        ("q0", "_"): ("qaccept", "1", "R"),   # tape-এর শেষে একটা 1 জুড়ে দিলেই increment
    },
    start="q0", accept="qaccept", reject="qreject",
)

# ── Machine ২: {0^n 1^n} স্বীকৃতি — আগের section-এর table-ই এখানে data ──
m_eqcount = TuringMachine(
    states=["q0", "q1", "q2", "q3", "qaccept", "qreject"],
    alphabet=["0", "1", "X", "Y"], blank="_",
    delta={
        ("q0", "0"): ("q1", "X", "R"), ("q0", "Y"): ("q3", "Y", "R"),
        ("q0", "_"): ("qaccept", "_", "R"),
        ("q1", "0"): ("q1", "0", "R"), ("q1", "Y"): ("q1", "Y", "R"),
        ("q1", "1"): ("q2", "Y", "L"),
        ("q2", "0"): ("q2", "0", "L"), ("q2", "Y"): ("q2", "Y", "L"),
        ("q2", "X"): ("q0", "X", "R"),
        ("q3", "Y"): ("q3", "Y", "R"), ("q3", "_"): ("qaccept", "_", "R"),
    },
    start="q0", accept="qaccept", reject="qreject",
)

print("একই U দিয়ে দুইটা ভিন্ন 'প্রোগ্রাম' চালাচ্ছি:\n")
print("U(⟨m_incr⟩,    '111')  =", universal_simulate(m_incr, "111"))
print("U(⟨m_eqcount⟩, '0011') =", universal_simulate(m_eqcount, "0011"))
print("U(⟨m_eqcount⟩, '0010') =", universal_simulate(m_eqcount, "0010"))

নিজে বাড়ান:

একটা binary increment TM লিখুন (101 → 110) আর m_incr-এর পাশাপাশি একই universal_simulate-এ চালান
একটা palindrome-checker TM লিখুন (দুই প্রান্ত থেকে ভেতরের দিকে symbol মিলিয়ে, X দিয়ে mark করে — {0,1} ভাষায় {0011ⁱ...} এর বদলে সরাসরি palindrome)
TuringMachine object-কে সত্যিকার একটা string (তার আক্ষরিক encoding, JSON-এর বদলে) বানিয়ে সেটাকে একটামাত্র tape-এ ⟨M⟩#w আকারে লিখুন, আর universal_simulate-কে বদলে দিন যাতে এটা সেই encoded string parse করে নিজের delta বানায় — এখন আপনার কাছে একটা “সত্যিকার” tape-based universal TM আছে
max_steps timeout হলে বার্তায় লিখুন — “এটা সিদ্ধান্তহীন প্রমাণ, এই মেশিন কখনো থামবে না তার প্রমাণ নয়” — কেন এই পার্থক্যটা গুরুত্বপূর্ণ তা এক প্যারায় লিখুন (হ্যালটিং প্রবলেম লেসনের প্রস্তুতি)

বাস্তব সিস্টেমে

Universal TM থেকে stored-program computer

এই ধারণাটা — একটা মেশিন যা নিজের tape-এ পড়া “প্রোগ্রাম” অনুযায়ী আচরণ বদলায় — কম্পিউটার আর্কিটেকচারের সবচেয়ে মৌলিক সিদ্ধান্তের তাত্ত্বিক পূর্বপুরুষ: von Neumann architecture, যেখানে program আর data একই মেমরিতে থাকে।

Universal TM-এর ধারণা কীভাবে stored-program computer-এ নামল

Universal Turing Machine (১৯৩৬)⟨M⟩ tape-এ ডেটা হিসেবে এনকোড করা — U নিজে fixed, শুধু ইনপুট বদলে ভিন্ন আচরণ
ENIAC (১৯৪৫)বিপরীত ডিজাইন — "প্রোগ্রাম" ছিল physical wiring/switch, বদলাতে দিন লাগত
Von Neumann architecture (১৯৪৫)প্রোগ্রাম ইনস্ট্রাকশনকে সংখ্যা হিসেবে সেই একই মেমরিতে রাখা যেখানে data থাকে
আধুনিক CPU — fetch-decode-execute cyclePC রেজিস্টার মেমরি থেকে instruction "পড়ে" — ঠিক U যেমন tape থেকে ⟨M⟩-এর পরের নিয়ম পড়ে
JIT compiler, self-modifying code, eval()প্রোগ্রাম রানটাইমে নিজেকে ডেটা হিসেবে দেখে/বদলায় — universality-র সরাসরি প্রয়োগ

এই সংযোগটা কাকতালীয় নয়। Turing নিজে ১৯৪৫-৪৬ সালে (Bletchley Park-এ কোডব্রেকিং-এর পর) ACE (Automatic Computing Engine) ডিজাইনের প্রস্তাবে সরাসরি universal TM-এর ধারণা প্রয়োগ করেছিলেন — একটা মেশিন যার program মেমরিতে ডেটা হিসেবেই থাকবে, hardware wiring হিসেবে না। Computer-architecture module-এর ISA লেসনে এই একই নীতি ফিরে আসে “fetch” ধাপ হিসেবে — PC যা নির্দেশ করে সেই মেমরি ঠিকানা থেকে next instruction পড়া, ঠিক যেমন universal TM-এর head ⟨M⟩ অংশ থেকে পরবর্তী নিয়ম পড়ে।

Turing completeness — বাস্তব জগতের একটা মজার পরিণতি। যেকোনো সিস্টেম যেটা একটা universal TM simulate করতে পারে তাকে বলা হয় “Turing-complete”। এই তালিকাটা প্রায়ই আশ্চর্যজনক:

C++ template metaprogramming — compile-time-এই Turing-complete, মানে একটা C++ compiler টেমপ্লেট resolve করতে গিয়ে infinite loop-এ আটকাতে পারে
Conway’s Game of Life — cellular automaton-এর সরল নিয়ম দিয়েও একটা universal TM বানানো সম্ভব প্রমাণিত হয়েছে
Magic: The Gathering, PowerPoint animation, CSS (with HTML checkbox hacks), এক্সেল spreadsheet formula — সবগুলোই আনুষ্ঠানিকভাবে Turing-complete প্রমাণিত, বিনোদনমূলক গবেষণাপত্রে
SQL (recursive CTE সহ), regular expression engine (backreference সহ, শুধু regular নয়) — practical language যা মূল তাত্ত্বিক category ছাড়িয়ে গেছে

গুরুত্বপূর্ণ সতর্কতা: Turing-complete হওয়া মানে “কার্যত যেকোনো কিছু efficiently করা যায়” না — শুধু মানে “নীতিগতভাবে (given unlimited time/memory) যা গণনাযোগ্য তার সব গণনা করা যায়”। CSS-এ Turing-complete গণনা সম্ভব প্রমাণ করা একটা curiosity, প্রোডাকশন কোডে CSS দিয়ে sorting algorithm লেখার পরামর্শ নয়।

Compiler আর interpreter-এ

প্রতিটা programming language interpreter আসলে একটা universal machine-এরই একটা প্র্যাক্টিক্যাল রূপ — Python interpreter নিজে একটা fixed প্রোগ্রাম, যা ইনপুট হিসেবে (আপনার লেখা) .py ফাইল নেয় আর সেই “encoded program”-কে চালায়। Compilers module-এ আমরা দেখব কীভাবে একটা compiler নিজে একটা programming language-এ লেখা (self-hosting) — এটাও universal TM-এর সেই একই self-referential কাঠামোর একটা ব্যবহারিক ঝলক।

যে ভুলগুলো সবাই করে

“Turing machine-এর tape অসীম, তাই কোনো real computer আসলে Turing machine নয় — এই মডেলটা তাত্ত্বিক কল্পকাহিনী, প্র্যাক্টিক্যাল প্রাসঙ্গিকতা নেই।”

আংশিক সত্য, কিন্তু ভুল সিদ্ধান্তে নিয়ে যায়।

হ্যাঁ, কোনো বাস্তব কম্পিউটারের মেমরি সসীম — কঠোরভাবে বললে প্রতিটা বাস্তব কম্পিউটার একটা বিশাল কিন্তু সসীম-state finite automaton, Turing machine নয়।

কিন্তু TM মডেলের আসল উদ্দেশ্য বাস্তব হার্ডওয়্যার বর্ণনা করা নয় — একটা প্রশ্নের সীমা টানা: “নীতিগতভাবে, মেমরি বাধা না থাকলে, কী গণনাযোগ্য?” এই প্রশ্নটা অত্যন্ত প্র্যাক্টিক্যাল, কারণ এটাই বলে দেয় — আজকে যদি halting problem অমীমাংসিত (undecidable) হয়, তাহলে আগামীকাল আরো বড় RAM কিনলেও সেটা মীমাংসিত হবে না। সসীম মেমরির সীমাবদ্ধতা সমস্যাটাকে সহজ করত না, শুধু আকারে ছোট করত — মূল মডেলের সিদ্ধান্তগুলো (decidable/undecidable) মেমরির আকারের উপর নির্ভরই করে না।

একটা কাছাকাছি, সসীম-memory মডেলও আছে — linear bounded automaton (LBA), যেখানে tape input-এর দৈর্ঘ্যের সমানুপাতিক আকারে সীমাবদ্ধ। LBA প্রকৃতপক্ষেই আসল কম্পিউটারের কাছাকাছি একটা মডেল, আর তার decidability-র প্রশ্নগুলো ভিন্ন (এবং এখনো আংশিক খোলা!)। কিন্তু “গণনা কী” প্রশ্নের জন্য অসীম-tape TM-ই মানসম্মত উত্তর, কারণ এটা মেমরির আকার নিয়ে একটা স্বেচ্ছাচারী সিদ্ধান্তে আটকে থাকে না।

“Nondeterministic TM deterministic TM-এর চেয়ে বেশি ভাষা চেনে।”

না — computability-র দিক থেকে হুবহু একই ভাষার সেট চেনে। এই লেসনের “hood” অংশে দেখা BFS simulation argument-টাই প্রমাণ — যেকোনো NTM-এর জন্য একটা সমতুল্য DTM বানানো যায় যা একই ভাষা চেনে (শুধু সূচকীয় ধীরগতিতে)।

যেটা সত্যি: NP (nondeterministic polynomial time) আর P (deterministic polynomial time) সম্ভবত ভিন্ন — কিন্তু সেটা efficiency নিয়ে প্রশ্ন (একটা সমস্যা কত দ্রুত সমাধান করা যায়), computability নিয়ে নয় (সমস্যাটা আদৌ সমাধানযোগ্য কি না)। এই দুইটাকে গুলিয়ে ফেলা এই module-এর সবচেয়ে সাধারণ বিভ্রান্তি — পরবর্তী লেসনগুলোতে (complexity classes) এই পার্থক্যটা আরো স্পষ্ট হবে।

“Universal Turing machine একটা বিশেষ, আরো শক্তিশালী ধরনের মেশিন।”

না — universal TM নিজেও একটা সাধারণ TM, নিজস্ব সসীম state সেট আর transition function সহ। এর “universality” কোনো অতিরিক্ত computational power থেকে আসে না — আসে এই ঘটনা থেকে যে এর tape-এর একটা অংশে অন্য একটা TM-এর বর্ণনা এনকোড করে দেওয়া হয়েছে, ইনপুট হিসেবে।

উপমা: একটা Python interpreter নিজেও একটা প্রোগ্রাম (C-তে লেখা, সসীম কোড) — এটা “সবচেয়ে শক্তিশালী প্রোগ্রাম” নয়, এটা একটা সাধারণ প্রোগ্রাম যেটা অন্য প্রোগ্রামের (আপনার .py ফাইল) বর্ণনা ডেটা হিসেবে নিয়ে সেটা অনুসরণ করে। ঠিক একইভাবে universal TM-ও “সাধারণ”, শুধু তার ইনপুট বিশেষভাবে ব্যাখ্যা করা হয়।

“Multi-tape TM single-tape TM-এর চেয়ে বেশি শক্তিশালী, কারণ এটা 'বাস্তবে' জটিল কাজ করতে পারে যা single tape পারে না।”

আবারও, computability-র দিক থেকে সমতুল্য — যেকোনো k-tape TM-কে একটা single-tape TM দিয়ে simulate করা যায় (polynomial slowdown সহ, O(t²))।

এই ভুল ধারণাটা প্রায়ই আসে কারণ multi-tape TM-এ অ্যালগরিদম লেখা সত্যিই সহজ — একটা tape input-এর জন্য অক্ষত রাখা, আরেকটাতে scratch কাজ করা প্র্যাক্টিক্যালি অনেক পরিষ্কার। এটা programmer-এর সুবিধা, কিন্তু কী গণনাযোগ্য তার সংজ্ঞা বদলায় না — ঠিক যেমন একটা higher-level language-এ প্রোগ্রাম লেখা সহজ, কিন্তু assembly-তে লেখা প্রতিটা প্রোগ্রামও (turing-complete হলে) একই ক্ষমতার।

বুঝেছেন কি না দেখুন

Turing machine-এর 7-tuple সংজ্ঞায় δ-এর ধরন কী? এটা DFA-এর transition function থেকে ঠিক কী কী দিক দিয়ে আলাদা?

স্মরণ

δ : Q × Γ → Q × Γ × {L, R}।

DFA-র δ : Q × Σ → Q-এর সাথে তিনটা পার্থক্য:

Output-এ নতুন state-এর পাশাপাশি একটা লেখার symbol আছে — TM tape বদলাতে পারে, DFA-র input tape শুধু পড়া হয়, কখনো লেখা হয় না
Output-এ একটা movement direction আছে (L/R) — DFA-তে head সবসময় শুধু ডানে যায় (implicit, কোনো choice নেই)
Domain-এ Σ-এর বদলে Γ — TM tape-এ শুধু input symbol না, কাজের সময় লেখা অতিরিক্ত symbol-ও (যেমন X, Y, blank) থাকতে পারে

এই পার্থক্যগুলোই TM-কে “read-only, one-directional” থেকে “read-write, bidirectional” বানায় — আর ঠিক এই অতিরিক্ত ক্ষমতাটাই TM-কে PDA-র চেয়েও বেশি ভাষা (recursively enumerable) চেনার যোগ্য করে।

লেসনের {0ⁿ1ⁿ} মেশিনটা input "0110"-এ চালালে কী ঘটবে? ধাপে ধাপে বলুন কোথায় reject হয় এবং কেন।

প্রয়োগ

Trace:

q0 পড়ে 0 (position 0) → লেখে X, move R, state q1। Tape: X110, head=1
q1 পড়ে 1 (position 1) → লেখে Y, move L, state q2। Tape: XY10, head=0
q2 পড়ে X (position 0) → move R, state q0। head=1
q0 পড়ে Y (position 1) → move R, state q3। head=2
q3 পড়ে 1 (position 2) — q3-এর table-এ 1-এর জন্য কোনো entry নেই (“Y” আর ”⊔” ছাড়া) → reject

কেন এটা সঠিক: "0110" 0ⁿ1ⁿ-এর প্যাটার্নে নেই (এটা 0, তারপর 1, তারপর 1, তারপর 0 — অর্থাৎ 01-এর পরে আরেকটা 10)। প্রথম 0-1 জোড়া মিলে যাওয়ার পর, machine q3-এ ঢুকে বাকি tape-এ শুধু Y (crossed marks) আর blank আশা করে — কিন্তু একটা raw 1 (এবং পরে 0) পেয়ে যায়, যা প্রমাণ করে uncrossed অংশে এখনো 0/1 আছে — তাই সঠিকভাবে reject।

একজন সহপাঠী দাবি করছেন: “যেহেতু nondeterministic TM simulate করতে deterministic TM-এর সূচকীয় সময় লাগে, তার মানে NTM ‘বেশি শক্তিশালী’। ‘শক্তিশালী’ শব্দটার দুইটা ভিন্ন অর্থ এখানে গুলিয়ে যাচ্ছে — কী কী, আর কোনটা এখানে প্রযোজ্য?

যুক্তি

“শক্তিশালী” শব্দটার দুইটা সম্পূর্ণ ভিন্ন গাণিতিক অর্থ:

অর্থ ১ — computational power (কোন ভাষার সেট চেনা যায়): এই অর্থে NTM আর DTM সমান শক্তিশালী। প্রতিটা NTM-এর জন্য একটা সমতুল্য DTM আছে যা ঠিক একই ভাষা চেনে (BFS simulation)। কোনো ভাষা নেই যা NTM চেনে কিন্তু কোনো DTM-ই চিনতে পারে না।

অর্থ ২ — computational efficiency (কত দ্রুত): এই অর্থে NTM “বেশি শক্তিশালী” মনে হতে পারে — একই ভাষা NTM অনেক কম সময়ে (nondeterministic ভাবে) চিনতে পারে, DTM-কে সেই একই ভাষা চিনতে সূচকীয় বেশি সময় লাগতে পারে (যতদূর জানা)।

সহপাঠীর বিভ্রান্তি: প্রথম বাক্যে “সূচকীয় সময় লাগে” বলে efficiency-র কথা বলছেন, তারপর “শক্তিশালী” শব্দে অর্থ ১-এ লাফ দিচ্ছেন। সঠিক দাবি হলো: “NTM আর DTM computability-তে সমতুল্য, কিন্তু efficiency-তে (possibly) ভিন্ন — আর ঠিক এই দ্বিতীয় প্রশ্নটাই P বনাম NP-এর বিষয়বস্তু, যেটা এখনো একটা খোলা গাণিতিক সমস্যা।”

{ww : w ∈ {0,1}*} (যেকোনো string নিজের সাথে জোড়া লাগানো, যেমন 0110 0110) ভাষাটার জন্য একটা TM-এর অ্যালগরিদম (ইংরেজি বর্ণনা, পুরো transition table না) ডিজাইন করুন। কেন এই ভাষাটা PDA দিয়ে চেনা যায় না (শুধু TM দিয়ে) তার একটা স্বজ্ঞাত কারণ দিন।

ডিজাইন

অ্যালগরিদম (multi-tape ব্যবহার করলে সহজ, তারপর single-tape-এ অনুবাদযোগ্য বলে জানি):

প্রথমে tape scan করে মোট দৈর্ঘ্য জোড় (even) কি না যাচাই করুন (না হলে সরাসরি reject — ww-এর দৈর্ঘ্য সবসময় জোড়)
মাঝের বিন্দু খুঁজে বের করুন — দুই প্রান্ত থেকে একসাথে ভেতরের দিকে হাঁটুন (দুইটা “কাউন্টার” style marker ব্যবহার করে) যতক্ষণ না তারা মিলে যায়
এখন প্রথমার্ধের প্রথম symbol আর দ্বিতীয়ার্ধের প্রথম symbol compare করুন — একটা mark করে (crossed), অন্যটা mark করে, এগিয়ে যান
প্রতিটা জোড়া মিললে accept, কোথাও না মিললে reject

কেন PDA পারে না: PDA-র stack একটামাত্র “দিক থেকে” access পায় (LIFO — শুধু top)। ww চেক করতে প্রথমার্ধ পড়ে stack-এ push করলে, দ্বিতীয়ার্ধের সাথে compare করার সময় stack থেকে উল্টো ক্রমে (LIFO pop) বেরোবে — এটা w wᴿ (palindrome) চেক করার জন্য উপযুক্ত, কিন্তু ww (একই ক্রমে দুইবার) চেক করার জন্য না। এই অসামঞ্জস্যটাই মূল কারণ — stack-ভিত্তিক memory-র “স্বাভাবিক” আকৃতি reversal-এর সাথে মেলে, repetition-এর সাথে না। TM-এর tape-এ এই সমস্যা নেই কারণ tape-এ যেকোনো ক্রমে আগের লেখা আবার পড়া যায় (random-access-এর মতো আচরণ), stack-এর বাধ্যতামূলক LIFO ক্রম নেই।

(আনুষ্ঠানিক প্রমাণ pumping lemma for context-free languages দিয়ে হয় — সেটা আগের লেসনের বিষয়।)

একটা single-tape TM k=3 tape-এর একটা multi-tape TM-কে simulate করছে, যেটা t = 1000 step-এ থামে। Simulation-এ single-tape TM-এর আনুমানিক কত step লাগবে (big-O না, একটা সংখ্যার order দিন), আর কেন এই সংখ্যাটাই decidability-র প্রশ্নে গুরুত্বপূর্ণ নয়, কিন্তু practical performance-এ গুরুত্বপূর্ণ?

প্রয়োগ

O(t²) simulation cost অনুযায়ী, t = 1000-এ প্রায় 10⁶ (দশ লক্ষ) step লাগবে single-tape সিমুলেশনে — মূল মেশিনের চেয়ে ১০০০ গুণ বেশি, কিন্তু এখনো সসীম, পরিমাপযোগ্য সংখ্যা।

কেন decidability-তে গুরুত্বপূর্ণ নয়: একটা ভাষা “decidable” কি না — অর্থাৎ কোনো TM আদৌ সসীম সময়ে থামে কি না — এই প্রশ্নের উত্তর polynomial factor-এ বদলায় না। t সসীম হলে t²-ও সসীম; মেশিন থামে কি না এই বাইনারি প্রশ্নে polynomial slowdown কোনো প্রভাব ফেলে না। তাই “multi-tape না single-tape” এই পার্থক্যটা এই মডিউলের আগামী কয়েক লেসনে (decidability, halting problem) সম্পূর্ণ অপ্রাসঙ্গিক — যেকোনো TM variant দিয়ে প্রমাণ করলেই চলবে।

কেন practical performance-এ গুরুত্বপূর্ণ: বাস্তব সফটওয়্যারে O(t) বনাম O(t²) পার্থক্যটা সেকেন্ড বনাম দিনের পার্থক্য হতে পারে। এটাই কারণ যে জটিল অ্যালগরিদম বাস্তবে multi-tape-এর মতো “একাধিক ওয়ার্কিং এরিয়া” ব্যবহার করে লেখা হয় (যেমন একাধিক array/ buffer একসাথে ব্যবহার করা) — না হলে single-tape-এর মতো একটামাত্র রৈখিক মেমরি দিয়ে সবকিছু সামলাতে গেলে বাস্তব প্রোগ্রামও ধীর হয়ে যেত। Complexity theory-তে (পরের কয়েক লেসন পরে) আমরা দেখব polynomial factor উপেক্ষা করাটা একটা ইচ্ছাকৃত সরলীকরণ — “কী গণনাযোগ্য” প্রশ্নে সাহায্য করে, “কত দ্রুত” প্রশ্নে আলাদাভাবে গুরুত্ব দিতে হয়।

এরপর কী

আমরা এখন জানি Turing machine কী, কীভাবে ডিজাইন করতে হয়, আর কেন multi-tape/nondeterminism নতুন ক্ষমতা যোগ করে না। কিন্তু একটা গভীর প্রশ্ন এখনো উত্তরহীন: কেন বিশ্বাস করব যে TM “সবকিছু” গণনা করতে পারে? আমরা শুধু দেখিয়েছি TM অনেক কিছু গণনা করতে পারে (উদাহরণ দিয়ে) — কিন্তু “সবকিছু” একটা সর্বজনীন দাবি, যা উদাহরণ দিয়ে প্রমাণ করা যায় না।

পরের লেসনে আমরা Church-Turing thesis দেখব — একটা দাবি যা গণিতের কোনো উপপাদ্যের মতো প্রমাণিত নয় (প্রমাণ করা যায় না, কারণ “algorithm”-এর কোনো স্বাধীন, পূর্ব-আনুষ্ঠানিক সংজ্ঞা নেই যার বিরুদ্ধে তুলনা করা যায়), বরং একটা অভিজ্ঞতালব্ধ (empirical) দাবি — এবং কেন independently আবিষ্কৃত একাধিক মডেল (Turing machine, lambda calculus, general recursive functions) সবাই সমতুল্য প্রমাণিত হওয়াটাই এর পক্ষে সবচেয়ে শক্তিশালী প্রমাণ।

Turing Machine — গণনার সবচেয়ে সরল আনুষ্ঠানিক মডেল

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

আনুষ্ঠানিক সংজ্ঞা

ভাষা গ্রহণ — accept, reject, আর loop

ভেতরে কী ঘটছে

কেন এত সরল কিছু এত শক্তিশালী

Variant — বেশি ক্ষমতা মনে হয়, কিন্তু নেই

Multi-tape TM

Nondeterministic TM (NTM)

Two-way infinite tape, বনাম half-infinite

উদাহরণ

হাতে একটা TM বানানো — `{0ⁿ1ⁿ : n ≥ 0}`

Trace — input `0011`

নিজে চালিয়ে দেখুন

TM simulator লিখে হাতে-করা trace যাচাই করুন

নিজে বানান

Universal Turing Machine simulator — encoded ⟨M, w⟩ থেকে সিমুলেশন

বাস্তব সিস্টেমে

Universal TM থেকে stored-program computer

Compiler আর interpreter-এ

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

আনুষ্ঠানিক সংজ্ঞা

ভাষা গ্রহণ — accept, reject, আর loop

⚙ভেতরে কী ঘটছেUnder the hood

কেন এত সরল কিছু এত শক্তিশালী

Variant — বেশি ক্ষমতা মনে হয়, কিন্তু নেই

Multi-tape TM

Nondeterministic TM (NTM)

Two-way infinite tape, বনাম half-infinite

▶উদাহরণExample

হাতে একটা TM বানানো — {0ⁿ1ⁿ : n ≥ 0}

Trace — input 0011

⌘নিজে চালিয়ে দেখুনExperiment

TM simulator লিখে হাতে-করা trace যাচাই করুন

⚒নিজে বানানBuild it yourself

Universal Turing Machine simulator — encoded ⟨M, w⟩ থেকে সিমুলেশন

◉বাস্তব সিস্টেমেReal-world usage

Universal TM থেকে stored-program computer

Compiler আর interpreter-এ

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

হাতে একটা TM বানানো — `{0ⁿ1ⁿ : n ≥ 0}`

Trace — input `0011`

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী