Dear Editor, attached a revised version of manuscript. This revision addresses the concerns expressed by the reviewers. In the following we highlight the changes that better address the single points of criticisms. -------------------------- Referee: 1 1. Our inequality resembles the CHSH one only because it takes into account two parties and two local measurements. However, this is the end of the resemblance. It is fundamentally different than the CHSH. The biggest difference is that our inequality is not tight but it does not depend on the number and on the labeling of outcomes, whereas CHSH is tight, but is only suitable for measurements whose outcomes are +1 or -1. In addition, optimal settings for the violation of our inequality are different than the ones used in the CHSH scenario. We refer to CHSH before 4.1 just to give an additional prove that the data is non-classical (since CHSH is tight, it must be violated if our inequality is violated, but the reverse is not always true). This is stated in the introduction of section 3 (section 4 of the previous version): “A separate test of a CHSH-type ..." In order to better emphasize the difference between the proposed approach and a standard Bell test, the Introduction has been entirely rewritten. 2. It is not true that any nondeterministic theory would violate all computable hidden variable theories. For example, standard Bell inequalities are also valid for nondeterministic hidden variables, i.e., these that are distributed according to some probability distribution. More precisely, Bell inequalities are satisfied as long as there exists a joint probability distribution for all measurable outcomes (even for those that cannot be jointly measured) - see the paper by Fine [PRL 48, 291 (1982)]. In case of the example presented by the referee there is only a single observable that is measured and therefore a joint probability distribution exists. Moreover, there exists a number computable hidden variable models for a qubit. Take for example the one due to Bell - see the review paper by Mermin [Rev. Mod. Phys. 65, 803 (1993)] - which can be applied to a situation discussed by the referee. In fact, the Bell model can be easily reformulated as a computer algorithm, which clearly shows that it is computable. 3. It seems that to answer this we need to use the argument that in fact our source is i.i.d. In this case we can use the Shannon entropy and show that for each compression the value approaches the Shannon limit (calculated for the measured data). This is done in section 3. 4. This is the counterfactual reasoning problem that up to now appears in every Bell test (however, see the recent paper arXiv:1505.07037 that also refers to our work). Because the measurements are incompatible, we cannot gather all data that is needed to test a given inequality on the same system. We therefore need to make measurements on a whole ensemble of systems and make some additional assumptions to make the test realizable in the lab. We discuss this problem on page 4 (bottom). In our experiment we generate one string x_{a_0} when jointly measured with b_0, and another string x'_{a_0} when jointly measured with b_1. However, we assume that the Kolmogorov complexities of x_{a_0} is the same as the one of x'_{a_0}. This is a reasonable assumption that allows us to perform a test. 5.1 The entire Introduction of the paper have been rewritten. It is now clearly emphasized the scope and result of our results. 5.2 The entire introduction of Section 2 has been rewritten, in order to better clarify the point that even if UTM_A and UTM_B are fed the same input program \Lambda, the basis choice input is different and non-correlated. 5.3 The assumption that a Turing machine can reproduce any string of length N if fed a suitable program is the definition itself of a Turing machine. As such, it does not require any hidden variable. Regarding the figure. The program Lambda describe the entire system, and as such it is fed to both UTM's. We have updated the representation: it is now implied that each UTM is fed a description of the measurement basis. The resulting output was the same only by a depiction accident. It has been changed in the curent version of the manuscript. 5.4 The atricle suggested by the Referee does not use Kolmogorov complexity. It presents two cases where computation and quantum mechanics produce interesting results, but we did not find any evident connection with our results. -------------------------- Referee: 2 1) The expression "Local universal Turing machine" has been replaced with "spatially separated universal Turing machines". This should be clearer to the reader. 2) At the beginning of section 4.1 we added the following comment: "In the realization of this proof of principle experiment, we did not intend to provide a loophole-free demonstration. Due to the limited efficiency of the APD detectors, we assume a fair sampling. Similarly, even if Alice and Bob are not space-like separated, we assume that no communication happens between the two measurements. Moreover, the basis choice is not random, as expected in an ideal Bell-like experiment. We instead set the basis and record the number of events in a fixed time. We are assuming that the state generated by the source, and all the other parameters of the experiment, do not change between experimental runs." This should also address point 10. 3) We have rewritten section 2 to address this issue. 4) The relevant citations have been added: [8] Santos E 1986 Physics Letters A 115 363–365 [9] Schumacher B W 1991 Phys. Rev. A 44 7047–7052 [10] Kurzyn ́ski P and Kaszlikowski D 2014 Phys. Rev. A 89 012103 [11] Wajs M, Kurzyn ́ski P and Kaszlikowski D 2015 Phys. Rev. A 91 012114 5) We have revised the claims regarding the necessity of i.i.d. for our method. In the abstract we now states that "our approach relaxes the i.i.d. assumption, namely that individual bits in the outcome bit-strings do not have to be independent and identically distributed." Section 1 and 2 have been extensively rewritten in the same spirit. Our point is that Kolmogorov complexity and compression algorithms can be applied to finite bit strings that are non-i.i.d., i.e., each bit in a string does not need to be generated independently and with respect to the same distribution. We also reformulated our assumption that Kolmogorov complexity remains the same in each experimental run - see point 6. 6) We reformulated our assumption. The assumption of ‘uniform complexity’ states that our inequality applies only to strings whose complexity is the same up to a term (logN)/N. It follows that if the inequality (6) is violated, either local realism or uniform complexity are invalid. The end of section 2.2 now reads: "To address this issue, we introduce a new assumption: for every two experimental runs $i$ and $i'$ the complexity of the generated strings remains the same: $K(x_{i,a_j})\,=\,K(x_{i',a_j})$ and $K(x_{i,a_j}, y_{i,b_k})\,=\,K(x_{i',a_j}, y_{i',b_k})$ up to a term $\frac{\log_2 N}{N}$. We call this assumption uniform complexity. Thus our inequality only applies to programs that have this property. It follows that if the inequality (6) is violated, either local realism or uniform complexity are invalid. Uniform complexity can in principle be tested experimentally." 7) The section was rewritten and the issue was clarified. H(X) is the Shannon entropy of an ensemble of all possible bit strings. 8) In the new version we clearly state that our inequalities hold up to a term logN/N 9) In the description of the experimental setup we have added the following text: "[and polarization beam splitter](extinction ration 1/2000 and 1/200 respectively for transmitted and reflected arm)" 10) See point 2) 11) We have clarified the association between detectors and binary value, as well as the fate of multiple pairs detection events. Section 4.1, second paragraph, now read: "A detection event at the transmitted output of each PBS is associated with 0, reflected one with 1. Three- and four-fold coincidences, as well as two-fold coincidences between detectors belonging to the same party, correspond to multiple pairs of photos generated withing the coincidence time window. The rate of these events is negligible, therefore we discarded them." 12) In section 3, we have added the following sentence: "To avoid artifacts due to the limited data block size of the compression algorithms, the elements of $x$ and $y$ are interleaved: for example, for string $x = (0, 0, 0)$ and $y = (1, 1, 1)$, the resulting strings is $xy = (0,1,0,1,0,1)$. The same interleaving procedure is also implemented for the strings generated in the experiment, as described later on." 13) In section 4.1 we have added the following text: "In order to obtain long enough strings for a stable compression, see figure 3, this measurement is repeated 11 times and the results concatenated, obtaining strings of average length 1E5 bits" In section 5 we have added the following text: "To estimate an uncertainty of the experimentally obtained values for S, we set theta = 8.6deg, for which we expect the maximum violation, and collected results from a larger number of photon pairs. We then repeated the measurement of S, as described in the previous section, 10 times, and considered the average value and standard deviation of this set obtaining the final result of S(theta = 8.6deg) = 0.0494 +/- 0.0076." M1) We added the following text after Eq.(2): "This distance is a metric, up to a correction $\frac{\log_2 N}{N}$, where $N$ is the length of strings $x$ and $y$." M2) Typo corrected.