Funkcja obliczalna

Funkcja obliczalna – 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 są analogiczne do intuicyjnego pojęcia algorytmu. Tego pojęcia używa się do omawiania obliczalności bez odniesienia do określonego modelu, takiego jak maszyna Turinga, lub maszyna von Neumanna. Definicja funkcji obliczalnej musi jednak mieć odniesienie do określonego modelu obliczalności.

Z początku matematycy używali nieformalnego terminu „funkcji efektywnych”, jednak po wprowadzeniu precyzyjnej definicji funkcji obliczalnych, zaczęto utożsamiać funkcje efektywne z obliczalnymi. W szczególności dla niektórych funkcji efektywnych można wykazać, że każdy algorytm je obliczający będzie niewydajny (będzie potrzebował czasu rosnącego wykładniczo, w zależności od długości wprowadzonych do niego danych). Teoria obliczalności i teoria złożoności zajmują się zagadnieniami obliczalności oraz złożoności obliczeń funkcji obliczalnych.

Zgodnie z hipotezą Churcha-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, hipoteza ta oznacza, że każda funkcja dająca się wyrazić przez algorytm jest obliczalna.

Aksjomaty Bluma mogą być użyte do zdefiniowania abstrakcyjnej teorii złożoności obliczeniowej na zbiorze funkcji obliczalnych. W teorii złożoności obliczeniowej, problem określenia złożoności funkcji obliczalnej jest znany jako zagadnienie funkcji.

Definicja

Istnieje wiele równoważnych sposobów określenia klasy funkcji obliczalnych. Dla potrzeb tego artykułu przyjmiemy, że funkcje obliczalne zostały określone jako skończone funkcje częściowe na liczbach naturalnych, które dają się obliczyć za pomocą maszyny Turinga. Istnieje wiele równoznacznych modeli obliczalności, określających tę samą kategorię funkcji obliczalnych, takich jak:

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

oraz inne.

Każda obliczalna funkcja $f$ posiada skończoną liczbę argumentów będących liczbami naturalnymi. Ponieważ funkcje te są cząstkowe, mogą one być nieokreślone dla dowolnie wybranych argumentów. Jeśli funkcja obliczalna jest określona, to jej wynikiem jest pojedyncza liczba naturalna. Takie funkcje nazywa się również funkcjami częściowo rekurencyjnymi. W teorii obliczalności jako dziedzinę funkcji przyjmuje się zbiór wszystkich wprowadzeń, dla których dana funkcja jest określona.

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

Zapis $f(x_{1},\dots ,x_{k})\downarrow$ oznacza, że częściowa funkcja $f$ jest określona na argumentach $x_{1},\dots ,x_{k},$ a zapis $f(x_{1},\dots ,x_{k})\downarrow =y$ oznacza, że $f$ jest określona dla argumentów $x_{1},\dots ,x_{k}$ i jej wartością jest $y.$

Cechy funkcji obliczalnych

Główną cechą funkcji obliczalnej jest istnienie skończonej procedury (algorytmu) określającej sposób obliczenia danej funkcji. Różne modele obliczalności dają różne interpretacje tego, czym jest taka procedura i jak jej użyć. Interpretacje te mają jednak wiele cech wspólnych. Dane modele określają równoznaczne klasy funkcji obliczalnych, gdyż każdy z tych modeli jest w stanie odczytywać i wykonywać procedury określone przez różne modele (podobnie kompilator potrafi wczytać instrukcje dla jednego języka oprogramowania i wygenerować polecenia w innym języku).

Enderton [1977] podaje następujące cechy procedury wyliczającej funkcję obliczalną. Podobne charakterystyki zostały podane przez Turinga [1936], Rogersa [1967] i innych:

• „Muszą istnieć precyzyjne polecenia (w szczególności program), skończone w długości dla danej procedury”.

Każda funkcja obliczalna musi posiadać program w pełni opisujący sposób, w który należy obliczać daną funkcję – możliwe jest obliczenie danej funkcji, poprzez ścisłe wykonywanie odpowiednich kroków w danym programie, bez zgadywania czy czerpania z dodatkowej wiedzy.

• „Jeśli do danej procedury wprowadzimy krotkę $\mathbf {x}$ o $k$ elementach, należącą do dziedziny funkcji $f,$ to po skończonej liczbie kroków procedura musi zakończyć się wynikiem $f(\mathbf {x} )$”.

