FOM: intuition

Vladik Kreinovich vladik at cs.utep.edu
Sun Jan 7 21:04:29 EST 2001


There is a formal justification of this "physics-type" induction in math using 
Kolmogorov complexity; see, e.g., M. Li and P. Vitanyi, An Introduction to 
Kolmogorov Complexity and its Applications, Springer-Verlag, 1997 (especially 
Chpater 5). 

Crudely speaking, Kolmogorov complexity of a word is the shortest length of a 
program (in some universal language like C) which computes this word. There are 
quite a few results justifying induction. The main result is that, crudely 
speaking, if for every n, we select the simplest (in this sense) hypothesis 
consistent with the first n observations, then at some point, we will find the 
correct hypothesis. In this sense, thge correct answer minus 10^{-something} 
is, of course, also consistent, but it is NOT the simplest hypothesis. 

Vladik

P.S. To add my two cents worth: I have my own paper dealing with induction in 
math:

V. Kreinovich,
  "Coincidences are Not Accidental: a Theorem", 
  Cybernetics and Systems: An International Journal, 
  1999, Vol. 30, No. 5, pp. 429-440.
  
  Can be downloaded from http://www.cs.utep.edu/vladik/1997/tr97-36.ps




More information about the FOM mailing list