💻 computer science

Nonlinear Arithmetic with SMTLIB Division is Undecidable

The paper demonstrates that nonlinear real arithmetic (NRA) as defined in the SMTLIB standard is undecidable because its treatment of division by zero as an uninterpreted function enables the encoding of undecidable integer arithmetic problems.

Original authors: Dejan Jovanovic

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dejan Jovanovic

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 a detective trying to solve a mystery using a very strict set of rules. In the world of computer science, these rules are called "theories," and they help computers decide if a mathematical puzzle has a solution or not.

This paper is about a specific set of rules called Nonlinear Real Arithmetic (NRA). Think of this as a game played with real numbers (like 3.14, -5, or 0.001) where you can add, subtract, multiply, and divide them.

The "Magic" Rule That Breaks the Game

For a long time, mathematicians believed this game was perfectly solvable. If you gave a computer a puzzle using these numbers, it could eventually say, "Yes, there is a solution," or "No, there isn't."

However, the author, Dejan Jovanović, discovered a hidden trap in the official rulebook (the SMTLIB standard). The trap is in how the rules handle division by zero.

In normal math, dividing by zero is a big "No." But in this specific computer rulebook, the rules say: "If you divide by zero, we don't care what the answer is. It can be anything, as long as it acts like a normal number when you aren't dividing by zero."

The author calls this an "uninterpreted function." To use an analogy: Imagine a vending machine that works perfectly for every snack you buy. But if you try to buy a "Zero Snack," the machine doesn't crash; instead, it just spits out something—maybe a candy bar, maybe a rock, maybe a cloud. The rules don't tell you what it will be; they just say, "It will be something."

How This Turns the Game Unsolvable

The paper argues that this "anything goes" rule for zero division is the key that unlocks a door to chaos.

Here is the logic, simplified:

