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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

Internal Structure at a Fixed Representation: Degrees, Dimensions, and Counting

Wenjie Yang
4 citations
Zenodo (CERN European Organization for Nuclear Research)
Computability, Logic, AI Algorithms
preprint

Internal Structure at a Fixed Representation: Degrees, Dimensions, and Counting

Wenjie Yang
preprint en
4 citations

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Computability, Logic, AI Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Internal Structure at a Fixed Representation: Degrees, Dimensions, and Counting — Wenjie Yang · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS