Re: Testy losowości liczb

Newsgroups	pl.comp.programming
Date	2016-09-25 10:15 -0700
References	(1 earlier) <ns2paj$lu0$1@node2.news.atman.pl> <ns2rle$o74$1@node2.news.atman.pl> <66aa9fc9-8d4a-421a-a992-f3842ee4e5f0@googlegroups.com> <fce115b3-8e66-4a32-ad8d-1f6a40d7d60b@googlegroups.com> <af75dbb0-9a80-4bac-a6bf-707d0e2032b8@googlegroups.com>
Message-ID	<43be2ca1-ed4e-4f55-8e02-ead40b2ef80f@googlegroups.com> (permalink)
Subject	Re: Testy losowości liczb
From	bartekltg <bartekltg@gmail.com>

Show all headers | View raw

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

Thread

Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 00:16 +0200
  Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 10:32 +0200
    Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 11:12 +0200
      Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 02:54 -0700
        Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 14:00 +0200
          Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 05:17 -0700
            Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 19:27 +0200
              Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 10:45 -0700
                Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 13:35 +0200
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-24 05:12 -0700
                Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 14:18 +0200
                Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 13:38 +0200
                Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-24 13:56 +0200
                Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 14:09 +0200
                Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-24 14:36 +0200
      Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-23 03:19 -0700
        Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 13:55 +0200
        Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 10:47 -0700
          Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-23 18:06 -0700
            Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 10:15 -0700
              Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-25 11:25 -0700
                Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 11:48 -0700
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-25 12:36 -0700
                Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-25 21:03 +0000
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-25 15:53 -0700
                Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-26 09:02 +0000
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 07:19 -0700
                Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-26 15:09 +0000
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 12:27 -0700
                Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-26 20:40 +0000
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 14:07 -0700
                Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-27 00:04 +0000
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 17:22 -0700
                Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-27 09:04 +0200
                Re: Testy losowości liczb godek.maciek@gmail.com - 2016-09-27 03:41 -0700
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-27 09:25 -0700
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-27 09:11 -0700
                Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-27 19:06 +0200
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-27 10:16 -0700
                Re: Testy losowości liczb Tomasz Kaczanowski <kaczus@dowyciecia_poczta.onet.pl> - 2016-09-28 09:55 +0200
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-28 03:51 -0700
    Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-25 14:20 +0200
      Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 14:47 +0200
        Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-25 15:07 +0200
          Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 15:11 +0200
  Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 14:20 +0200

csiph-web