What is computation?
The cuts
Computation is what a universal machine can do: any procedure that can be written as steps can be mechanized — by one machine that can imitate them all.
Made 'computable' a precise property of problems rather than machines, and made the modern computer conceivable.
On Computable Numbers, with an Application to the Entscheidungsproblem1936
Computation is the evaluation of functions built from pure substitution — the λ-calculus.
A second, machine-free road to the same boundary. Their equivalence became the Church–Turing thesis.
An Unsolvable Problem of Elementary Number Theory1936
Computation is not something minds use. It is what minds are — patterns implementing themselves.
Turns a mathematical question into an ontological one: if minds compute, what isn't computation?
Principles of Synthetic Intelligence: PSI, An Architecture of Motivated Cognition2009The tensions
Before 1936, ‘to compute’ was something clerks did. Turing’s cut made it a property of the universe: any stepwise procedure can be mechanized, and a single universal machine can run them all. Church reached the same boundary without imagining a machine at all.
The question reopened when minds entered the picture. If everything rule-like is computable, is a mind rule-like? Bach’s lens states today’s stakes plainly: perhaps the question was never what machines can do, but whether ‘machine’ was ever the right boundary to draw.
