Computation as constraint

0. Orientation: Computation as Constraint, Not Convenience

Computation here is not “apps”, “software”, or “industry.” It is symbolic state under explicit update rules inside finite resources.

Three layers:

1. Formal — abstract machines, grammars, programs.
2. Complexity-theoretic — time, space, randomness, communication.
3. Physical — energy, noise, latency, faults.

Core lineage (stacked): Turing/Church define effective procedure; von Neumann binds it to hardware architecture; Knuth quantifies algorithmics; Dijkstra/Hoare turn programs into contracts and proofs; Sipser canonizes automata/computability/complexity; Papadimitriou exposes structural complexity and reductions.

1. Models of Computation and the Church–Turing Boundary

1.1 Equivalent formal models

Three foundational characterizations of “effective procedure”:

• Turing machines — finite control + tape + head; stepwise read/write/move/state update.
• λ-calculus — terms + β-reduction; computation as substitution/function application.
• (Partial) recursive functions — closure under composition/recursion/minimization.

Variants extend the claim from computability to efficiency (polynomial simulation) and from abstract procedures to physically realizable devices.

2. Computability: Decidable, Enumerable, Undecidable

2.1 Recursive, r.e., co-r.e.

• Decidable / recursive: halts on all inputs and answers correctly.
• r.e. / semi-decidable: halts and accepts on members; may run forever on non-members.
• co-r.e.: complements of r.e. languages.

2.2 Halting problem

Given a program P and input x: will P(x) halt? No total algorithm decides this for all pairs.

2.3 Rice’s theorem (semantic undecidability)

Any non-trivial semantic property of programs is undecidable in full generality. Static analyzers must trade completeness, soundness, and termination: general semantic perfection is blocked.

3. Algorithms: Procedure, Correctness, Resource

3.1 Total vs partial

Explicitly track termination: some “procedures” are partial (may not halt), and the difference matters everywhere computability bites.

3.2 Programs as logic (Dijkstra & Hoare)

• Hoare logic: {P} C {Q} — if P holds and C terminates, then Q holds.
• Weakest precondition: wp(C,Q) — the weakest condition guaranteeing postcondition Q after C.

3.3 Time and space

Complexity classes arise from resource bounds (P, PSPACE, EXP, …). Hierarchy theorems guarantee strict stratification as bounds increase.

4. Data Structures: Architecture of State and Access

Data structures encode what is cheap vs expensive, and which invariants define “valid state.” Any real registry is a design choice over structure + invariants.

5. Automata and Formal Languages: The Chomsky Hierarchy

Machine power is memory power:

• FA/NFA → regular languages.
• PDA → context-free languages (NPDA = CFL; DPDA is a strict subset).
• LBA → context-sensitive languages.
• TM → r.e. languages.

6. Complexity Theory: Cost and Intractability

6.1 Classes and containment

P ⊆ NP ∩ co-NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE (some strictness known; many frontiers open).

6.2 P vs NP and NP-completeness

NP-completeness organizes hardness via reductions: SAT is NP-complete; thousands of problems inherit the same worst-case wall unless P=NP.

7. Randomized Computation

Randomness changes the model: bounded error (BPP), one-sided error (RP/co-RP), zero-error expected time (ZPP). Guarantees can become statistical rather than absolute.

8. Algorithmic Information: Kolmogorov Complexity

K(x) = length of the shortest program outputting x on a fixed universal TM. K measures compressibility; algorithmic randomness is incompressibility.

9. Physical Limits: Energy and Communication

9.1 Landauer (erasure costs energy)

Irreversible erasure implies a minimum heat dissipation per bit: k_B T ln 2.

9.2 Communication complexity (Yao)

Distributed coordination has hard lower bounds on bits exchanged, independent of local compute power.

10. Distributed Limits: Consensus and Tradeoffs

• FLP impossibility: no deterministic consensus with faults in a fully asynchronous system (agreement + termination cannot be guaranteed in all executions).
• CAP: under partitions, cannot simultaneously guarantee strong consistency and full availability.

11. Cryptographic Hardness and Asymmetry

Modern cryptography exploits assumed hardness to create effort asymmetries:

• easy to verify, hard to forge;
• easy to check, hard to invert;
• easy to validate commitments, hard to violate them without keys.

Hardness is not just constraint — it is a resource used to build unforgeability and irreversibility into protocols.

12. The Thinkers as One Architecture

1. Church & Turing: formalize procedure; expose undecidable limits.
2. von Neumann: stored-program architecture; abstract computation becomes hardware organization.
3. Knuth: quantitative algorithmics and data structures; analysis becomes discipline.
4. Dijkstra & Hoare: programs as proofs and contracts; concurrency as formal interaction.
5. Sipser: canonical pipeline (automata → computability → complexity → NP-completeness).
6. Papadimitriou: structural complexity (reductions/web of classes), games, modern completeness notions.

13. Synthesis: The Law of Finite Symbolic Power

This is the unified picture: computation is a layered lattice of impossibilities and tradeoffs. Any system—algorithmic, institutional, cryptographic, or distributed—lives inside these walls.

Resource Index (All Links)

Indexed as r1…r33. Inline chips jump here.