 The mathematical model for a “universal” computer was defined long before the invention of computers and is called the  Turing machine  (Turing 1936). A Turing machine consists of an unbounded tape, a head capable of reading from and writing to it which can occupy one of a potentially infinite number of possible states, and an instruction table (i.e. a transition function). This table, given the head’s initial state and the input it reads from the tape in that state, determines (a) the symbol that the head will write on the tape, (b) the internal state it will occupy, and (c) the displacement of the head on the tape. In 1936 Turing showed that since one can encode the instruction table of a Turing machine \(T\) and express it as a binary number \(\#(T)\), there exists a universal Turing machine \(U\) that can simulate the instruction table of any Turing machine on any given input. That the Turing machine model captures the concept of computability in its entirety is the essence of the  Church-Turing thesis,  according to which any effectively calculable function can be computed using a Turing machine. Admittedly, no counterexample to this thesis (which is the result of convergent ideas of Turing, Post, Kleene and Church) has yet been found. But since it identifies the class of computable functions with the class of those functions which are computable using a Turing machine, this thesis involves both a precise mathematical notion and an informal and intuitive notion, hence cannot be proved or disproved. Simple cardinality considerations show, however, that not all functions are Turing-computable (the set of all Turing machines is countable, while the set of all functions from the natural numbers to the natural numbers is not), and the discovery of this fact came as a complete surprise in the 1930s (Davis 1958).