On 8 Sie, 13:33, "Mariusz Marszałkowski" <b...@N...gazeta.pl>
wrote:
> Marcin 'Qrczak' Kowalczyk <q...@k...org.pl> napisał(a):
>
> > Samomodyfikacja może przyspieszyć o stały czynnik, ale nigdy nie jest
> > konieczna dla poprawy asymptotycznej złożoności.
>
> Jakie jest źródło tej informacji? Skąd to wiadomo?

Chodzi o to, że każdy program który jest samomodyfikujący się można
też wykonywać w emulatorze naszego pierwotengo systemu - i wtedy już
nie wykonujemy programu samomodyfikującego się. Emulacja zwykłych
programów nie zmienia asympototycznej złożoności ich algorytmów - po
prostu każda instrukcja się wykonuje np. 100 razy wolniej i tyle.

A czy są niezwykłe programy? Może mogą być, gdy w jakiś nietrywialny
sposób oddziałują z systemem operacyjnym (tak, że taka emulacja wprost
się załamuje). Na przykład wywołują funkcje systemu operacyjnego,
która oblicza skrót kryptograficzny wybranego fragmentu pamięci
zawierającej kod wykonywanego programu (normalnie takich funkcji nie
ma, ale to tylko przykład).

-ms