Funkcja obliczalna 📖 Wikipedia

Istnieje wiele równoważnych sposobów określenia klasy funkcji obliczalnych. Są to częściowe funkcje na liczbach naturalnych, które można obliczyć za pomocą maszyny Turinga. Równoważne modele obliczalności, wyznaczające tę samą klasę funkcji, obejmują m.in.:

• funkcje μ-rekurencyjne,
• maszyny Turinga,
• maszyny von Neumanna,
• maszyny znakujące,
• rachunek lambda,
• programy GOTO,
• programy WHILE.

Każda obliczalna funkcja ${\displaystyle f}$  ma skończoną liczbę argumentów będących liczbami naturalnymi. Funkcje te mogą być częściowe, tzn. nie muszą być określone dla wszystkich argumentów. Jeżeli funkcja jest określona dla danego argumentu, jej wartością jest pojedyncza liczba naturalna. Funkcje takie nazywa się również funkcjami częściowo rekurencyjnymi. W teorii obliczalności dziedziną funkcji częściowej jest zbiór wszystkich argumentów, dla których jest ona określona.

Funkcję określoną dla wszystkich argumentów nazywa się funkcją zupełną. Jeżeli funkcja obliczalna jest zupełna, nazywa się ją zupełną funkcją obliczalną lub zupełną funkcją rekurencyjną.

Zapis ${\displaystyle f(x_{1},\dots ,x_{k})\downarrow }$  oznacza, że funkcja częściowa ${\displaystyle f}$  jest określona dla argumentów ${\displaystyle x_{1},\dots ,x_{k}}$ , natomiast zapis ${\displaystyle f(x_{1},\dots ,x_{k})\downarrow =y}$  oznacza, że jest ona określona dla tych argumentów i przyjmuje wartość ${\displaystyle y}$ .

Podstawową cechą funkcji obliczalnej jest istnienie skończonej procedury (algorytmu) określającej sposób jej obliczania. Poszczególne modele obliczalności różnią się interpretacją pojęcia procedury, jednak definiują równoważne klasy funkcji, ponieważ potrafią symulować się wzajemnie (podobnie jak kompilator może tłumaczyć program z jednego języka na inny).

W 1977 roku Herbert Enderton podał następującą charakterystykę procedury wyznaczającej funkcję obliczalną:^[2]

• Muszą istnieć precyzyjne, skończone instrukcje (program) opisujące procedurę.
• Dla każdej krotki argumentów ${\displaystyle {\boldsymbol {x}}}$  należącej do dziedziny funkcji ${\displaystyle f}$  procedura po skończonej liczbie kroków zwraca wartość ${\displaystyle f({\boldsymbol {x}})}$ .
• Dla argumentów nienależących do dziedziny funkcji procedura może nie zakończyć działania albo zakończyć się bez zwrócenia wartości.

Jeżeli procedura zwraca wartość ${\displaystyle f({\boldsymbol {x}})}$ , to musi ona być poprawna.

Enderton wskazuje ponadto, że:

• nie ma ograniczenia liczby argumentów funkcji,
• liczba kroków potrzebnych do uzyskania wyniku jest skończona, lecz nieograniczona z góry,
• nie zakłada się ograniczeń pamięci – w modelu dopuszcza się dowolnie dużą ilość zasobów.

Teoria złożoności bada funkcje obliczalne przy dodatkowych ograniczeniach dotyczących czasu lub pamięci.

Podzbiór ${\displaystyle A}$  zbioru liczb naturalnych nazywa się obliczalnym (rekurencyjnym, rozstrzygalnym), jeżeli istnieje funkcja obliczalna ${\displaystyle f}$  taka, że dla każdej liczby ${\displaystyle n}$  zachodzi:

• ${\displaystyle f(n)\downarrow =1}$ , gdy ${\displaystyle n\in A}$ ,
• ${\displaystyle f(n)\downarrow =0}$ , gdy ${\displaystyle n\notin A}$ .

