Turing's most famous contribution is his definition [1936] of an
automatic machine (amachine), now called a Turing
machine. Less famous is Turing's very brief suggestion [1939, §4]
of an oracle machine (omachine), a Turing machine which
could consult an outside database which he called an "oracle". Post
[1944] took Turing's sketch and developed it into the theory of one
set B being reducible to another set A which he named
"Turing reducibility". The latter is the most important
concept in computability because it encompasses plain computability,
gives a model for accessing a data base which we do every time we go
the internet, and it enables us to measure the information content of
a mathematical structure. It allows us to measure the complexity of
algebraic structures, unsolvable problems in mathematics, Kolmogorov
complexity, and algorithmic complexity, objects in model theory, and
many other structures in mathematics and computer science.
