Computation

Computation is the process of performing a sequence of steps to transform inputs into outputs according to a predefined set of rules. It encompasses both abstract procedures that exist independently of any physical device and concrete processes realized by machines. In mathematics and computer science, computation is studied as an abstract activity, focusing on what can be calculated and how efficiently.

Models of computation include Turing machines, lambda calculus, finite automata, and cellular automata. These models help formalize what it means for a problem to be computable. The Church-Turing thesis posits that any function that can be effectively computed by an algorithm can be computed by a Turing machine, a conjecture supported by equivalent formal systems.

Computational complexity analyzes resources required for computation, such as time and space. Problems are classified into complexity classes (P, NP, EXP, etc.) and into decidable or undecidable categories. Algorithms are designed to solve problems within resource constraints, and the field studies lower bounds and efficiency.

History and applications: computation emerged from mathematical reasoning and later mechanical and electronic devices. Key milestones include the work of Charles Babbage, Alan Turing, Alonzo Church, and John von Neumann. Today, computation underpins information processing, science, engineering, cryptography, data analysis, AI, and simulations. Emerging areas include quantum computation, probabilistic models, and information-theoretic approaches.