On 2012-10-16, Baranosiu <r...@w...pl> wrote:
> Dla zbiorów dyskretnych (a ściślej dla dyskretnych ich reprezentacji w
> maszynie) to jak najbardziej algorytm zadziała, ale nie wszystkie
> zbiory są przeliczalne (a więc nie zawsze dają się posortować) i... z

Ależ przeliczalność w ogóle nie jest konieczna (liczby rzeczywiste
sortują się naprawdę dobrze - polecam sprawdzić :)).

Aby sortowanie miało sens (teoretyczny) musi istnieć jakaś metoda
porównywania, czyli na zbiorze musi istnieć jakiś porządek liniowy.

> Wszystkie współczesne komputery cyfrowe (łącznie z kwantowymi) to
> maszyny Turinga, więc rozróżnienia się nie robi, w tym sensie można
> pominąć szczegóły maszyny, ale samo pojęcie algorytmu to coś więcej
> niż "proces wykonywany przez maszynę cyfrową".

Z tym "wszystkie komputery cyfrowe to maszyny Turinga" to taki trochę
niepewny tekst (zależy co by nazwać komputerem).
Za to nie wszystkie języki programowania są zupełne (kompletne
w sensie Turinga).

pozdrawiam,
PK