Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

bibkey: hughes2026a27755 authors: Charles E. Hughes year: 2026 title: “Undecidability of Adjacent Equality for Insertion, Shuffle, and Crossover Language Operations” doi: null url: https://arxiv.org/abs/2608.27755v1 claim: “Section 10 conjectures that the minimum iteration-depth spectrum of literal fixed-degree insertion for arbitrary languages is an initial interval of the non-negative integers.” strata_touched:

  • D5/S1/Words/HughesIterationDepthNoGap license: citation-only triage: anchor

Iteration-depth spectrum no-gap conjecture

For a finite alphabet Σ and arbitrary languages A and B contained in Σ*, the source defines literal k-insertion with empty factors allowed, then iterates a single fixed positive degree k from stage zero B. The minimum iteration depth of a word is the least stage at which it appears for some positive degree. The conjecture in Section 10 states that if a depth r occurs, every depth from zero through r occurs.

This note records the published conjecture and its formal settlement. It is distinct from the finite-language theorem in Section 10 and from the insertion-degree conjecture in Section 11.

Formal settlement

The frozen declaration D5/S1/Words/HughesIterationDepthNoGap.result proves the Section 10 arbitrary-language conjecture. For every finite alphabet (including the empty alphabet), arbitrary languages A,B, and natural numbers q ≤ r, attainment of minimum depth r implies attainment of minimum depth q. Each insertion uses k source factors and k+1 base factors, all allowed to be empty; their respective concatenations belong to A and to the preceding stage. The output is x₁y₁…xₖyₖxₖ₊₁, interleaving base and source factors. Stage zero is B, and a single positive k is fixed throughout each history. Minimum depth excludes appearance at every earlier stage through any positive degree, even a different one. No finiteness of A or B, membership of epsilon in A, or monotonicity in depth is assumed. Empty and epsilon-only languages are included; an empty spectrum satisfies the conclusion vacuously.

The theorem uses iterationDepthSpectrumAt closedSourceZero, which is extensionally equal to the published zero-based spectrum. Empty-pair padding lifts histories to a common degree, so a minimum-depth successor has a predecessor of exactly the preceding minimum depth. Induction gives the full downward closure.

The result’s frozen declaration statement ID is sha256:f70ed374412ea1dd3c1bf1824ebbab657e78231bcbe1a2c20f1d6618a5d45075; the containing S1 module’s frozen statement ID is sha256:99025dc3bb5fb68fb04400b89fb31c63acd763d73478a6b35389d0b5e6c99bba. The companion module D5/S3/ConceptDynamics/InformationEscape/HughesIterationDepthNoGapRegistration registers this same theorem using its actual zero-based depth coordinate and a finite two-origin arena. Its shifted-origin counterfactual establishes variation and sensitivity; it does not restrict the arbitrary languages in the theorem. Its frozen module statement ID is sha256:c22e88f8dd3d6d6d8172c48148f489a2776a2d3a94f5ebc85164b3af69ddc926. The typed Proved resolution claim belongs only to the S1 result Describe node, for problem slug hughes-iteration-depth-no-gap.

Verified locator

The source is arXiv v1. The literal insertion definition is on page 2, the minimum-depth and spectrum definitions are on page 7, the Iteration-Depth No-Gap Conjecture is on page 8, and the open-question discussion is on page 11. PDF SHA-256: dd840a73b56821f5342811bcae34904356c7aa2553e624e7fea5183843dfa1cf. The stable URL is https://arxiv.org/abs/2608.27755v1.

The bounded prior-art check of 19 September 2026 found no exact resolution in the searched scope. The following accessible texts address related operations or decision problems:

  • Ibarra–McQuillan (2025), DOI 10.1007/s11047-025-10032-x: the 21-page accepted manuscript, including its introductory definitions, 15 propositions, seven corollaries and conclusion, treats decision, closure and transducer results for binary operations and represented languages. It does not state the repeated fixed-degree minimum-depth spectrum theorem. SHA-256: b3860e952a646f2863a493de9228820a8bf82c3d74df86a006d5972e44b7a700. The final publisher version was not compared.
  • Hughes’s 2007 UCF notes, slides 275–292 and 341–346 of 408, cover fixed-degree insertion, equality and finite-convergence undecidability. These are not the minimum-depth spectrum assertion. SHA-256: 342a07e2430d86a44ffcace6f8384cf8e2b8aac0be6caacd199a210987200065.
  • The 2023 UCF computability notes, pages 315–327, give a decision theorem for finite powers under concatenation, not this insertion-depth assertion. SHA-256: 4084c09363427a9301fe7553b5e49b0047a8f66961885f14343ee70df5bd3215.
  • arXiv:2603.26162v2 studies single-trajectory shuffle, disjoint alphabets and context-freeness classification, not the minimum-depth spectrum assertion. SHA-256: 7f1209a8581aed36c6adcd22ce2aa60bf0c55cb38a6b30804b610bf9b33586bf.

The Ito–Sugiura chapter (DOI 10.1007/978-3-540-24635-0_15) was accessible only as a subscription preview. Ito’s older book, the 1981 Hughes–Selkow original and the 2005 CS-TR05 original were not retrieved. The later UCF notes do not substitute for these unread originals.

The repository, pinned Mathlib, Loogle and bounded exact-query searches yielded no exact resolution. OpenAlex returned zero citations; Semantic Scholar returned HTTP 429, and general search engines were unusable. These limits preclude a worldwide absence or exhaustive priority claim. Hughes retains credit for the conjecture. The released project lead is credited for selecting it as a formalization target; no first-discovery or priority claim is made here.