> Svih source kodova u bilo kojem programskom jeziku koji implementiraju neku funkciju sa Z u Z ima prebrojivo mnogo (alef_0).
Ova mi uopće nije očito. Imaš neki dokaz?
Fkors. Unicode je, usprkos svim nastojanjima da se postigne suprotno:-P, još uvijek konačan (a čak i da nije, ideja da je code point prirodan broj znači da bi morao biti prebrojiv, pa bi tvrdnja svejedno vrijedila, samo bi dokaz bio kompliciraniji). Dakle, mogućih znakova ima konačno mnogo (u).
Mogućih nizova od 2 znaka sada također ima konačno mnogo (u^2, jer prvi i drugi možemo nezavisno birati svaki na u načina). Mogućih nizova od 3 znaka također ima konačno mnogo (u^3), i tako dalje, za svaki n, mogućih nizova znakova duljine n ima konačno mnogo (u^n).
To znači da ako poredamo sve stringove prvo po duljini, pa onda po code pointima (leksikografski, kao što strcmp radi samo na širem skupu), možemo ih redom enumerirati i svaki će doći na red, jer onih manje duljine od njega ima samo konačno mnogo (1+u+u^2+...+u^(|w|-1)=(u^|w|-1)/(u-1)), a ovih iste duljine kao on samo leksikografski manjih od njega također ima konačno mnogo (svakako manje od u^|w|).
Naravno, mnogi od njih bit će sintaksno neispravni, te neće imati nikakvu suvislu semantiku, ali oni koji hoće će pokrivati sve što se uopće može implementirati. Dakle, ima ih prebrojivo mnogo.
Friday, December 15, 2017
Thursday, December 14, 2017
Odgovor na Python meetup komentar
> Specijalni je slučaj iteratora onaj koji vraća iste vrijednosti svaki puta.
Matematički je neosporno da onih drugih ma beskonačno puta više.
Npr, next() bi mogao jednostavno vraćati i neku random vrijednost. To bi i dalje bio iterator, ali se ne može reversati.
S obzirom da se samo konačno podijeljeno sa beskonačno iteratora može reversati, to je zaista poseban slučaj.
Ako već hoćeš biti sasvim principijelan, onda je pravo pitanje zašto uopće postoje liste. Odgovor je, naravno, "Although practicality beats purity."
Hoćeš matematiku? Evo ti onda par matematički neospornih stvari. :-D
1. Svih funkcija sa Z u Z ima neprebrojivo mnogo (kontinuum). Svih source kodova u bilo kojem programskom jeziku koji implementiraju neku funkciju sa Z u Z ima prebrojivo mnogo (alef_0). Dakle, ima samo zanemarivo funkcija koje uopće možemo implementirati. Zašto uopće koristimo takav formalizam (programske jezike) koji hvata samo zanemariv dio općeg prostora funkcija? :-P
2. I za općenite tipove (ne samo Z -> Z), svih implementabilnih (izračunljivih) funkcija ima beskonačno mnogo. No u svakom konkretnom trenutku, do tog trenutka smo implementirali samo konačno mnogo njih, dakle zanemarivo malo u odnosu na opći prostor onih koje možemo implementirati. Zašto se uopće bavimo programiranjem? :-P
3. Čak i za funkcije koje jesmo implementirali, ako im je domena beskonačna, one zapravo bilo koji element od beskonačno mnogo njih mogu funkcijskim pozivom preslikati u element kodomene koji vrate. No do svakog konkretnog trenutka, izvršili smo samo konačno mogo funkcijskih poziva, dakle npr. za funkciju iz Z u Z, pokrili smo zanemarivo malen dio općeg interfacea jedne konkretne funkcije. Zašto uopće pokrećemo naše aplikacije? :-P
Odgovor na sva tri pitanja je isti: kardinalni broj skupa je vrlo jadna procjena važnosti / korisnosti njegovih elemenata. Naravno da su Reversible iteratori specijalan slučaj, ali su važan specijalni slučaj, koji se pojavljuje daleko češće nego da slučajno piknemo neki element općeg prostora iteratora.
Liste imaju svoju svrhu postojanja i u sasvim čistom platonističkom programiranju: random access, i držanje vlastitih elemenata _na različitim mjestima u isto vrijeme_, je važan aspekt programiranja, čak i apstraktnog. Iteratori drže svoje elemente _na istom "mjestu" u različitim vremenima_, i kao takvi su sasvim ortogonalni na liste, iako, kao što ćemo pokazati, nema nikakvog bitnog razloga da mnogi od njih ne podržavaju random access također.
Matematički je neosporno da onih drugih ma beskonačno puta više.
Npr, next() bi mogao jednostavno vraćati i neku random vrijednost. To bi i dalje bio iterator, ali se ne može reversati.
S obzirom da se samo konačno podijeljeno sa beskonačno iteratora može reversati, to je zaista poseban slučaj.
Ako već hoćeš biti sasvim principijelan, onda je pravo pitanje zašto uopće postoje liste. Odgovor je, naravno, "Although practicality beats purity."
Hoćeš matematiku? Evo ti onda par matematički neospornih stvari. :-D
1. Svih funkcija sa Z u Z ima neprebrojivo mnogo (kontinuum). Svih source kodova u bilo kojem programskom jeziku koji implementiraju neku funkciju sa Z u Z ima prebrojivo mnogo (alef_0). Dakle, ima samo zanemarivo funkcija koje uopće možemo implementirati. Zašto uopće koristimo takav formalizam (programske jezike) koji hvata samo zanemariv dio općeg prostora funkcija? :-P
2. I za općenite tipove (ne samo Z -> Z), svih implementabilnih (izračunljivih) funkcija ima beskonačno mnogo. No u svakom konkretnom trenutku, do tog trenutka smo implementirali samo konačno mnogo njih, dakle zanemarivo malo u odnosu na opći prostor onih koje možemo implementirati. Zašto se uopće bavimo programiranjem? :-P
3. Čak i za funkcije koje jesmo implementirali, ako im je domena beskonačna, one zapravo bilo koji element od beskonačno mnogo njih mogu funkcijskim pozivom preslikati u element kodomene koji vrate. No do svakog konkretnog trenutka, izvršili smo samo konačno mogo funkcijskih poziva, dakle npr. za funkciju iz Z u Z, pokrili smo zanemarivo malen dio općeg interfacea jedne konkretne funkcije. Zašto uopće pokrećemo naše aplikacije? :-P
Odgovor na sva tri pitanja je isti: kardinalni broj skupa je vrlo jadna procjena važnosti / korisnosti njegovih elemenata. Naravno da su Reversible iteratori specijalan slučaj, ali su važan specijalni slučaj, koji se pojavljuje daleko češće nego da slučajno piknemo neki element općeg prostora iteratora.
Liste imaju svoju svrhu postojanja i u sasvim čistom platonističkom programiranju: random access, i držanje vlastitih elemenata _na različitim mjestima u isto vrijeme_, je važan aspekt programiranja, čak i apstraktnog. Iteratori drže svoje elemente _na istom "mjestu" u različitim vremenima_, i kao takvi su sasvim ortogonalni na liste, iako, kao što ćemo pokazati, nema nikakvog bitnog razloga da mnogi od njih ne podržavaju random access također.
Subscribe to:
Posts (Atom)
