Computability and Complexity Vocabulary

Vocabulary flashcards on key theoretical computer science definitions from Chapter 1 notes.

Turing machine

A 5-tuple $T = (Q, \Sigma, s, \delta, F)$ consisting of states $Q$, tape alphabet $\Sigma$, start state $s \in Q$, accepting states $F \subseteq Q$, and transition function $\delta$, operating on an infinite tape divided into cells with a read/write head.

Church-Turing thesis

The thesis stating that anything intuitively computable can be computed by a Turing machine, equating an informal notion of algorithm with a formal computational model.

Turing completeness

The equivalence of computational power across different Turing machine variants, such as multi-tape or non-deterministic machines.

Turing-recognizable

A property of a language for which some Turing machine halts and accepts every input in the language, but on inputs not in the language it may reject or run forever.

Turing-decidable

A property of a language for which some Turing machine halts, either accepting or rejecting, on every input without looping forever.

Undecidable problem

A problem or language that no Turing machine can decide, even given unlimited tape and unlimited time.

Halting problem

The canonical undecidable problem of determining whether an arbitrary Turing machine $X$ halts on a given input $I$.

Universal Turing machine

A Turing machine capable of simulating any other Turing machine when provided with that machine's description as input.

Regular language

The innermost tier of the Chomsky hierarchy, decided by a deterministic finite automaton with no memory using regular expressions.

Context-free language

A tier in the Chomsky hierarchy decided by a pushdown automaton using stack memory, whose rewriting rules do not depend on neighboring symbols.

Context-sensitive language

A tier in the Chomsky hierarchy decided by a linear-bounded automaton restricted to tape space no longer than the input, whose rewriting rules can depend on neighboring symbols.

Big-O notation

An asymptotic upper bound that describes an algorithm's worst-case running time growth relative to input size $n$.

Big-$\Omega$ notation

An asymptotic lower bound that describes an algorithm's best-case running time growth relative to input size $n$.

Big-$\Theta$ notation

An asymptotic tight bound describing both the upper and lower bounds of an algorithm's running time growth, typically used for average-case analysis.

Complexity class P

The set of problems decidable by a deterministic single-tape Turing machine in $O(n^k)$ time for some constant $k$.

Complexity class NP

The set of problems whose proposed solutions can be verified in polynomial time, or equivalently, decided in polynomial time by a non-deterministic Turing machine.

Polynomial reduction

A conversion from problem $C$ to problem $B$ taking polynomial time, demonstrating that problem $B$ is at least as hard to solve as problem $C$.

Cook-Levin theorem

The theorem establishing that a polynomial-time solution to any single NP-complete problem would provide a polynomial-time solution for every problem in NP.

NP-complete

A class of problems inside NP to which every problem in NP can be reduced in polynomial time.

NP-hard

A class of problems to which every problem in NP reduces in polynomial time, but which themselves do not need to belong to NP.

Savitch's theorem

The theorem proving $\text{PSPACE} = \text{NPSPACE}$ by demonstrating that a non-deterministic machine using space $S(n)$ can be simulated deterministically in space $S(n)^2$.

PSPACE

The complexity class of problems decidable by a deterministic Turing machine using tape space polynomial in input size $n$.

NPSPACE

The complexity class of problems decidable by a non-deterministic Turing machine using tape space polynomial in input size $n$.