💻 computer science

Encoding Peano Arithmetic in a Minimal Fragment of Separation Logic

This paper demonstrates that Peano arithmetic can be encoded into a minimal fragment of separation logic containing only the intuitionistic points-to predicate, zero, and the successor function, thereby proving the undecidability of validity in this fragment and showing that it can express complex properties like system consistency and non-termination.

Original authors: Sohei Ito, Makoto Tatsuta

Published 2026-03-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sohei Ito, Makoto Tatsuta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to prove a math theorem, but you are only allowed to use a very specific, tiny set of tools. You can't use a calculator, you can't write long equations, and you can't even use the words "plus" or "times." You only have three tools:

A pointer: A way to say "This box contains that number."
Zero: The number 0.
The "Next" button: A way to say "The number after this one."

You might think, "With such limited tools, I can't possibly solve complex math problems." You'd be right about solving them easily, but this paper proves something shocking: You can actually solve any problem that involves checking if a mathematical statement is always true, even with just these three tools.

Here is the story of how the authors, Sohei Ito and Makoto Tatsuta, pulled off this magic trick.

The Setup: The Memory Room

Think of Separation Logic as a way to describe a messy room full of boxes (memory). Usually, this logic is used by computer programmers to check if their code handles memory correctly without crashing.

The authors looked at the simplest version of this logic. They stripped away all the fancy features (like "separating conjunction," which is like saying "this part of the room is separate from that part"). They were left with just the ability to say: "Box A holds the value B."

Then, they added the numbers: 0 and Next (which turns 0 into 1, 1 into 2, etc.).

The Trick: Building a "Cheat Sheet" in the Room

The big question was: How do you do math like $2 + 2 = 4$ or $5 \times 3 = 15$ if you don't have a plus sign or a multiplication sign?

The authors' solution was brilliant: Don't calculate the math; look it up.

Imagine you have a giant, infinite wall of boxes in your memory room. You decide to use this wall as a Cheat Sheet (or a lookup table).

If you want to know $2 + 3$ , you don't add them. You go to the specific spot on the wall labeled "Addition," find the row for 2 and 3, and read the answer written there.
If you want to know if $5 \le 10$ , you go to the "Inequality" section of the wall and check if the answer is written there.

The authors proved that even though the logic is tiny, you can force the "memory room" to build this entire Cheat Sheet for you. The logic can say: "If the wall has a box that says 'Addition of 2 and 3 equals 5', then I accept that 2+3=5."

By building these tables inside the memory, the tiny logic can simulate Peano Arithmetic (the standard math we learn in school).

The Big Result: The "Undecidable" Puzzle

In computer science, there is a famous problem called the Halting Problem. It asks: "Can we write a program that looks at any other program and tells us if it will run forever or stop?" The answer is no. It is impossible to decide.

Because the authors showed that their tiny logic can simulate standard math, and because standard math contains the Halting Problem, they proved that it is impossible to decide if a statement in this tiny logic is true or false.

