Theory Glossary

Browse 34 theory terms defined in plain English, from the cultural dictionary of computing.

34 Theory Terms

AGI
Artificial General Intelligence — a hypothetical AI system that matches or exceeds human cognitive abilities across all domains, not just narrow tasks. Whether...
Algebraic Data Type
A composite type formed by combining other types using sum (OR — one of several variants) and product (AND — a combination of fields). Sum types (tagged...
Algebraic Effects
A programming language feature where functions can 'perform' effects (I/O, exceptions, async, state) and a handler higher up the call stack decides how to...
Boolean Algebra
A branch of algebra dealing with variables that have two possible values: true/false (1/0). Operations include AND, OR, NOT, XOR, NAND, and NOR. The...
CAP Theorem
The theorem stating that a distributed data store can provide at most two of three guarantees: Consistency, Availability, and Partition tolerance. Since...
Category Theory
A branch of mathematics that studies structures and the relationships between them at a highly abstract level, using concepts such as objects, morphisms,...
Church-Turing Thesis
The hypothesis that any function computable by an effective mechanical procedure can be computed by a Turing machine (or equivalently, by lambda calculus). Not...
Computer Science
The academic and technical field concerned with computation, algorithms, systems, data, logic, and related theory and practice. In culture discussions it is...
Continuation
An abstract representation of 'the rest of the computation' at any given point in a program. First-class continuations (call/cc in Scheme) allow capturing and...
Conway's Law
The observation that organizations design systems that mirror their communication structures. A company with four teams will produce a four-component...
Covariance
A type relationship where a generic type preserves the subtyping direction of its parameter — if Cat extends Animal, then List<Cat> is assignable to...
Dependent Type
A type that depends on a value — for example, Vector<n> where n is the length, allowing the compiler to verify that you never access an out-of-bounds index....
Dunbar's Number
The theoretical cognitive limit (~150) on the number of stable social relationships a human can maintain. In tech organizations, explains why communication...
Dynamic Programming
An optimization technique that solves problems by breaking them into overlapping subproblems and storing their solutions (memoization/tabulation) to avoid...
Effect System
A type system extension that tracks computational side effects (I/O, exceptions, state mutation, async) in function signatures. The compiler enforces that...
Finite State Machine
A computational model with a finite number of states, transitions between them triggered by inputs, and defined start/accept states. Used to model parsers, UI...
General Intelligence
The capability to perform effectively across a wide range of tasks and domains rather than being limited to one narrow specialized function. In AI discussions,...
Graph Theory
The mathematical study of graphs — structures consisting of vertices (nodes) connected by edges. Undirected or directed, weighted or unweighted, cyclic or...
Halting Problem
The proven impossibility of writing a general algorithm that determines whether any given program will eventually stop (halt) or run forever. Alan Turing...
Horn Clause
A logical formula consisting of a disjunction of literals with at most one positive literal, forming the basis of logic programming languages like Prolog. A...
Intelligence Explosion
A hypothetical scenario in which increasingly capable AI systems rapidly improve themselves or accelerate progress so quickly that intelligence grows...
Lambda Calculus
A formal system for expressing computation using function abstraction (λx.body) and application (f x). Equivalent in power to Turing machines but models...
Nominal Typing
A type system where compatibility is determined by explicit declarations (class name, implements/extends) rather than structural similarity. Two types with...
NP-Completeness
A class of problems where: (1) a proposed solution can be verified quickly (in polynomial time), but (2) no known algorithm can find a solution quickly. All...
OSI Model
A seven-layer conceptual model for understanding network communication: Physical (1), Data Link (2), Network (3), Transport (4), Session (5), Presentation (6),...
Quantum Computing
A computing paradigm using quantum bits (qubits) that can exist in superposition (both 0 and 1 simultaneously) and entanglement (correlated across distance)....
Referential Transparency
A property of expressions where they can be replaced with their value without changing program behavior. A function is referentially transparent if calling it...
Scaling Hypothesis
The idea that simply scaling up model size, data, and compute can continue to produce substantial capability gains. The scaling hypothesis is influential in...
Seed AI
A hypothetical initial AI system capable of meaningfully improving itself or helping create more capable successor systems. The term appears mainly in...
Self-Improvement
The process by which an AI system helps improve its own capabilities, training process, or supporting infrastructure over time. The term appears both in...
Turing Completeness
The property of a computational system that can simulate any Turing machine — meaning it can compute anything that is computable, given enough time and memory....
Turing machine
A theoretical mathematical model of computation defined by Alan Turing in 1936, consisting of an infinite tape, a read/write head, and a finite set of states....
Type System
The set of rules a programming language uses to assign and check types, preventing certain classes of errors. Ranges from dynamic (Python, JS) to static (Rust,...
Utility Function AI
The concept of defining AI behavior around a utility function that encodes what outcomes should be preferred or optimized. The term appears mainly in alignment...

Related Topics