For thousands of years, computing was done with pen and paper, chalk and slate, or even mentally, sometimes with the aid of tables. The theory of computation began early in the twentieth century, before modern electronic computers had been invented. At that time, mathematicians were trying to find which math problems could be solved by simple methods and which could not. The first step was to define what was meant by a "simple method" for solving a problem, implying a need for a formal model of computation.

Several different computational models were devised by these early researchers. One model, the Turing machine, stores characters on an infinitely long tape, with one square at any given time being scanned by a read/write head. Another model, recursive functions, uses functions and function composition to operate on numbers. The lambda calculus uses a similar approach. Still others, including Markov algorithms and tag systems, use grammar-like rules to operate on strings. All of these formalisms were shown to be equivalent in computational power -- that is, any computation that can be performed with one can be performed with any of the others.