Szanowny Użytkowniku,

25 maja 2018 roku zaczyna obowiązywać Rozporządzenie Parlamentu Europejskiego i Rady (UE) 2016/679 z dnia 27 kwietnia 2016 r. w sprawie ochrony osób fizycznych w związku z przetwarzaniem danych osobowych i w sprawie swobodnego przepływu takich danych oraz uchylenia dyrektywy 95/46/WE (określane jako „RODO”, „ORODO”, „GDPR” lub „Ogólne Rozporządzenie o Ochronie Danych”). W związku z tym informujemy, że wprowadziliśmy zmiany w Regulaminie Serwisu i Polityce Prywatności. Prosimy o poświęcenie kilku minut, aby się z nimi zapoznać. Możliwe jest to tutaj.

Rozumiem

Czy teza Churcha ma jeszcze jakieś znaczenie dla informatyki?

Czy teza Churcha ma jeszcze jakieś znaczenie dla informatyki?

21.08.2016
Czyta się kilka minut
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:

Dodaj komentarz

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.

Zaloguj się albo zarejestruj aby dodać komentarz