Undecidability of Finite Orbit Recognition in Polynomial Maps
Pith reviewed 2026-05-21 21:43 UTC · model grok-4.3
The pith
Deciding if a polynomial map on infinite integer tuples has a finite orbit is undecidable.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
There is no algorithm that, given a Turing machine, decides whether its trajectory is eventually periodic. Encoding each machine into a polynomial dynamical system on infinite integer tuples yields the further result that there is likewise no algorithm deciding whether the orbit of a point under iteration of the map is finite.
What carries the argument
A polynomial map on infinite integer tuples that encodes Turing-machine steps so finite orbits correspond exactly to eventually periodic trajectories.
If this is right
- Orbit finiteness cannot be decided algorithmically for this class of polynomial systems.
- Questions about eventual periodicity of Turing machines reduce directly to questions about algebraic orbits.
- The undecidability is inherited by any larger class of maps that contains the constructed family.
Where Pith is reading between the lines
- Similar reductions might apply to other algebraic or geometric dynamical systems that can simulate computation.
- The result highlights a boundary between decidable local properties and undecidable global orbit properties in infinite-state systems.
Load-bearing premise
The explicit polynomial map is built so that an orbit stays finite precisely when the encoded Turing-machine trajectory eventually repeats.
What would settle it
An algorithm that takes the coefficients of any such polynomial map and outputs in finite time whether its orbit is finite.
read the original abstract
We prove the undecidability of determining whether a Turing machine yields an eventually periodic trajectory. From this, we deduce the undecidability of orbit finiteness in the polynomial dynamical system on infinite tuples of integers.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper first proves the undecidability of determining whether a Turing machine produces an eventually periodic trajectory. It then reduces this problem to the recognition of finite orbits under iteration of a polynomial map f: Z^∞ → Z^∞ (with each coordinate depending polynomially on finitely many others), showing that the forward orbit of a starting tuple encoding the initial TM configuration is finite if and only if the TM trajectory is eventually periodic.
Significance. If the reduction is faithful, the result establishes undecidability of a natural decision problem in algebraic dynamics over infinite-dimensional integer spaces, linking classical computability results to orbit finiteness in polynomial systems. The explicit construction of the map provides a concrete bridge between TM configurations and polynomial updates, which could inform further work on computability in dynamical systems if the equivalence holds without gaps.
major comments (2)
- [reduction construction] The central reduction (detailed after the TM undecidability result) requires explicit verification that the polynomial map faithfully encodes TM transitions (tape symbols, head position, and state) such that finite orbits occur exactly when the trajectory is eventually periodic. Any auxiliary variables or interpolation used to arithmetize the configuration must be shown not to introduce spurious finite orbits or allow non-periodic TM behaviors to produce finite orbits; the current sketch leaves open whether the coordinate-wise polynomial updates prevent extra cycles.
- [main theorem proof] The claim that the orbit is infinite precisely when the TM trajectory is non-periodic relies on the map forcing coordinates to change indefinitely in the non-periodic case. This equivalence must be checked against possible stabilizing behaviors in the infinite tuple that are not present in the TM simulation; a concrete counter-example or invariant showing that non-periodic inputs produce unbounded coordinate growth would strengthen the argument.
minor comments (2)
- [preliminaries] Clarify the precise notion of 'infinite tuples of integers' and the topology or metric (if any) under which orbits are considered; the manuscript should specify whether coordinates are indexed by naturals and how the polynomial dependence is formally stated.
- [introduction] Add a reference to the standard result on undecidability of eventual periodicity for TMs to make the first part self-contained.
Simulated Author's Rebuttal
We thank the referee for their thorough review and valuable comments on our paper. We address each major comment below and indicate the revisions we plan to make.
read point-by-point responses
-
Referee: [reduction construction] The central reduction (detailed after the TM undecidability result) requires explicit verification that the polynomial map faithfully encodes TM transitions (tape symbols, head position, and state) such that finite orbits occur exactly when the trajectory is eventually periodic. Any auxiliary variables or interpolation used to arithmetize the configuration must be shown not to introduce spurious finite orbits or allow non-periodic TM behaviors to produce finite orbits; the current sketch leaves open whether the coordinate-wise polynomial updates prevent extra cycles.
Authors: We appreciate the referee pointing out the need for more explicit verification in the reduction. The manuscript constructs the polynomial map f such that each coordinate update corresponds directly to the TM transition rules applied to the encoded configuration. Specifically, the infinite tuple encodes the tape content in coordinates 1 to infinity, with additional coordinates for the head position and current state. The polynomials are chosen to perform the exact symbol replacement and head movement as per the TM delta function. Regarding auxiliary variables, they are not independent but are functions of the main configuration coordinates, ensuring that any cycle in the orbit must correspond to a periodic TM trajectory. We will add a detailed lemma proving that the map preserves the equivalence without introducing extra finite orbits, including a proof that non-periodic behaviors lead to changes in at least one coordinate indefinitely. This will be incorporated in the revised manuscript. revision: yes
-
Referee: [main theorem proof] The claim that the orbit is infinite precisely when the TM trajectory is non-periodic relies on the map forcing coordinates to change indefinitely in the non-periodic case. This equivalence must be checked against possible stabilizing behaviors in the infinite tuple that are not present in the TM simulation; a concrete counter-example or invariant showing that non-periodic inputs produce unbounded coordinate growth would strengthen the argument.
Authors: We agree that strengthening the argument with an explicit invariant would be beneficial. In the non-periodic case, the TM trajectory visits infinitely many distinct configurations, which translates to the tuple having coordinates that are updated in a way that prevents the entire tuple from repeating. We will include an invariant in the proof that tracks the 'progress' of the simulation, such as the maximum position visited by the head or a counter that increments with each step in non-repeating cases. This shows that stabilization of the tuple would imply eventual periodicity of the TM. A concrete counter-example for a simple non-periodic TM (e.g., one that moves right indefinitely) will also be provided to illustrate the infinite orbit. We plan to expand this section accordingly. revision: yes
Circularity Check
No circularity; independent reduction from external TM undecidability result
full rationale
The derivation begins with a claimed proof of undecidability for eventual periodicity of Turing machine trajectories, which rests on standard computability results external to the paper rather than any self-definition or fitted input. It then applies an explicit polynomial map construction on Z^∞ to reduce orbit finiteness to that TM property. No equations or steps are shown to reduce by construction to their own inputs, no self-citations are load-bearing for the central claim, and the equivalence is presented as a direct arithmetization without renaming known results or smuggling ansatzes. The paper is self-contained against external benchmarks for the reduction step.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math The problem of deciding whether a Turing machine produces an eventually periodic trajectory is undecidable.
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/ArithmeticFromLogic.leanLogicNat recovery and embed_injective unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Theorem 1.3. It is undecidable, given a finite set S of polynomial maps on Z^N and a point x in Z^N, whether or not x is S-stable.
-
IndisputableMonolith/Foundation/ArrowOfTime.leanforward_accumulates and z_monotone_absolute unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We represent Conway’s Game of Life as an action of a polynomial map on Z^N ... global transition function ... polynomial map φ: Z^N → Z^N
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.