Defining a mechanical procedure
In the 1930s, mathematicians investigated whether a definite procedure could decide every mathematical statement of a specified formal kind. Alan Turing began with the activities of a person calculating on paper, separating reading, writing and changing position into finite operations. His paper was received in 1936 and appeared in the journal volume dated 1937. It used computable numbers to investigate what mechanical procedures could accomplish.
Tape, states and rules
Turing’s machine has a tape divided into squares, each holding a symbol. In a particular state it reads one square, follows a rule to write or erase, moves left or right, and changes state. The tape supplies working records, while a finite set of rules determines each action. Complex calculations can thus be expressed as sequences of elementary operations, giving precise form to the idea of computing by a procedure.
References: [1]
One machine simulates other machines
The paper also encodes a machine’s rules as symbols. A universal machine reads such a description and simulates the corresponding operations. Supplying another description changes the computation without redefining the universal machine itself. Rules and inputs can both be represented on the tape. This separates a general computing mechanism from a particular task and provides a model for understanding programs and general-purpose computation.
References: [1]
Establishing limits of computation
Using machine descriptions and self-reference, Turing established that no uniform mechanical method solves the general decision problem. Alonzo Church reached related negative results through a different formal system, and Turing discussed the equivalence of their definitions. These investigations placed both the power and the limits of algorithms within mathematics: some tasks admit procedures, while others have no program that decides every instance.