What Is a Symbolic System?

Three Parts, One System

A symbolic system is a triple:

1. An alphabet: a finite set of tokens (symbols).
2. A grammar (formation rules): which finite sequences of tokens count as well-formed expressions of the system.
3. An interpretation (semantics): a rule for assigning meaning to the well-formed expressions.

The first two parts are syntactic. The third is semantic. Together they make a symbolic system usable: the syntax says which strings are legal, the semantics says what those strings denote.

Many systems share this structure:

The shared structure is what lets results in one system bear on another. Gödel's encoding of arithmetic in arithmetic, the trick that makes incompleteness work, exploits this unification: a single notion of formal symbol-manipulation captures arithmetic, the lambda calculus, and Turing machines (the Church-Turing thesis is the claim that all reasonable formalizations of "effective procedure" pick out the same class of functions).

Building One From Scratch

To make the abstraction concrete, we will define a tiny symbolic system and run a derivation in it. Call it $\mathcal{S}$.

Step 1: alphabet

Take five tokens: $\{0, S, +, =, \texttt{?}\}$.

The semantics will be: $0$ denotes zero, $S$ is the successor function (think plus one), $+$ is addition, $=$ is equality, and $\texttt{?}$ is a metasymbol for "what is the value of." Numerals are built up from $0$ by repeated successor: $S0 = 1$, $SS0 = 2$, $SSS0 = 3$, and so on.

Step 2: formation rules

Define what counts as a well-formed expression.

• A numeral is either $0$ or $S$ followed by a numeral. Examples: $0$, $S0$, $SS0$, $SSS0$.
• A term is a numeral, or a numeral $+$ a numeral. Examples: $S0$, $SS0 + S0$.
• A query is the form $\texttt{?} \, t$, where $t$ is a term. Example: $\texttt{?} \, (SS0 + S0)$.
• An equation is the form $t_1 = t_2$, where $t_1$ and $t_2$ are terms. Example: $SS0 + S0 = SSS0$.

A string of tokens is well-formed iff it is a numeral, term, query, or equation by these rules.

Step 3: interpretation

Define what the well-formed strings mean.

• A numeral $S^n 0$ (the result of applying $S$ $n$ times to $0$) denotes the natural number $n$.
• A term $t_1 + t_2$ denotes the sum of the natural numbers denoted by $t_1$ and $t_2$.
• An equation $t_1 = t_2$ is true iff the natural numbers denoted by $t_1$ and $t_2$ are equal.
• A query $\texttt{?} \, t$ asks for the normal form of $t$, the unique numeral $S^n 0$ that denotes the same number.

Step 4: derivation rules

To make the system computable rather than just interpretable, add rules for transforming terms.

• $0 + t \to t$ (rule R1: zero is the additive identity).
• $St_1 + t_2 \to S(t_1 + t_2)$ (rule R2: successor commutes outward through addition).

A derivation is a sequence of terms where each is obtained from the previous by applying R1 or R2 to a sub-term. The terminating term in a derivation is the normal form of the starting term.

A worked derivation

Compute $\texttt{?} \, (SS0 + S0)$, that is, ask for the normal form of $2 + 1$.

The normal form is $SSS0$, which interprets as $3$. The query $\texttt{?} \, (SS0 + S0)$ thus has answer $SSS0 = 3$.

That is a complete tiny symbolic system. It has an alphabet, formation rules, an interpretation, and derivation rules. It computes a real (if very limited) function on the natural numbers. Extending it with multiplication, predecessor, equality-checking, and quantification gives Peano arithmetic; extending it with abstraction and application gives the lambda calculus.

The Three Parts in Action

Three concrete observations the worked example makes precise.

Syntax versus semantics is genuine. The string $SSS0$ is a sequence of four tokens. The number 3 is a mathematical object. The interpretation maps the first to the second, but the two are not identical. The derivation lives entirely in the syntactic layer; the interpretation lives outside it. This is the same distinction made formal in Syntax vs Semantics.

Derivation rules can be sound but incomplete. The rules R1 and R2 in $\mathcal{S}$ are sound with respect to the interpretation: if $t_1 \to t_2$ by the rules, then $t_1$ and $t_2$ denote the same number. They are complete for addition expressions: every term in the language has a derivation to a normal-form numeral. For the system as it stands, soundness and completeness coincide. Extending the system with more operations or quantifiers can break this, Gödel's incompleteness theorems show that any system rich enough to encode arithmetic with quantification has true statements it cannot derive.

