# Are the No Free Lunch Theorem and Halting Problem connected?

I just read about the no free lunch theorem where it is said:

Uniformly averaged over all target functions $F$, $\mathcal{E}_1 (E|F, > n) — \mathcal{E}_2(E|F, n) = 0$

The words "all target functions", reminded me of the halting problem:

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

This made me wonder if the two are related, if yes, how ?

EDIT:

Here is a different reason why they might be connected:

-Intelligence is a form of (lossy) compression

-Measure of compressability is Kolmogorov complexity

-Calculating the Kolmogorov complexity for an arbitrary string is undecidible (-> Halting problem)

(One flaw with this similarity that the Kolmogorow complexity is defined for lossless compression, while Intelligence is a form of lossy compression).

• Quick google search gives this : researchgate.net/publication/… – user70990 Aug 25 '16 at 9:16
• and this : cs.stackexchange.com/questions/59608/… – user70990 Aug 25 '16 at 9:17
• Intelligence is not a form of lossy compression. See vimeo.com/17553536 – James Bowery Dec 23 '17 at 13:55
• The best way to compress data is to discover the way it was generated and use that algorithm to generate it. For example the digits of PI. Any physics equation. Any working scientific theory. Speech. Vision. Is there an example where this does not hold ? For example, if I want to understand language /speech then I need to compress the probability distribution of all heard sentences. This compression will lead to a model of language / world that describes how speech is generated. Is there an example where this viewpoint does not hold ? – user70990 Dec 27 '17 at 14:45
• The vimeo link describes lossless, as opposed to lossy, compression, as a universal measure of intelligence. Any set of data will have noise. Even if you know the algorithm that generated the data, your measurement instrument will introduce noise. You can't throw the noise away because one man's noise is another man's ciphertext. Throwing away noise is indistinguishable from confirmation bias. – James Bowery Dec 27 '17 at 15:28