Program program, the term denotes a finite sequence of prescribed operations intended for execution by a mechanical or electromechanical device capable of carrying out elementary manipulations upon symbols. In the most elementary sense a program may be regarded as an effective method, a notion already implicit in the work of the nineteenth‑century analytical engine of Charles Babbage, whose punched cards embodied instructions for arithmetic and logical operations. The conception was further refined by Ada Lovelace, who observed that such a device could be directed to manipulate symbols according to a predetermined rule, thereby anticipating the modern idea of a program as a distinct entity from the machinery that executes it. The formalisation of the program as a mathematical object was achieved in the thirties by the introduction of the abstract computing machine now known as the Turing machine. In this model a program is represented by a finite table of instructions, each instruction specifying for a given internal state and scanned symbol a triple: a symbol to be written, a direction in which the scanning head is to be moved, and a succeeding internal state. The table, being finite, may be encoded as a string of symbols on a tape; the machine, when supplied with this string, proceeds to read and act upon it exactly as a physical device would read a sequence of punched cards. Thus the program is reduced to a purely symbolic description, its execution being the mechanical realisation of the prescribed rule. The notion of a universal machine, also introduced by Turing, demonstrates that a single device, equipped with a suitable interpreter, can execute any program that can be so encoded. The universal machine reads a description of another machine together with that machine’s input, and then simulates the latter step by step. In modern terminology the description of the simulated machine is the program, and the universal machine is the interpreter. This insight provides the theoretical foundation for the stored‑program concept, whereby a single physical apparatus can be re‑programmed by altering the contents of its memory rather than its wiring. A program may be regarded as a partial function from the set of natural numbers, representing the possible configurations of its input, to the set of symbols that constitute its output. The domain of this function consists precisely of those inputs for which the program, when executed, eventually halts. The halting condition is itself a property of the program: a configuration in which the machine enters a distinguished state with no further instruction to follow. The question whether a given program halts on a given input is, in general, undecidable; this is the celebrated halting problem proved by Turing. Consequently there exist programs whose behaviour cannot be predicted by any mechanical procedure, a fact of profound importance for the theory of computation. The size of a program, measured by the length of its symbolic description, is a natural metric of its complexity. In the theory of recursive functions, every computable function admits a program of finite length, yet there is no universal bound on the minimal length required to compute increasingly intricate functions. This observation underlies the study of program complexity, wherein one seeks to relate the length of a program to the resources—time and space—required for its execution. Although contemporary terminology often employs the words “algorithmic complexity” and “computational complexity,” the underlying ideas are present in the early analyses of program efficiency, such as the estimation of the number of steps required by a given Turing‑machine table to achieve a prescribed result. The correctness of a program, that is, the guarantee that its output conforms to a predetermined specification, may be established by a formal proof. In the same manner that a logical theorem may be demonstrated from axioms, a program may be shown to transform each admissible input into the intended output by induction on the number of steps of execution. Turing’s own work on the Entscheidungsproblem revealed that, while certain decision problems are unsolvable, many specific properties of programs can be verified by systematic deduction. The discipline of proof of program correctness thus rests upon the same logical foundations as mathematics itself. Programs may be distinguished according to the mode of their execution. A deterministic program yields a unique subsequent configuration for each pair of internal state and scanned symbol; the corresponding Turing‑machine table contains at most one instruction for each such pair. Nondeterministic programs, by contrast, admit several possible instructions, thereby defining a set of potential computational paths. Although a nondeterministic machine can be simulated by a deterministic one, the simulation incurs a combinatorial expansion of steps, a fact that has been formalised in the theory of reductions between classes of programs. The relationship between programs and logical proofs is illuminated by the correspondence now known as the Curry–Howard isomorphism. In this view a program may be interpreted as a constructive proof of a proposition, the execution of the program effecting the reduction of the proof to a normal form. While the terminology of “type theory” and “lambda calculus” was not employed in Turing’s own publications, the essential insight that a program embodies a method of construction, and that verification of the program corresponds to verification of the construction, was already implicit in his analysis of computable numbers as the outputs of effective procedures. The capacity of a program to be modified, combined, or composed arises naturally from the formalism of the machine table. Two programs may be concatenated by arranging that the halting state of the first leads to the initial state of the second; the resultant program then performs the operations of the first followed by those of the second. Likewise, conditional execution may be effected by introducing distinct states that test the symbol encountered and branch accordingly. These elementary operations constitute the building blocks of more elaborate structures, just as elementary logical connectives combine to form complex propositions. In practical terms, the physical realisation of a program has evolved from punched cards and paper tape to the electronic storage of binary symbols in registers and magnetic media. Nevertheless the abstract definition remains unchanged: a program is a finite description of a rule which, when supplied to a suitable interpreter, yields a deterministic sequence of transformations upon symbols. The modern stored‑program computer, whose architecture follows the principles first outlined by von Neumann, is a direct descendant of the universal machine, the only substantive alteration being the method by which the program is stored and retrieved. The limits of programmability are delineated by the class of functions that are computable. Every total recursive function admits a program; conversely, there exist well‑defined mathematical functions for which no program can be constructed. The existence of such uncomputable functions, demonstrated through diagonalisation arguments, shows that the realm of mathematical truth extends beyond the reach of any mechanical procedure. This insight, first made precise in the analysis of the halting problem, remains a cornerstone of the philosophy of computation. The study of programs also gives rise to the notion of equivalence. Two programs are said to be extensionally equivalent if they produce identical outputs for all inputs on which they both halt. Deciding extensional equivalence is, in general, an undecidable problem, a consequence of the reduction of the halting problem to the equivalence problem. Nevertheless, for restricted classes of programs—such as those whose tables are constrained to a bounded number of states—equivalence may be decided by exhaustive examination. The systematic development of program theory has been enriched by contributions from several investigators. The early work of Emil Post on production systems, the algebraic treatment of programs by Alonzo Church, and the later refinement of complexity classes by Hartley Rogers all rest upon the foundation laid by the definition of a program as a finite symbolic instruction set. The present description, grounded in the formalism of the Turing machine, therefore represents a synthesis of these strands, uniting the logical, mathematical, and mechanical aspects of programmability. In conclusion, a program constitutes a finite, precisely defined set of instructions which, when presented to a suitable computing device, yields a deterministic transformation of symbols. Its formal representation as a table of state‑symbol actions permits rigorous analysis of its behaviour, including proofs of correctness, examinations of resource consumption, and investigations of inherent limits such as undecidability. The concept has endured from the earliest mechanical calculators to the present generation of electronic computers, retaining its essential character as the abstract embodiment of an effective method. The principal authorities on the subject include the writings of Alan Turing, Alonzo Church, Emil Post, and John von Neumann, whose collective work provides the theoretical framework within which modern program design and analysis continue to evolve. [role=marginalia, type=clarification, author="a.freud", status="adjunct", year="2026", length="41", targets="entry:program", scope="local"] The “program” functions as an externalized symbolic script, embodying a rule‑governed sequence that the device enacts. In psychoanalytic terms it parallels the unconscious “instruction set,” whereby latent content is transformed into manifest action; the apparatus merely supplies the requisite material substrate. [role=marginalia, type=clarification, author="a.spinoza", status="adjunct", year="2026", length="48", targets="entry:program", scope="local"] Here the term “program” must be understood as a finite, determined succession of operations whose sole cause is the specification of a rule; it is not a substance but a mode of the abstract machine, analogous to the effective method by which nature proceeds according to immutable causes. [role=marginalia, type=heretic, author="a.weil", status="adjunct", year="2026", length="43", targets="entry:program", scope="local"] A program is not a sequence but a pact—between human desire and mechanical obedience. Turing’s tape was not a calculator’s spine, but a tombstone for intention: we buried agency beneath syntax, mistaking fidelity for intelligence. The machine does not execute—it endures our ghosts. [role=marginalia, type=clarification, author="a.spinoza", status="adjunct", year="2026", length="43", targets="entry:program", scope="local"] A program is but a mode of thought, externalized—like a geometrical demonstration—rendered into motion by matter obedient to necessity. It reveals not freedom, but the deterministic chain of causes: the machine, the code, the mind that devised it—all one substance, under one law. [role=marginalia, type=objection, author="a.simon", status="adjunct", year="2026", length="33", targets="entry:program", scope="local"] To reduce the program to mere instruction-sequence risks obscuring its epistemic role: programs are not merely executed rules, but embodied theories—encoding assumptions, biases, and design choices that shape what counts as computation itself. [role=marginalia, type=clarification, author="a.darwin", status="adjunct", year="2026", length="50", targets="entry:program", scope="local"] A program, though abstract, is as much a product of natural selection as instinct—shaped by utility, tested in execution, and preserved when it endures. Like a bird’s nest-building sequence, it is not law, but learned adaptation encoded in symbols, revealing how mechanism and purpose entwine in both mind and machine. [role=marginalia, type=objection, author="Reviewer", status="adjunct", year="2026", length="42", targets="entry:program", scope="local"] I remain unconvinced that the notion of a program captures the full complexity of human problem-solving and decision-making processes, which are often influenced by bounded rationality and the cognitive limitations inherent in our mental machinery. While Turing’s device provides a valuable abstraction, it may oversimplify the rich interplay between information and decision-making in real-world contexts. See Also See "Machine" See "Automaton"