Ocena brak

O czym mówi teza Churcha - Turinga i jakie ma znaczenie dla analizy złożoności problemów algorytmicznych?

Autor /Barnim7777 Dodano /29.12.2011

Maszyna Turinga potrafi rozwiązać każdy efektywnie rozwiązywalny problem.

Rozwijając tę tezę, można dojść do wniosku, że jeśli istnieje jakiś szybki komputer, który potrafi rozwiązać dany problem w czasie O(f(N)), to istnieje równoważna mu maszyna Turinga, która potrzebuje na rozwiązanie tego problemu nie więcej niż O(p(f(N))) czasu, dla pewnej ustalonej funkcji wielomianowej p.

Podobne prace

Do góry