John McCarthy

The Arithmetic Hardware Baseline

In the mid-to-late 1950s, the state of digital computation was defined by vacuum-tube and first-generation discrete-transistor architectures, typified by the IBM 704 (introduced in 1954). The mechanical and logical layout of these systems was designed almost exclusively for ballistic trajectories, crystal lattice calculations, matrix inversion, and numerical fluid dynamics:

• Word Architecture: The IBM 704 operated on a fixed-width 36-bit word. Execution hardware was partitioned into specialized register fields: an Accumulator ($AC$), a Multiplier-Quotient register ($MQ$), and three 15-bit index registers ($XR_A, XR_B, XR_C$) working under two's- or ones'-complement arithmetic.
• Storage Topology: Main memory consisted of magnetic core storage ranging from 4,096 to 32,768 words. Access was strictly linear and uniform: fetching a word required presenting an integer physical address to the memory address register ($MAR$). Data structures were structurally contiguous: arrays, matrices, and lookup tables mapped monotonically into adjacent physical locations ($\text{Loc}(A[i]) = \text{Base}(A) + i \cdot w$).
• Control Flow Mechanics: Program sequencing relied on hardware program counters, direct address jumps (TRA), and hardware conditional branches tied to arithmetic register states (e.g., TZE—Transfer on Zero, TPL—Transfer on Plus). Subroutine linkages were primitive; early architectures lacked a hardware-supported call stack, requiring self-modifying code or jump-and-store-return-address instructions (TSX) that wrote return pointers directly into the entry address of the target subroutine.

The Cybernetic Blindspot

Cognitive simulation in the 1950s was dominated by the cybernetics paradigm spearheaded by Norbert Wiener, W. Ross Ashby, and Warren McCulloch. This tradition approached intelligence through continuous-state dynamical systems:

1. Analogue and Stochastic Homology: Cognition was modeled as continuous feedback loops governed by systems of coupled ordinary differential equations: $$\frac{d\mathbf{x}}{dt} = \mathbf{f}(\mathbf{x}(t), \mathbf{u}(t), t)$$
2. Threshold Logic and Neural Nets: Following McCulloch and Pitts (1943), intellectual processing was situated in static networks of binary threshold elements characterized by fixed connection weights and uniform summation thresholds: $$y_i(t + \Delta t) = \Theta \left( \sum_{j} w_{ij} x_j(t) - \theta_i \right)$$
3. Absence of Symbolic Structure: These systems possessed no mechanisms for variable binding, dynamic quantification, structural recursion, or the explicit manipulation of formal syntax. Cognitive states were vector points within continuous or high-dimensional binary phase spaces, rendering them incapable of representing nested linguistic clauses, inductive assertions, or counterfactual epistemic operators.

Physical Batch Constraints and Sociotechnical Friction

The reigning mode of computer operation was the closed-shop batch-processing regime:

• Medium: Data and programs were punched onto 80-column Hollerith cards (e.g., via the IBM 026 keypunch).
• Execution Flow: Card decks were surrendered to machine operators, batched onto magnetic tape drives (e.g., IBM 727), and executed sequentially without interactive intervention. Program output—or post-mortem core dumps detailing raw octal register dumps—was written to output tapes, printed on IBM 716 line printers, and returned to researchers hours or days later.
• Epistemic Impedance: The human cognitive feedback loop operates on time scales ranging from $10^{-1}$ to $10^1$ seconds. The batch execution latency ($10^4$ to $10^5$ seconds) created an extreme impedance mismatch. Exploratory symbolic programming, interactive theorem proving, and incremental semantic debugging were impossible under this regime. Software was treated as an immutable, linear execution script rather than an interactive topological medium.

S-Expressions and List Algebra

McCarthy decoupled data structures from physical memory layouts by defining an inductive formal grammar over an alphabet of atomic tokens.

Inductive Definition

