pluto@beowulf.ucsd.edu (Mark E. P. Plutowski) (09/11/89)
In article <11494@boulder.Colorado.EDU> bill@synapse.Colorado.EDU (Bill Skaggs) writes: > Ah yes, Occam's razor slashes again! But the whole point, the very crux >of the problem, is that "simplest" is not a well-defined concept. I will >illustrate. > > There is an old mathematician's joke-paradox-problem, which goes as >follows. The first five elements of a sequence are 1,2,4,8,16 -- what >is the next element? > > Answer: 31. > > Why? Well, the way to extend a sequence is to find the simplest function >that is consistent with the numbers you have. But the simplest sorts of >functions, as every mathematician knows, are polynomials; and the >polynomial (1/24)n^4 - (1/12)n^3 + (11/24)n^2 + (7/12)n + 1 , >for n = 0,1,2,3,4, is the lowest order one that gives the members of the >sequence. So to get the next element, just plug in n = 5; if you do, >you get 31. > > You say that there is a simpler function? I say you're wrong. The >function 2^n is really quite a complicated one -- it only looks simpler >to you because you're familiar with it. I really liked this posting! It was a good point, well made. I am curious, though, as to the measure by which "every mathematician" considers polynomials to be the simplest sorts of functions. Conversely, by what measure do you consider 2^n relatively complicated? For the point you make, I grasp the intuition, and am sincerely not trying to split hairs. But to nail it down, what was the pertinent measure? The rate of growth? By this measure, surely the polynomial fit to the given empirical data would be "simpler" than the exponential fit. What if we instead employed a measure of the complexity of the formula? For instance, the length of the encoding, or, the number of parameters needed to specify the function. (In coarser terms, the amount of ink it takes to write it down.)