逻辑与可计算性

父级：math

领域

• chomsky-hierarchy — 四类语言及其对应的机器；regular-languages 及其等价性。
• turing-machines — 图灵机模型、停机问题、几台著名的图灵机。
• recursive-functions — 原始递归与一般递归，阿克曼函数。
• minsky-machine — 计数器机，双计数器机的图灵完备性。
• first-order-logic — 语法与语义，完备性，判定问题（Entscheidungsproblem）。
• soundness-and-completeness — 可靠性与完备性这两个方向，典范模型，希尔伯特—哥德尔—塔尔斯基这条脉络。

参考笔记

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

（原先"软化为优化"的综合内容——relaxation/——仍保留在 raw/math/logic/ 中。）