What is a symbolic system?

A symbolic system is a system that represents knowledge as discrete symbols combined into structured expressions, and reasons by applying explicit rules that create, transform and compare those expressions. Because every symbol and every rule can be read, each conclusion can be traced back through the exact steps and premises that produced it.

1. What is a symbolic system?

“Symbolic system” is used in several fields, including semiotics, anthropology and mathematics. In artificial intelligence and cognitive science it has a specific meaning. A symbolic system has three parts:

• Symbols. Discrete tokens that stand for something: an individual (ann), a relation (parent), a class (Person), a number, an action.
• Expressions. Structures built from symbols by fixed rules of combination: parent(ann, bill), $\forall x\left(\mathrm{Human}\right(x)\to \mathrm{Mortal}(x\left)\right)$, a row in a rule table, a triple in a graph.
• Processes. Operations that take expressions and produce new ones: substitution, matching, rule application, search.

The defining property is that the processes act on the form of expressions. A rule that derives $\mathrm{Mortal}\left(\mathrm{socrates}\right)$ from $\mathrm{Human}\left(\mathrm{socrates}\right)$ and the universal statement above does not need to know what a human is. It needs to match shapes and substitute a constant for a variable. That is what makes symbolic reasoning mechanical and checkable. It is also, as §7 shows, the root of its best-known weakness.

Symbolic systems are ordinary infrastructure: a database query planner, a compiler’s type checker, a rules engine, a Prolog program, an OWL reasoner, a SAT solver, a proof assistant such as Coq, Isabelle or Lean. Symbolic AI is the branch of artificial intelligence built on them; for the field as a whole see What is symbolic AI?, and for how it developed see the history of symbolic AI.

2. The physical symbol system hypothesis

Allen Newell and Herbert A. Simon received the 1975 ACM Turing Award. Their award lecture, published in Communications of the ACM in 1976 as “Computer Science as Empirical Inquiry: Symbols and Search”, gave the idea its classic statement [1].

In their definition, a physical symbol system consists of a set of entities called symbols, which are physical patterns that can occur as components of another kind of entity called an expression or symbol structure. At any moment the system holds a collection of these structures, and it contains processes that operate on expressions to produce other expressions: processes of creation, modification, reproduction and destruction. Two further notions give the symbols their power:

• Designation. “An expression designates an object if, given the expression, the system can either affect the object itself or behave in ways dependent on the object.”
• Interpretation. “The system can interpret an expression if the expression designates a process and if, given the expression, the system can carry out the process.”

The hypothesis itself is one sentence:

Necessary means that any system exhibiting general intelligence will, on analysis, turn out to be a physical symbol system. Sufficient means that any physical symbol system of sufficient size can be organised to exhibit general intelligence. The same lecture adds a second claim, the heuristic search hypothesis: “The solutions to problems are represented as symbol structures. A physical symbol system exercises its intelligence in problem solving by search—that is, by generating and progressively modifying symbol structures until it produces a solution structure.”

Newell and Simon presented this as an empirical hypothesis, to be tested like a law of nature, not as a theorem. The programs they had built with Cliff Shaw, the Logic Theorist (1956) and the General Problem Solver, were offered as evidence. The hypothesis has been challenged ever since: by connectionism, by behaviour-based robotics, which argued that useful behaviour needs no central symbolic model at all [2], and by the philosophical objections in §7. Few researchers now defend the strong form. The narrower claim this page relies on is easier to defend: when an answer must be exact, justified and reproducible, explicit symbol manipulation is the right tool.

3. Formal systems: the math of symbols

A symbolic system need not be a logic, but logic is where its properties are sharpest. The following definitions are standard.

Derivability is a purely syntactic notion. Checking that a given sequence is a derivation takes one pass over it, each step a decidable test. This is the mathematical core of the claim that symbolic conclusions are checkable.