Let $\mathcal{A}$ be a countable set of atomic symbols (atomic strings of alphanumeric characters). The universe of Symbolic Expressions (S-expressions), denoted $\mathcal{S}$, is the minimal set closed under the following inductive base and step: $$\begin{aligned} \text{Base:} \quad & \forall a \in \mathcal{A} \implies a \in \mathcal{S} \\ \text{Step:} \quad & \forall e_1, e_2 \in \mathcal{S} \implies (e_1 \cdot e_2) \in \mathcal{S} \end{aligned}$$ The terminal atom $\text{NIL} \in \mathcal{A}$ serves as the canonical empty list. Syntactic lists are defined recursively as dotted pairs whose right element is itself a list: $$(m_1, m_2, \dots, m_n) \equiv (m_1 \cdot (m_2 \cdot (\dots \cdot (m_n \cdot \text{NIL}) \dots )))$$

Elementary Primitives (The McCarthy Basis)

The algebraic structure over $\mathcal{S}$ is generated by five elementary operators:

1. Atomicity Predicate: $$\text{atom}[x] \triangleq \begin{cases} \mathbf{T} & \text{if } x \in \mathcal{A} \\ \mathbf{F} & \text{if } x = (e_1 \cdot e_2) \end{cases}$$
2. Atomic Identity: $$\text{eq}[x; y] \triangleq \begin{cases} \mathbf{T} & \text{if } x, y \in \mathcal{A} \text{ and } x \equiv y \\ \mathbf{F} & \text{if } x, y \in \mathcal{A} \text{ and } x \not\equiv y \\ \text{undefined} & \text{otherwise} \end{cases}$$
3. Left Projector (Contents of the Address part of Register): $$\text{car}[(e_1 \cdot e_2)] \triangleq e_1, \quad \text{car}[a] \text{ is undefined for } a \in \mathcal{A}$$
4. Right Projector (Contents of the Decrement part of Register): $$\text{cdr}[(e_1 \cdot e_2)] \triangleq e_2, \quad \text{cdr}[a] \text{ is undefined for } a \in \mathcal{A}$$
5. Constructor: $$\text{cons}[e_1; e_2] \triangleq (e_1 \cdot e_2), \quad \text{where } e_1, e_2 \in \mathcal{S}$$

Conditional Expressions

Prior to McCarthy, programming statements (e.g., in FORTRAN I) handled conditionality through non-value-returning jump instructions: $$\text{IF } (A - B) \; 10, 20, 30$$ McCarthy introduced the conditional expression as a first-class mathematical function mapping truth-value expressions directly to arbitrary values within an expression tree: $$(p_1 \to e_1, \; p_2 \to e_2, \; \dots, \; p_n \to e_n)$$

Operational Evaluation Semantics

Given an environment $\rho$, the evaluation rule is governed by strict serial evaluation with short-circuiting: $$\llbracket (p_1 \to e_1, \; \dots, \; p_n \to e_n) \rrbracket_\rho \triangleq \begin{cases} \llbracket e_1 \rrbracket_\rho & \text{if } \llbracket p_1 \rrbracket_\rho = \mathbf{T} \\ \llbracket (p_2 \to e_2, \; \dots, \; p_n \to e_n) \rrbracket_\rho & \text{if } \llbracket p_1 \rrbracket_\rho = \mathbf{F} \\ \bot & \text{if } \llbracket p_1 \rrbracket_\rho = \bot \text{ or } n = 0 \end{cases}$$ This operational formulation enabled recursive base-case detection inside pure mathematical expressions without imperative jump escapes.

The Universal Meta-Circular Evaluator: $\text{eval}$ and $\text{apply}$

The cornerstone of McCarthy’s symbolic epistemology was the proof that the semantics of a reflective list-processing language can be formally expressed via a function within the language itself, taking expressions encoded as S-expressions as inputs.

Let an environment (association list) $a$ be represented as an S-expression of key-value dotted pairs: $$a = ((x_1 \cdot v_1) \cdot ((x_2 \cdot v_2) \cdot \dots \cdot \text{NIL}))$$

McCarthy formulated the mutual recursion of $\text{eval}$ and $\text{apply}$ (presented here in modern mathematical meta-notation reflecting the 1960 CACM paper):

