funkcja obliczalna

Funkcje obliczalne – podstawowy obiekt badań teorii obliczalności. Zbiór funkcji obliczalnych jest równoważny zbiorowi funkcji obliczalnych w sensie Turinga oraz funkcji częściowo rekurencyjnych. Funkcje obliczalne stanowią analogon intuicyjnego pojęcia algorytmu. Tego pojęcia używa się do dyskusji obliczalności bez odniesienia do określonego modelu obliczalności takiego jak maszyna Turinga lub . Jednak ich definicja musi mieć odniesienie do określonego modelu obliczalności. Zanim wprowadzono precyzyjną definicję funkcji obliczalnych, matematycy używali nieformalnego terminu „funkcji efektywnych”. Od tego czasu to określenie zaczęto utożsamiać z funkcjami obliczalnymi. Dokładniej można dla niektórych funkcji efektywnych wykazać, że każdy algorytm je obliczający będzie niewydajny w takim sensie, że każdy taki algorytm będzie potrzebował czasu rosnącego wykładniczo w zależności od długości wprowadzanych doń danych. Teoria obliczalności i teoria złożoności zajmują się zagadnieniami obliczalności oraz złożoności obliczeń funkcji obliczalnych wydajnie. Zgodnie z hipotezą Churcha i Turinga, funkcjami obliczalnymi są dokładnie te funkcje, które można obliczyć, używając urządzenia maszynowego, mając nieskończenie wiele czasu oraz przestrzeni pamięciowej. Równoważnie twierdzenie to oznacza, że każda funkcja dająca się wyrazić przez algorytm jest obliczalna. Aksjomaty Bluma dają nam abstrakcyjną definicję teorii złożoności na zbiorze funkcji obliczalnych. W teorii złożoności obliczeń problem określenia złożoności obliczalności jest znany jako zagadnienie funkcji.