Soundness is the property that matters most in practice: a sound system never derives something false from true premises. Completeness says nothing true-in-every-model is out of reach. Standard proof systems for propositional logic and first-order logic have both; for first-order logic, completeness is Gödel’s completeness theorem of 1930 [3].

3.1 A short derivation

The workhorse rule is modus ponens: from $\phi$ and $\phi \to \psi$, infer $\psi$.

Take $\Gamma =\{p,p\to q,q\to r\}$. Then $\Gamma ⊢r$:

3.2 Resolution

Automated reasoning mostly uses a different rule. In 1965 J. A. Robinson introduced resolution, a single inference rule over clauses (disjunctions of literals), together with the unification algorithm that makes it work for first-order logic [4]. In the propositional case, for clauses $C$, $D$ and a literal $\ell$:

In the first-order case the complementary literals need only be unifiable: if $\sigma$ is a most general unifier of $L_1$ and $L_2$, then

Resolution works by refutation: to show $\Gamma \models \phi$, add $\neg \phi$ and derive the empty clause $\square$, a contradiction. The example above in clause form: $\left\{p\right\}$, $\{\neg p\vee q\}$, $\{\neg q\vee r\}$, plus the negated goal $\{\neg r\}$. Resolving on $r$ gives $\neg q$; on $q$, $\neg p$; on $p$, $\square$. Resolution, together with factoring (merging unifiable literals within a clause), is sound and refutation-complete for first-order logic: whenever a clause set is unsatisfiable, some sequence of resolution steps derives the empty clause. It underlies Prolog and most classical theorem provers.

3.3 Limits: decidability and Gödel

Completeness does not mean a question can always be answered. Two limits are exact and worth stating precisely.

• Undecidability. Validity in propositional logic is decidable: a truth table over $n$ variables has $2^n$ rows. Validity in first-order logic is not. Church and Turing showed independently in 1936 that no algorithm decides it [5] [6]. It is semi-decidable: because first-order logic is complete, a proof search will find a proof of any valid formula, but on an invalid one it may run forever.
• Incompleteness. Gödel’s theorems of 1931 are about a different kind of completeness [7].

Gödel’s 1931 proof of (1) assumed a slightly stronger condition, ω-consistency; Rosser (1936) showed that plain consistency suffices [8]. The theorem says that such a theory is not negation-complete: some sentences are neither provable nor refutable in it. That is different from the completeness in Definition 4, which first-order logic has. The theorem does not say that symbolic reasoning fails or that proofs are unreliable. It says that no single consistent, effectively axiomatised theory strong enough for arithmetic settles every arithmetic question. Many systems used in practice, such as propositional logic and the description logics behind OWL, are too weak for the theorem to apply, and their reasoning problems are decidable.

4. Knowledge representation

Knowledge representation is the part of AI that decides what symbols a system uses and what they mean. Each scheme below trades expressiveness against the cost and reliability of reasoning.

• Propositional and first-order logic. Facts and general statements as formulas; reasoning by proof, as in §3. First-order logic is expressive enough to state most things precisely and too expressive for reasoning to be decidable in general.
• Production rules. Knowledge as condition–action pairs: IF the working memory matches a pattern THEN add, remove or change facts. The expert systems of the 1970s and 1980s were largely rule-based, and Forgy’s Rete algorithm (1982) made matching many rules against many facts efficient [9].
• Semantic networks. Concepts as nodes, relations as labelled links, with properties inherited along is-a links. Quillian’s 1968 model of semantic memory is the classic source [10].
• Frames. Minsky (1974) proposed the frame, “a data-structure for representing a stereotyped situation”, with slots, default values and attached procedures [11]. A restaurant frame expects a menu, a waiter and a bill; missing slots are filled by defaults until evidence overrides them.
• Description logics and OWL. Decidable fragments of first-order logic designed for classes and relations [12]. A description logic states definitions such as the one below, and a reasoner can check consistency and compute the class hierarchy. The W3C’s Web Ontology Language, OWL (2004; OWL 2 in 2009), is built on description logics [13].
• Knowledge graphs. Facts as subject–predicate–object triples, which together form a directed, labelled graph. RDF, the W3C data model, defines an RDF graph as a set of such triples [14]. Google popularised the term “knowledge graph” in 2012; Hogan et al. survey the field [15].

