pith. sign in

arxiv: 2606.09336 · v2 · pith:3U24TNGYnew · submitted 2026-06-08 · 🧮 math.LO

Undecidability, Chaos and Universality in Arithmetic Terms

Gabriel Istrate , Mihai Prunescu , Joseph M. Shunia This is my paper

Pith reviewed 2026-06-27 14:21 UTC · model grok-4.3

classification 🧮 math.LO
keywords arithmetic termsundecidabilityHilbert's tenth problemTuring completenesslogistic mapproof searchrecurrence relationsKalmar elementary functions
0
0 comments X

The pith

Hilbert's tenth problem reduces to testing whether an arithmetic term equals zero.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that whether a one-variable arithmetic term evaluates to zero, or whether two such terms agree on all inputs, is undecidable. This follows from a direct encoding of Hilbert's tenth problem into the syntax of arithmetic terms built from addition, subtraction, multiplication, remainder and exponentiation. The same class of terms can be assembled via an explicit construction to represent any function given by a recurrence relation, which immediately yields exact arithmetic-term representations of chaotic maps such as the logistic map. The construction further produces a Turing-complete arithmetic term and a Turing-universal function, plus a single term that, given codes for a sentence, a theory and a length bound, returns a proof shorter than the bound if one exists. A reader cares because these results demonstrate that fixed compositions of elementary arithmetic operations already suffice to embed full computability and proof search.

Core claim

By interpreting Hilbert's Tenth Problem in arithmetic terms, it is shown that it is undecidable whether one-variable arithmetic term takes the value 0, or whether two such terms take or not the same values. An algorithm constructs the arithmetic term representing an arbitrary function which has been defined by a recurrence rule. Functions with chaotic behavior, like the Logistic Map, can be expressed as arithmetic terms. Finally, we construct a Turing complete arithmetic term and we express a Turing universal function by an arithmetic term. A somewhat unexpected application: there is a wise arithmetic term. It gets the code of a sentence, the code of a formalized theory and a bound B, and af

What carries the argument

Arithmetic terms: finite fixed compositions of additions, subtractions, multiplications, remainder divisions and exponentiations on natural-number variables.

If this is right

  • Deciding whether a given one-variable arithmetic term evaluates to zero is undecidable.
  • Deciding whether two arithmetic terms agree on all natural-number inputs is undecidable.
  • Any function defined by a recurrence rule can be represented exactly by an arithmetic term.
  • The logistic map and other chaotic iterations can be expressed as arithmetic terms.
  • A single arithmetic term can simulate arbitrary Turing-machine computation and extract short proofs from any theory.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same encoding technique might transfer undecidability results to other restricted syntactic classes that still contain the five allowed operations.
  • Proof search for bounded-length derivations reduces to evaluation of one fixed arithmetic term.
  • Extensions could test whether arithmetic terms suffice to express other universal systems such as tag systems or register machines.
  • The wise-term construction suggests that bounded proof existence becomes a simple arithmetic predicate once the bound is fixed.

Load-bearing premise

The reduction of Hilbert's tenth problem to zero-testing and equality of arithmetic terms can be performed while remaining inside the allowed operations of addition, subtraction, multiplication, remainder and exponentiation.

What would settle it

An algorithm that correctly decides, for every one-variable arithmetic term, whether there exists a natural-number input making the term evaluate to zero would falsify the undecidability claim.

read the original abstract

Arithmetic terms are finite fixed compositions of additions, subtractions, multiplications, divisions with remainder and exponentiations, containing variables interpreted as natural numbers. They build a well-defined notion of closed formula. It is known that every Kalmar elementary function can be expressed as an arithmetic term. In this paper, one studies the power of expression of the arithmetic terms. By interpreting Hilbert's Tenth Problem in arithmetic terms, it is shown that it is undecidable whether one-variable arithmetic term takes the value $0$, or whether two such terms take or not the same values. An algorithm constructs the arithmetic term representing an arbitrary function, which has been defined by a recurrence rule. This construction has various applications. Functions with chaotic behavior, like the Logistic Map, can be expressed as arithmetic terms. Finally, we construct a Turing complete arithmetic term and we express a Turing universal function by an arithmetic term. A somewhat unexpected application: there is a {\it wise} arithmetic term. It gets (the code of) a sentence, (the code of) a formalized theory and a bound $B$, and after performing a constant number of operations, it outputs (the code of) a proof of the sentence using the given theory if such a proof does exist and its length is less than $B$. Otherwise, it outputs $0$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper claims that arithmetic terms (finite compositions of +, −, *, rem, and ^ on natural numbers) can represent all Kalmar elementary functions, and by interpreting Hilbert's Tenth Problem within this class it is undecidable whether a one-variable term evaluates to 0 or whether two terms are equal. It further asserts an algorithm to build terms for recurrence-defined functions, expressions for chaotic maps such as the logistic map, a Turing-complete arithmetic term together with a universal function, and a 'wise' term that, given codes of a sentence, theory, and bound B, outputs a short proof if one exists within B steps or else 0.

