Turing universality, computability, and incompleteness in hypergraph Turán theory
Abstract
Given a finite family ℱ of forbidden r-graphs, the Turán problem asks for the maximum asymptotic edge density of ℱ-free r-graphs and the structure of near-extremal examples. We show that both questions can encode arbitrary computation. Fix a universal Turing machine U. For every sufficiently large fixed r, there is a rational τr∈(0,1) such that, from each binary word β, one can construct a finite family ℱr,β with π(ℱr,β)=τr if U does not halt on β, and π(ℱr,β)>τr otherwise. The same dichotomy governs extremal structure. We construct finite families 𝒢r,β such that nonhalting gives a unique extremal limit and Erdős--Simonovits stability, whereas halting gives two nonempty compact extremal phases separated by the sign of a fixed continuous statistic. Hence uniqueness and connectedness of the extremal space, symmetry breaking, two-phase behavior, and stability are all undecidable. The reductions are effective and verifiable in ZFC by finite certificates. Consequently, for every consistent computably axiomatized extension of ZFC and every sufficiently large fixed r, there is a finite family ℱ for which the true equality π(ℱ)=τr is neither provable nor refutable; analogous independence holds for the five structural properties above. We also obtain effective approximation, classify exact comparison complexity, and show that the smallest improvement witnesses have Busy-Beaver growth, with no uniform computable positive lower bound on the density gain.
Related
- Hypergraph Universality and Erdos-Posa Failure for Chromatically Rich Odd Cycles
- Proof of Universality of the Operator Dχ in ZEBTS Theory: From Spectral Ontology to the Law of Unity of the Triune Substance
- Universality in the Transition from Inspiral to Plunge for Extreme-Mass-Ratio-Inspirals: High-Accuracy Analytic Solutions and Catastrophe Theory
- Translation Universality and Countable Configuration Theory for Dense Gδ-Sets in Polish Abelian Groups
- Renormalization Group on Wiener Space: Spectral Theory and Universality
BibTeX
@misc{li2026turing,
title = {{Turing universality, computability, and incompleteness in hypergraph Turán theory}},
author = {Heng Li and Xizhi Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04295},
eprint = {2609.04295},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04295},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Turing universality, computability, and incompleteness in hypergraph Turán theory
AU - Heng Li
AU - Xizhi Liu
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.04295
UR - https://arxiv.org/abs/2609.04295
AB - Given a finite family ℱ of forbidden r-graphs, the Turán problem asks for the maximum asymptotic edge density of ℱ-free r-graphs and the structure of near-extremal examples. We show that both questions can encode arbitrary computation. Fix a universal Turing machine U. For every sufficiently large fixed r, there is a rational τ_r∈(0,1) such that, from each binary word β, one can construct a finite family ℱ_r,β with π(ℱ_r,β)=τ_r if U does not halt on β, and π(ℱ_r,β)>τ_r otherwise. The same dichotomy governs extremal structure. We construct finite families 𝒢_r,β such that nonhalting gives a unique extremal limit and Erdős--Simonovits stability, whereas halting gives two nonempty compact extremal phases separated by the sign of a fixed continuous statistic. Hence uniqueness and connectedness of the extremal space, symmetry breaking, two-phase behavior, and stability are all undecidable. The reductions are effective and verifiable in ZFC by finite certificates. Consequently, for every consistent computably axiomatized extension of ZFC and every sufficiently large fixed r, there is a finite family ℱ for which the true equality π(ℱ)=τ_r is neither provable nor refutable; analogous independence holds for the five structural properties above. We also obtain effective approximation, classify exact comparison complexity, and show that the smallest improvement witnesses have Busy-Beaver growth, with no uniform computable positive lower bound on the density gain.
ER -