Foundations

Build an inspectable physics record, test and revise a bounded cart model, preserve processing history, and plan findable data with appropriate sharing conditions.

A bit has two possible states; a fixed-width unsigned binary word encodes an integer.

Shannon entropy measures uncertainty in a specified probability distribution.

An algorithm specifies effective steps; a decision procedure must terminate on every permitted input.

No total algorithm decides halting for every program and input in a general computation model.

Big O bounds eventual growth up to a fixed constant factor.

A DFA consists of finite states Q, finite alphabet Σ, total transition δ:Q×Σ→Q, start q₀ and accepting states F.

Regular expressions built from letters, the empty word and empty language using union, concatenation and star describe exactly the DFA/NFA-recognizable languages.

A context-free grammar has finite variables, terminal alphabet, rules A→w with one variable on the left, and a start variable.

A nondeterministic pushdown automaton augments finite control with one unbounded last-in-first-out stack.

A recognizer accepts every member of its language but may run forever on a nonmember.

Every nontrivial property of the language recognized by a Turing machine is undecidable from its machine description.

For eventually nonnegative costs f,g, f=Θ(g) means c₁g(n)≤f(n)≤c₂g(n) for all sufficiently large n and constants c₁,c₂>0.

If operation i changes state Dᵢ₋₁ to Dᵢ, define ĉᵢ=cᵢ+Φ(Dᵢ)−Φ(Dᵢ₋₁).

For a 3CNF formula with m clauses, make a vertex for each literal occurrence.

A fixed finite-tape deterministic Turing machine running in time t(n)≥n can be simulated by a single-tape machine in O(t(n)²) time by storing tape contents and head markers and scanning them for each simulated step.

A deterministic decider's time cost counts steps and its space cost counts used storage cells; worst-case bounds maximize over inputs of the same encoded length.

If a language is regular, some p≥1 ensures every accepted word x with |x|≥p decomposes as uvw with |uv|≤p, |v|≥1 and uvᵐw accepted for all m≥0.

The language {0ⁿ1ⁿ:n≥0} is not regular.

A DFA's language is empty iff no accepting state is reachable from its start.

A finite context-free grammar has decidable membership: convert to Chomsky normal form and enumerate bounded derivations for a nonempty input word.

For a finite CFG, chart Iⱼ stores dotted productions [A→β·γ,k], where k is the starting position.

For T(n)=aT(n/b)+f(n), T(1)=Θ(1), let q=log_b a.

DSPACE(s(n)) and NSPACE(s(n)) contain decision languages solvable with O(s(n)) workspace by deterministic and nondeterministic Turing machines.

A time bound t(n)≥n is time constructible here when a Turing machine on unary input 1ⁿ can write 1ᵗ⁽ⁿ⁾ in O(t(n)) time.

For a space-constructible s(n)≥log n, NSPACE(s(n))⊆DSPACE(s(n)²).

A logspace many-one reduction computes f with x∈A exactly when f(x)∈B, using a read-only input, O(log n) work tape and write-only output.

NL=coNL: complements of nondeterministic logspace decision languages also lie in NL.

For time-constructible f,g≥n with f(n)log f(n)=o(g(n)), DTIME(f(n)) is a proper subset of DTIME(g(n)).

If S is space constructible, S(n)≥n, and s(n)=o(S(n)), then DSPACE(s(n))⊊DSPACE(S(n)).