Internal Structure at a Fixed Representation: Degrees, Dimensions, and Counting
Once a syntactic or machine presentation has been fixed, representation dependence no longer explains the remaining quantitative variation. We ask: what controls the internal structure of the resulting effective closed class? Three kinds of control emerge. First, under a stage-sound machine presentation, the survival probability computes the random left boundary and is therefore Turing equivalent to the halting problem; the conditioned survival distribution has the same computational obstruction. Second, finite-prefix growth controls pointwise Kolmogorov complexity. We prove a uniform compression inequality for every effectively closed class, a cylinder-embedding theorem, and an explicit sparsification construction producing perfect null classes in which every point has effective dimension zero but an arbitrary prescribed rational secondary complexity exponent. Thus a mother class may have zero complexity infimum while containing subclasses with a rich spectrum of positive secondary exponents. Third, exact counting is computationally strong: for any computable exhausting window sequence, the exact number of realizable patterns is Turing equivalent to the theorem set. A parallel statement holds for live-prefix counts of effective closed classes. Finally, finite-order local marginals can be completely free while global entropy is only logarithmic, placing a sharp limitation on bounded-order correlation methods. We also determine the abstract covering-array threshold: subexponential size is compatible with full projections of order t(m) exactly when t(m) = o(m). These are statements about support projections, not uniform probability marginals. Arithmetic conclusions use explicitly stated cell axioms; no unverified finite-compiler bridge is assumed. Keywords: effective closed classes; algorithmic dimension; Chaitin halting probability; Turing degree; finite projections; Kolmogorov complexity; local marginals.
Authors
- Wenjie Yang (ORCID: https://orcid.org/0000-0002-5326-5382)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-09-28
- DOI
- https://doi.org/10.5281/zenodo.23007746
- Citations
- 4
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- preprint