Left: a description-logic definition (a parent is exactly a person who has at least one child who is a person). Right: the same kind of knowledge as a single triple. Given that triple and $\mathrm{Person}\left(\mathrm{ann}\right)$ and $\mathrm{Person}\left(\mathrm{bill}\right)$, a reasoner classifies $\mathrm{ann}$ as a $\mathrm{Parent}$ without being told.

5. Kinds of symbolic reasoning

5.1 Deduction, induction and abduction

The American philosopher Charles Sanders Peirce distinguished three forms of inference [16]. Using his own example, with the rule “all beans from this bag are white”, the case “these beans are from this bag” and the result “these beans are white”:

• Deduction goes from rule and case to result. If the premises are true, the conclusion must be true. This is the only one of the three that is truth-preserving, and it is what §3 formalises.
• Induction goes from cases and results to a rule: every observed bean from the bag was white, so all of them are. The conclusion can be false even when every premise is true.
• Abduction goes from a result and a rule to a case: the beans are white, and beans from this bag are white, so perhaps they came from this bag. It is inference to a hypothesis that would explain an observation. Peirce’s best-known formulation: “The surprising fact, C, is observed; But if A were true, C would be a matter of course; Hence, there is reason to suspect that A is true” [16].

Abduction is logically invalid as a proof and useful as a search strategy. Diagnosis, fault finding and scientific hypothesis generation are abductive. A careful system keeps the difference visible: an abduced hypothesis is a candidate to be tested, not a fact.

5.2 Forward and backward chaining

Forward chaining is data-driven. Starting from known facts, it fires every rule whose conditions match, adds the conclusions, and repeats until nothing new appears. Backward chaining is goal-driven. Starting from a question, it finds rules whose conclusion matches the goal and turns their conditions into sub-goals, recursively, until they bottom out in known facts. Prolog works this way. Both are sound when the rules are; they differ in which facts they derive.

5.3 Unification

Unification finds a substitution that makes two expressions identical. It is how a general rule is applied to a specific case. For example:

whereas $P(x,x)$ and $P(a,b)$ do not unify, because $x$ cannot be both $a$ and $b$. Robinson’s 1965 paper gave the first unification algorithm and showed that when a unifier exists, a most general one exists [4].

5.4 Constraint solving

A constraint satisfaction problem has variables, a domain of values for each, and constraints that restrict which combinations are allowed: timetables, register allocation, circuit verification, Sudoku. Solvers combine search with propagation, which prunes impossible values. Boolean satisfiability (SAT) is the central case; Cook proved in 1971 that it is NP-complete [17], yet modern SAT and SMT solvers routinely decide industrial instances with very large numbers of variables. When a solver says unsatisfiable, many can also emit a proof that an independent checker can verify.

5.5 Planning

Planning searches for a sequence of actions that turns an initial state into one satisfying a goal. STRIPS, from SRI (Fikes and Nilsson, 1971), fixed the classic representation: each operator has a precondition list, an add list and a delete list [18]. The same shape survives in PDDL, the language of planning competitions. A plan is itself a symbolic object, so it can be validated before anything runs.

6. What symbolic systems do well

• Compositionality. The meaning of a complex expression is fixed by the meanings of its parts and the way they are combined. A system that understands parent and ancestor and the rule linking them handles family trees it has never seen, of any depth.
• Systematicity. Fodor and Pylyshyn (1988) argued that human thought is systematic: anyone who can think “Ann introduced Bill to Claire” can think “Bill introduced Claire to Ann” [19]. Symbolic systems have this property by construction, because the same rule applies to any symbols in the same roles. Whether neural networks can reach it without implementing a symbol system is still debated.
• Exactness. A symbolic answer is either derived or not. There is no “86% correct” fact inside a sound derivation. When nothing derives an answer, the honest output is unknown.
• Inspectability. Every rule and fact can be read, questioned, corrected or deleted by a person. Explanations are not reconstructed after the fact; the derivation is the explanation.
• Determinism and replay. The same premises and rules give the same conclusions every time. A decision can be replayed exactly months later, audited, and diffed against a new rule set to see precisely what changed.

