Neblux Knowledge Graph
Computation
Computation is the rule-governed manipulation or transformation of representations, formalized in the 1930s through foundational models such as Turing machines and Alonzo Church's lambda calculus.
Overview
The Church-Turing thesis posits that effectively calculable functions correspond to functions computable by a Turing machine, establishing formal boundaries for computability. Computational complexity theory categorizes problems by the resource bounds required to solve them, prominently investigated through the open P versus NP problem.
Why it matters
Formal models of computation inform complexity analysis and algorithm design across mathematics and computer science. The concept also serves as an analytic framework in biology, physics, and philosophy of mind to model rule-governed transformations in natural systems.
What it builds on
Where it leads
Related concepts
- AlgorithmconceptualAlgorithms are the procedural specifications that define specific computations, giving concrete form to abstract computational processes
- Information (Shannon Theory)conceptualComputation transforms information, and physical limits on computation are set by information-theoretic and thermodynamic constraints
- DNA (Deoxyribonucleic Acid)appliedDNA transcription and protein synthesis implement biological computation through molecular machines that process genetic information
- TechnologylogicalComputation provides conceptual grounding that helps explain Technology in this knowledge graph.