On the Empirical Agreement Between Compression and Program-Execution Approaches to Algorithmic Complexity: A...

Algorithmic complexity is a foundational notion in theoretical computer science, but its incomputability has led to two families of practical estimators: compression-based and program-execution-based (e.g., the Coding Theorem Method, CTM). Despite widespread use, the correspondence between these paradigms remains poorly understood. We present a systematic comparative framework that uses the Block Decomposition Method (BDM) to extend CTM-based estimates to longer strings, enabling direct comparison with compression-based estimators across multiple computational models. A control estimator (BDM_Id) isolates the contribution of block structure from algorithmic information, providing a rigorous baseline for interpreting correlations. Our results show that cross-paradigm correlations are weak and decrease systematically as model resolution decreases; for the lowest-resolution model, correlations are essentially null. In long strings, per-length correlations vanish, while global correlations appear high but are largely explained by the control estimator, indicating that they are driven primarily by trivial length effects rather than shared sensitivity to algorithmic structure. Crucially, for low-resolution models, BDM_Id outperforms BDM itself, indicating that the inclusion of CTM information does not improve-and may even reduce-agreement with compression-based estimators. These findings suggest that compression-based and program-execution-based estimators capture fundamentally different aspects of structure. Rather than invalidating either approach, this work provides a systematic methodology for assessing cross-paradigm correspondence and highlights the importance of explicit controls in empirical comparisons of algorithmic complexity.