Robert Irving Soare (University of Chicago)
Turing Computability and Information Content

Turing's most famous contribution is his definition [1936] of an automatic machine (a-machine), now called a Turing machine. Less famous is Turing's very brief suggestion [1939, §4] of an oracle machine (o-machine), 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.