Semantic Algorithmic Information Theory: From Kolmogorov Complexity to Semantic Equivalence
Entropy · 14.05.2026 · 28 (5) · 554
DOI: 10.3390/e28050554 ↗Kurz gefasst
Fachartikel in der Zeitschrift Entropy, online erschienen am 14.05.2026. Verfasst von Jiatong Wu und 4 weiteren Autor:innen. Beteiligte Einrichtung: State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China. Die Arbeit nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China, Beijing University of Posts and Telecommunications, China Mobile Communications Group Co., Ltd. Joint Institute.
Abstract (Originalsprache)
Classical Algorithmic Information Theory (AIT) provides a rigorous foundation for information-based similarity measurement, but classical formulations and their compression-based approximations largely operate at the syntactic level, making them sensitive to surface-level variation and insufficient for semantic equivalence. To address this limitation, this paper introduces Semantic Algorithmic Information Theory. The contributions are organized around three core aspects. First, regarding algorithmic extension, we formalize the Semantic Turing Machine System (STMS) to decouple abstract concepts from their diverse syntactic realizations. Within this framework, Semantic Complexity is defined as the minimum program length required to generate some realization in a synonymous set, thereby characterizing compact meaning representation. Second, to enable approximate computation, we move from the ideal, uncomputable semantic information distance to a model-based direct estimator of the Normalized Semantic Information Distance (NSID), which uses neural autoregressive models as conditional probability estimators. Finally, through experimental validation and comparative analysis, we show that the NSID estimator suppresses syntactic variance while preserving semantic structure. Empirical results indicate that NSID provides a practical, computable surrogate for semantic distance and improves upon classical syntactic metrics in evaluating cross-representational equivalence.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China.
- China Mobile Research Institute, Beijing 100080, China.
- Key Laboratory of Universal Wireless Communications, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing 100876, China.
ORCID-Profile: Jiatong Wu, Sen Wang, Kai Niu, Yifei She, Ping Zhang
Förderung
- National Natural Science Foundation of China
- Beijing University of Posts and Telecommunications
- China Mobile Communications Group Co., Ltd. Joint Institute
Zitieren
APA
Wu, J., Wang, S., Niu, K., She, Y., & Zhang, P. (2026). Semantic Algorithmic Information Theory: From Kolmogorov Complexity to Semantic Equivalence. Entropy, 28(5), 554. https://doi.org/10.3390/e28050554
Vancouver
Wu J, Wang S, Niu K, She Y, Zhang P. Semantic Algorithmic Information Theory: From Kolmogorov Complexity to Semantic Equivalence. Entropy. 2026;28(5):554. doi:10.3390/e28050554
BibTeX
@article{Wu2026,
author = {Wu, Jiatong and Wang, Sen and Niu, Kai and She, Yifei and Zhang, Ping},
title = {Semantic Algorithmic Information Theory: From Kolmogorov Complexity to Semantic Equivalence},
journal = {Entropy},
year = {2026},
volume = {28},
number = {5},
pages = {554},
doi = {10.3390/e28050554}
}
EUVIMED