Computation Glossary

Browse 8 computation terms defined in plain English, from the cultural dictionary of computing.

8 Computation Terms

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...
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...
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...
Homomorphic Encryption: An encryption scheme that allows computation on encrypted data without decrypting it first — the result, when decrypted, matches the result of performing the...
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...
Number Crunching: Working through large amounts of calculation, data, or quantitative analysis. In engineering slang, it often refers to the less glamorous but necessary...
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....