In 1936 an American (Alonzo Church) and a Briton (Alan M. Turing) published independently (as is often the coincidence in science) the basics of a new branch in Mathematics (and logic): computability or recursive functions (later to be developed into Automata Theory).

The authors confined themselves to dealing with computations which involved