A Machine on Paper, and a Limit on Procedures
Turing's 1936 abstract model of computation
In his 1936 work, Alan Turing described abstract machines to investigate effective computation. These were mathematical devices, not physical computers assembled from motors, wires, or electronic components.
Imagine a clerk following written instructions to sort names without improvising. Describing each permitted step helps distinguish a repeatable procedure from an intuitive judgment. A mathematical model studies the procedure's possibilities without requiring an actual clerk or office to exist.
A machine followed specified rules while reading and writing symbols on a tape. The model made an informal idea of carrying out instructions precise enough to examine.
Turing also described a universal machine capable of simulating other such machines. Instructions could themselves be represented as symbols, linking the description of a procedure with its execution.
His argument established limits as well as possibilities. There is no general effective procedure that decides every instance of the mathematical decision problem he investigated.
Related formalisms developed by Alonzo Church and Emil Post strengthened the study of computability. The foundation grew through converging approaches rather than one isolated intellectual achievement.
A recipe may specify a finite way to compare every possible schedule for a workplace. With enough employees, completing it could take an impractical amount of time. Having a procedure and having a usable solution are different achievements.
Computable in principle does not mean feasible in practice. The model idealizes available memory and time, while physical machines must work within material and operational limits.
Later computers made programmable procedures enormously useful, but their engineering had many contributors. Turing's abstract model should not be mistaken for the sole invention of modern hardware.
Formal computation also does not settle every question about human judgment. Defining a task mechanically may leave unresolved which goals, meanings, or values the procedure should serve.
Human reasoning and mathematical work continued beyond the model's immediate scope. A proof about procedures neither promises automatic answers to everything nor declares all inquiry futile.
Turing's shift gave clearer language for asking what computation can accomplish. Its significance includes disciplined optimism about machines and equally disciplined recognition of their boundaries.
Further reading
How should we distinguish tasks worth formalizing into procedures from decisions whose practical constraints or human purposes require additional kinds of judgment?