🚀 go-pugleaf

Michal Przybylek <mrp@neostrada.pl> napisał(a): 

> "Aleksander Galicki" <tretete.SKASUJ@gazeta.pl> wrote:
> 
> > Po namysle: zalozenie o prefix-free w tym tez nie pomoze.
> 
> Tak czy inaczej musisz najpierw doprecyzowac co miales na mysli, zanim
> zaczniesz sie zastanawiac czy jest to prawda. Ja odczytalem Twoje slowa
> "asymptotycznie wieksza o skladnik nierekurencyjny" (inaczej jest to
> trywialne, ale nieciekawe).
> 

To bylo zludzenie optycznie-wieczorowe - myslalem, ze ta l(n) to moze byc
jedna z postaci K(n) - czyli zlozonoscia opisowa, ale nie - te rzeczy sa
niezalezne. (zalozenie o prefix-free jest czasem potrzebne, bo bez tego
zalozenia maszyna moze przeczytac tylko kawalek programu i sie zatrzymac nie
czytajac reszty). Dlatego tez podalem link do ksiazki o zlozonosci opisowej -
ale sie mylilem - dlugosc najkrotszego dowodu nie ma za wiele wspolnego ze
zlozonoscia opisowa (przynajmniej nie wprost).
Ale i tak moj przyklad (banalny bo banalny) spelnial swoja role - pokazanie,
ze rownie wolnych funkcji - nierekurencyjnych - mozna sobie na peczki
znajdowac. Duzo trudniejszym zadaniem byloby znalezienie _programow_, ktore
generuja duuze liczby (moze byc jedna). Byl nawet kiedys-gdzies konkurs na ten
temat (ale juz nie moge znalezc info w Internecie).

A wspominanie o bledach w ksiazce - to czepialstwo. Te bledy sa przewaznie
glupie literowki i przeoczenia (w dowodach - jak sie znany dowod tlumaczy na
wlasna nomenklature). 


A.

-- 
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/