The Goal: The author wants to prove that if you have this "magic" division rule, you can trick the computer into solving integer puzzles (puzzles with whole numbers like 1, 2, 3).
The Problem: Solving integer puzzles is famously impossible for computers to do perfectly for every case (this is known as Hilbert's 10th Problem). It's like trying to find a needle in a haystack that keeps growing forever.
The Trick: The author shows that by using the "magic" division by zero, you can build a mathematical bridge. You can take a hard integer puzzle and translate it into a real-number puzzle using this division trick.
- Analogy: Imagine you have a secret code written in a language only humans understand (integers). You build a machine (the division trick) that translates this code into a language computers understand (real numbers). Because the computer's language has this "magic" zero-division rule, the computer can accidentally solve the human code.
The Result: Since we know computers cannot solve all integer puzzles, and this trick lets them try to solve integer puzzles using real numbers, it means the computer cannot solve all real-number puzzles either. The game becomes undecidable.

The "Floor" Function Analogy

To prove this, the author uses a clever trick. They show that if you have this "magic" division, you can force the computer to act like a floor function (a function that rounds a number down to the nearest whole number, like turning 3.9 into 3).

Once the computer can round numbers down, it can start counting integers. Once it can count integers, it can try to solve those impossible integer puzzles. Since those puzzles are impossible to solve generally, the whole system of real-number math with this division rule becomes impossible to solve generally.

What This Means for the Real World (According to the Paper)

The paper doesn't talk about future AI or medical uses. It focuses on the current state of computer benchmarks (test problems):

The Trap: Many existing test problems in the SMTLIB library (a huge collection of math puzzles used to test computers) use division with variables (like x / y). If y happens to be zero, these puzzles fall into the "undecidable" trap.
The Solution? The author suggests two ways to fix the rulebook:
1. Pick a specific answer: Decide that dividing by zero always equals a specific number (like 0 or 1), just like how some computer systems handle it for binary numbers.
2. Split the game: Create a new, separate category for problems where you divide by variables, and keep the "safe" category for problems where you only divide by known numbers (constants).

The Bottom Line

The paper claims that a specific, seemingly harmless rule about how computers handle "dividing by zero" accidentally breaks the ability of computers to solve all math problems involving real numbers. It turns a solvable game into an unsolvable one by allowing the computer to sneakily solve problems it wasn't supposed to be able to solve.

Technical Summary: Nonlinear Arithmetic with SMTLIB Division is Undecidable

Problem Statement
The paper addresses the decidability status of the theory of Nonlinear Real Arithmetic (NRA) as formally defined in the SMTLIB standard. While the theory of real closed fields (comprising equalities and inequalities over polynomials) is a well-established decidable fragment of mathematical logic (Tarski [7]), the SMTLIB definition of NRA extends this signature to include division. The critical issue arises from the treatment of division by zero. In the SMTLIB standard, division is interpreted as expected for non-zero divisors but remains an uninterpreted function when the divisor is zero. Specifically, the axiom $(\forall x, y \in \mathbb{R}) (y \neq 0) \Rightarrow (x = \frac{x}{y} \cdot y)$ allows any value for $\frac{x}{0}$ provided the standard behavior is maintained elsewhere. The paper investigates whether this specific treatment of division by zero preserves the decidability of the theory.

Methodology
The author employs a reduction proof to demonstrate undecidability. The methodology proceeds in two logical steps:

Reduction from Integer Arithmetic: The paper first establishes that real arithmetic augmented with a single unary uninterpreted function is undecidable. This is achieved by axiomatizing the uninterpreted function $f$ $f$ to behave as the floor function $\lfloor \cdot \rfloor$ $⌊ \cdot ⌋$ using the axioms:
- $(\forall x \in \mathbb{R}) f(x) + 1 = f(x + 1)$
- $(\forall x \in \mathbb{R}) (0 \le x < 1) \Rightarrow (f(x) = 0)$
  By enforcing these axioms, any formula over integer variables can be equisatisfiable with a formula over real variables involving $f$ . Since integer arithmetic is undecidable (Hilbert's 10th problem [4]), the extended real arithmetic theory becomes undecidable.
Mapping to Division by Zero: The paper then maps the uninterpreted function $f$ from the previous step directly to the division-by-zero operation ( $\frac{x}{0}$ ). By treating $\frac{x}{0}$ as the uninterpreted function, the axioms required to simulate the floor function can be encoded within the NRA theory. Consequently, the satisfiability of arbitrary integer formulas can be reduced to the satisfiability of NRA formulas involving division by zero.

Key Contributions and Results

Proof of Undecidability: The primary result is the demonstration that the SMTLIB theory of Nonlinear Real Arithmetic (NRA) is undecidable. This is a direct consequence of including division where the divisor is an uninterpreted function at zero.
Encoding Mechanism: The paper provides a concrete encoding (Example 1) showing how to translate the satisfiability of Diophantine equations (e.g., $a^3 + b^3 = c^3$ over integers) into NRA formulas. This is done by asserting that variables act as integers via the floor-function simulation using $\frac{x}{0}$ , and then applying the polynomial constraints.
Impact on Existing Benchmarks: The analysis reveals that while many benchmarks in the SMTLIB NRA category use division only with constant divisors (a decidable fragment), those utilizing non-constant divisors fall into the newly identified undecidable fragment.

Significance and Claims
The paper claims that this result is "unexpected" given that the decidable fragment of polynomial constraints is a landmark result in mathematical logic. The significance lies in clarifying the theoretical boundaries of the SMTLIB standard: the inclusion of division as an uninterpreted function at zero fundamentally alters the decidability landscape, rendering the full theory undecidable.

The author notes that this limitation precludes the extension of complete quantifier elimination techniques (such as those used in CAD or lazy quantifier elimination approaches [3, 5, 6]) to the full NRA theory in the presence of division by zero.

Proposed Mitigations
The paper concludes by outlining two potential approaches to address this undecidability, without claiming to have solved the problem within the current standard:

Total Division: Assigning a specific value to division by zero (similar to bitvector theory [1]), though this presents challenges in selecting an appropriate value.
Theory Separation: Moving division with non-constant divisors to a separate theory (proposed as UFNRA) and restricting NRA to polynomial constraints plus division by non-zero constants. The author acknowledges this would necessitate reclassifying existing benchmarks.