On Wed, 9 Feb 2005, Knut M. Wittkowski wrote:
Last Friday, Gregory Chaitin (http://www.umcs.maine.edu/~chaitin/lm.html) mentioned that there can be no proof that a given code is the shortest for a problem, even within a language.
I presume he said something more like `for some problems there is no proof' or `there is no procedure for constructing a proof'
You can prove that function(x) x+1 is the shortest function for computing x+1 in R by listing all the shorter functions and verifying that none of them computes x+1, both of which tasks can be done fairly fast. This approach doesn't generalise because you can't give a general way to perform the second step: checking that none of the smaller programs works.
I would expect that the TDT falls in the category of problems checkable by enumeration.
Still, the script below, a replacement of the "TDT", one of the most frequently used tests in genetics (http://mustat.rockefeller.edu under "downloads") may get close. It contains a few additional bytes for clarity, as in (2^1) for 2, but, otherwise, I don't think one could make this much shorter, especially the part that does the exact distribution.
I'm looking forward to comments on improving the programming efficiency for this problem. (The "return(...)" seems to be necessary in R only.)
The return() should not be necessary in R.
-thomas
Thomas Lumley Assoc. Professor, Biostatistics [EMAIL PROTECTED] University of Washington, Seattle
______________________________________________ [email protected] mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
