math

Turing machine

A Turing machine is an abstract computational model that manipulates symbols on a tape.
4 related articles · 1 who worked here

Description

Formally, a Turing machine consists of an infinite tape divided into cells, each containing a symbol from a finite alphabet; a control unit with finite state memory; and a head capable of reading, writing, and shifting by one cell. The transition function determines, based on the current state and the read symbol, a new symbol, the direction of head movement (L/R), and a new state. The machine starts with an input word on the tape and may halt in an accepting or rejecting state, or get stuck in an infinite loop. A universal Turing machine can simulate any other machine given its description — anticipating the concept of a programmable computer.

History

In 1936, Alan Turing, solving David Hilbert's Entscheidungsproblem (decision problem), introduced the notion of an 'a-machine' (automatic machine) in his paper 'On Computable Numbers'. His goal was to formalize the intuitive concept of an algorithm. Independently, Alonzo Church arrived at an equivalent notion via λ-calculus. The Church-Turing thesis asserts that any intuitively computable process can be implemented on a Turing machine. In 1945, John von Neumann used this model in the EDVAC architecture — the prototype of modern computers. In 1985, David Deutsch proposed a quantum Turing machine, paving the way for quantum computing.

How it works

A Turing machine computes by manipulating symbol strings. Algorithmically, it is equivalent to a programming language with a single array of infinite length. Key properties: existence of a universal machine (interpreter), undecidability of the halting problem (one cannot algorithmically determine whether an arbitrary machine halts on a given input), the recursion theorem (a machine can obtain its own description). In complexity theory, one considers oracle machines (with extra information) and probabilistic machines (with a random bit source). Quantum Turing machines operate on states in a Hilbert space and use unitary transformations; they do not violate the Church-Turing thesis but may provide exponential speedup for certain problems.

In practice

Any computer program — from a calculator to an AI assistant — reduces to instructions that a Turing machine can execute. The entire theory of computation is based on it.

Fun fact

The simplest universal Turing machine, devised by Marvin Minsky, uses only 7 states and 4 symbols — and yet it can compute everything a powerful supercomputer can, albeit incredibly slowly.

Concept graph →

Related articles · 16

Four Conductors of the Cellular Orchestra: How Epithelium Chooses Its Path to Fluidity
Epithelium lines our organs like tiles on a floor. At rest, cells cling to each other, and the tissue is elastic. But during embryonic development, wound healing, or tumor growth, this layer begins to flow like thick honey. What exactly triggers such softening?
cs.GL2026-07-133 minarXiv:2607.13089
Restoring the Z3: How Relay Clicks Brought a Lost Computer Back to Life
Berlin, December 1943. A bomb flash, and the first fully automatic programmable computer in history, the Z3, vanishes in flames. Its creator, Konrad Zuse, doesn’t even try to rebuild the hardware: after the war, he constructs new machines. But the idea of the Z3—like a lost painting, with only sketches and memories left — awaits its moment.
cs.OS2026-07-063 minarXiv:2607.04668
Orchestra Without a Conductor: An Elastic Gang for LLM Inference
Seven cores froze at an invisible barrier. The eighth lingered on someone else's process, and the entire LLM inference hung. That's the central collision of machine learning tasks and ordinary processes sharing a CPU. An inference gang demands that all cores strike in perfect unison — otherwise silence.
math.FA2026-06-302 minarXiv:2607.00123
Threshold 2: How a Rubber Ruler Withstands Endless Averaging
2 is the threshold beyond which a well-behaved sequence risks losing its structure. Instead of the usual uniform scale, picture a rubber ruler with uneven elasticity. That's exactly how Orlicz spaces work: Banach spaces of sequences where each scale has its own stiffness, described by a convex Young function (a kind of spring).
q-bio.QM2026-05-221 minarXiv:2605.23745express
A Chemical Computer in a Test Tube
Molecules float in a test tube. Their abundance (say, the concentration of some protein) becomes the input signal. And the output isn't just a cloudy solution but a clear yes-or-no answer. The authors build a chemical cascade that does exactly that.
Handwriting Without an Alphabet: How the Brain Draws Letters It Has Never Seen
The hand traces the word "mom" in the air — familiar arcs and strokes. The brain, meanwhile, is not flipping through a photo of each letter. It launches a chain of simple movements.
Statistical Mech2026-05-092 minarXiv:2605.09105express
How to Stop Molecular Motors from Spinning Their Wheels
Inside every cell, life is bustling: tiny protein machines tirelessly haul cargo, read genes, and fix errors. But their work is far from perfect: they often 'spin their wheels,' take backward steps, or get stuck in futile cycles. It's like a city traffic jam where cars dart around aimlessly, burning fuel.
Statistical Mech2026-05-092 minarXiv:2605.09148express
How to Tune a Molecular Motor Without Losing Your Mind
Imagine a factory where hundreds of tiny assembly lines run nonstop. Each line is a molecular motor that converts chemical fuel into motion. To make the motor go faster or in the right direction, an engineer tweaks the settings — the shape of parts, the strength of interactions.
Artificial Intelligence Paves the Way for Optical Chips
A laser beam is split into dozens of thin filaments, passes through frosted glass, and reconverges to a single point. This is the workbench where the program took a seat. It received no instructions — only a general goal: figure out how light changes when passing through a scattering medium, and find something new.
Atomic Physics2026-04-241 minarXiv:2604.22406express
Atom Traps: How to Fill Them to the Brim
An optical tweezer is a laser beam that holds an atom in place, much like fingers holding a pea. Arrays of these tweezers form the basis of future quantum computers. But there's a catch: not every tweezer catches an atom. Typically, only half of the traps get filled, and for molecules, even fewer. Empty spots break the whole setup.
cs.ET2026-04-181 minarXiv:2604.17109express
The Machine That Doesn't Get in Its Own Way
An orchestra where each musician plays their own part but hears only the neighbor. One wrong note, and a wave of errors rolls through the hall. That's how Ising machines work — special devices for solving problems where you need to find the best option among many.
Quantum Physics2026-04-151 minarXiv:2604.13872express
Dance of Ions: How Quantum Vortices Are Born
In a field trap, scientists assembled a crystal — 150 ions at ultra-low temperature. Each ion behaves like a tiny magnet, capable of rotating in any direction. By controlling forces that depend on this rotation, physicists made all the magnets swirl into a common vortex called a skyrmion.
Ideas Nobody Was Looking For
Science is like a city where residents pave the streets themselves. Where paths are already worn, new houses go up, while untouched vacant lots go unnoticed — not because building there is impossible, but because no one ever looks.
stat.ME2026-02-191 minarXiv:2602.17772express
The Brain Prints Itself: How Electrode Pairs Speed Up Mind Reading
A person looks at a screen where letters flash. They don't move a hand or an eye: they only mentally note the desired symbol. Sensors on the head pick up the brain's faint electrical waves, and the computer figures out which letter the person chose. That's how a brain–computer interface works: it gives a voice to those who can't speak or move.
Superconductivity2026-01-101 minarXiv:2601.06632express
Superconducting Memory: A Switch That Never Forgets
Ordinary computer memory constantly consumes energy to avoid forgetting what's stored. A superconductor could store data without loss, but it's hard to make it switch. In the new work, a superconductor is sandwiched between two magnetic insulators.
Tunnel Resonance: How Diodes Learn to See
In 1974, physicists first described a device in which electrons pass through an energy barrier thanks to quantum tunneling. Today, that device, the resonant tunneling diode, is becoming the heart of an unusual computing architecture.