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 ?


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).

  • 1
    $\begingroup$ Quick google search gives this : researchgate.net/publication/… $\endgroup$ – user70990 Aug 25 '16 at 9:16
  • $\begingroup$ and this : cs.stackexchange.com/questions/59608/… $\endgroup$ – user70990 Aug 25 '16 at 9:17
  • $\begingroup$ Intelligence is not a form of lossy compression. See vimeo.com/17553536 $\endgroup$ – James Bowery Dec 23 '17 at 13:55
  • $\begingroup$ 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 ? $\endgroup$ – user70990 Dec 27 '17 at 14:45
  • 2
    $\begingroup$ 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. $\endgroup$ – James Bowery Dec 27 '17 at 15:28

No they are not related. In NFL, a function can be considered as a look-up-table (that is, a list of input-output pairs.) We are not concerned with how a function is implemented with NFL. With computability theory, we are concerned with how a function is actually computed.

try Woodward J. Computable and Incomputable Search Algorithms and Functions. IEEE International Conference on Intelligent Computing and Intelligent Systems (IEEE ICIS 2009) November 20-22,2009 Shanghai, China. pdf.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy