🚀 go-pugleaf

Zupelnie z innej beczki:

"Wezmy dowolne efektywne kodowanie zdan logiki pierwszego rzedu. Niech l(n) -
dlugosc najkrotszego dowodu (w dowolnym efektywnym formalizmie) formuly \phi
o numerze n. Okreslmy funkcje f : N -> N nastepujaco:

f(n) = \sum{i = 0..n} l(n)

Ta funkcja rosnie niewyobrazalnie szybciej od ss i prawdopodobnie szybciej
niz dowolna funkcja, ktora jestes w stanie zdefiniowac (nie uzywajac f ani
l). "

To jest raczej oczywista nieprawda. Zakladajac ze mowimy o prefix-free
maszynach/jezykach itepe, a takze zakladajac, ze dlugoscia dowodu jest dlugosc
maszyny (a nie np. wykonania) to mozna latwo znalezc szybciej (a napewno nie
wolniej) rosnace funkcje. Np uzywajac "dlugosc _najszybszego_ dowodu" zamiast
l(n).

Jednak w kontekscie oryginalnego watku (generowaniu liczb) to troche bez
sensu, bo te funkcje sa enumerable ale nie computable.

A tak by the way: http://www.mcs.vuw.ac.nz/~downey/

"Denis Hirschfeldt and I are writing a book entitled Algorithmic Randomness
and Complexity The current latest draft can be downloaded by clicking on the
attachment above. It is also available as a .pdf file : Algorithmic Randomness
and Complexity (pdf) Denis and I would appreciate any feedback. "

Na razie mozna sciagnac za darmo : http://www.mcs.vuw.ac.nz/~downey/randomness.pdf

Jest to zaledwie trzecia ksiazka, ktora traktuje obszernie o tej tematyce. Za
dwie inne trzeba placic po jakies 50 euro.


A.

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