NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/ai/neuraln/3343

Text File | 1992-08-29 | 2.7 KB | 58 lines

Xref: sparky comp.ai.neural-nets:3343 comp.ai:3254 comp.theory:1834
Newsgroups: comp.ai.neural-nets,comp.ai,comp.theory
Path: sparky!uunet!s5!sethb
From: [e-mail] (Seth Breidbart)
Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
Message-ID: <[e-mail]>
Organization: Morgan Stanley & Co., New York, NY
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Fri, 28 Aug 1992 16:49:41 GMT
Lines: 46

In article <[e-mail]> [e-mail] (Jamie Andrews) writes:
>In article <[e-mail]> [e-mail] (Seth Breidbart) writes:
>|In article <[e-mail]> [e-mail]
>|(Jamie Andrews) writes:

>     I suppose I was intending to mean something like this:  an
>epsilon-delta algorithm A which, when given a string S, outputs
>a program P such that
>(a) P outputs S, and
>(b) with probability (1-delta), the length of P is within
>    epsilon percent of the length of the minimal program which
>    outputs S.
>(It's trivial to output *some* program which outputs S -- it
>would be just (defun (result) (quote S)), where S is the listing
>of the string.  The problem is getting the length down, for long S.)

I assume that A is a random "algorithm".

What do you mean by probability?  If you mean, for any string S, with
probability > (1-delta) P is within epsilon of the shortest program
for S, then A will lead to a probabilistic solution to the busy beaver
problem.

If you mean, for S a random string (with some probability), then the
trivial program you give will (almost) work:  for almost all strings,
the shortest program involves quoting the string.  Of course,
assigning probabilities to strings is highly non-trivial; that aspect
alone prevents this interpretation from being useful (if strings have
non-zero probability, then a finite number of them have total
probability > 1-delta).

>     This might not be the exact formulation needed... is this
>problem trivial too?  Do we need some tighter epsilon-delta
>bound?  What is the sample space -- all strings of length k
>or less, or all strings output by programs of length k or less,
>or something else?  What is the distribution on the sample
>space?  And what would the algorithms look like, and what would
>be their time and space bounds?  I think these are pretty
>interesting questions.

If you say "for all k, assigning equal probabilities to all strings of
length bounded by k and 0 to all others", then you avoid the last
problem I raise, but once again the trivial program works almost
everywhere (and a finite correction to it works everywhere).

Seth        [e-mail]