Intuicyjnie procedura jest wykonywana krok po kroku, stosując określone reguły opisujące każdy krok obliczeniowy. Tylko skończona ilość kroków może zostać wykonana, nim otrzymana zostanie wartość danej funkcji.

• „Jeśli do danej procedury wprowadzimy krotkę $\mathbf {x}$ o $k$ elementach, nienależącą do dziedziny funkcji $f,$ to procedura może nigdy się nie zatrzymać. Może się też zatrzymać w pewnym miejscu, nie zwracając jednak wartości funkcji $f$ dla $\mathbf {x}$”.

Jeśli otrzymamy jakąś wartość dla $f(\mathbf {x} ),$ to musi być wartość poprawna danej funkcji. Nie wymaga się od wykonującego daną procedurę, aby rozróżniał wartości wyników poprawne od niepoprawnych, albowiem wymaga się, żeby każda zwrócona wartość wynikowa była poprawna.

Enderton podaje kilka uściśleń, których wymagają procedury umożliwiające obliczenie wartości funkcji obliczalnych:

• Nie ma ograniczenia liczby argumentów. Nie zakłada się na przykład, że liczba argumentów jest mniejsza niż liczba atomów w Ziemi.
• Wymaga się, aby procedura zatrzymała się po skończonej liczbie kroków, jeśli wynik ma zostać zwrócony. Liczba tych kroków może być jednak zupełnie dowolna. Nie zakłada się żadnych ograniczeń w czasie.
• Pomimo iż procedura może potrzebować jedynie skończonej ilości pamięci podczas pomyślnego obliczania wyniku, nie ma żadnego ograniczenia do co użytego miejsca. Zakłada się, że zawsze można dodać dowolną ilość dodatkowej pamięci, jeśli procedura tego wymaga.

Dziedziną badań teorii złożoności są funkcje z określonymi ograniczeniami co do czasu lub też pamięci potrzebnej do przeprowadzenia obliczeń.

Zbiory i relacje obliczalne

Podzbiór $A$ zbioru liczb naturalnych jest nazywany obliczalnym (lub też: rekurencyjnym, rozstrzygalnym), jeśli istnieje funkcja obliczalna $f,$ taka, że dla każdej liczby $n,$ $f(n)\downarrow =1,$ gdy $n$ należy do $A$ i $f(n)\downarrow =0,$ gdy $n$ nie jest elementem zbioru $A.$

Podzbiór $A$ zbioru liczb naturalnych jest nazywany obliczalnie przeliczalnym (lub też: rekurencyjnie przeliczalnym, semi-rozstrzygalnym), jeśli istnieje obliczalna funkcja $f,$ taka, że dla każdej liczby $n,$ $f(n)$ jest określone wtedy i tylko wtedy, gdy $n$ jest elementem danego zbioru. Tak więc zbiór jest obliczalny przeliczalnie wtedy i tylko wtedy, gdy jest dziedziną pewnej funkcji obliczalnej.

Każda relacja skończona określona dla liczb naturalnych może zostać utożsamiona z odpowiednim zbiorem skończonych ciągów liczb naturalnych, zatem analogicznie można zdefiniować pojęcia relacji obliczalnych i relacji obliczalnych przeliczalnie.

Języki formalne

W informatycznej teorii obliczalności powszechnie rozważa się języki formalne. Alfabetem jest dowolny zbiór. Słowem nad danym alfabetem nazywa się skończony ciąg znaków danego alfabetu, w którym ten sam znak może występować wielokrotnie. Przykładowo ciągi binarne są słowami nad alfabetem $\{0,1\}.$ Językiem jest podzbiór zbioru wszystkich słów nad określonym alfabetem. Przykładem jest zestaw wszystkich wyrażeń zawierających dokładnie trzy jedynki nad alfabetem binarnym.

Kluczową cechą języka formalnego jest stopień trudności wymagany, aby rozstrzygnąć, czy dane słowo przynależy do danego języka. Należy stworzyć pewien system kodowania, aby umożliwić funkcji obliczalnej przyjęcie na wejście dowolnego słowa w danym języku (zwykle jest to pewien algorytm). Język nazywa się obliczalnym (lub też: rekurencyjnym, rozstrzygalnym), jeśli istnieje funkcja obliczalna $f,$ taka, że dla każdego słowa $w$ w danym alfabecie $f(w)\downarrow =1,$ gdy dane słowo jest słowem języka oraz $f(w)\downarrow =0,$ gdy słowo nie jest słowem danego języka. Tak więc język jest obliczalny wtedy i tylko wtedy, gdy istnieje algorytm pozwalający ustalić, czy dowolne słowo należy do danego języka.

