Summary: We adapt an algorithmic approach to the problem of local realism in a bipartite scenario. We assume that local outcomes are simulated by spatially separated universal Turing machines. The outcomes are calculated from inputs encoding information about a local measurement setting and a description of the bipartite system sent to both parties. In general, such a description can encode some additional information not available in quantum theory, i.e., local hidden variables. Using the Kolmogorov complexity of local outcomes we derive an inequality that must be obeyed by any local realistic theory. Since the Kolmogorov complexity is in general uncomputable, we show that this inequality can be expressed in terms of lossless compression of the data generated in such experiments and that quantum mechanics violates it. Finally, we confirm experimentally our findings using pairs of polarisation-entangled photons and readily available compression software. We argue that our approach relaxes the independent and identically distributed (i.i.d.) assumption, namely that individual bits in the outcome bit-strings do not have to be i.i.d.