These properties are why symbolic methods remain the default wherever an error must be explained afterwards: compilers, databases, hardware verification, and the safety layers of §9.

7. The classic objections, honestly

• The symbol grounding problem. Harnad (1990) asked how “the semantic interpretation of a formal symbol system [can] be made intrinsic to the system, rather than just parasitic on the meanings in our heads” [20]. His analogy is learning Chinese from a Chinese–Chinese dictionary alone: every symbol is defined only by other symbols. A symbol system on its own has no route from cat to cats. Harnad’s proposed answer was hybrid, grounding elementary symbols in sensory categories learned by non-symbolic means.
• The Chinese room. Searle (1980) imagined a person who knows no Chinese, locked in a room with a rule book for manipulating Chinese characters, producing replies that fluent speakers outside cannot tell from a native’s [21]. His conclusion: running a program, which is syntax, is not by itself sufficient for understanding, which needs semantics. The argument remains contested, and it is aimed at claims of understanding, not at whether symbolic systems compute correct answers.
• The frame problem. McCarthy and Hayes (1969) found that describing the effects of an action in logic also requires stating everything the action does not change [22]. Painting a block does not move it or change any other block, and writing all of that out is infeasible. Techniques such as successor-state axioms and the STRIPS assumption, that anything not in the add or delete list stays the same, handle the technical problem; the broader question of how any system decides what is relevant remains hard.
• Brittleness and the knowledge-acquisition bottleneck. A rule base is only as good as the rules someone wrote. Outside the cases its authors anticipated, it does not degrade gracefully; it fails outright or says nothing. Expert systems were expensive to build and maintain because each rule had to be elicited from a human expert. This, more than any theorem, is why statistical learning displaced symbolic AI for perception and language.
• Combinatorial explosion. Search spaces grow exponentially with problem size. The UK’s Lighthill report (1973) named this as a central reason early AI methods did not scale beyond toy problems [23]. Heuristics, clever encodings and decidable fragments tame it in many real domains, but not in general, as §3.3 and the NP-completeness of SAT make clear.

None of these objections says symbolic systems compute wrong answers from their premises. They say the premises must come from somewhere, symbols mean nothing by themselves, and search can be expensive. That is why most modern designs pair a symbolic layer with learned components: the learned part handles perception and proposal, the symbolic part handles admission and proof. See neuro-symbolic AI for the ways the two are combined.

8. Typed traversal: the path is the justification

A knowledge graph supports a form of reasoning that is easy to overlook: traversal. In a typed graph every edge has a named relation type, and a relation can be declared transitive (part_of), inverse of another (parent_of / child_of) or functional (at most one value, like date_of_birth). A query walks edges whose types the question permits:

The answer to “is $v_k$ related to $v_0$?” comes with the path that connects them. Checking the answer means checking $k$ edges, in time proportional to $k$. That is the sense in which the path is the justification: a similarity search can say two things are near each other, but not why; a traversal says exactly which asserted facts connect them. Because a traversal only composes asserted edges, it cannot return a relation that is not in their closure, and a functional relation with two different values is detected as a contradiction rather than averaged. Our paper Traversing Data in Symbolic Systems states these properties as theorems and gives a reproducible validation [24].

The same idea applies one level up. When several models, tools and services are chained together, some properties can only be checked across the whole chain: that every fact used downstream came from an admitted source, that a refusal by one component is not quietly routed around by another. No single model can enforce an invariant over a chain it is only one link of. Our paper The Orchestration Gap argues that such chain-level invariants need a symbolic layer outside the models, where they can be stated exactly and checked deterministically [25]. Symbolic flows describes pipelines built on that principle.