Zbiór jest obliczalnie przeliczalny (rekurencyjnie przeliczalny, półrozstrzygalny), jeżeli istnieje funkcja obliczalna ${\displaystyle f}$  taka, że ${\displaystyle f(n)}$  jest określona wtedy i tylko wtedy, gdy ${\displaystyle n\in A}$ . Innymi słowy, zbiór jest obliczalnie przeliczalny wtedy i tylko wtedy, gdy jest dziedziną pewnej funkcji obliczalnej.

Analogicznie definiuje się relacje obliczalne i relacje obliczalnie przeliczalne, utożsamiając relacje z odpowiednimi zbiorami skończonych ciągów liczb naturalnych.

W teorii obliczalności rozważa się również języki formalne. Alfabet to dowolny zbiór symboli. Słowo nad alfabetem to skończony ciąg symboli z tego alfabetu. Język to podzbiór zbioru wszystkich słów nad danym alfabetem.

Język jest obliczalny (rekurencyjny, rozstrzygalny), jeżeli istnieje funkcja obliczalna ${\displaystyle f}$  taka, że dla każdego słowa ${\displaystyle w}$ :

• ${\displaystyle f(w)\downarrow =1}$ , gdy ${\displaystyle w}$  należy do języka,
• ${\displaystyle f(w)\downarrow =0}$ , gdy ${\displaystyle w}$  nie należy do języka.

Język jest obliczalnie przeliczalny (rekurencyjnie przeliczalny, półrozstrzygalny), jeżeli istnieje funkcja obliczalna ${\displaystyle f}$  taka, że ${\displaystyle f(w)}$  jest określona wtedy i tylko wtedy, gdy ${\displaystyle w}$  należy do języka.

Do funkcji obliczalnych należą m.in.:

• każda funkcja o skończonej dziedzinie,
• każda funkcja stała,
• Dodawanie liczb naturalnych,
• funkcja wyznaczająca czynniki pierwsze liczby,
• Największy wspólny dzielnik,
• rozwiązania wynikające z tożsamości Bézouta oraz liniowe równania diofantyczne.

Jeżeli ${\displaystyle f}$  i ${\displaystyle g}$  są obliczalne, to obliczalne są również ich suma, iloczyn, złożenie (przy odpowiednich założeniach) oraz wiele innych operacji konstruowanych z użyciem operatora minimizacji.

Przykładem funkcji obliczalnej, dla której nie jest znany jawny algorytm, jest funkcja zależna od własności rozwinięcia dziesiętnego liczby ${\displaystyle \pi }$  (np. istnienia dowolnie długich bloków tej samej cyfry).

Skończone fragmenty wartości funkcji pracowitego bobra są obliczalne, choć sama funkcja nie jest obliczalna.

Teza Churcha głosi, że każda funkcja obliczalna w intuicyjnym sensie efektywnej procedury jest obliczalna w sensie formalnym (np. przez maszynę Turinga). Ze względu na nieformalny charakter pojęcia „efektywnej procedury” tezy tej nie można ściśle udowodnić.

Na jej rzecz przemawia m.in. równoważność wielu niezależnie zaproponowanych modeli obliczeń oraz brak ogólnie akceptowanego silniejszego modelu odpowiadającego intuicyjnemu pojęciu obliczalności.

Ponieważ każda funkcja obliczalna ma skończony opis, istnieje przeliczalnie wiele funkcji obliczalnych.

Z kolei zbiór wszystkich funkcji z liczb naturalnych w liczby naturalne jest nieprzeliczalny, a więc „większość” takich funkcji jest nieobliczalna.

Klasycznym przykładem problemu nierozstrzygalnego jest Problem stopu. Zagadnienie rozstrzygalności postawione przez Davida Hilberta doprowadziło do wykazania przez Turinga i Churcha, że nie istnieje ogólna efektywna procedura rozstrzygająca prawdziwość wszystkich zdań arytmetyki.

Pojęcie obliczalności można zrelatywizować względem zbioru ${\displaystyle A}$  (lub funkcji ${\displaystyle f}$ ) poprzez rozważanie maszyny Turinga z wyrocznią. Otrzymane w ten sposób funkcje nazywa się A-obliczalnymi (odpowiednio f-obliczalnymi).

Badania nad rozszerzeniami klasycznej obliczalności obejmują m.in. hiperobliczalność oraz uogólnione teorie rekurencji.

• Teoria obliczalności