Re: Testy losowości liczb - Grupy dyskusyjne w eGospodarka.pl

eGospodarka.pl › Grupy › pl.comp.programming › Testy losowości liczb › Re: Testy losowości liczb

X-Received: by 10.157.11.215 with SMTP id 81mr787109oth.8.1474823704553; Sun, 25 Sep
2016 10:15:04 -0700 (PDT)
X-Received: by 10.157.11.215 with SMTP id 81mr787109oth.8.1474823704553; Sun, 25 Sep
2016 10:15:04 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!news.glorb.com!
u18no4336358ita.0!news-out.google.com!b4ni12153iti.0!nntp.google.com!u18no43363
53ita.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Sun, 25 Sep 2016 10:15:04 -0700 (PDT)
In-Reply-To: <a...@g...com>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=212.87.7.105;
posting-account=CvUQzQoAAABvVQmR58QmR6N4Cev1qhAS
NNTP-Posting-Host: 212.87.7.105
References: <ns1l8a$oh4$1@node1.news.atman.pl> <ns2paj$lu0$1@node2.news.atman.pl>
<ns2rle$o74$1@node2.news.atman.pl>
<6...@g...com>
<f...@g...com>
<a...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <4...@g...com>
Subject: Re: Testy losowości liczb
From: bartekltg <b...@g...com>
Injection-Date: Sun, 25 Sep 2016 17:15:04 +0000
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:209668
[ ukryj nagłówki ]

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