On 16/10/2012 11:51, Baranosiu wrote:
> Dnia 16.10.2012 Michoo <m...@v...pl> napisał/a:
>>> analogowej może już nie być algorytmem na maszynie dyskretnej.
>>
>> Dlatego napisałem - "na pewnej abstrakcyjnej maszynie".
>
> Na "abstrakcyjnej" czyli na żadnej :D

Dlaczego aż żądnej? Algorytm sam też jest abstrakcją.

> Zwykle w informatyce przyjmuje
> się w domyśle maszyny Turinga, ale samo pojęcie algorytmu nie musi ich
> dotyczyć :D
[...]
> 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
[...]
> Ok, są, ale to są tylko konkretne modele. Można na przykład
> zdefiniować pojęcie algorytmu w oparciu o maszyny Turinga ale...

Z tymi Maszynami Turinga to raczej nieporozumienie. Maszyna Turinga
wykonuje jeden konkretny algorytm, żadnego innego nie potrafi. To, o
czym się rozważa przy pomocy Maszyn Turinga to nie są algorytmy, tylko
obliczenia. I tak owszem, każdy algorytm obliczający cokolwiek jest
równoważny MT, ale równoważność obliczeniowa to nie jest tożsamość na
poziomie rozmowy o algorytmach. Najprostszy przykład (skoro jesteśmy już
w takim temacie) - wszystkie algorytmy sortujące są równoważne
obliczeniowo, chociaż nie ulega wątpliwości, że quicksort i bubble sort
to dwa różne algorytmy.