$$\begin{aligned} \text{eval}[e; a] = [ & \text{atom}[e] \to \text{cdr}[\text{assoc}[e; a]]; \\ & \text{atom}[\text{car}[e]] \to [ \\ &\quad \text{eq}[\text{car}[e]; \text{QUOTE}] \to \text{cadr}[e]; \\ &\quad \text{eq}[\text{car}[e]; \text{ATOM}] \to \text{atom}[\text{eval}[\text{cadr}[e]; a]]; \\ &\quad \text{eq}[\text{car}[e]; \text{EQ}] \to \text{eq}[\text{eval}[\text{cadr}[e]; a]; \text{eval}[\text{caddr}[e]; a]]; \\ &\quad \text{eq}[\text{car}[e]; \text{CAR}] \to \text{car}[\text{eval}[\text{cadr}[e]; a]]; \\ &\quad \text{eq}[\text{car}[e]; \text{CDR}] \to \text{cdr}[\text{eval}[\text{cadr}[e]; a]]; \\ &\quad \text{eq}[\text{car}[e]; \text{CONS}] \to \text{cons}[\text{eval}[\text{cadr}[e]; a]; \text{eval}[\text{caddr}[e]; a]]; \\ &\quad \text{eq}[\text{car}[e]; \text{COND}] \to \text{evcon}[\text{cdr}[e]; a]; \\ &\quad \mathbf{T} \to \text{apply}[\text{car}[e]; \text{evlis}[\text{cdr}[e]; a]; a] \\ & ]; \\ & \mathbf{T} \to \text{apply}[\text{car}[e]; \text{evlis}[\text{cdr}[e]; a]; a] ] \end{aligned}$$

$$\begin{aligned} \text{apply}[f; x; a] = [ & \text{atom}[f] \to [ \\ &\quad \text{eq}[f; \text{CAR}] \to \text{caar}[x]; \\ &\quad \text{eq}[f; \text{CDR}] \to \text{cdar}[x]; \\ &\quad \text{eq}[f; \text{CONS}] \to \text{cons}[\text{car}[x]; \text{cadr}[x]]; \\ &\quad \mathbf{T} \to \text{eval}[\text{cons}[f; \text{mapquote}[x]]; a] \\ & ]; \\ & \text{eq}[\text{car}[f]; \lambda] \to \text{eval}[\text{caddr}[f]; \text{pairlis}[\text{cadr}[f]; x; a]]; \\ & \text{eq}[\text{car}[f]; \text{LABEL}] \to \text{apply}[\text{caddr}[f]; x; \text{cons}[\text{cons}[\text{cadr}[f]; \text{caddr}[f]]; a]] ] \end{aligned}$$

Auxiliary functions $\text{evcon}$ and $\text{assoc}$ maintain semantics: $$\begin{aligned} \text{evcon}[c; a] = [ & \text{eval}[\text{caar}[c]; a] \to \text{eval}[\text{cadar}[c]; a]; \\ & \mathbf{T} \to \text{evcon}[\text{cdr}[c]; a] ] \end{aligned}$$ $$\begin{aligned} \text{assoc}[x; a] = [ & \text{eq}[\text{caar}[a]; x] \to \text{car}[a]; \\ & \mathbf{T} \to \text{assoc}[x; \text{cdr}[a]] ] \end{aligned}$$

This formulation established that an interpreter is simply an explicit state machine over trees, fundamentally proving that any sufficiently expressive recursive list processor can evaluate its own semantic definition.

Recursion Induction

In 1963, McCarthy established the mathematical basis for verifying program equivalence over non-numerical domains through Recursion Induction.

Let two functions $f$ and $g$ be defined recursively over a domain $\mathcal{D}$. To prove $\forall x \in \mathcal{D}, f(x) = g(x)$: 1. Identify a system of recursive conditional equations satisfied by $f$: $$\mathcal{F}[\phi] = \phi$$ 2. Substitute $g$ into $\mathcal{F}$. If $\mathcal{F}[g] = g$ identically over the domain where both functions converge (terminate), then $f$ and $g$ compute identical functions over the common convergence subdomain: $$\text{Domain}(f) \cap \text{Domain}(g) \implies f(x) \equiv g(x)$$ This liberated algorithmic correctness proofs from hardware execution traces, grounding them directly in the algebra of recursively constructed symbolic structures.

