Dnia 16.10.2012 bartekltg <b...@g...com> napisał/a:
> W dniu 2012-10-16 22:06, Baranosiu pisze:
>
>>
>> To zależy jak się rozumie pojęcie "posortować", bo w CIĄG rosnący to
>> się ich ustawić nie da (choć zgoda, każde dwie da się porównać i tak
>
> Nieprzeliczalnego zbioru (jak choćby wspomniany (0,1)) w ogole
> nie da się ustawić w _jakikolwiek_ ciąg;-)

No właśnie, nie da się ustawić w ciąg, a więc nie da się za pomocą
"sekwencyjnie wykonywanych instrukcji" zbioru uporządkować, czyli nie
istnieje algorytm w takim pojęciu, w jakim rozważamy go w tym wątku,
mało tego, nie istnieje nawet algorytm "zapętlony na wieczność"
rozwiązujący ten problem w nieskończonym czasie :D

>
>> ustawić, że "każda po prawo jest większa od tej po lewej")
>> ale... jeśli nie da się ułożyć w ciąg, to też nie da się podać
>> algorytmu sortującego, więc... coś za coś, jeśli zluzujemy z definicją
>> "posortowany" (niekoniecznie w ciąg) to luzujemy z definicją
>> "algorytmu" (rezygnujemy z "sekwencja następujących po sobie
>> instrukcji") bo inaczej nie da się przedstawić algorytmu sortowania w
>> "nie-ciąg" :D
>
>
> Nie chodziło mi o to. Przez posortować rozumiałem potencajlną
> możliwość ustawianie w sposób posortowany. Nie algorytm.
> Ale niech będzie algorytm, jak zauważasz, to nieistotne.

Zgoda, mój błąd, zagalopowałem się :D Samo istnienie dobrego porządku
nie gwarantuje możliwości ustawienia elementów zbioru w
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).
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).