Theoretical computer science

Theoretical computer science studies the mathematical foundations of computation, including what can be computed, how efficiently, and through which formal models.

Turing machine: An abstract machine that computes by changing symbols on an unbounded tape according to a finite set of rules. It provides a precise model for defining algorithms and computability.
Algorithm: A finite, well-defined procedure for solving a problem or performing a computation. Algorithms are the objects whose correctness and resource use are analyzed.
Hilbert's tenth problem: The problem of deciding whether a polynomial equation with integer coefficients has an integer solution. Its undecidability helped establish that some precise mathematical questions have no algorithmic solution.
Cryptography: The study and practice of securing information through mathematical techniques. Its security claims often depend on assumptions about computational hardness.
P versus NP problem: The open question of whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time. It asks whether efficient verification implies efficient solution.
Lambda calculus: A formal system for expressing computation through function abstraction and application. Its equivalence to Turing machines connects programming languages to computability.
Many-one reduction: A transformation that converts instances of one decision problem into instances of another while preserving answers. Reductions compare problem difficulty and transfer hardness results.
Entscheidungsproblem: The question of whether an algorithm can decide the validity of every statement in first-order logic. Its negative solution helped define computability as a mathematical subject.
Formal verification: The use of mathematical methods to prove that a system satisfies specified properties. It applies logic and computation theory to establish software and hardware correctness.
Riemann hypothesis: The conjecture that every nontrivial zero of the Riemann zeta function has real part one-half. Its possible influence on algorithms connects number theory with computational complexity.

Linked from 3 pages