Logic & computability

Parent: math

Areas

• chomsky-hierarchy — the four language classes and their machines; regular-languages and its equivalences.
• turing-machines — the model, the halting problem, famous machines.
• recursive-functions — primitive vs general recursion, Ackermann.
• minsky-machine — counter machines, two-counter Turing-completeness.
• first-order-logic — syntax/semantics, completeness, the Entscheidungsproblem.
• soundness-and-completeness — the two directions, canonical models, the Hilbert–Gödel–Tarski lineage.

Reference notes

• decidability · semi-decidable · sat · kleene-fixed-point · modal-logic
• curry-howard · lambda-calculus · type-theory · proof-theory · lean4

(The original softening-to-optimization synthesis — relaxation/ — is still in raw/math/logic/.)