Epistemic Logic: The Situation Calculus

In 1969, McCarthy and Patrick J. Hayes formalized an axiomatic framework for dynamic environments, creating the Situation Calculus.

Formal Ontology

• Situations ($\mathcal{S}$): A set of first-order objects denoting complete instantaneous snapshots of the universe.
• Fluents ($\mathcal{F}$): Functions whose values vary across situations. A propositional fluent is a function: $$f: \mathcal{S} \to \{\mathbf{T}, \mathbf{F}\}$$ Alternatively, situational predicates are expressed as $P(s)$ or $\text{Holds}(f, s)$.
• Actions ($\mathcal{A}$): First-order terms designating acts executable by an agent.
• Dynamic Transition Function: $$\text{result}: \mathcal{A} \times \mathcal{S} \to \mathcal{S}$$ $\text{result}(a, s)$ returns the successor situation realized after the execution of action $a$ in situation $s$.

Causal Axiomatization

Dynamic state changes are codified via effect axioms: $$\forall s \, \big( \text{Holds}(\text{At}(\text{agent}, x), s) \land \text{Adjacent}(x, y) \implies \text{Holds}(\text{At}(\text{agent}, y), \, \text{result}(\text{move}(x, y), s)) \big)$$

The Frame Problem

Standard classical first-order logic requires positive deduction; it does not assume that unmentioned states remain static. To state that moving an object does not alter the color of an unrelated object, classical logic requires explicit Frame Axioms: $$\forall s, a, x, c \, \big( \text{Holds}(\text{Color}(x, c), s) \land a \neq \text{paint}(x) \implies \text{Holds}(\text{Color}(x, c), \, \text{result}(a, s)) \big)$$ For an ontology of $|\mathcal{A}|$ actions and $|\mathcal{F}|$ fluents, this demands the generation and verification of $\mathcal{O}(|\mathcal{A}| \times |\mathcal{F}|)$ non-effect axioms, generating combinatorial computational intractability.

Mathematical Non-Monotonic Reasoning: Predicate Circumscription

To resolve the Frame Problem and the brittleness of monotonic classical logic (where $\Gamma \vdash \phi \implies \Gamma \cup \{\psi\} \vdash \phi$), McCarthy invented Circumscription (1980). This formal framework enables common-sense reasoning by syntactically minimizing the extension of chosen predicates.

Second-Order Formula

Let $A(P)$ be a first-order sentence containing a tuple of predicate symbols $P = (P_1, \dots, P_n)$ alongside other non-minimized parameters. Let $\Phi = (\Phi_1, \dots, \Phi_n)$ be predicate variables of identical arities.

Define the partial order of predicate subsumption: $$(\Phi \le P) \triangleq \bigwedge_{i=1}^n \forall \bar{x} \, (\Phi_i(\bar{x}) \to P_i(\bar{x}))$$ $$(\Phi < P) \triangleq (\Phi \le P) \land \neg (P \le \Phi)$$

The circumscription of $P$ in sentence $A(P)$, written $\text{Circ}(A; P)$, is the second-order sentence: $$\text{Circ}(A; P) \triangleq A(P) \land \forall \Phi \, \big[ (A(\Phi) \land (\Phi \le P)) \implies (P \le \Phi) \big]$$

Expanded into explicit universal implication: $$\text{Circ}(A; P) \triangleq A(P) \land \forall \Phi \, \left[ \left( A(\Phi) \land \forall \bar{x} \, (\Phi(\bar{x}) \to P(\bar{x})) \right) \implies \forall \bar{x} \, (P(\bar{x}) \to \Phi(\bar{x})) \right]$$

Model-Theoretic Characterization

Let $\mathcal{M}_1, \mathcal{M}_2$ be two models of $A(P)$ sharing the same universe $\mathcal{D}$ and identical interpretations for all non-logical constants except $P$. $$\mathcal{M}_1 \le_P \mathcal{M}_2 \iff P^{\mathcal{M}_1} \subseteq P^{\mathcal{M}_2}$$ A model $\mathcal{M}$ is a $P$-minimal model of $A(P)$ if there is no model $\mathcal{M}'$ of $A(P)$ such that $\mathcal{M}' <_P \mathcal{M}$.

