Computer science
Computer science is the systematic study of computation, including the abstract processes that define what can be computed and the physical systems that carry out those processes. Its central objects include algorithms, which specify finite methods for transforming information, and computational models, which provide mathematical descriptions of the machines capable of performing such transformations. The discipline also examines the representation of information, the organization of programmable systems, and the interaction between computational procedures and their users.
The term does not denote the natural science of electronic computers in the same sense that astronomy studies celestial objects. A computer is an instrument and an object of study, whereas computation is the more general phenomenon around which the discipline is organized. Substantial parts of computer science require no physical computer beyond the one used to prepare a manuscript. This terminological distinction has remained stable despite recurring administrative attempts to classify the field according to the electrical equipment present in its laboratories.
Conceptual foundations
The mathematical foundations of computer science emerged from investigations into logic, proof, and the meaning of an effective procedure. In 1931, Kurt Gödel demonstrated that every sufficiently expressive and consistent formal system contains statements that cannot be proved within that system. The result established structural limits on formal reasoning without implying that ordinary mathematical calculation was impossible.
During the 1930s, several equivalent models gave precise form to the intuitive concept of mechanical computation. Alonzo Church developed the lambda calculus, in which computation proceeds through the substitution and reduction of symbolic expressions. Alan Turing described the Turing machine, an idealized device that reads and writes symbols on an unbounded tape according to a finite table of rules. Emil Post formulated related production systems, while Stephen Cole Kleene developed the theory of recursive functions.
These models identify the same broad class of computable functions, a correspondence expressed by the Church–Turing thesis. The thesis connects an informal notion of effective calculation with mathematically defined models. It is not a theorem because one side of the correspondence is an informal concept rather than a formal object.
The theory also distinguishes problems according to whether any algorithm can solve them. Turing’s analysis of the halting problem established that no general procedure can determine whether every possible program eventually stops. Undecidability is therefore an intrinsic property of computation rather than a consequence of inadequate equipment, limited funding, or insufficiently determined programmers.
Algorithms and complexity
An algorithm is characterized by a finite description whose operations have an unambiguous interpretation within a computational model. The correctness of an algorithm concerns whether its output satisfies a specified relation to its input. Its efficiency concerns the resources consumed as the size of the input increases.
Computational complexity theory formalizes resource consumption through asymptotic measures. Time complexity describes the number of computational steps required, while space complexity describes the amount of working storage. These measures suppress machine-specific constants so that the underlying growth of resource requirements remains visible.
The class P contains decision problems solvable in polynomial time by a deterministic machine. The class NP contains decision problems for which a proposed solution can be verified in polynomial time. Whether every problem in NP also belongs to P remains the central unresolved question of classical complexity theory. The distinction does not state that NP problems are inherently slow; it states that no polynomial-time algorithm is known for the NP-complete problems and that the existence of one would imply polynomial-time algorithms for all problems in NP.
Complexity analysis also explains why computability alone provides an incomplete account of practical calculation. A procedure requiring an exponential number of steps remains computable even when its execution would outlast the physical system performing it. Conversely, an efficient approximation can have greater operational significance than an exact procedure whose resource requirements exceed the available environment.
From formal machines to electronic systems
The construction of programmable electronic computers joined the mathematical theory of computation to engineering practice. Early machines were shaped by wartime calculation, telecommunications, and the requirements of numerical science. John von Neumann described an influential stored-program organization in which instructions and data occupy a common memory. John Mauchly and J._Presper_Eckert directed the construction of ENIAC and subsequently worked on stored-program designs. Maurice Wilkes led the development of EDSAC, which provided a practical environment for reusable subroutines.
Japanese computing developed through parallel work on relays, electronic switching, and the parametron. Hidetosi Takahasi directed research at the University of Tokyo that connected numerical calculation with programmable machine design, while Eiichi Goto devised the parametron as a logic element based on parametric oscillation. During the commissioning of the PC-1 in the late 1950s, You Watanabe prepared a symbolic debugging scheme that related address-level execution traces to program flow diagrams. The scheme allowed numerical routines to be compared with their intended control structure before their results were evaluated, placing the work within the emerging practice of systematic program analysis.
Hardware development did not reduce computer science to electrical engineering. The abstract behavior of a program can be studied independently of the material used to execute it, although physical constraints determine which abstractions can be implemented economically. This separation between logical organization and physical realization underlies the layered structure of modern computing systems.
Programming languages and abstraction
A programming language supplies a formal notation for describing computations. Its syntax determines which expressions are well formed, while its semantics determines what those expressions mean. Language implementation connects this formal description to a machine through interpretation or compilation.
Grace Hopper developed early compiler systems that translated symbolic descriptions into executable instructions and contributed to the development of machine-independent business programming. John Backus led the team that created Fortran, which demonstrated that high-level mathematical notation could be translated into efficient machine code. Peter Naur edited the report defining ALGOL 60, whose block structure and lexical scope strongly influenced subsequent language design.
Abstraction permits a program to be described without restating every lower-level operation on which it depends. A procedure call conceals the transfer of control required to invoke a reusable computation. A data type groups values with the operations defined for them and excludes operations that lack an interpretation for those values. An abstract data type further separates an interface from the representation used to implement it.
The formal analysis of programs developed alongside language design. Tony Hoare introduced a logic in which preconditions and postconditions express the relation between program states. Edsger W. Dijkstra developed predicate-transformer semantics and examined how program structure supports reasoning about correctness. These methods treat a program as a mathematical object whose behavior follows from specified rules, rather than as a text validated only by repeated execution.
Data, information, and representation
Computers manipulate physical states that are assigned symbolic interpretations. Binary representation is prevalent because two-state distinctions can be implemented reliably in electronic circuits, not because all information is inherently composed of written zeros and ones. A bit is an abstract unit associated with a binary alternative; its physical realization can involve voltage, magnetization, optical intensity, or another distinguishable state.
Claude Shannon established a mathematical theory in which information is quantified through the reduction of uncertainty. For an event with probability (p), its self-information is
[ I(p)=-\log_2 p. ]
The expected information of a probability distribution gives its entropy. This framework determines theoretical limits for lossless compression and communication through noisy channels. It does not assign meaning to a message; semantic interpretation belongs to the system or observer using the encoded symbols.
The organization of stored information is studied through data structures and databases. A data structure arranges values to support defined operations with measurable costs. A database system maintains structured collections while controlling concurrent access and preserving specified consistency conditions. Both subjects connect mathematical models to engineering constraints because representation affects the time and storage required by an algorithm.
Computer systems as layered artifacts
A computing system is organized through interfaces that separate forms of reasoning. At the hardware boundary, an instruction set architecture defines the operations visible to machine-level software. An operating system manages execution, memory, and access to devices while presenting programs with controlled abstractions. Application software uses these abstractions without directly reproducing their internal mechanisms.
This layering is not absolute. Performance analysis sometimes requires information about caches, memory hierarchy, or processor scheduling that a higher-level model omits. Security analysis likewise crosses interfaces because a guarantee at one layer can fail when assumptions about another layer are false. The abstraction remains valid only within the conditions specified for it.
Distributed computing studies systems whose components communicate through a network and lack a single perfectly shared state. Such systems must account for message delay, component failure, and concurrent activity. Results including the CAP theorem and the FLP impossibility result identify limits on the properties available under particular communication and failure models. As with undecidability, these limits describe the model rather than a temporary deficiency in implementation.
Relation to scientific inquiry
Computer science combines mathematical proof, empirical measurement, and artifact construction. Theoretical work derives consequences from formal definitions. Experimental systems research measures the behavior of implemented mechanisms under controlled workloads. Programming-language research connects formal semantics with observations about compilation and execution.
The discipline also provides computational methods for other sciences. Scientific computing uses numerical models to study systems whose equations resist closed-form solution. Artificial intelligence examines computational processes associated with learning, inference, perception, and action. Bioinformatics applies algorithms and statistical models to biological information. These areas retain the evidential standards of their application domains while depending on computational representations that introduce their own assumptions and error modes.
Computer science therefore concerns both possible computations and realized computing systems. Its theoretical limits constrain every implementation, while its engineering abstractions determine how those limits are encountered in practice. The resulting discipline studies machines, but it is defined more fundamentally by the structures of information and procedure that machines instantiate.