9. Symbolic systems as the floor of a fail-safe model

A fail-safe model is an AI model built so that when it fails, the failure drives it toward a controlled, safe state: it abstains when evidence is missing, and its learning can narrow what it does but never widen what it is authorised to do. That requires a part of the system whose answers are exact, whose rules can be read, and which the learner cannot rewrite. Those are the properties of §6, and they are why the natural floor of a fail-safe model is symbolic.

• Exactness gives fail-closed behaviour. A symbolic check either admits a fact or does not. When nothing admits it, the answer is unknown, not a guess.
• Inspectability gives accountable refusals. A refusal can name the rule that produced it, and a person can read and challenge that rule.
• Determinism gives replay. Any decision can be re-run and audited later with the same result.
• Separation gives bounded learning. If what is permitted is computed by the symbolic layer first, a learner that only chooses among permitted options cannot add a permission, however it is trained.

Peel, by Perslis Research, is built this way. It is, to our knowledge, the first fail-safe model; the exact claim and the closest earlier work are on What is a fail-safe model?. Knowledge in Peel is typed, sourced cards; learning is readable counts; there is no neural network in the loop that decides. A language model may propose; only the floor admits a fact. Peel is a research prototype, not a certified safety system. For how Perslis uses symbolic AI more broadly, see Symbolic AI at Perslis, and for a worked comparison of a symbolic floor against a confidence-scored classifier, see the floor vs the classifier.

10. Questions

What is a symbolic system in AI?

A symbolic system in AI represents knowledge as discrete symbols combined into structured expressions, such as logical formulas, rules or graph triples, and reasons by applying explicit rules that create and transform those expressions. Because the symbols and rules are readable, every conclusion can be traced to the premises and steps that produced it.

What is the physical symbol system hypothesis?

It is the claim, stated by Allen Newell and Herbert Simon in their 1975 Turing Award lecture published in 1976, that a physical symbol system has the necessary and sufficient means for general intelligent action. Necessary means any generally intelligent system will turn out to be a symbol system; sufficient means a large enough symbol system can be organised to be generally intelligent. It is an empirical hypothesis and remains contested.

What is symbolic reasoning?

Symbolic reasoning is the derivation of new expressions from existing ones by explicit rules that act on their form. It includes deduction, which is truth-preserving, induction, which generalises from cases, and abduction, which proposes explanatory hypotheses, together with techniques such as forward and backward chaining, unification, constraint solving and planning.

What is the symbol grounding problem?

Stated by Stevan Harnad in 1990, it asks how the symbols of a formal system can mean something to the system itself rather than only to the people who interpret it. If every symbol is defined only by other symbols, as in a dictionary, nothing connects them to the world. Proposed solutions ground basic symbols in perception or action.

Are knowledge graphs symbolic?

Yes. A knowledge graph stores facts as subject–predicate–object triples with named relations, and it can be queried, traversed and reasoned over by explicit rules. Knowledge graph embeddings, which map the graph into vectors, are a sub-symbolic layer built on top of it.

What is the difference between soundness and completeness?

A proof system is sound if everything it can derive is true in every interpretation where its premises are true, written: if Γ ⊢ φ then Γ ⊨ φ. It is complete if everything so entailed can be derived: if Γ ⊨ φ then Γ ⊢ φ. First-order logic has proof systems that are both.

Does Gödel’s incompleteness theorem mean symbolic AI cannot work?

No. It says that any consistent formal theory whose axioms can be listed by an algorithm and which includes a modest amount of elementary arithmetic contains sentences it can neither prove nor refute, and cannot prove its own consistency. It limits what one theory can settle; it does not make sound derivations unreliable, and many practical symbolic systems are decidable.

How are symbolic systems used in AI safety?