McCarthy established the completeness of circumscription relative to minimal models: $$\mathcal{M} \models \text{Circ}(A; P) \iff \mathcal{M} \text{ is a } P\text{-minimal model of } A(P)$$ This mathematical leap guaranteed that default assertions—e.g., an abnormal state $\text{Ab}(x)$ is presumed false unless compelled otherwise by $A$—are syntactically enforceable inside symbolic deductive systems.

The IBM 704 Register Architecture & The Genesis of cons

The physical architecture of the IBM 704 directly determined the vocabulary and operational mechanics of pointer structures in early computer science:

                      IBM 704 36-BIT HARDWARE WORD
 0    2 3                  17 18 20 21                     35
+------+---------------------+-----+-------------------------+
| PREFIX|      DECREMENT      | TAG |         ADDRESS         |
+------+---------------------+-----+-------------------------+
   3 b          15 bits        3 b            15 bits
                   │                               │
                   ▼                               ▼
            Stored in CDR                   Stored in CAR
       (Contents of Decrement)         (Contents of Address)

By mapping two 15-bit address spaces into a single physical 36-bit word, McCarthy realized the fundamental list building block: the binary tree node (cons cell).

                      LOGICAL CONS-CELL TOPOLOGY
                +-------------------+-------------------+
                |      CAR Ptr      |      CDR Ptr      |
                |  (Bits 21-35)     |    (Bits 3-17)    |
                +---------+---------+---------+---------+
                          │                   │
                          ▼                   ▼
                     Payload Node       Next Cons-Cell
                     (e.g., ATOM)              │
                                               ▼
                                     +---------+---------+
                                     |   CAR   |   CDR   |──> NIL
                                     +----+----+---------+
                                          │
                                          ▼
                                    Payload Node

The Mark-and-Sweep Garbage Collection Engine (1959)

McCarthy decoupled dynamic pointer allocation from manual hardware memory reclamation by introducing the first automatic runtime garbage collector:

 [ Phase 1: Normal Allocation / Heap Exhaustion ]
   Free-List Traversal:
   FREE ──> [Cell 1] ──> [Cell 2] ──> ... ──> NIL
   (Consing decrements available pointer nodes until FREE == NIL)
                               │
                               ▼ 
                 Heap Exhaustion Triggered
                               │
                               ▼
 [ Phase 2: Root-Set Identification & Graph Mark Phase ]
   Global Pointer Roots: [ Base Registers ] ∪ [ Object Push-Down List ] ∪ [ Oblist ]
                               │
                               ▼
   Traverse Accessible Graph recursively via CAR and CDR pointers:
   For every reachable node: Set Mark-Bit = 1
   (Unreachable orphan nodes retain Mark-Bit = 0)
                               │
                               ▼
 [ Phase 3: Linear Physical Core Sweep Phase ]
   Scan physical memory words contiguously from HEAP_START to HEAP_END:

           Memory Address:  k          k+1        k+2        k+3
                          +----------+----------+----------+----------+
            Core Cell:    | Cell_k   | Cell_k+1 | Cell_k+2 | Cell_k+3 |
            Mark Bit:     |    1     |    0     |    1     |    0     |
                          +----+-----+----+-----+----+-----+----+-----+
                               │          │          │          │
                               ▼          ▼          ▼          ▼
                            Preserve   Reclaim!   Preserve   Reclaim!
                           (Reset Bit) (Prepend              (Prepend
                                       to Free)              to Free)
                                          │                     │
                                          └──────────┬──────────┘
                                                     ▼
                                      Reconstructed FREE List:
                                      FREE ──> [Cell_k+3] ──> [Cell_k+1]

The Architecture of Time-Sharing (1959 MIT Design)

