mechanisms are Turing complete [ 2]. One of the practical consequences of this is that hardware designers can largely ignore the issue of whether their instruction sets are universal (they are) and focus on finding instruction sets that can be made to run very quickly in hardware.

Of course this doesn’t preclude the
possibility that someone might some-
day come up with a radically different
design for a computer that couldn’t be
simulated by a Turing machine. But
thus far, every computational system
that’s been devised has either been
Turing complete (can simulate and be
simulated by any other Turing com-
plete system) or is weaker than a Tur-
ing machine (i.e. can’t simulate a Tur-
ing machine but can still be simulated
by a Turing machine). So it is generally
assumed that any function that can be
computed can be computed by a Tur-
ing machine. This is known as Church’s
Thesis, or sometimes as the Church-
Turing Hypothesis, after 20th century
meta-mathematician Alonzo Church.

THE LIMITS OF COMPUTATION
You may have noticed a certain care-
fulness of wording in our definition of
universality. We didn’t say that univer-
sal machines could compute anything,
only that they could compute anything
other machines could compute. It
turns out that not only are some prob-
lems provably uncomputable, but in a
sense it’s the very power of universal
machines that makes those problems
uncomputable.