EUVIMEDSkopri EUVIMED
Open access · CC BY 4.0

Semantic Algorithmic Information Theory: From Kolmogorov Complexity to Semantic Equivalence

Jiatong Wu iD, Sen Wang iD, Kai Niu iD, Yifei She iD, Ping Zhang iD

Entropy · 2026-05-14 · 28 (5) · 554

DOI: 10.3390/e28050554 ↗

At a glance

Journal article in Entropy, published online on 2026-05-14. Written by Jiatong Wu and 4 co-authors. Institution: State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China. 18 references. The full text is freely available (open access, CC BY 4.0). Funded by: National Natural Science Foundation of China, Beijing University of Posts and Telecommunications, China Mobile Communications Group Co., Ltd. Joint Institute.

AstrattSubjectsDettalji biblijografiċiCiteRelated studies

Abstract (original language)

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.

Subjects

Author keywords

algorithmic information theorykolmogorov complexitynormalized semantic information distancesemantic information theoryset-theoretic metricssynonymous set

Authors and institutions

  • 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 profiles: Jiatong Wu, Sen Wang, Kai Niu, Yifei She, Ping Zhang

Funding

  • National Natural Science Foundation of China
  • Beijing University of Posts and Telecommunications
  • China Mobile Communications Group Co., Ltd. Joint Institute

Cite

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}
}
Start for free →