Prior to McCarthy's January 1, 1959 internal memorandum, computation was strictly mono-programmed and non-preemptive. McCarthy designed the architectural mechanics required to dynamically cycle an expensive central core across decoupled, low-cost human input terminals:

               +-------------------------------------------+
               |     CENTRAL PROCESSING UNIT (IBM 704)     |
               |  - Interrupt-Driven Hardware Relocation   |
               |  - Paged Memory Limits / Protection Keys  |
               +---------------------+---------------------+
                                     │
                        High-Speed Direct Channel
                                     │
                                     ▼
               +-------------------------------------------+
               |        HIGH-SPEED MAGNETIC CORE/DRUM       |
               |  Active User Workspace Dynamic Relocation |
               +---------------------+---------------------+
                                     │
                     Hardware Multiplexer Controller
                                     │
             ┌───────────────────────┼───────────────────────┐
             │ Interleaved           │ Interleaved           │ Interleaved
             ▼ Time-Slices           ▼ Time-Slices           ▼ Time-Slices
       +-----------+           +-----------+           +-----------+
       | Teletype  |           | Teletype  |           | Teletype  |
       | Terminal  |           | Terminal  |           | Terminal  |
       |  User 1   |           |  User 2   |           |  User N   |
       +-----------+           +-----------+           +-----------+
         (Human                  (Human                  (Human
       Read-Eval-              Read-Eval-              Read-Eval-
       Print Loop)             Print Loop)             Print Loop)

The IBM 704 Implementation (MIT Building 26, 1958–1959)

The theoretical formulation of symbolic processing was verified on the MIT Computation Center's IBM 704 vacuum-tube computing system.

• Physical Testbed: IBM 704 with 8,192 36-bit words of core storage (later upgraded to 32,768 words). Machine cycle time: 12 microseconds. Secondary storage: IBM 727 magnetic tape units, IBM 737 magnetic core storage unit.
• The Assembly Effort: McCarthy, aided by Steve Russell, Paul Abrahams, Fischer Black, and Nathaniel Rochester, specified the system as "LISP I".
• Russell's Meta-Circular Implementation Proof: In late 1958, McCarthy published the mathematical specification of eval (using universal M-expressions to compute values of S-expressions) as a conceptual proof-of-principle, asserting that it could serve as a functional interpreter. Steve Russell observed that eval could be directly implemented as an IBM 704 machine language routine:
• Hand-coded the machine language version of eval directly into SAP (Share Assembly Program) for the IBM 704.
• Used eval as an operative interpreter rather than compiling code down to machine language, proving empirically that McCarthy's algebraic formulation of eval was computationally complete and operational.

The Wang vs. McCarthy Propositional Logic Trials (1959)

To evaluate the viability of symbolic processing versus algorithmic numerical automation, McCarthy and Hao Wang implemented deductive inference algorithms on the IBM 704: * Apparatus: A 704 program running Wang's algorithmic decision procedure for the propositional calculus (based on a sequent-calculus refinement of Herbrand's theorem). * Empirical Metric: Evaluation of all 220 propositional logic theorems from Chapters 1 through 5 of Whitehead and Russell's Principia Mathematica. * Result: Wang's system proved all 220 theorems in under 3 minutes of central processor time. This experiment verified McCarthy's thesis that symbolic list processing could handle discrete combinatorial deduction at speeds exceeding human paper-and-pencil performance, invalidating the cybernetic claim that cognitive modeling required continuous-state feedback.

The First Operational Time-Sharing Prototype (1961–1962)

McCarthy’s 1959 time-sharing proposal was experimentally validated across two distinct platforms: 1. The MIT PDP-1 Modification: Working with Digital Equipment Corporation, McCarthy helped design the architecture of an interrupt-driven memory-modification board on a DEC PDP-1. In early 1962, this machine was successfully configured to drive multiple interactive Flexowriters simultaneously. 2. The Compatible Time-Sharing System (CTSS): Built on an IBM 7090 at MIT by Fernando Corbató and based directly on the design criteria McCarthy articulated in his 1959 memorandum to John Russell (relocation registers, interrupt timers, drum-to-core memory swapping). The deployment of CTSS verified that interactive user computing increased human cognitive productivity by orders of magnitude while keeping machine hardware capacity utilized near saturation.

1. The Hanks-McDermott Shooting Problem (1986)

