KolmogorovNCD: A Compression-Based Recommender System Grounded in Kolmogorov Complexity and Turing Equivalence

Every existing collaborative filtering method imposes a handcrafted similarity function — cosine, dot product, Pearson — without theoretical justification for why that function, rather than any other, captures true user–item affinity. Kolmogorov complexity provides the deepest answer: two objects are similar to the degree that knowing one allows a short description of the other. Cilibrasi and Vitányi (2005) proved that the Normalised Compression Distance (NCD) is a computable approximation of this universal similarity and that it converges to the optimal metric as compressor quality improves. NCD(u,i) = (C(r_u · r_i) − min(C(r_u), C(r_i))) / max(C(r_u), C(r_i))KolmogorovNCD(u,i) = 1 − NCD(r_u, r_i) [C(·) = gzip compressed length] The Turing equivalence connection: user u and item i are Turing-equivalent when NCD ≈ 0 — each can describe the other with near-zero additional information. Theorem 1 bounds the approximation error as O(log(M+N)/(M+N)), tightening as vector length grows. Proposition 1 characterises the fixed points: pairs where one vector is compressible to near-zero given the other. The method is entirely parameter-free and training-free — it performs no matrix factorisation, no gradient descent, no similarity tuning. Despite this, it achieves Coverage = 36.7% on ML-100K, the highest of any method tested including all trained baselines, because the universal metric distributes attention evenly across the catalogue without any popularity bias baked in by training.