Computation and interpretation are different views of the same system. The derivation rules tell us how to compute. The interpretation tells us what the computed result means. A computer running $\mathcal{S}$ can produce $SSS0$ as output without "knowing" that $SSS0$ denotes 3. Whether this is a deficiency depends on what we mean by "knowing", see The Chinese Room Argument.

The Newell-Simon Physical Symbol System Hypothesis

In their 1976 ACM Turing Award lecture, Allen Newell and Herbert Simon proposed:

A physical symbol system has the necessary and sufficient means for general intelligent action.¹

This is the Physical Symbol System Hypothesis (PSSH). A "physical symbol system" in their sense is roughly: a system that contains physical patterns (symbols), can combine them into structures, and can manipulate the structures by physically realized rules. The hypothesis is empirical, not definitional.

PSSH has two halves.

Necessity: general intelligent action requires a physical symbol system. There is no intelligence without symbol manipulation.

Sufficiency: a physical symbol system is enough. With sufficient size and the right organization, symbol manipulation suffices for general intelligence.

The history of cognitive science from 1976 to the present can be told as the history of disagreements with PSSH.

The hypothesis has not been refuted. It has been displaced: the dominant working assumption in current AI is that some combination of symbol manipulation and learned representations is doing the work, and the question of which level is foundational remains open. The clean PSSH position, pure symbol manipulation is necessary and sufficient, has fewer defenders today than in 1976. The clean anti-PSSH position, symbol manipulation is unnecessary or insufficient, also has fewer defenders. Most working researchers now hold a hybrid view they would not have called "symbolic" in 1976 but would not call "non-symbolic" either.

Why It Matters Beyond Logic

Three live applications of the symbolic-system frame.

Programming languages and compilers. A compiler is a translation between two symbolic systems: source code (one alphabet, grammar, and operational semantics) and target code (another). Type systems are formal symbolic systems whose interpretations characterize "well-typed" programs. The Curry-Howard correspondence shows a deep equivalence between proofs (in a formal logical system) and programs (in a typed lambda-calculus): a proof of $A \to B$ corresponds to a program that takes input of type $A$ and returns output of type $B$.

Theorem provers and proof assistants. Lean, Coq, Isabelle, and Agda are symbolic systems whose interpretations are mathematical statements and whose derivation rules implement formal proof. A "proof" in these systems is literally a derivation in a symbolic system, machine-checkable. The reliability of formal verification rests on this property.

Symbolic AI and neuro-symbolic systems. Classical AI from McCarthy through expert systems explicitly took symbolic-system manipulation as the foundation of artificial intelligence. The deep-learning revolution displaced this approach for many tasks. Recent neuro-symbolic work tries to combine the two: neural networks for perception and learning, symbolic structures for reasoning, planning, and verification. Whether this combination is the right path or a transitional artifact is one of the most-active questions in current AI research.

Common Confusions

Confusion 1: symbolic system vs symbolic AI. A symbolic system is a formal triple of alphabet, rules, and interpretation. Symbolic AI is a research program that takes such systems as the substrate for intelligence (the McCarthy-Newell-Simon tradition). Symbolic systems are studied by mathematicians and logicians independently of any AI commitment. The success or failure of symbolic AI as a research program does not bear on whether symbolic systems are useful objects of study.

Confusion 2: symbolic = rule-based. Symbolic systems include rule-based ones, but they are broader. The lambda calculus, Markov chains, finite automata, and pushdown automata are all symbolic systems and are not naturally described as "rule-based" in the expert-systems sense.

Confusion 3: symbols must be discrete. Many treatments assume the alphabet is finite and the tokens are discrete. This is the standard case but not the only one. Continuous symbol systems exist (with continuous parameters, infinitary alphabets, or measure-theoretic semantics) and are studied in formal verification, model theory, and mathematical logic.

Confusion 4: a symbolic system is a language. A symbolic system has the structure of a formal language, but "language" in the linguistic sense (English, Mandarin, Yoruba) is a different object. Linguistics studies natural languages with their full pragmatic, social, and historical dimensions. Formal symbolic systems are designed objects with stipulated interpretations. The relationship between the two is studied in formal semantics, not assumed.

Two Exercises

Exercise 1: extend $\mathcal{S}$ with multiplication.

Add a multiplication operator $\times$ to the alphabet. Write down (a) the formation rules that include $\times$, (b) the interpretation of $t_1 \times t_2$, and (c) two derivation rules sufficient to compute multiplication of any two numerals. Verify your rules by computing $\texttt{?} \, (SS0 \times SS0)$, expecting normal form $SSSS0 = 4$.