The primary failure mode of McCarthy’s Circumscription framework emerged in temporal non-monotonic reasoning. Steve Hanks and Drew McDermott demonstrated that syntactic predicate minimization can yield non-intended, non-intuitive minimal models.

The Scenario

• Fluents: $\text{Alive}, \text{Loaded}$.
• Actions: $\text{Load}, \text{Wait}, \text{Shoot}$.
• Axioms: 1. $\text{Holds}(\text{Alive}, s_0)$ 2. $\forall s \, \text{Holds}(\text{Loaded}, \text{result}(\text{Load}, s))$ 3. $\forall s \, (\text{Holds}(\text{Loaded}, s) \implies \neg \text{Holds}(\text{Alive}, \text{result}(\text{Shoot}, s)) \land \neg \text{Holds}(\text{Loaded}, \text{result}(\text{Shoot}, s)))$ 4. Minimizing the abnormal fluent $\text{Ab}(a, f, s)$ through Circumscription: $$\forall a, f, s \, (\neg \text{Ab}(a, f, s) \land \text{Holds}(f, s) \implies \text{Holds}(f, \text{result}(a, s)))$$

The Mechanical Breakdown

Consider the situation trajectory: $$s_1 = \text{result}(\text{Load}, s_0), \quad s_2 = \text{result}(\text{Wait}, s_1), \quad s_3 = \text{result}(\text{Shoot}, s_2)$$

Circumscription seeks to minimize the global set of abnormalities: $$\mathcal{E} = \{ (a, f, s) \mid \text{Ab}(a, f, s) \}$$

• Intended Model ($M_1$):
• The gun stays loaded throughout the wait action: $\neg \text{Ab}(\text{Wait}, \text{Loaded}, s_1)$.
• Shooting kills the victim: $\text{Ab}(\text{Shoot}, \text{Alive}, s_2)$.
• Total abnormality instances: 1.
• Unintended "Skeptical" Model ($M_2$):
• The gun mysteriously unloads itself during the wait action: $\text{Ab}(\text{Wait}, \text{Loaded}, s_1)$.
• The victim remains alive after shooting: $\neg \text{Ab}(\text{Shoot}, \text{Alive}, s_2)$.
• Total abnormality instances: 1.

Because both models possess an abnormality extension of cardinality 1, Circumscription declares them logically equivalent. The system cannot deduce that the victim is dead: $$\text{Circ}(A; \text{Ab}) \not\models \neg \text{Holds}(\text{Alive}, s_3)$$ This demonstrated that purely static predicate minimization cannot account for the directional flow of causality in temporal domains.

2. The Semantic Scope Conflict (Dynamic vs. Lexical Scope)

In the original 1960 Lisp formulation, McCarthy implemented variable environments using a single global association list: $$\text{assoc}[x; a]$$

The Scope Failure Mode

When higher-order functions (functions passed as arguments or returned as values) are evaluated, free variables are dynamically captured by the calling environment rather than the defining environment:

(DEFINE (FOO (LAMBDA (X)
  (LAMBDA (Y) (CONS X Y)))))

