On 19 Sie, 21:53, Mariusz Marszałkowski <m...@g...com> wrote:

> Istnieje wiele algorytmów które rozstrzygają problem
> stopu na automacie skończonym, przypomnijmy
> jeden algorytm:

Niestety bezużyteczny w praktyce ze względu na nieredukowalność
obliczeniową wielu automatów.
Chodzi o to, że aby ten problem rozstrzygnąć, musisz (zgodnie ze
opisanymi metodami), *wykonać* badany algorytm. To jest zwykły
emulator.
Nie ma w tych metodach żadnego "skrótu", który by oszacował wynik
szybciej, niż trwa wykonanie badanego automatu.

Przykład: powiedzmy, że mamy komputer z 1GB RAMu i program, który na
całej tej pamięci robi licznik na wszystkich dostępnych bitach,
zwiększany ze średnią czybkością 1GHz - to taka pierwsza lekcja
asemblera. Ten program musi się albo zapętlić albo zatrzymać, ale jego
wykonanie trwa:

(2**(8*(2**30)))/(10**9) sekund,

czyli dłużej, niż będzie istniał cały wszechświat.

Jeżeli Twój algorytm nie potrafi tego rozstrzygnąć szybciej, niż przez
obserwację tego nudnego procesu, to jest kompletnie bezużyteczny.

--
Maciej Sobczak * http://www.inspirel.com