Lupetanje ko šta stigne

Za sada ne postoji univerzalna inteligencija koja bi za svaki zadati niz napisala najkraći mogući program za zadatu arhitekturu na kojoj piše programe, niti takva koja bi potvrdila da je napisani program najkraći mogući? Ako bi za zadate nizove programe pisao početnik u php, i ekspert level C asembler, rezultati bi bili prilično različiti, kao i ako bi program morao da bude pisan na bušenim karticama?



Bilo koje vrednosti dužine bajt, relativne frekvencije nizova dužine 9 bile bi bliske 1/512, dužine 10 1/1024 itd.. sve do veličina kad više nisu ni bliske, pojedini nizovi počinju da nedostaju, a neki se mnogo više pojavljuju? Pa onda takav niz iako ima frekvencije 1/256 proglasimo da uopšte nije slučajan, pre ima svoju jedinstvenu strukturu i osobine?

Matematika se uobičajeno izlaže zasnovana na klasičnoj logici, po kojoj je bilo koji matematički iskaz ili tačan ili netačan, nezavisno od ljudskog znanja i neznanja i nezavisno od mogućnosti ili nemogućnosti dokazivanja ili opovrgavanja tog stava.

Za program P je iskaz da jednom pušten u rad, u konačnom vremenu završava sa radom reprodukujući na standardnom izlazu niz N ili tačan ili netačan. Pritom, postoji barem jedan program koji na taj način reprodukuje dati niz N. Na osnovu datog niza N je lako napisati barem jedan takav program.

Svaki program ima veličinu, koju je čak vrlo lako odrediti. Iskaz, veličinu V ima barem jedan program koji na opisani način reprodukuje niz N, je takođe ili tačan ili netačan. Štaviše, za svaki niz N postoji barem jedan prirodan broj V, koji ispunjava taj uslov i za dati niz N je neke takve brojeve lako naći.

Na osnovu principa najmanjeg elementa, ako neki prirodan broj ima neko svojstvo, onda postoji najmanji prirodan broj sa tim svojstvom, pa samim tim postoji najmanji prirodan broj koji predstavlja veličinu barem jednog programa koji na opisani način reprodukuje dati niz N. Njega ćemo nazivati složenošću niza N i označavati sa S(N), bez obzira što ne možemo praktično da ga izračunamo.

Svih nizova date dužine d ima 256^d, što je konačan broj. Broj 256^d označimo sa k. Neka su n₁,...,n_k svi nizovi dužine d. Neka su njihove složenosti s_i=S(n_i). Tada je s₁,...,s_k konačan niz prirodnih brojeva.

Za svaki konačan niz prirodnih brojeva postoji najveći prirodan broj koji se u tom nizu pojavljuje najmanje jedanput. Taj broj, koji postoji, zvaćemo složenošću dužine d i označavaćemo sa C(d).

Slučajni nizovi dužine d su nizovi n_i za one vrednosti i za koje je s_i=C(d).

Bez obzira što nije moguće za dati konačan niz utvrditi da li je slučajan ili nije u odnosu na izabrani sistem izračunljivosti i što nije moguće naći barem jedan takav niz iole velike dužine, znamo da takvi nizovi postoje za svaku dužinu i znamo njihova svojstva koja su dovoljna da dokažemo da takav pojam slučajnosti reprodukuje Kolmogorovljeve zakone teorije verovatnoće u odgovarajućoj interpretaciji.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Evo nečega što se standardno koristi za testiranje generatora pseudoslučajnih brojeva.

https://en.wikipedia.org/wiki/Diehard_tests

Ali, ovo mogu da zadovolje i generatori pseudoslučajnih brojeva, u kojima nema ni malo slučajnosti.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Testovi su takvi da im poturiš nešto od Šekspira u binarnom obliku utvrdili bi da je slučajnost u pitanju :)

Ne bi, osim ako je mnogo dobro komprimovano.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Pa i dalje bi bio Šekspir, makar i u komprimovanom obliku (sa mogućnošću dekompresije), a ne slučajnost ..

Onaj poslednji post na prethodnoj strani već malo teže mogu da pratim, pa ne mogu da tvrdim sa sigurnošću, ali možda si ispustio na par mesta da pomeneš "baš taj" fajl, ili niz, (osim ako ti se podrazumeva) pošto i sam znaš da je lako napraviti, i da može da bude veoma kratak zapis programa koji reprodukuje sve fajlove iz nekog opsega, ili sve ikad, i slično, mislim da nije problem da program koji je kraći od fajla reprodukuje neki fajl, već da reprodukuje "baš taj" i samo njega, neki zadati fajl ...

Uprošćeno, po Kolmogorovu je konačan niz slučajan ako se ne može nikako komprimovati.

Dakle, ako je nešto komprimovano do daske, onda je binarni zapis slučajan.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Jeste, ali nema nikakav pomak u kvalitetu od izjava koje se vrte u krug još od Šanona, random je nekompresabilno, komprsabilno je sa niskim nivoom entropije (i obrnuto), deluje da su samo termini random i entropija zamenjeni terminima slučaj i kompleksnost? I samo je dodat hipotetički program da to potvrdi (podeblja što bi ja rekao).

Sad mu još samo nedostaje arhiver koji se zove do daske, ali pošto takav još uvek nema, moraće da se zadovolji sa 10 drugih koji daju 10 različitih rezultata.

Nedostaje samo momenat što bi deca rekla zašto, zašto nešto što je komprimovano je slučajno, ili ne može dalje da se komprimuje? Da li je sastavljeno od bita kao i početni fajl - jeste, da li nema ponavljanja, redundanse - ima, da li je neka statistička osobina - pa odmah bi napravio arhiver zasnovan baš na toj osobini, najverovatnije ne može da se komprimuje istim metodom koji je već primenjen, pa ćemo morati da nađemo neki drugi, ne do u beskonačno naravno ..