Significance. If the reductions and constructions remain strictly inside the syntactic class of arithmetic terms, the results would establish that this limited fragment suffices to encode undecidability, universal computation, and bounded proof search, extending known representability of Kalmar elementary functions in a direct and uniform way.

major comments (3)
  1. [Abstract] Abstract: the reduction of Hilbert's Tenth Problem to zero-testing (or equality) of one-variable arithmetic terms is asserted without any explicit term construction, pairing function, or verification that the encoding of an arbitrary Diophantine polynomial stays inside the closure of +,−,*,rem,^; this is load-bearing for the undecidability claim.
  2. [Abstract] Abstract: the construction of a Turing-complete arithmetic term and the Turing-universal function is stated without a description of how machine simulation or the universal function is realized using only the five allowed operations, preventing verification that the result remains within the Kalmar-elementary fragment.
  3. [Abstract] Abstract: the 'wise' arithmetic term is claimed to perform a constant number of operations to recover short proofs, but no encoding of proof search or bounded enumeration is supplied, so it is impossible to check that the construction does not require operations outside the permitted syntax.
minor comments (2)
  1. The abstract refers to 'divisions with remainder' but the body should clarify whether the remainder operation is the standard floor-division remainder or a different variant, and whether it is total on natural numbers.
  2. No references are given for the background fact that every Kalmar elementary function is representable by an arithmetic term; a standard citation should be added.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful review and for identifying points where the abstract could better support verification of the claims. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the reduction of Hilbert's Tenth Problem to zero-testing (or equality) of one-variable arithmetic terms is asserted without any explicit term construction, pairing function, or verification that the encoding of an arbitrary Diophantine polynomial stays inside the closure of +,−,*,rem,^; this is load-bearing for the undecidability claim.

    Authors: The body of the manuscript (in the section on undecidability via Hilbert's Tenth Problem) supplies the explicit reduction: a pairing function is constructed from multiplication and addition, and arbitrary Diophantine polynomials are encoded into a single-variable term via iterated application of the allowed operations. We agree the abstract is too terse on this point and will revise it to include a concise description of the encoding steps and a reference to the relevant section. revision: yes

  2. Referee: [Abstract] Abstract: the construction of a Turing-complete arithmetic term and the Turing-universal function is stated without a description of how machine simulation or the universal function is realized using only the five allowed operations, preventing verification that the result remains within the Kalmar-elementary fragment.

    Authors: The manuscript details the Turing-machine simulation in the section on Turing completeness, encoding tape contents and transitions via exponentiation for state vectors and remainder for symbol extraction, all within the five operations. We will revise the abstract to briefly indicate this encoding approach and point to the section for full verification. revision: yes

  3. Referee: [Abstract] Abstract: the 'wise' arithmetic term is claimed to perform a constant number of operations to recover short proofs, but no encoding of proof search or bounded enumeration is supplied, so it is impossible to check that the construction does not require operations outside the permitted syntax.

    Authors: The application section on the wise term describes the bounded enumeration of proofs via a recurrence relation (itself converted to an arithmetic term) that iterates over possible derivations up to bound B and checks syntactic validity using the permitted operations. We acknowledge the abstract lacks this outline and will expand it with a high-level description of the encoding. revision: yes

Circularity Check

0 steps flagged

No circularity: reduction from external undecidable problem using stated background fact

full rationale

The derivation begins from the external, independently established fact that every Kalmar elementary function is expressible as an arithmetic term (explicitly labeled 'it is known'), then reduces the independently undecidable Hilbert's Tenth Problem to zero-testing and equality of one-variable arithmetic terms. Subsequent constructions (recurrence-to-term algorithm, chaotic maps, Turing-complete term, wise term) are algorithmic translations that inherit their power from this reduction and the background closure property; none of the seven enumerated circularity patterns appear, as there are no self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the background fact that every Kalmar elementary function is representable by an arithmetic term and on the assumption that the H10 reduction can be performed inside that class; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Every Kalmar elementary function can be expressed as an arithmetic term.
    Explicitly stated as known background in the abstract.

pith-pipeline@v0.9.1-grok · 5769 in / 1474 out tokens · 26672 ms · 2026-06-27T14:21:03.897062+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 9 canonical work pages

  1. [1]

    Computational Complexity: A Modern Approach

    Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach. Cambridge Univer- sity Press. 2009

    2009

  2. [2]

    H. Bruin. For almost every tent map, the turning point is typical.Fundamenta Mathematicae. 155.3, 215 - 235, 1998

    1998

  3. [3]

    L. Collatz. Aufgaben E.Mathematische Semesterberichte. 1, 35, 1950

    1950

  4. [4]

    P. Clote. Computation Models and Function Algebras, in D. Leivant, ed.,Logic and Computational Complexity. LCC 1994. Lecture Notes in Computer Science, vol 960., Springer, Berlin, Heidelberg,

    1994

  5. [5]

    URLhttps://doi.org/10.1007/3-540-60178-3_81

    work page doi:10.1007/3-540-60178-3_81

  6. [6]

    Grzegorczyk

    A. Grzegorczyk. Some Classes of Recursive Functions.Rozprawy Matematyczne,4, 1953. URL http://matwbn.icm.edu.pl/ksiazki/rm/rm04/rm0401.pdf

    1953

  7. [7]

    Immerman.Descriptive Complexity

    N. Immerman.Descriptive Complexity. Springer, 1999. URLhttps://doi.org/10.1007/ 978-1-4612-0539-5

    1999

  8. [8]

    J. P. Jones and Yu. V. Matiyasevich. A New Representation for the Symmetric Binomial Coefficient and Its Applications.Annales des Sciences Math´ ematiques du Qu´ ebec, 6(1):81–97, 1982. Gaston Julia (1918): Sur l’it´ eration des fonctions rationnelles, Journal de Math´ ematiques Pures et Appliqu´ ees

    1982

  9. [9]

    Sur l’it´ eration des fonctions rationnelles.Journal de Math´ ematiques Pures et Ap- pliqu´ ees.8e s´ erie, tome 1, p

    Gaston Julia. Sur l’it´ eration des fonctions rationnelles.Journal de Math´ ematiques Pures et Ap- pliqu´ ees.8e s´ erie, tome 1, p. 47-245, 1918

    1918

  10. [10]

    S. S. Marchenkov. A Superposition Basis in the Class of Kalmar Elementary Functions.Mathematical Notes of the Academy of Sciences of the USSR,27(3):161–166, 1980. ISSN 0001-4346. URLhttps: //doi.org/10.1007/BF01140159

    work page doi:10.1007/bf01140159 1980

  11. [11]

    S. S. Marchenkov. Superpositions of Elementary Arithmetic Functions.Journal of Applied and Industrial Mathematics,1(3):351–360, 2007. ISSN 1990-4789. URLhttps://doi.org/10.1134/ S1990478907030106

    2007

  12. [12]

    Matiyasevich

    Y. Matiyasevich. Hilbert’s Tenth Problem. MIT press, ISBN 0-262-13295-8, 1993

    1993

  13. [13]

    R. M. May. Simple mathematical models with very complicated dynamics.Nature,261(5560), 459-467

  14. [14]

    Mazzanti

    S. Mazzanti. Plain bases for classes of primitive recursive functions.Mathematical Logic Quarterly, 48(1):93–104, 2002. ISSN 0942-5616. URLhttps://doi.org/10.1002/1521-3870(200201)48: 1%3C93::AID-MALQ93%3E3.0.CO;2-8

    work page doi:10.1002/1521-3870(200201)48: 2002

  15. [15]

    Mendelson.Introduction to Mathematical Logic

    E. Mendelson.Introduction to Mathematical Logic. Chapman and Hall/CRC, New York, sixth edition, 2015. URLhttps://doi.org/10.1007/978-1-4615-7288-6

    work page doi:10.1007/978-1-4615-7288-6 2015

  16. [16]

    I. Oitavem. New Recursive Characterizations of the Elementary Functions and the Functions Com- putable in Polynomial Space.Revista Matem´ atica de la Universidad Complutense de Madrid, 10(1): 109–125, 1997. URLhttp://eudml.org/doc/44242

    1997

  17. [17]

    Prunescu

    M. Prunescu. On other two representations of the C-recursive integer sequences by terms in modular arithmetic.Journal of Symbolic Computation, 130, 2025. URLhttps://doi.org/10.1016/j.jsc. 2025.102433

    work page doi:10.1016/j.jsc 2025

  18. [18]

    Prunescu and L

    M. Prunescu and L. Sauras-Altuzarra. An arithmetic term for the factorial function.Examples and Counterexamples, 5, 2024. ISSN 2666-657X. URLhttps://doi.org/10.1016/j.exco.2024. 100136

    work page doi:10.1016/j.exco.2024 2024

  19. [19]

    Prunescu and L

    M. Prunescu and L. Sauras-Altuzarra. Computational considerations on the representation of number-theoretic functions by arithmetic terms.Journal of Logic and Computation, 35, 2025. URL https://doi.org/10.1093/logcom/exaf012. 29

    work page doi:10.1093/logcom/exaf012 2025

  20. [20]

    Prunescu and L

    M. Prunescu and L. Sauras-Altuzarra. On the representation of C-recursive integer sequences by arithmetic terms.Journal of Difference Equations and Applications, 31, 2025. URLhttps://doi. org/10.1080/10236198.2025.2530478

    work page doi:10.1080/10236198.2025.2530478 2025

  21. [21]

    Prunescu, L

    M. Prunescu, L. Sauras-Altuzarra and J. M. Shunia. A Minimal Substitution Basis for the Kalmar Elementary Functions URLhttps://arxiv.org/abs/2505.23787

    arXiv

  22. [22]

    Prunescu and J

    M. Prunescu and J. M. Shunia. Arithmetic-term representations for the greatest common divisor,

  23. [23]

    Preprint

    URLhttps://arxiv.org/abs/2411.06430. Preprint

    arXiv

  24. [24]

    Prunescu and J

    M. Prunescu and J. M. Shunia. On arithmetic terms expressing the prime-counting function and the n-th prime, 2024. URLhttps://arxiv.org/abs/2412.14594. Preprint

    arXiv 2024

  25. [25]

    Prunescu and J

    M. Prunescu and J. M. Shunia, On Modular Representations of C-Recursive Integer Sequences, Journal of Integer Sequences, 28, 2025. URLhttps://cs.uwaterloo.ca/journals/JIS/VOL28/ Prunescu/prunescu3.pdf

    2025

  26. [26]

    R¨ odding

    D. R¨ odding. ¨Uber die Eliminierbarkeit von Definitions-schemata in der Theorie der rekursiven Funktionen.Mathematical Logic Quarterly, 10, 315–330, 1964. URLhttps://doi.org/10.1002/ malq.19640101806

    1964

  27. [27]

    Theoretische Informatik - kurz gefaßt

    Uwe Sch¨ oning. Theoretische Informatik - kurz gefaßt. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1, 2008

    2008

  28. [28]

    J. M. Shunia and L. Sauras Altuzarra, Arithmetic Terms for Sums of Multinomial Coefficients,The Ramanujan Journal. Volume 68. Issue 3. 2025.https://doi.org/10.1007/s11139-025-01222-3

    work page doi:10.1007/s11139-025-01222-3 2025

  29. [29]

    Tarski.A Decision Method for Elementary Algebra and Geometry

    A. Tarski.A Decision Method for Elementary Algebra and Geometry. University of California Press, Berkeley, 1951. Turing, A. M. (1936). ”On Computable Numbers, with an Application to the Entscheidungsproblem” (PDF). Proceedings of the London Mathematical Society. 2. 42 (published 1937): 230–265

    1951

  30. [30]

    A. M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem.Pro- ceedings of the London Mathematical Society.2.42. 1936. 30

    1936