Turing Machine
A theoretical model of computation used to define the limits of what can be calculated.
A Turing Machine is a theoretical computing device that manipulates symbols on an infinite tape according to a table of rules, serving as a foundational model for computation and defining the limits of what can be algorithmically computed.
graph LR
Center["Turing Machine"]:::main
Pre_computer_science["computer-science"]:::pre --> Center
click Pre_computer_science "/terms/computer-science"
Rel_antimatter_propulsion["antimatter-propulsion"]:::related -.-> Center
click Rel_antimatter_propulsion "/terms/antimatter-propulsion"
Rel_arpanet["arpanet"]:::related -.-> Center
click Rel_arpanet "/terms/arpanet"
Rel_artificial_consciousness["artificial-consciousness"]:::related -.-> Center
click Rel_artificial_consciousness "/terms/artificial-consciousness"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧒 5 yaşındaki gibi açıkla
It's like a super simple robot with a very long paper strip (tape) and a pencil; it follows a list of instructions to read, write, and move on the strip, and can do any calculation a real computer can.
🤓 Expert Deep Dive
The formal definition of a Turing machine $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$ involves a set of states $Q$, an input alphabet $\Sigma$, a tape alphabet $\Gamma$ (where $\Sigma \subseteq \Gamma$ and $B \in \Gamma \setminus \Sigma$ is the blank symbol), a transition function $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$, a start state $q_0 \in Q$, the blank symbol $B$, and a set of final/accepting states $F \subseteq Q$. The transition function dictates the machine's behavior: given the current state and the symbol read, it determines the next state, the symbol to write, and the direction to move the head (L for left, R for right). Undecidable problems, such as the Halting Problem, are formally proven to be unsolvable by any Turing machine, establishing the theoretical limits of computation. Variants like multi-tape Turing machines or non-deterministic Turing machines have equivalent computational power (can compute the same set of functions) but differ in efficiency or operational characteristics, forming the basis for complexity classes like P and NP.