Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

Symbols vs. Connections

The long debate between logic and neural networks.

Is intelligence the rule-governed manipulation of symbols, or the settling of a network of simple units into useful patterns? The argument has run for seventy years, and it has produced real theorems: about what perceptrons cannot compute, about how vectors can bind roles to fillers, and about what it would take to be systematic. It has not ended. It has moved inside today's models.

What you’ll learn

  • State and prove Minsky and Papert's theorem that parity has order nn, and contrast it with a two-layer network that computes parity with nn hidden units.
  • Explain distributed representations and the PDP program, and why backpropagation revived connectionism in 1986.
  • Reconstruct Fodor and Pylyshyn's systematicity argument, and evaluate the connectionist replies, including tensor product representations.
  • Assess the modern evidence on compositional generalization, and the case for neurosymbolic hybrids.

What a perceptron cannot see

The two traditions were born together. Symbolic AI crystallized in Newell and Simon's physical symbol system hypothesis (1976): "A physical symbol system has the necessary and sufficient means for general intelligent action." Connectionism grew from McCulloch and Pitts (1943), Hebb's learning postulate (1949) and Rosenblatt's perceptron (1958). Minsky and Papert's Perceptrons (1969) gave the first deep analysis of what a layer of learnable weights can compute.

DerivationProof by symmetrization
  1. ψ(x)=[ p(x)>θ ],p(x)=∑∣T∣≤kcT∏i∈Txi\psi(x)=\big[\,p(x)>\theta\,\big],\qquad p(x)=\sum_{\abs T\le k}c_T\prod_{i\in T}x_i

    Write inputs as x∈{0,1}nx\in\{0,1\}^n. A predicate with support SS is a Boolean function of (xi)i∈S(x_i)_{i\in S}, hence a multilinear polynomial in those variables of degree at most ∣S∣\abs S. So an order-kk perceptron computes [ p(x)>θ ][\,p(x)>\theta\,] for a multilinear polynomial pp of degree at most kk.

  2. q=1n!∑σp∘σ,q(x)=Q(∣x∣),deg⁡Q≤kq=\frac{1}{n!}\sum_{\sigma}p\circ\sigma,\qquad q(x)=Q\big(\abs x\big),\qquad\deg Q\le k

    Parity is invariant under permutations σ\sigma of the retina, so every p∘σp\circ\sigma also represents it, and so does their average qq (averaging preserves ">θ>\theta on odd inputs, ≤θ\le\theta on even ones"). The average is symmetric, so it depends only on m=∣x∣m=\abs x, and since ∑∣T∣=j∏i∈Txi=(mj)\sum_{\abs T=j}\prod_{i\in T}x_i=\binom{m}{j} is a polynomial of degree jj in mm, q(x)=Q(m)q(x)=Q(m) with deg⁡Q≤k\deg Q\le k.

  3. sign⁡(Q(m)−θ′)=(−1)m+1(m=0,…,n) ⟹ deg⁡Q≥n\operatorname{sign}\big(Q(m)-\theta'\big)=(-1)^{m+1}\quad(m=0,\dots,n)\ \Longrightarrow\ \deg Q\ge n

    Raise θ\theta slightly to θ′\theta' so that even counts give strictly negative values. Then Q(m)−θ′Q(m)-\theta' alternates in sign on m=0,1,…,nm=0,1,\dots,n, so it has a root in each of the nn intervals (m,m+1)(m,m+1).

  4. hj=[∑ixi≥j],ψpar=[∑j=1n(−1)j+1hj≥1]h_j=\Big[\sum_ix_i\ge j\Big],\qquad\psi_{\mathrm{par}}=\Big[\sum_{j=1}^n(-1)^{j+1}h_j\ge1\Big]

    Hence k≥nk\ge n. With a hidden layer, parity is easy: nn threshold units count "at least jj inputs are on", and the output combines them with alternating signs.

Think first Check the two-layer construction: why does ∑j=1n(−1)j+1hj\sum_{j=1}^n(-1)^{j+1}h_j equal the parity of xx?

If mm inputs are on, exactly h1,…,hmh_1,\dots,h_m fire, so the sum is 1−1+1−⋯1-1+1-\cdots with mm terms: 11 when mm is odd and 00 when mm is even. So n+1n+1 threshold units compute what no single layer of local features can.

Minsky and Papert also showed that the connectedness of a figure is not of bounded order. Their book is often blamed for the decline of neural network research in the 1970s; historians debate how much it caused that decline and how much it reflected it. In the 1988 expanded edition they argued that multilayer networks would face analogous scaling problems, a challenge the following decades answered only in part.

Parallel distributed processing

The two Parallel Distributed Processing volumes of 1986 (Rumelhart, McClelland and the PDP Research Group) relaunched the program. They brought backpropagation to a wide audience and showed hidden units discovering features nobody had programmed: a network trained on family relationships learned codes for nationality and generation.

They also modeled the English past tense with a single network that, like children, went through a phase of overregularizing ("goed"). Pinker and Prince (1988) replied that the model's failures showed the need for explicit rules alongside memory, opening a decade-long "past tense debate".

Distributed codes capture similarity, and some relational structure, for free. Do they capture the combinatorial structure of thought, where "John loves Mary" and "Mary loves John" share their constituents but differ in who does what to whom? That is the challenge Fodor and Pylyshyn posed.

The systematicity challenge

Fodor and Pylyshyn (1988) argued that human thought is systematic (anyone who can think John loves Mary can think Mary loves John) and productive (we can think indefinitely many new thoughts). A classical architecture explains both: representations have a combinatorial syntax, and the same constituent appears in many structures. Connectionism then faces a dilemma.

Smolensky's reply was to show that vectors can carry structure without classical concatenation. A tensor product representation binds each filler vector fi\mathbf f_i to a role vector ri\mathbf r_i by an outer product, and superimposes the bindings.

DerivationBinding and unbinding with tensor products
  1. T=∑ifi ri⊤,loves(John, Mary)=fJohnragent⊤+fMaryrpatient⊤\mathbf T=\sum_i\mathbf f_i\,\mathbf r_i^\top,\qquad\text{loves(John, Mary)}=\mathbf f_{\text{John}}\mathbf r_{\text{agent}}^\top+\mathbf f_{\text{Mary}}\mathbf r_{\text{patient}}^\top

    Encode a structure with roles (say agent and patient) and fillers (John, Mary) as a single matrix:

  2. T rj=∑ifi(ri⊤rj)=fj\mathbf T\,\mathbf r_j=\sum_i\mathbf f_i\big(\mathbf r_i^\top\mathbf r_j\big)=\mathbf f_j

    If the role vectors are orthonormal, multiplying by a role vector recovers its filler exactly:

  3. loves(Mary, John)=fMaryragent⊤+fJohnrpatient⊤\text{loves(Mary, John)}=\mathbf f_{\text{Mary}}\mathbf r_{\text{agent}}^\top+\mathbf f_{\text{John}}\mathbf r_{\text{patient}}^\top

    Swapping who loves whom swaps the bindings: a different matrix built from the same constituents, systematicity by linear algebra. With roles that are merely linearly independent, unbind with the dual basis instead. The price is size: the dimension grows multiplicatively, dim⁡f×dim⁡r\dim\mathbf f\times\dim\mathbf r, and recursive structures need higher-order tensors or lossy compression.

Check your understanding

With orthonormal role vectors, T=f1r1⊤+f2r2⊤\mathbf T=\mathbf f_1\mathbf r_1^\top+\mathbf f_2\mathbf r_2^\top. How do you retrieve f2\mathbf f_2?

  1. T⊤f2\mathbf T^\top\mathbf f_2
  2. T r1\mathbf T\,\mathbf r_1
  3. r2⊤T\mathbf r_2^\top\mathbf T
  4. T r2\mathbf T\,\mathbf r_2
Show the answer

D. T r2\mathbf T\,\mathbf r_2

Tr2=f1(r1⊤r2)+f2(r2⊤r2)=0+f2\mathbf T\mathbf r_2=\mathbf f_1(\mathbf r_1^\top\mathbf r_2)+\mathbf f_2(\mathbf r_2^\top\mathbf r_2)=0+\mathbf f_2.

Other replies followed: networks that transform distributed encodings of whole structures directly (Pollack's recursive auto-associative memories and Chalmers's active-to-passive transformations, both 1990), and the argument that compositionality can be functional rather than concatenative (van Gelder, 1990).

The empirical test came later. In SCAN (Lake and Baroni, 2018), sequence-to-sequence networks that mapped commands such as "jump twice" to action sequences scored near-perfectly on random splits, but failed when a primitive seen only in isolation ("jump") had to be combined in new ways. In 2023 the same authors showed that a standard transformer trained by meta-learning over many compositional tasks matched human systematic generalization on their tasks: compositionality can be learned, given the right training distribution.

The debate moves inside the models

Deep learning's victories in perception (from 2012) and language (from 2017) seemed to settle the matter in connectionism's favor. The old questions came back in new form: out-of-distribution and compositional generalization, data efficiency, reliable multi-step reasoning, and opacity. Marcus (2018) argued that deep learning alone would not deliver robust abstraction and called for hybrids. Meanwhile the most celebrated systems already were hybrids:

SystemLearned (connectionist) partSymbolic or search part
AlphaGo and AlphaZero (2016–17)policy and value networksMonte Carlo tree search over the game's rules
AlphaGeometry (2024)a language model that proposes auxiliary constructionsa symbolic deduction engine that proves olympiad geometry problems
DeepProbLog (2018)neural predicates for perceptionprobabilistic logic programming
Language models with toolsa transformer language modelcalculators, code interpreters, theorem provers and solvers that it calls
Neurosymbolic designs divide the labor: networks for perception and intuition, symbolic machinery for exact rules, search and verification.

At the same time, interpretability research finds symbol-like structure inside trained networks: induction heads that copy earlier tokens to continue repeated patterns (Olsson et al., 2022), internal board states in models trained only on game moves, and features that behave like variables. If networks learn to implement symbolic computation where it helps, both camps were partly right: Fodor and Pylyshyn about what cognition needs, the connectionists about how it can be acquired.

Key takeaways

  • Parity has order nn (by symmetrization and counting sign changes), yet nn hidden threshold units compute it: Minsky and Papert's limits concern single layers of local features, not networks.
  • The PDP program (1986) revived connectionism with backpropagation and distributed representations, which encode similarity and some relational structure, such as analogy offsets.
  • Fodor and Pylyshyn's dilemma: without constituent structure, no systematicity; with it, mere implementation. Tensor product representations bind roles to fillers (Trj=fj\mathbf T\mathbf r_j=\mathbf f_j) without classical concatenation.
  • SCAN exposed failures of compositional generalization; meta-learning, hybrids such as AlphaGo and AlphaGeometry, and interpretability findings suggest the debate is now about what networks learn internally.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A single-layer perceptron on an nn-point retina uses only predicates that each look at fewer than nn points. What follows for parity?

  1. It can compute parity if it has enough predicates
  2. It can compute parity if its weights are large enough
  3. It cannot compute parity, whatever its weights or number of predicates
  4. It can compute parity, but only for even nn
Show the answer

C. It cannot compute parity, whatever its weights or number of predicates

Parity has order nn: any representing polynomial has degree nn, which requires a predicate whose support is the whole retina. No choice of weights changes the degree.

Question 2

How many hidden threshold units does the construction hj=[∑ixi≥j]h_j=\big[\sum_ix_i\ge j\big] use to compute nn-bit parity?

  1. nn
  2. 2n2^n
  3. log⁡2n\log_2n
  4. n2n^2
Show the answer

A. nn

One unit per threshold j=1,…,nj=1,\dots,n; the output alternates their signs. A hidden layer turns a predicate of order nn into a network of linear size.

Question 3

According to Fodor and Pylyshyn, what follows if a connectionist model does explain systematicity?

  1. Connectionism is refuted
  2. The model merely implements a classical symbol system, so it is not an alternative theory of cognition
  3. Symbolic AI is refuted
  4. The model must be a lookup table
Show the answer

B. The model merely implements a classical symbol system, so it is not an alternative theory of cognition

That is the second horn of the dilemma: structure-sensitive processing requires constituent structure, which they take to be the classical architecture, merely implemented in a network.

Question 4

What did Lake and Baroni's SCAN experiments (2018) show?

  1. Neural networks cannot learn any mapping from commands to actions
  2. Recurrent networks generalize compositionally as well as people do
  3. Transformers solve every split of SCAN
  4. Standard sequence-to-sequence networks did well on random splits but failed to use a primitive seen only in isolation in new combinations
Show the answer

D. Standard sequence-to-sequence networks did well on random splits but failed to use a primitive seen only in isolation in new combinations

Near-perfect accuracy on random train/test splits hid a failure of systematic generalization to new combinations, the kind Fodor and Pylyshyn predicted. Later work showed that meta-learning can close much of the gap.

Further reading

  • M. Minsky & S. Papert, Perceptrons: An Introduction to Computational Geometry (MIT Press, 1969; expanded edition 1988).
  • D. E. Rumelhart, J. L. McClelland & the PDP Research Group, Parallel Distributed Processing: Explorations in the Microstructure of Cognition, vols. 1–2 (MIT Press, 1986).
  • J. A. Fodor & Z. W. Pylyshyn, "Connectionism and cognitive architecture: A critical analysis," Cognition 28, 3–71 (1988).
  • P. Smolensky, "Tensor product variable binding and the representation of symbolic structures in connectionist systems," Artificial Intelligence 46, 159–216 (1990).
  • B. M. Lake & M. Baroni, "Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks," ICML (2018).