TuringCompleteness: Recommendation via Markov Transition Entropy Matching Grounded in Turing Machine Complexity

Read full text Summarise with VIRAT
Authors: Assil KHELIFI
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

A Turing machine is not defined by its inputs and outputs but by the complexity of its state transition function. A machine that re-uses the same transitions has low entropy; one that explores diverse states has high entropy. The paper imports this insight directly into recommendation: each user's rating history is modelled as a symbolic sequence, and its first-order Markov transition entropy over discretised rating states becomes their computational complexity signature. H^trans_u = −Σ_{s,s'} T̂^u_{ss'} log T̂^u_{ss'} (Markov transition entropy)TC(u,i;β) = r̂_ui · exp(−β · |H^trans_u − H^trans_i|) The exponential penalty ensures that when user and item entropies match perfectly, the full SVD signal passes through; as they diverge, the score decays smoothly. Theorem 1 connects this to Kolmogorov complexity: under a stationary Markov model, the expected conditional complexity E[K(i|u)] is bounded above by a decreasing function of the entropy match. Corollary 1 predicts the high coverage result: because every entropy level gets matched by at least some users, items of every diversity profile receive recommendations. The empirical results are the most striking in the benchmark. TuringCompleteness achieves Coverage = 76.2% on ML-100K and 98.5% on ML-1M — more than double any baseline — with Gini = 0.487 and 0.430 respectively, compared to 0.866 and 0.875 for NMF. These figures represent a fundamental redistribution of recommendation mass across the entire item catalogue, not achievable by any trained method without explicit diversity constraints.

Fields of Study & Subjects

Recommender Systems and Techniques Advanced Bandit Algorithms Research Information Retrieval and Search Behavior

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
21 March 2026
Language
EN