Reklama

Czy teza Churcha ma jeszcze jakieś znaczenie dla informatyki?

Czy teza Churcha ma jeszcze jakieś znaczenie dla informatyki?

21.08.2016
Tytułowe pytanie jest nawiązaniem do tytułu artykułu Marka Burgina "The Rise and Fall of Church-Turing Thesis", w którym autor kwestionuje wartość tezy Churcha dla informatyki na obecnym (i przyszłym) stadium jej rozwoju.
Artystyczna wizja maszyny Turinga [commons.wikimedia.org]
J

Jak wiadomo po upływie niemal osiemdziesięciu lat od sformułowania TC, jej wartość logiczna nie została rozstrzygnięta, co jest zadziwiające samo w sobie. Tradycyjny pogląd w odniesieniu do TC jest taki, że wyznacza ona ograniczenie górne na klasę funkcji efektywnie obliczalnych w sensie intuicyjnym, zrównując ją (tę klasę) z klasą funkcji (częściowo) rekurencyjnych. Jeśli więc za podstawowe narzędzie informatyki uznamy algorytm,to TC ogranicza poważnie ramy tego, co może uzyskać informatyka (informatyk), zarówno w sensie teoretycznym, jak i praktycznym. Zadaniem tej pracy jest obrona wyjątkowej roli TC dla informatyki w kontekście całej klasy proponowanych modeli obliczeń posiadających cechę hiperobliczalności (tak zwane hypercomputations).

[Fragment artykułu, całość w załączniku].

Załączniki:

Usługodawca nie ponosi odpowiedzialności za treści zamieszczane przez Użytkowników w ramach komentarzy do Materiałów udostępnianych przez Usługodawcę.

Zapoznaj się z Regułami forum
Jeśli widzisz komentarz naruszający prawo lub dobre obyczaje, zgłoś go klikając w link "Zgłoś naruszenie" pod komentarzem.

Dodaj komentarz

Zaloguj się albo zarejestruj aby dodać komentarz