5 ms·
> Why are simple expressions not simple in all "natural" representations? Another example might be the primes, which have a very simple description and very su
by schoen 10y ago
> Why are simple expressions not simple in all "natural" representations?
Another example might be the primes, which have a very simple description and very subtle structure in their distribution.
- qubex 10y agoI don't really agree that the primes “have a very simple definition” in that the notion of ‘primeness’ is one of satisfiability and no constructive algorithm is known to exist.
- Chinjut 10y agoI'm not sure what you're getting at here. Is it not relevant that there is a simple algorithm to enumerate the primes, or, even more so, determine whether a given value is prime?
- spacehome 10y agoOf course it's relevant. qubex is just confused.
- jerf 10y agoI'm not sure what you mean by not having a constructive algorithm to produce primes. The Sieve of Eratosthenes will output any given prime, with the primes coming out in order, given enough time. There may not be an efficient algorithm, but for most definitions of "information" that won't matter. The sequence of all primes is both so richly structured we've probably only scratched the surface and almost entirely bereft of information.
- qubex 10y agoYup you're right and I'm wrong.