Hint: the standard recursive definition of multiplication is $0 \times t = 0$ and $St_1 \times t_2 = (t_1 \times t_2) + t_2$. Your rules can mirror that structure.

Exercise 2: a different symbolic system.

Define a tiny symbolic system $\mathcal{B}$ for binary numbers. Its alphabet is $\{0, 1, \cdot\}$ where $\cdot$ is concatenation. A binary numeral is any nonempty string over $\{0, 1\}$ (with the leading-zero convention you prefer). The interpretation maps a binary numeral to the natural number it denotes in base 2. Add an addition operator $\oplus$ and define formation rules and derivation rules for binary addition. Run the derivation $\texttt{?} \, (10 \oplus 11)$, expecting normal form $101 = 5$.

This exercise is open-ended. Any well-defined system that gets the right normal form counts as a correct answer; the goal is to practice specifying alphabet, grammar, interpretation, and rules in a non-arithmetic-style notation.

Sketches of solutions

Exercise 1. Formation rule: if $t_1$ and $t_2$ are terms, so is $t_1 \times t_2$ (and treat $\times$ as binding tighter than $+$). Interpretation: $t_1 \times t_2$ denotes the product of the natural numbers denoted by $t_1$ and $t_2$. Rules: $0 \times t \to 0$ (rule M1) and $St_1 \times t_2 \to (t_1 \times t_2) + t_2$ (rule M2). Then:

Normal form $SSSS0 = 4$, as expected.

Exercise 2. One sketch (many are valid). Use binary numerals with implicit big-endian convention; treat $\oplus$ as a left-associative infix. The derivation rules can mimic schoolbook binary addition, working column-by-column from least-significant bit with carries handled as a small additional state. The full rule set is more involved than $\mathcal{S}$'s; the educational point is that you, the rule designer, must specify it explicitly. There is no "default" symbolic system for binary addition, every choice of grammar and rule set is a design.

If you can specify $\mathcal{B}$ on paper and execute it by hand, you have the basic shape of how a digital computer's instruction set is specified by its designers.

Prerequisites and Next Pages

• Prerequisite: What Is Logic?, for the broader frame.
• Prerequisite: Syntax vs Semantics, for the formal-systems version of the syntax-semantics distinction this page builds on.
• Next: The Chinese Room Argument, Searle's argument that pure symbol manipulation is not sufficient for understanding.
• Forward link to TheoremPath: the Generative Models as Free-Energy Accounting blog post is the technical complement on the connectionist / continuous-systems side.

References

Primary texts:

• Newell, Allen, and Herbert A. Simon. "Computer Science as Empirical Inquiry: Symbols and Search." Communications of the ACM 19, no. 3 (March 1976): 113-126. The Turing Award lecture and the canonical statement of the Physical Symbol System Hypothesis.
• Turing, Alan M. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society s2-42 (1936): 230-265. The foundational paper on Turing machines as a symbolic-system formalization of computation.
• Church, Alonzo. "An Unsolvable Problem of Elementary Number Theory." American Journal of Mathematics 58, no. 2 (1936): 345-363. The paper introducing the lambda calculus and the Church-Turing thesis.

Modern reference:

• Sipser, Michael. Introduction to the Theory of Computation. Cengage, 3rd ed. 2013. Standard textbook on formal languages, automata, and computability.
• Pierce, Benjamin C. Types and Programming Languages. MIT Press, 2002. The lambda calculus and modern type-theory treatment of programming languages as symbolic systems.
• Dennett, Daniel C. Brainstorms. MIT Press, 1978. Section II contains accessible early treatments of the symbolic-system frame in cognitive science.

Major critics:

• Rumelhart, David E., and James L. McClelland, eds. Parallel Distributed Processing: Explorations in the Microstructure of Cognition, 2 vols. MIT Press, 1986. The connectionist alternative.
• van Gelder, Tim. "What Might Cognition Be, If Not Computation?" Journal of Philosophy 92, no. 7 (1995): 345-381. The dynamical-systems alternative.
• Varela, Francisco, Evan Thompson, and Eleanor Rosch. The Embodied Mind. MIT Press, 1991. The embodied cognition alternative.

Stanford Encyclopedia entries (link, not paraphrase):

• "The Computational Theory of Mind", covers PSSH and its critics in depth.
• "The Church-Turing Thesis", the unification claim that makes "symbolic system" a robust object.
• "The Lambda Calculus", one of the canonical symbolic systems.
• "Connectionism", the most-developed alternative to PSSH.