Pa, nema redundanse.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Pa 50% su jedinice, kako nema redundanse, 25% je zastupljen niz "00" itd.. to je ogromna redundansa, verovatno nema neke druge koja bi nekom odgovarala :)

Kada bi podatak koji se beleži bio da li ima jedinica i da li ima nula, onda bi ti bio u pravu.

Ako je podatak koji se beleži tekst, onda to nije redundansa.

Redundansa = dužina u bitovima - entropija.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

> Uprošćeno, po Kolmogorovu je konačan niz slučajan ako se ne može nikako komprimovati.

Nikako znaci da niko nikad nece uspeti da pronadje neko drugacije komprimovanje koje bi moglo da predje tu granicu?

Objasnio sam ovde.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Bez obzira na tip podataka redundansa je ponavljanje, ili višak informacija.

A to kad bi bilo tako kako si napisao taman bi bio dokaz da ne postoji fajl sa maksimumom entropije, pa ni nekompresibilan, jer ne postoji ni sa maksimumom redundanse, ili bar ne takav koji bi se mogao kompresovati na veličinu nula.

Binarnih reči koje nemaju više od jedne nule, niti više od jedne jedinice, ima pet - prazna reč, kao i reči 0, 1, 01 i 10. Primeti da ih ne možeš zabeležiti sa dva bita, jer ih ima više od četiri.

Ako je podatak koji se pamti tekst, onda nije dovoljno imati samo takve binarne reči, jer mogućih tekstova ima mnogo više od pet.

Za beleženje jednog štampajućeg ASCII znaka treba sedam bitova, jer takvih znakova ima 95. Ako je verovatnoća pojavljivanja svakog znaka ista, onda je entropija . Ako ga beležimo sa 7 bita, onda je redundansa , a ako ga beležimo jednim bajtom od 8 bita, onda je redundansa .

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

To verovatno u matematici, u računarskim naukama ne može da bude "prazna reč" jer bi podosta takvih onda moglo da se smesti između dva bita .. ili bi mogli da tumačimo da se niz od recimo 17 bita sastoji od još 16 praznih reči između tih bita itd ..



Bilo koji tekst, slika, muzika itd itekako bi mogli da se pamte samo uz pomoć gorenavedenih binarnih reči, u stvari dovoljni bi bili 0 i 1, u stvari ljudi tako i rade, to što su organizovane najčešće u bajtove i slično manje bitno ..



Nisam siguran ni zašto ovo pišeš, ni šta tačno računaš? Entropiju i redundansu po znaku, ili za ceo neki potencijalni tekst ispisan takvim znakovima, i da su pri tom verovatnoće pojavljivanja svakog znaka iste?

Šta ako bi neko odabrao 64 znaka od tih 95, i da ne bi arčio resurse lepo svakom znaku dodelio tačno 6 bita, i tako iscrpeo sve kombinacije od po 6 bita, tj sve kodne reči, i sa tih 64 znaka ispisao neki tekst dug tačno 64 znaka, i pri tom su verovatnoće pojavljivanja svakog znaka iste, tj svaki znak bi se pojavio tačno jedanput?

Računica bi onda išla: , a pošto bi tekst beležili kodnim rečima dužine 6 onda bi nastavak računice bio da je redundansa pa bi ispalo da je takav tekst/fajl maksimalno entropičan a redundansa nula, međutim i ovakav tekst (fajl) bi se dao kompresovati slanjem rednog broja permutacije umesto samog teksta ..

Slično i sa tekstom dužine 128 znakova, tj set od 64 znaka dva puta da se pojavljuje (i svaki pojedinačni znak tačno 2 puta) po ovoj tvojoj računici entropija bi i dalje bila 6, redundansa nula, sve verovatnoće pojavljivanja svih znakova jednake, a tekst i dalje kompresibilan na sličan način?

> Šta ako bi neko odabrao 64 znaka od tih 95, i da ne bi arčio resurse lepo svakom znaku dodelio tačno 6 bita,
> tako iscrpeo sve kombinacije od po 6 bita, tj sve kodne reči, i sa tih 64 znaka ispisao neki tekst dug tačno 64
> znaka, i pri tom su verovatnoće pojavljivanja svakog znaka iste, tj svaki znak bi se pojavio tačno jedanput?

Taj ko bi to uradio bi vec uradio komprimovanje.

Mada verovatnoce pojavljivanja svakog znaka kod nekog dugog kucanog teksta nisu iste.

Da, MajorFatal je smetnuo s uma raspodelu verovatnoće.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Ne razumem baš najbolje šta hoćeš da kažeš, da je neko birajući odgovarajuću dužinu kodne reči već izvršio komprimovanje? Možda ako porediš sa neracionalnim (ali jedinim mogućim za te prilike) načinima kodovanja kao ascii. Moja primedba i primer se odnosilo na "Ako je verovatnoća pojavljivanja svakog znaka ista, onda je entropija.. a redundansa .." itd .. jer u tom primeru i pored najracionalnije odabrane dužine kodne reči, kao i jednakih frekvencija pojavljivanja istih, i dalje ima mesta da se skrati niz ..





Da ali takvi nizovi se kompresuju baš na osnuvu razlika u frekvencijama, a jednakostima dužine kodnih reči, frekventnije reči se zamene kraćim nizovima, a manje frekventne produže itd ..

Nastavlja se praksa inaslova teme.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.