Because symbolic checks are exact, readable and deterministic, they can decide what an AI system is permitted to do and which facts it may treat as true, independently of any learned model. In a fail-safe model the symbolic floor admits facts and permissions, and the learner can only choose among what the floor allows.

11. References

1. A. Newell, H. A. Simon. Computer Science as Empirical Inquiry: Symbols and Search. Communications of the ACM 19(3):113–126, 1976. doi:10.1145/360018.360022.
2. R. A. Brooks. Intelligence without representation. Artificial Intelligence 47(1–3):139–159, 1991.
3. K. Gödel. Die Vollständigkeit der Axiome des logischen Funktionenkalküls. Monatshefte für Mathematik und Physik 37:349–360, 1930.
4. J. A. Robinson. A Machine-Oriented Logic Based on the Resolution Principle. Journal of the ACM 12(1):23–41, 1965. doi:10.1145/321250.321253.
5. A. Church. A Note on the Entscheidungsproblem. Journal of Symbolic Logic 1(1):40–41, 1936.
6. A. M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society s2-42:230–265, 1936.
7. K. Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik 38:173–198, 1931. doi:10.1007/BF01700692.
8. J. B. Rosser. Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic 1(3):87–91, 1936.
9. C. L. Forgy. Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem. Artificial Intelligence 19(1):17–37, 1982.
10. M. R. Quillian. Semantic Memory. In M. Minsky (ed.), Semantic Information Processing. MIT Press, 1968.
11. M. Minsky. A Framework for Representing Knowledge. MIT AI Laboratory Memo 306, 1974.
12. F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider (eds.). The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2003.
13. W3C OWL Working Group. OWL 2 Web Ontology Language Document Overview. W3C Recommendation, 27 October 2009 (second edition 2012). The first OWL became a W3C Recommendation on 10 February 2004.
14. R. Cyganiak, D. Wood, M. Lanthaler (eds.). RDF 1.1 Concepts and Abstract Syntax. W3C Recommendation, 25 February 2014.
15. A. Hogan et al. Knowledge Graphs. ACM Computing Surveys 54(4), Article 71, 2021. doi:10.1145/3447772. arXiv:2003.02320.
16. C. S. Peirce. Deduction, Induction, and Hypothesis. Popular Science Monthly 13:470–482, 1878; and Collected Papers of Charles Sanders Peirce, Vol. 5: Pragmatism and Pragmaticism, ed. C. Hartshorne and P. Weiss, §5.189. Harvard University Press, 1934.
17. S. A. Cook. The Complexity of Theorem-Proving Procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), 151–158, 1971.
18. R. E. Fikes, N. J. Nilsson. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence 2(3–4):189–208, 1971.
19. J. A. Fodor, Z. W. Pylyshyn. Connectionism and Cognitive Architecture: A Critical Analysis. Cognition 28(1–2):3–71, 1988.
20. S. Harnad. The Symbol Grounding Problem. Physica D 42:335–346, 1990. doi:10.1016/0167-2789(90)90087-6.
21. J. R. Searle. Minds, Brains, and Programs. Behavioral and Brain Sciences 3(3):417–424, 1980. doi:10.1017/S0140525X00005756.
22. J. McCarthy, P. J. Hayes. Some Philosophical Problems from the Standpoint of Artificial Intelligence. In B. Meltzer, D. Michie (eds.), Machine Intelligence 4, 463–502. Edinburgh University Press, 1969.
23. J. Lighthill. Artificial Intelligence: A General Survey. In Artificial Intelligence: a paper symposium. Science Research Council, London, 1973.
24. Perslis Research. Traversing Data in Symbolic Systems: Typed-Relation Traversal as a First-Class Retrieval Primitive. 2026. research.perslis.com/traversal
25. Perslis Research. The Orchestration Gap: Why Model-Level Alignment Cannot Survive Multi-Model Runtimes. 2026. research.perslis.com/orchestration-gap