Język jest obliczalny przeliczalnie (lub też: rekurencyjnie przeliczalny, semi-rozstrzygalny), jeśli istnieje funkcja obliczalna $f,$ taka, że $f(w)$ jest określona wtedy i tylko wtedy, gdy słowo $w$ należy do danego języka. Określenie przeliczalny ma tę samą etymologię, co w przypadku obliczalnych przeliczalnie zbiorów liczb naturalnych.

Przykłady

Następujące funkcje są obliczalne:

• Każda funkcja o skończonej dziedzinie, a w szczególności każdy ciąg liczb naturalnych
• Każda funkcja stała $f\colon \mathbb {N} ^{k}\to \mathbb {N} ,f(n_{1},\dots n_{k}):=n$
• Dodawanie $f\colon \mathbb {N} ^{2}\to \mathbb {N} ,f(n_{1},n_{2}):=n_{1}+n_{2}$
• Funkcja podająca czynniki pierwsze danej liczby
• Największy wspólny dzielnik dwóch liczb jest funkcją obliczalną
• Tożsamość Bézouta, liniowe równanie diofantyczne

Jeśli $f$ i $g$ są obliczalne, to również: $f+g,$ $fg,$ $f\circ g$ (zakładając, że f jest funkcją jednoargumentową), $\max(f,g),$ $\min(f,g),$ $\operatorname {argmin} \{y\leqslant f(x)\}$ oraz wiele innych kombinacji.

Poniższe przykłady są funkcjami obliczalnymi, dla których jednak nieznany jest algorytm ich obliczania:

• Funkcja $f,$ taka, że $f(n)=1,$ gdy istnieje ciąg $n$ następujących piątek w rozwinięciu dziesiętnym $\pi$ i $f(n)=0,$ w przeciwnym przypadku jest obliczalna. (Dana funkcja $f$ jest albo stałą funkcją 1, która jest obliczalna, albo istnieje takie $k$ że $f(n)=1$ dla $n<k$ i $f(n)=0$ dla $n\geqslant k.$ Wiemy, że każda taka funkcja $f$ musi być obliczalna – nie wiadomo jednak czy istnieją dowolnie długie ciągi następujących po sobie piątek w rozwinięciu dziesiętnym π, tak więc nie wiemy, które z tych dwóch przekształceń definicji funkcji $f$ jest poprawne, a jeżeli drugie byłoby poprawne, to ile wynosiłoby $k.$)

• Każdy skończony ciąg nieobliczalnych liczb naturalnych (takich, że Funkcja pracowitego bobra $\Sigma$) jest obliczalny. W szczególności dla każdej liczby naturalnej $n$ istnieje algorytm obliczający skończony ciąg $\Sigma (0),\Sigma (1),\Sigma (2),\dots ,\Sigma (n)$ – w przeciwieństwie do tego, że nie ma algorytmu obliczającego pełny ciąg $\Sigma ,$ tzn. $\Sigma (n)$ dla każdego $n.$ Tak więc „Drukuj 0, 1, 4, 6, 13” jest trywialnym algorytmem obliczającym $\Sigma (0),\Sigma (1),\Sigma (2),\Sigma (3),\Sigma (4).$ Podobnie istnieje taki trywialny algorytm dla każdego danego $n,$ obliczający (nawet jeśli nigdy nie będzie on nikomu znany lub przez kogokolwiek odkryty) $\Sigma (0),\Sigma (1),\Sigma (2),\dots ,\Sigma (n).$

Hipoteza Churcha-Turinga

Teza Churcha głosi, że każda funkcja obliczalna poprzez procedurę posiadającą trzy własności wymienione powyżej jest funkcją obliczalną. Ponieważ te trzy właściwości nie zostały podane w sposób formalnie ścisły, twierdzenia tego nie można udowodnić. Następujące obserwacje przyjmuje się jako przesłanki prawdziwości tejże tezy:

