Before formal computation theory, there was no precise definition of what it means to “compute” something. Informal notions of “effective procedure” or “mechanical process” were insufficient for proving fundamental limits.
An algorithm is a finite, unambiguous, step-by-step procedure for solving a problem or computing a function. It must terminate after a finite number of steps for all valid inputs.
Algorithms have these key characteristics (from Church-Turing thesis):
- Finiteness — algorithm has finite description, terminates for all inputs
- Definiteness — each step is precisely defined, no ambiguity
- Input — zero or more inputs from a specified set
- Output — at least one output that is the solution to the problem
- Effectiveness — each operation must be basic enough to be done exactly and in finite time
Algorithms can be expressed in many forms: pseudocode, programming languages, Turing machines, lambda calculus expressions, or flowcharts.
- Correctness — produces right output for all valid inputs
- Termination — halts after finite steps (unlike infinite loops)
- Complexity — time and space requirements as function of input size
- Determinism — same input always produces same output (for deterministic algorithms)
- Built from: Mathematical Logic — formal reasoning about procedures
- Builds into: Turing Machine — formal model of algorithmic computation
- Builds into: Computability Theory — what algorithms can/cannot compute
- Builds into: Computational Complexity Theory — resources required by algorithms
- Related: Big O Notation — measuring algorithm efficiency
- Contrasts with: Heuristic — rules of thumb vs guaranteed procedures
- Not all procedures are algorithms — must terminate (halting problem shows some procedures don’t)
- Algorithm ≠ program — algorithms are abstract, programs are concrete implementations
- Nondeterministic algorithms allow “guessing” — basis for NP complexity class