Turing Machine

সাত-tuple (Q, Σ, Γ, δ, q0, q_accept, q_reject) — state সেট, input/tape alphabet, transition function (δ : Q × Γ → Q × Γ × {L,R}), start state, আর দুইটা বিশেষ state।

DFA/PDA-র চেয়ে তিনটা বাড়তি ক্ষমতা: অসীম memory, tape-এ যেকোনো দিকে movement, আর tape-এ লেখার ক্ষমতা। Multi-tape ও nondeterministic variant একই ভাষা চেনে (শুধু speed ভিন্ন) — computational power নয়, শুধু efficiency বদলায়।

Universal Turing machine — একটা TM যা tape-এ এনকোড করা অন্য যেকোনো TM-এর বর্ণনা পড়ে সেটা simulate করে। এই ধারণাটাই stored-program computer (von Neumann architecture)-এর তাত্ত্বিক পূর্বপুরুষ — Level 3-এর ISA লেসনের fetch-decode-execute cycle এই একই নীতির হার্ডওয়্যার রূপ।