• Jest znanych wiele równoważnych modeli obliczalności i wszystkie one zawierają równoznaczne definicje obliczalności funkcji (lub słabsze wersje w niektórych przypadkach).
• Nie podano jak dotąd żadnego ściślejszego modelu obliczalności, który zostałby ogólnie uznany za wykonalnie obliczalny.

Hipoteza Churcha-Turinga bywa czasem używana w dowodach do uzasadnienia obliczalności określonej funkcji poprzez podanie opisu procedury służącej do jej obliczenia. Jest to dopuszczalne, albowiem panuje przekonanie, iż każdy tego rodzaju opis można by uściślić poprzez mozolne podanie pełnego formalnego zapisu tego rodzaju procedury w pewnym z modeli obliczalności.

Funkcje nieobliczalne i zagadnienia nierozwiązywalne

Ponieważ każda funkcja obliczalna posiada skończoną procedurę opisującą jak ją obliczyć, istnieje przeliczalnie wiele funkcji obliczalnych.

Niech więc $\Sigma$ oznacza skończony zbiór symboli, np. niech $\Sigma =\{0,1\}.$ Następnie niech $\Sigma ^{*}$ będzie zbiorem wszystkich ciągów skończonych składających się ze znaków z $\Sigma$ wraz z pustym ciągiem.

Tak więc $\Sigma ^{*}$ jest zbiorem skończonym i w naszym przykładzie mamy $\emptyset \in \Sigma ^{*},0\in \Sigma ^{*},1\in \Sigma ^{*},00\in \Sigma ^{*}\ldots$

Każdy skończony podzbiór $S\subset \Sigma ^{*}$ jest przeliczalny, gdyż elementy $S$ można uporządkować według ich długości, ustanawiając bijekcję ze zbiorem liczb naturalnych.

Zbiór wszystkich programów dla danego komputera jest podzbiorem zbioru $\Sigma ^{*}.$ Tak więc zbiór wszystkich programów dla danego komputera jest przeliczalny, a co za tym idzie – zbiór wszystkich funkcji obliczalnych jest przeliczalny.

Liczby rzeczywiste są nieprzeliczalne. Patrz: liczby obliczalne.

Zbiór funkcji skończonych na liczbach naturalnych jest nieprzeliczalny, tak więc ich większość jest nieobliczalna. Funkcja pracowitego bobra jest przykładem takiej funkcji.

Podobnie większość podzbiorów zbioru liczb naturalnych jest nieobliczalna. Problem stopu był pierwszym skonstruowanym zbiorem tego rodzaju. Problem rozstrzygalności, sformułowany przez Dawida Hilberta, stawia pytanie, czy istnieje efektywna procedura do określenia, które wyrażenia matematyczne (zakodowane jako liczby naturalne) są prawdziwe. Turing i Church niezależnie wykazali w roku 1930, że ten zbiór liczb naturalnych jest nieobliczalny. Zgodnie z tezą Churcha-Turinga, nie istnieje efektywna procedura (z algorytmem) będąca w stanie wykonać tego rodzaju obliczenie.

Rozszerzenia obliczalności

Pojęcie obliczalności funkcji może zostać zrelatywizowane do dowolnego zbioru liczb naturalnych $A$ lub równoważnie do dowolnej funkcji $f,$ odwzorowującej liczby naturalne na liczby naturalne, przy użyciu maszyny Turinga (lub dowolnego innego modelu obliczalności) rozszerzonej o wyrocznię dla $A$ lub $f.$ Tego rodzaju funkcje nazywa się A-obliczalnymi lub odpowiednio f-obliczalnymi.

Pomimo iż teza Churcha-Turinga postuluje, że wszystkie funkcje obliczalne zawierają wszystkie funkcje posiadające algorytm, można rozważać również szersze klasy funkcji, pomijając postulat istnienia algorytmu. Dziedziną badań hiperobliczalności są metody i procedury mogące rozwiązać zagadnienia nierozstrzygalne algorytmicznie. Teoria hiperarytmetyki bada różnego rodzaju rozszerzenia zwykłej obliczalności. Badano również nawet jeszcze bardziej ogólne teorie rekurencji, takie jak teoria E-rekurencji, w której każdy zbiór może być argumentem funkcji E-rekurencyjnej.

Zobacz też

• teoria obliczalności