(DEFINE (BAR (LAMBDA (FUN)
  (LET ((X 100))
    (FUN 2))))

If evaluating ((FOO 1) 2), the variable X must resolve to 1. However, in McCarthy’s original dynamic environment architecture: 1. (FOO 1) returns a naked $\lambda$-term without an environment closure: (LAMBDA (Y) (CONS X Y)). 2. When applied inside BAR, the reference to X binds dynamically to BAR's local variable X = 100. 3. The expression returns (100 . 2) instead of (1 . 2).

This dynamic scoping bug—the "Funarg Problem" identified by Joel Moses in 1970—persisted in symbolic Lisp systems until Guy Steele and Gerald Sussman integrated Alonzo Church's true lexical closures into Scheme in 1975, standardizing static lexical scope in Common Lisp (1984).

3. Hardware Overhead and Memory Fragmentation

Early dynamic pointer execution exposed major performance limits on core-memory architectures:

• Locality of Reference: Lisp's non-contiguous, pointer-chained graph structures undermined cache lines and virtual memory systems. While a contiguous FORTRAN array allowed for prefetching and localized memory references, sequential traversals of deep cons cells traversed disjoint memory banks, causing persistent translation-lookaside buffer (TLB) misses and paging thrashing ("page-fault storms").
• Stop-the-World Latency: McCarthy’s original Mark-and-Sweep garbage collector was synchronous and non-incremental. Marking required freezing the entire execution thread while recursively traversing the live pointer graph, causing multi-second latency spikes unusable for hard real-time systems.

(Badge Key: V Verified Verified Primary Source; C Corroborated Corroborated Multi-Source; S Single-Source Single Source; I Interpretation Critical Interpretation).

Foundational Monographs and Treatises

1. McCarthy, J., Minsky, M. L., Rochester, N., & Shannon, C. E. (1955). A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence. Dartmouth College / Rockefeller Foundation Manuscript. * Archival Role: Coined "Artificial Intelligence." Grounded the symbolic conjecture: that every function of intellectual behavior can be formally simulated via discrete symbolic manipulators.
2. McCarthy, J. (1959). Memorandum to J. H. Russell: A Proposal for a Computer Operating System that Permits Time-Sharing. MIT Computation Center Archives, Cambridge, MA. * Archival Role: The foundational design document for general-purpose interactive time-sharing. Specified memory partitioning, relocation registers, interrupt vectors, and teletype multiplexing.
3. McCarthy, J. (1960). "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I." Communications of the ACM, Vol. 3, No. 4, pp. 184–195. * Archival Role: The canonical Lisp foundation paper. Introduced the S-expression, the five primitive operations (car, cdr, cons, atom, eq), first-class conditional expressions, dynamic recursion, the automatic mark-and-sweep garbage collector, and the universal meta-circular eval.
4. McCarthy, J. (1963). "A Basis for a Mathematical Science of Computation." In P. Braffort & D. Hirschberg (Eds.), Computer Programming and Formal Systems, North-Holland Publishing Company, Amsterdam, pp. 33–70. * Archival Role: Pioneered mathematical program semantics, state transformations, conditional expressions as primitive algebraic operators, and the technique of Recursion Induction for proving code correctness.
5. McCarthy, J., & Hayes, P. J. (1969). "Some Philosophical Problems from the Standpoint of Artificial Intelligence." In B. Meltzer & D. Michie (Eds.), Machine Intelligence 4, Edinburgh University Press, pp. 463–502. * Archival Role: Formally defined the Situation Calculus, situational fluents, the causal operator $\text{result}(a, s)$, epistemological vs. heuristic adequacy, and provided the first formal articulation of the Frame Problem.
6. McCarthy, J. (1980). "Circumscription—A Form of Non-Monotonic Reasoning." Artificial Intelligence, Vol. 13, Nos. 1–2, pp. 27–39. * Archival Role: Introduced the mathematical schema of predicate circumscription, proving that common-sense default reasoning can be formalized as second-order predicate minimization over first-order theories.
7. McCarthy, J. (1986). "Applications of Circumscription to Formalizing Common-Sense Knowledge." Artificial Intelligence, Vol. 28, No. 1, pp. 89–116. * Archival Role: Advanced circumscription into domain axiomatizations using abnormal predicates ($\text{Ab}$), addressing qualification and default inheritance structures.

Critical Archival Commentaries

• Corbató, F. J. (1990). "On Building Systems That Will Fail." ACM Turing Award Lecture. (Explicitly cites McCarthy’s 1959 MIT internal memorandum as the engineering catalyst for the creation of CTSS and Multics).
• Hanks, S., & McDermott, D. (1986). "Default Reasoning, Nonmonotonic Logics, and the Frame Problem: Why Tms and Nonmonotonic Logics Don't Work." Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI-86), pp. 328–333. (Exposed the fundamental mathematical failure mode of circumscription in temporal dynamics).
• Steele, G. L., & Sussman, G. J. (1978). "The Revised Report on SCHEME: A Dialect of LISP." MIT AI Memo No. 452. (Archival resolution of McCarthy’s dynamic scope limit through lexical closures based on Church’s pure $\lambda$-calculus).