a universal Turing machine

Every Turing machine we have met so far is a special-purpose gadget: this one tests a^n b^n, that one adds two numbers. Each is like a single-purpose appliance, a toaster that can only toast. Now imagine one machine that is not built for any particular task, but instead reads a description of any other machine and then behaves exactly as that machine would. It is the appliance that becomes a toaster, a blender, or a radio depending on the manual you hand it. That is a universal Turing machine.

A universal Turing machine U takes as input the encoding of a machine M together with an input w, written <M, w>, and simulates M running on w. Internally U keeps three things on its tape(s): a copy of M's transition rules (the 'program'), the current contents of M's tape, and a marker for M's current state and head position. To take one step of M, U scans the rules to find the one matching M's current state and scanned symbol, then updates the simulated tape, state, and head accordingly, over and over. If M would accept, U accepts; if M would reject, U rejects; if M loops forever, so does U.

This is one of the most consequential ideas in computer science. A universal machine is the theoretical ancestor of the stored-program computer: the modern insight that one fixed piece of hardware can run any program, because the program is just data fed to a universal interpreter, is exactly universality. It is also the engine of self-reference at the heart of undecidability, since a universal machine can be told to simulate a machine on its own description. The honest caveat: universality is about what U can do, not how fast, simulating M costs U overhead per step, so U is slower than M (though, for the standard construction, only by a modest factor). And U does not escape M's fate: if M never halts on w, neither does U.