Long Linear Random Programs Don't Generalise

• Since outputs are independent of inputs
  behaviour on one test tells us only a little about another
  but tells us something about computer's bias

  
  

• Again assume we can multiply probabilities of passing each test together

  
  

• T representative tests from 2^m possible tests (m input bits)

  
  

• Suppose OK in total programs pass the T tests

  
  

• Chance a program passes all 2^m tests

  $\approx \left(\frac{\mbox{\em OK}}{\mbox{\rule{0pt}{1.8ex}\em total}}\right)^{2^{m}/T}$

  
  

• I.e. chance of finding a general solution falls exponentially.