Even though the logic looks simple (like a child's toy), it is actually a "monster" hiding inside. It is powerful enough to encode any mathematical truth, which means no computer program can ever be built to check all of its answers automatically.

The Catch: It Only Works One Way

The paper also points out a funny limitation. This "Cheat Sheet" trick works perfectly for questions that start with "For all numbers..." (like "For all numbers, $x+0=x$ "). This is called a $\Pi^0_1$ formula.

However, if you ask a question that starts with "There exists a number..." (like "There exists a number $x$ such that $x+0 \neq x$ "), the trick breaks.

Why? Because the Cheat Sheet in the memory room might be incomplete. If the memory room is small, it might not have the entry for your specific number. The logic might say, "Well, I don't have the answer in my book, so I'll just assume the statement is true."
This means the logic is great at proving things are always true, but it gets confused when trying to prove that something exists.

The "Two-Proof" Strategy

The authors didn't just rely on one method. They used two different ways to prove their point, like showing a magic trick from two different angles:

The Math Way: They built the translation from standard math into their tiny logic (the Cheat Sheet method).
The Finite World Way: They showed that you can use this logic to simulate any finite structure (like a small map of connections). Since checking if something is true for all possible finite maps is already known to be impossible to decide, their logic must also be impossible to decide.

Why Should You Care?

This paper is important for two reasons:

For Programmers: It sets a boundary. It tells us that if we want to build automated tools to check software bugs, we have to be very careful about how much math we let them use. Even a tiny bit of math combined with memory checking can make the problem impossible to solve automatically.
For Logicians: It shows that "simplicity" is deceptive. You don't need a complex language to be powerful. Sometimes, the simplest tools, when combined in the right way, can do the most complex things.

In a nutshell: The authors took a tiny, simple logic tool, taught it how to build a giant lookup table in its memory, and proved that this simple tool is actually powerful enough to solve (or fail to solve) the hardest math problems in the universe.

1. Problem Statement

The paper addresses the fundamental question of decidability in Separation Logic (SL) when extended with arithmetic. While Separation Logic is widely used for verifying heap-manipulating programs, its combination with arithmetic theories (like Presburger arithmetic) is often assumed to preserve decidability if the arithmetic fragment is decidable.

The authors investigate a minimal fragment of Separation Logic with Numbers (SLN), defined by:

Spatial Component: Only the intuitionistic points-to predicate ( $t_1 \to t_2$ ), representing a single memory cell.
Arithmetic Component: Only the constant $0$ and the successor function $s$ .
Exclusions: It explicitly excludes the separating conjunction ( $*$ ), the magic wand ( $-\ast$ ), and multi-field points-to predicates.

The core problem is to determine the expressive power of this extremely weak fragment. Specifically, the authors ask: Can this minimal fragment encode the undecidable $\Pi^0_1$ formulas of Peano Arithmetic (PA)?

2. Methodology

The authors employ a translation-based approach to prove undecidability and establish complexity bounds. The methodology involves three main technical pillars:

A. Heap-Based Operation Tables

The core innovation is encoding arithmetic operations (addition, multiplication, and inequality) directly into the structure of the memory heap. Instead of having built-in arithmetic operators, the logic simulates them using operation tables stored as linked memory cells.

Encoding Scheme: The heap stores entries in the form of consecutive cells.
- Addition: Tagged with 0. An entry for $x + y = z$ is stored as a sequence of cells starting at address $a$ : $(0, x+3, y+3, z+3)$ . The offset $+3$ avoids collision with tags.
- Multiplication: Tagged with 1. Entry: $(1, x+3, y+3, z+3)$ .
- Inequality: Tagged with 2. Entry: $(2, x+3, y+3)$ .
Consistency Constraints: A specific formula $H$ (the "Table Heap Condition") is constructed to enforce that if a heap contains an entry for an operation, the subsequent cells must contain the correct result based on inductive definitions (e.g., $s(x) + y = s(x+y)$ ).

B. Translation of $\Pi^0_1$ Formulas

The authors define a translation $(\cdot)^\circ$ from bounded formulas in PA to SLN.

Normal Form: They first transform PA formulas into a "normal form" where arithmetic operations ( $+, \times$ ) appear only within existential quantifiers of the form $\exists(x = t + u)$ .
Translation Logic:
- Arithmetic terms are replaced by references to the operation tables (e.g., $x + y = z$ becomes $\forall a ((a \to 0, [x], [y]) \to s^3(a) \to [z])$ ).
- Handling Finite Heaps: A critical challenge is that a heap is finite and may not contain entries for large numbers. The translation handles this by using implications: if the heap is "too small" to contain the required table entry, the implication is vacuously true. This ensures that validity in SLN (which requires truth for all heaps) aligns with validity in PA (standard model).
- Specifically, for bounded quantifiers $\exists x \le t$ , the translation includes a disjunction: either the heap is too small to check the bound (making the formula true), or the heap contains the necessary table entries to verify the bound.

C. Complexity Analysis

To establish the exact complexity class, the authors prove two directions:

Lower Bound ( $\Pi^0_1$ -hard): By showing the translation preserves validity for $\Pi^0_1$ formulas.
Upper Bound ( $\Pi^0_1$ ): By proving that the model-checking problem for SLN is decidable. They show that variables in the points-to predicate can be bounded by the size of the heap, reducing the problem to checking a decidable fragment of successor arithmetic (a sub-fragment of Presburger arithmetic).

3. Key Contributions

Undecidability of Minimal SLN: The paper proves that validity in SLN is undecidable. This is surprising because the fragment contains only the simplest spatial predicate and the weakest arithmetic (successor only), yet it is powerful enough to simulate full Peano Arithmetic for $\Pi^0_1$ sentences.
Representation Theorem: A rigorous translation is provided showing that a $\Pi^0_1$ formula $A$ is valid in PA if and only if its translation $A^\circ$ is valid in SLN.
$\Pi^0_1$ -Completeness: The authors establish that the validity problem for SLN is $\Pi^0_1$ -complete. This is a significant result as it precisely locates the complexity of the logic within the arithmetical hierarchy.
Limitation on $\Sigma^0_1$ : The paper demonstrates that the translation does not preserve validity for $\Sigma^0_1$ formulas. A counterexample ( $\exists x (x + 0 \neq x)$ ) is provided, showing that while the formula is false in PA, its translation is valid in SLN because "small" heaps can trivially satisfy the condition by lacking the necessary table entries.
Alternative Proof: An alternative undecidability proof is presented via a reduction from the validity problem in finite model theory (Trakhtenbrot's theorem), encoding finite structures into heaps.

4. Results

Main Theorem: The validity of $\Pi^0_1$ formulas in Peano Arithmetic is equivalent to the validity of their translations in the minimal SLN fragment.
Corollary: The validity problem for SLN is undecidable.
Complexity: The validity problem is $\Pi^0_1$ $Π_{1}^{0}$ -complete.
- Hardness: Derived from the encoding of PA.
- Membership: Derived from the decidability of the model-checking problem (variables in spatial atoms are bounded by heap size; remaining logic is decidable successor arithmetic).

5. Significance

Theoretical Boundaries: The results redefine the boundary between decidable and undecidable fragments of Separation Logic. It shows that adding even the most basic arithmetic (0 and successor) to a minimal spatial logic is sufficient to break decidability, provided the logic allows quantification over heaps.
Verification Implications: For program verification, this implies that automated reasoning tools for Separation Logic with numbers must be careful. Even if the spatial part is restricted to single-cell pointers, the combination with arithmetic can lead to undecidability, necessitating the use of heuristics or restricted fragments (e.g., symbolic heaps with specific inductive definitions) for practical tools.
Expressive Power: The paper highlights that the "intuitionistic" nature of the points-to predicate (which allows for partial heaps) combined with arithmetic constraints is sufficient to encode complex arithmetic reasoning, challenging the intuition that separating conjunction ( $*$ ) is necessary for high expressiveness in SL.

In summary, Ito and Tatsuta demonstrate that syntactic simplicity does not guarantee decidability in Separation Logic. A fragment with only one spatial atom and basic arithmetic is sufficient to encode the consistency and termination properties of logical systems, placing the validity problem at the level of $\Pi^0_1$ -completeness.