W dniu 2012-10-16 23:02, Baranosiu pisze:

> ciąg. Natomiast sama możliwość ustawienia elementów zbioru w ciąg
> (przeliczalność) jest (o ile się nie mylę :D) warunkiem niezbędnym na
> istnienie algorytmu sortującego (rozumianego jako "sekwencja
> instrukcji" - niekoniecznie skończona, być może sortująca w sensie
> granicznym).

Jeśli przez sortowanie rozumiemy znalezienie odwzorowania
z liczb naturalnych z zbiór, które zachowuje porządek, to ok.
Ale możesz bez trudu zbudować strukture danych, która
przechowa potencjalnie nieskończony zbiór z pynktami
skupienia, np wszytkie liczby postaci 1/n i 0 ;)

> Miałem na myśli to, że samo istnienie porządku liniowego (czy dobrego
> porządku, masz rację, na jedno wychodzi) nie gwarantuje istnienia
> algorytmu sortującego (w czasie skończonym bądź w sensie granicznym
> przy liczbie kroków dążącej do nieskończoności).

I znów zahaczamy o nieskończoność w algorytmach.

Ujmę to tak: mając dowolnej mocy zbiór*),
aby posortować algorytmicznie jego dowolny skończony
podzbiór (ustawić go w ciąg) potrzeba/wystarczy porządek
liniowy.


*) Nie, żeby na komputerze mógł się pojawić kiedykolwiek
większy niż przeliczalny;)


pzdr
bartekltg