Meaning of computation
Computation is the systematic transformation of information according to a defined set of rules or instructions. A computation may involve arithmetic operations, logical decisions, symbolic transformations, data retrieval, or complex algorithmic procedures. It can be performed by electronic computers, mechanical devices, abstract mathematical machines, or even manually by following a formal procedure.
Basic computational model
Input
Information supplied to a computational process. Inputs may include numbers, text, images, sensor measurements, instructions, or structured records.
Processing
The execution of operations and decision rules that transform the input or the current computational state.
Memory
The storage of data, instructions, intermediate results, and execution state required during computation.
Output
The result produced by the computational process, such as a calculated value, classification, report, control signal, or transformed dataset.
Control
The mechanism that determines the order of operations, manages decisions, and coordinates the execution of instructions.
Algorithmic foundations
An algorithm is a finite and precisely specified sequence of steps designed to solve a problem or perform a computational task. Algorithms provide the logical structure of computation independently of any particular programming language or hardware platform. Their quality can be evaluated through correctness, termination, efficiency, resource consumption, and suitability for the intended problem.
Essential properties of algorithms
Input specification: an algorithm may accept zero or more clearly defined inputs.
Output specification: it must define the required result or results.
Definiteness: each instruction must be sufficiently precise and unambiguous.
Finiteness: a terminating algorithm must complete after a finite number of steps for every input within its stated domain.
Effectiveness: its operations must be sufficiently basic and executable within the assumed computational model.
Correctness: it must produce results satisfying the problem specification.
Generality: it should solve the intended class of problems rather than only one isolated instance.
Computational models
Turing machine
An abstract mathematical model consisting of a control mechanism, a finite set of states, a transition function, and an unbounded tape in the classical formulation. It is used to investigate computability and the theoretical limits of algorithms.
Finite state machine
A computational model consisting of a finite number of states and transitions determined by input symbols. It is useful for modeling digital controllers, protocol behavior, lexical analysis, and sequential systems.
Lambda calculus
A formal system based on function abstraction and application that provides a mathematical foundation for functional computation and programming-language theory.
Register machine
An abstract computational model that operates on a finite collection of registers using a defined instruction set. It is useful for studying algorithmic computation.
Computational processes
Sequential computation
Operations are executed in a defined sequence, where later steps may depend on earlier results.
Parallel computation
Multiple computational operations execute simultaneously or with overlapping execution to improve performance or process independent tasks.
Concurrent computation
Multiple tasks make progress during overlapping periods, potentially coordinating access to shared resources even when they do not execute simultaneously.
Distributed computation
A computational task is performed by multiple interconnected computers that communicate and coordinate through a network.
Interactive computation
A system repeatedly receives external inputs and produces responses while interacting with users, devices, or other systems.
Computability
Computability theory investigates whether a problem can be solved by an algorithm under a formal model of computation. Some problems are computable, meaning an algorithm can produce the required answer for every valid input within the problem's specification. Other problems are undecidable, meaning no algorithm can solve all instances under the specified formal requirements.
Complexity and resources
Computational complexity examines the resources required to solve computational problems, particularly time and memory. Time complexity describes how the number of computational steps grows with input size, while space complexity describes how memory requirements grow. These measures help distinguish algorithms that are practical for large inputs from those that become prohibitively expensive.
Abstraction and state
Abstraction hides implementation details that are unnecessary for understanding a computational problem. A computational state represents the information relevant to the system at a particular stage of execution. State transitions describe how inputs and operations change that state.
Advanced concepts
Church-Turing thesis and the relationship between formal models of computation.
Decidable and undecidable computational problems.
Computational complexity classes such as P, NP, and PSPACE.
Reduction techniques for comparing computational problems.
Formal semantics of programming languages.
Parallel and distributed computational models.
Quantum computational models and their differences from classical computation.