On Saturday, September 24, 2016 at 3:06:29 AM UTC+2, M.M. wrote:
> On Friday, September 23, 2016 at 7:47:37 PM UTC+2, bartekltg wrote:
> > On Friday, September 23, 2016 at 12:19:59 PM UTC+2, M.M. wrote:
> >
> > > Jest jeden test, którego żaden deterministyczny generator nie
> > > przejdzie.
> > >
> >
> >
> > Jaki? Tylko nie mów "wykrycie okresu", bo dla wielu generatorów
> > nie jest to technicznie wykonalne;-)
> >
> > pzdr
> > bartekltg
>
> Chodziło o to, że teoretycznie można. Teoretycznie każdy
> deterministyczny ciąg da się mocno skompresować. W praktyce
> jest to niewykonalne, ponieważ trzaby sprawdzać kolejno
> wszystkie metody kompresji. Niemniej każdy deterministyczny
> ciąg ma małą złożoność kołmogorowa.

jest znacznie gorzej,
tu się okazuje, że nawet teoretycznie nie można ;-)

https://en.wikipedia.org/wiki/Kolmogorov_complexity#
Uncomputability_of_Kolmogorov_complexity

" there is no program which takes a string s as input and produces
the integer K(s) as output."

Polecam dowod, bardzo ładny.

pzdr
bartekltg